#include "gameworld.hpp"
#include "io.hpp"
#include "path.hpp"
#include <stack>


Prng::Prng(uint32_t s): seed(s) {
}


uint32_t Prng::get() {
    return seed = (1103515245u * seed + 12345u); // Linear Congruential Generator
}


uint32_t Prng::get(uint32_t min, uint32_t max) {
    assert(max > min);
    return (get() % (max-min+1)) + min;
}


void Prng::reset(uint32_t s) {
    seed = s;
}


bool Maze::choose_nb(unsigned x, unsigned y) { // can we free this neighbour up?
    if (!at(x, y).clip) return false;
    unsigned nbs = 0;
    if (x>0   && !at(x-1, y).clip) nbs++;
    if (x<w-1 && !at(x+1, y).clip) nbs++;
    if (y>0   && !at(x, y-1).clip) nbs++;
    if (y<h-1 && !at(x, y+1).clip) nbs++;
    return nbs == 1; // would not create an additional path
}


bool Maze::choose_nb(const coord_t& c, coord_t& n, Prng* rnd) { // pick an occupied neighbour to be freed
    coord_t nb[4];
    unsigned num = 0;
    if (c.x>0 && choose_nb(c.x-1, c.y)) {
        nb[num].x = c.x-1;
        nb[num++].y = c.y;
    }
    if (c.x<w-1 && choose_nb(c.x+1, c.y)) {
        nb[num].x = c.x+1;
        nb[num++].y = c.y;
    }
    if (c.y>0 && choose_nb(c.x, c.y-1)) {
        nb[num].x = c.x;
        nb[num++].y = c.y-1;
    }
    if (c.y<h-1 && choose_nb(c.x, c.y+1)) {
        nb[num].x = c.x;
        nb[num++].y = c.y+1;
    }
    if (!num) {
        return false;
    } else {
        n = nb[(num==1)? 0: rnd->get()%num];
        return true;
    }
}


Maze::Maze(unsigned x, unsigned y, unsigned ww, unsigned hh, Prng* rnd, const Layout* parent): Layout(ww, hh) {
    for (unsigned i=0; i<w*h; ++i) {
        buf[i] = tile_defaults[tile_t::TILE_ROCK];
    }
    std::stack<coord_t> bt;

    // pick start
    coord_t curr;
    curr.x = x;
    curr.y = y;
    at(curr.x, curr.y) = tile_defaults[tile_t::TILE_FLOOR]; // visited and free now
    at(curr.x, curr.y).start = true;
    bt.push(curr);
    size_t max_bt = 1; // depth measure

    // DFS
    unsigned last_x=x, last_y=y;
    coord_t next;
    while (true) {
        if (choose_nb(curr, next, rnd)) {
            at(next.x, next.y) = tile_defaults[tile_t::TILE_FLOOR];
            bt.push(next);
            if (bt.size() > max_bt) {
                max_bt = bt.size();
                last_x = next.x;
                last_y = next.y;
            }
            curr = next;
        } else if (!bt.size()) { // done
            break;
        } else { // backtrack and try again
            curr = bt.top();
            bt.pop();
        }
    }

    // set end
    assert(last_x != x || last_y != y);
    at(last_x, last_y) = tile_defaults[tile_t::TILE_DOOR];
    if (parent) {
        at(last_x, last_y).action = tile_t::TILE_ACTION_SWITCH;
        at(last_x, last_y).action_arg1 = parent->id;
    } else {
        at(last_x, last_y).action = tile_t::TILE_ACTION_FINISH;
    }

    assert(ShortestPath::is_reachable(this, last_x, last_y, x, y));
}


Sokoban::Sokoban(unsigned ww, unsigned hh, const pos_t* lvl, const Layout* parent): Layout(ww, hh) {
    for (unsigned i=0; i<w*h; ++i) {
        switch (lvl[i]) {
            case FLOOR:
                at(i) = tile_defaults[tile_t::TILE_FLOOR];
                break;
            case WALL:
                at(i) = tile_defaults[tile_t::TILE_ROCK];
                break;
            case PLAYER:
                at(i) = tile_defaults[tile_t::TILE_DOOR];
                at(i).start = true;
                at(i).action = tile_t::TILE_ACTION_SWITCH;
                at(i).action_arg1 = parent->id;
                break;
            case GOAL:
                at(i) = tile_defaults[tile_t::TILE_GOAL];
                at(i).action = tile_t::TILE_ACTION_GOAL;
                break;
            case GOALBOX:
                below(i) = tile_defaults[tile_t::TILE_GOAL];
                below(i).action = tile_t::TILE_ACTION_GOAL;
                // no break
            case BOX:
                at(i) = tile_defaults[tile_t::TILE_BOX];
                at(i).movable = true;
                break;
        }
    }
}


Sokoban* Sokoban::getInst(Prng* rnd, const Layout* parent) {
    char* buf;
    size_t len;
    if (!file_read_at(FILE_PREFIX "/sokoban", rnd->get(), buf, len)) {
        return NULL; // our generator should depend on the implementation only, not on external input - we thus do not retry with another level
    }

    pos_t* lvl = (pos_t*)calloc(len, sizeof(pos_t));
    pos_t* p = lvl;

    unsigned goals=0, boxes=0, players=0;
    const char* c = buf;
    unsigned x=0, max_x=0, max_y=0;
    while (len--) {
        x++;
        switch (*(c++)) {
            case '#':
                *(p++) = WALL;
                break;
            case '@':
                *(p++) = PLAYER;
                players++;
                break;
            case '.':
                *(p++) = GOAL;
                goals++;
                break;
            case '*':
                *(p++) = GOALBOX;
                goals++;
                boxes++;
                break;
            case '$':
                *(p++) = BOX;
                boxes++;
                break;
            case ' ':
            case '-':
            case '_':
                *(p++) = FLOOR;
                break;
            case '\n':
                if (max_x && x-1 != max_x) {
                    LOG("inconsistent level width: %u/%u", x, max_x);
                    free(buf);
                    free(lvl);
                    return NULL;
                }
                max_x = x-1;
                x = 0;
                max_y++;
                break;
            case '+': // player on goal: if start is on a goal we cannot leave it anymore when done
                // fall thru
            default:
                LOG("unknown/unsupported level char '%c'", *(c-1));
                free(buf);
                free(lvl);
                return NULL;
        }
    }
    free(buf);

    if (!max_x || !max_y || players != 1 || goals > boxes) {
        LOG("invalid level dimensions or obviously impossible to solve");
        free(lvl);
        return NULL;
    }

    Sokoban* rv = new Sokoban(max_x, max_y, lvl, parent);
    free(lvl);
    return rv;
}


bool Sokoban::is_done() const {
    for (unsigned i=0; i<w*h; ++i) { // TODO: track this somehow?
        if (at(i).action == tile_t::TILE_ACTION_GOAL) return false;
    }
    return true;
}


unsigned GameWorld::choose_nb(const coord_t& curr, coord_t& next) {
    coord_t nb[4];
    unsigned num = 0;
    if (curr.x>0   && !at(curr.x-1, curr.y).clip && !at(curr.x-1, curr.y).action && !at(curr.x-1, curr.y).start) {
        nb[num].x = curr.x-1;
        nb[num++].y = curr.y;
    }
    if (curr.x<w-1 && !at(curr.x+1, curr.y).clip && !at(curr.x+1, curr.y).action && !at(curr.x+1, curr.y).start) {
        nb[num].x = curr.x+1;
        nb[num++].y = curr.y;
    }
    if (curr.y>0   && !at(curr.x, curr.y-1).clip && !at(curr.x, curr.y-1).action && !at(curr.x, curr.y-1).start) {
        nb[num].x = curr.x;
        nb[num++].y = curr.y-1;
    }
    if (curr.y<h-1 && !at(curr.x, curr.y+1).clip && !at(curr.x, curr.y+1).action && !at(curr.x, curr.y+1).start) {
        nb[num].x = curr.x;
        nb[num++].y = curr.y+1;
    }
    if (num > 0) {
        next = nb[rnd.get()%num];
    }
    return num;
}


void GameWorld::grow(const tile_t& tile, unsigned tilenum, unsigned max_nb) {
    assert(tile.clip && !tile.action && !tile.start);
    assert(tilenum > 0);

    // choose start
    coord_t curr;
    do {
        curr.x = rnd.get() % w;
        curr.y = rnd.get() % h;
    } while (at(curr.x, curr.y).clip || at(curr.x, curr.y).action || at(curr.x, curr.y).start);
    at(curr.x, curr.y) = tile;
    tilenum--;
    std::vector<coord_t> vec;
    vec.push_back(curr);

    // now grow from this point on
    while (tilenum && vec.size()) {
        std::vector<coord_t>::iterator it = vec.begin() + (rnd.get() % vec.size());
        curr = *it;
        coord_t next;
        unsigned free_nbs = choose_nb(curr, next);
        if (free_nbs == 0) {
            vec.erase(it);
            continue;
        } else if (free_nbs <= MAX(1, max_nb)) {
            vec.erase(it);
        }

        at(next.x, next.y) = tile;
        tilenum--;
        vec.push_back(next);
    }
}


GameWorld::GameWorld(uint32_t ss, unsigned start_x, unsigned start_y, unsigned ww, unsigned hh, std::vector<Layout*>& worlds): Layout(ww, hh), rnd(ss) {
    std::vector<Layout*> newworlds;
    again:;
    while (!newworlds.empty()) {
        delete newworlds.back();
        newworlds.pop_back();
    }
    for (unsigned i=0; i<w*h; ++i) {
        buf[i] = tile_defaults[tile_t::TILE_FLOOR];
    }
    at(start_x, start_y).start = true; // mark as occupied

    // choose maze "rooms"
    unsigned rooms = 5;
    while (rooms--) {
        coord_t end;
        do {
            end.x = rnd.get() % w;
            end.y = rnd.get() % h;
        } while (at(end.x, end.y).clip || at(end.x, end.y).action || at(end.x, end.y).start || end.x < 10 || end.x > w-10 || end.y < 10 || end.y > h-10);

        Layout* room;
        if (rnd.get() % 2) {
            unsigned room_max_x = rnd.get(4, 6) * 2 + 1; // odd
            unsigned room_max_y = rnd.get(8, 12);
            room = (Layout*)new Maze(room_max_x/2, 0, room_max_x, room_max_y, &rnd, this);
        } else {
            room = (Layout*)Sokoban::getInst(&rnd, this) ?: (Layout*)new Maze(5/2, 0, 5, 5, &rnd, this);
        }
        newworlds.push_back(room);

        for (unsigned y=end.y; y<=end.y+2; y++) {
            for (unsigned x=end.x-2; x<=end.x+2; x++) {
                at(x, y) = tile_defaults[tile_t::TILE_ROCK];
                at(x, y).model = tile_t::TILE_MODEL_CUBE;
            }
        }
        at(end.x, end.y) = tile_defaults[tile_t::TILE_DOOR];
        at(end.x, end.y).action = tile_t::TILE_ACTION_SWITCH;
        at(end.x, end.y).action_arg1 = room->id;
        at(end.x-1, end.y-1) = tile_defaults[tile_t::TILE_GOAL];
        at(end.x-1, end.y-1).model = tile_t::TILE_MODEL_SPIKE_LOW;
        at(end.x-1, end.y-1).clip = true;
        at(end.x+1, end.y-1) = tile_defaults[tile_t::TILE_GOAL];
        at(end.x+1, end.y-1).model = tile_t::TILE_MODEL_SPIKE_LOW;
        at(end.x+1, end.y-1).clip = true;
    }


    // 5-10% water tiles
    unsigned max_tiles = 1 + ((w * h * rnd.get(5, 10)) / 100);
    unsigned tiles = max_tiles;
    while (tiles) {
        unsigned num = rnd.get(1, max_tiles/4); // 25% at max for this "lake"
        num = MIN(num, tiles);
        tiles -= num;
        grow(tile_defaults[tile_t::TILE_WATER], num, 1); // stop growing only if there is no neighbor left
    }

    // 5-10% rock tiles
    max_tiles = 1 + ((w * h * rnd.get(5, 10)) / 100);
    tiles = max_tiles;
    while (tiles) {
        unsigned num = rnd.get(1, max_tiles/10); // 10% at max
        num = MIN(num, tiles);
        tiles -= num;
        grow(tile_defaults[tile_t::TILE_ROCK], num, 3); // stop if there are 3 free nbs left
    }

    // check that every corner will be reachable.
    if (!ShortestPath::is_reachable(this, 0,     0  ,   start_x, start_y) ||
        !ShortestPath::is_reachable(this, 0,     h-1,   start_x, start_y) ||
        !ShortestPath::is_reachable(this, w-1,   0  ,   start_x, start_y) ||
        !ShortestPath::is_reachable(this, w-1,   h-1,   start_x, start_y)) {
        LOG("backtracking world layout (seed %u) (corners)", ss);
        goto again;
    }

    // for doors, too
    for (unsigned y=0; y<h; ++y) {
        for (unsigned x=0; x<w; ++x) {
            if (at(x, y).tile == tile_t::TILE_DOOR) {
                if (!ShortestPath::is_reachable(this, x, y, start_x, start_y)) {
                    LOG("backtracking world layout (seed %u) (doors)", ss);
                    goto again;
                }
            }
        }
    }

    while (!newworlds.empty()) {
        worlds.push_back(newworlds.back());
        newworlds.pop_back();
    }

    find_borders();
}


void GameWorld::gen(uint32_t ss, unsigned start_x, unsigned start_y, unsigned ww, unsigned hh, std::vector<Layout*>& worlds) {
    worlds.insert(worlds.begin(), new GameWorld(ss, start_x, start_y, ww, hh, worlds));
}