From 4e8f554286593ec8aca6c61fa0fb9c4934bd640c Mon Sep 17 00:00:00 2001 From: Kelly Rauchenberger Date: Fri, 13 Jul 2018 17:06:48 -0400 Subject: Redesigned the solver algorithm The new solver algorithm decreases the size of the search space by combining states. A flood fill is used to find all of the positions accessible by the player without changing the board state, and that flood is considered a node in the search graph, rather than there being a node for every position on every board state. Other optimizations are implemented too, like checking for changes locally instead of using tick, and using unordered_map/unordered_set because bitsets are hashable. Also changed wrap to use references, finally. refs #1 --- gamestate.cpp | 325 ++++++++++++++++++++++++++++++++++++++++++++-------------- util.cpp | 18 ++-- util.h | 2 +- 3 files changed, 260 insertions(+), 85 deletions(-) diff --git a/gamestate.cpp b/gamestate.cpp index 18e41c2..8c2df9c 100644 --- a/gamestate.cpp +++ b/gamestate.cpp @@ -14,6 +14,9 @@ #include #include #include +#include +#include +#include class GameBoard { public: @@ -23,13 +26,32 @@ class GameBoard { bool isObstructed(int x, int y) const; bool operator<(const GameBoard& other) const; + using coord = std::tuple; + private: void initialize(int level); - int solve(int playerx, int playery) const; + bool solve(int playerx, int playery) const; std::string dump() const; - std::bitset blocks; - std::bitset updateable; + using board_type = std::bitset; + + void incrementIfNeighbor( + int x, + int y, + const board_type& temp, + int playerx, + int playery, + int& tick) const; + + bool applyNeighbors( + int x, + int y, + const board_type& temp, + int playerx, + int playery) const; + + board_type blocks; + board_type updateable; int oldx; int oldy; }; @@ -80,18 +102,24 @@ void setRendererDeadColor(SDL_Renderer* renderer, int level) } } -void incrementIfNeighbor(int x, int y, std::bitset& temp, int* tick, int playerx, int playery) +void GameBoard::incrementIfNeighbor( + int x, + int y, + const board_type& temp, + int playerx, + int playery, + int& tick) const { int nx = x; int ny = y; - wrap(&x, &y); + wrap(x, y); if (!((nx!=x)&&(ny!=y))) { if ((temp[x+y*WIDTH])||((playerx==x)&&(playery==y))||((x==15)&&(y==15))) { - ++*tick; + ++tick; } } } @@ -285,7 +313,7 @@ State* PlayGameState::operator() (SDL_Window* window, SDL_Renderer* renderer) bool PlayGameState::move(int x, int y) { - wrap(&x, &y); + wrap(x, y); // Are we at the event? if ((x==15)&&(y==15)) @@ -317,8 +345,7 @@ GameBoard::GameBoard(int level, int playerx, int playery) tick(playerx, playery); } - int states = solve(playerx, playery); - if (states != 0) + if (solve(playerx, playery)) { break; } else { @@ -329,8 +356,8 @@ GameBoard::GameBoard(int level, int playerx, int playery) void GameBoard::tick(int playerx, int playery) { - std::bitset temp {blocks}; - std::bitset tempdateable {updateable}; + board_type temp {blocks}; + board_type tempdateable {updateable}; if ((playerx != oldx) || (playery != oldy)) { for (int dy = -1; dy <= 1; dy++) @@ -339,12 +366,12 @@ void GameBoard::tick(int playerx, int playery) { int tdx = oldx+dx; int tdy = oldy+dy; - wrap(&tdx, &tdy); + wrap(tdx, tdy); tempdateable.set(tdx+tdy*WIDTH); tdx = playerx+dx; tdy = playery+dy; - wrap(&tdx, &tdy); + wrap(tdx, tdy); tempdateable.set(tdx+tdy*WIDTH); } } @@ -364,23 +391,7 @@ void GameBoard::tick(int playerx, int playery) continue; } - int neighbors = 0; - - incrementIfNeighbor(x-1, y-1, temp, &neighbors, playerx, playery); - incrementIfNeighbor(x-1, y , temp, &neighbors, playerx, playery); - incrementIfNeighbor(x-1, y+1, temp, &neighbors, playerx, playery); - incrementIfNeighbor(x , y-1, temp, &neighbors, playerx, playery); - incrementIfNeighbor(x , y+1, temp, &neighbors, playerx, playery); - incrementIfNeighbor(x+1, y-1, temp, &neighbors, playerx, playery); - incrementIfNeighbor(x+1, y , temp, &neighbors, playerx, playery); - incrementIfNeighbor(x+1, y+1, temp, &neighbors, playerx, playery); - - if (temp[x+y*WIDTH]) - { - blocks[x+y*WIDTH] = ((neighbors >= 1) && (neighbors <= 4)); - } else { - blocks[x+y*WIDTH] = (neighbors == 3); - } + blocks[x+y*WIDTH] = applyNeighbors(x, y, temp, playerx, playery); if (temp[x+y*WIDTH] != blocks[x+y*WIDTH]) { @@ -390,7 +401,7 @@ void GameBoard::tick(int playerx, int playery) { int tdx = x+dx; int tdy = y+dy; - wrap(&tdx, &tdy); + wrap(tdx, tdy); updateable.set(tdx+tdy*WIDTH); } } @@ -399,6 +410,32 @@ void GameBoard::tick(int playerx, int playery) } } +bool GameBoard::applyNeighbors( + int x, + int y, + const board_type& temp, + int playerx, + int playery) const +{ + int neighbors = 0; + + incrementIfNeighbor(x-1, y-1, temp, playerx, playery, neighbors); + incrementIfNeighbor(x-1, y , temp, playerx, playery, neighbors); + incrementIfNeighbor(x-1, y+1, temp, playerx, playery, neighbors); + incrementIfNeighbor(x , y-1, temp, playerx, playery, neighbors); + incrementIfNeighbor(x , y+1, temp, playerx, playery, neighbors); + incrementIfNeighbor(x+1, y-1, temp, playerx, playery, neighbors); + incrementIfNeighbor(x+1, y , temp, playerx, playery, neighbors); + incrementIfNeighbor(x+1, y+1, temp, playerx, playery, neighbors); + + if (temp[x+y*WIDTH]) + { + return ((neighbors >= 1) && (neighbors <= 4)); + } else { + return (neighbors == 3); + } +} + void GameBoard::render(SDL_Renderer* renderer, int level) const { SDL_Rect block; @@ -426,7 +463,7 @@ void GameBoard::render(SDL_Renderer* renderer, int level) const bool GameBoard::isObstructed(int x, int y) const { - return blocks[x+y*WIDTH]; + return blocks[x+y*WIDTH] || (x == 15 && y == 15); } void GameBoard::initialize(int level) @@ -481,82 +518,220 @@ bool GameBoard::operator<(const GameBoard& other) const return false; } -int GameBoard::solve(int playerx, int playery) const +bool GameBoard::solve(int playerx, int playery) const { - std::deque> search; - std::set> done; - search.push_front(std::make_tuple(playerx, playery, *this, 0)); + std::deque> search; + std::unordered_map done; + + // Assume that the player will not move while the board is changing, so tick + // the board until it either stops changing, or it reaches a state that it has + // already been in (in the case of alternating systems). + { + GameBoard original = *this; + + std::unordered_set pastStates; + pastStates.insert(original.blocks); + + while (original.updateable.any()) + { + original.tick(playerx, playery); + if (pastStates.count(original.blocks)) + { + break; + } + + pastStates.insert(original.blocks); + } + + search.emplace_front(std::move(original), coord{playerx, playery}, 0); + } + + // Use breadth first search to find a solution. bool exists = false; while (!search.empty()) { - auto cur = search.front(); + auto cur = std::move(search.front()); search.pop_front(); - int cpx = std::get<0>(cur); - int cpy = std::get<1>(cur); - GameBoard& cbr = std::get<2>(cur); - int cns = std::get<3>(cur); - - auto cdn = std::make_tuple(cpx, cpy, cbr); - done.insert(cdn); + GameBoard& cbr = std::get<0>(cur); + coord& cpl = std::get<1>(cur); + int cns = std::get<2>(cur); - if (((cpx == 15) && ((cpy == 14) || (cpy == 16))) || ((cpy == 15) && ((cpx == 14) || (cpx == 16)))) + // If it has been over 100 generations, give up. + if (cns > 100) { - exists = true; - break; + continue; } - if (cns >= 100) + int cplx = std::get<0>(cpl); + int cply = std::get<1>(cpl); + + // If this section of this board state has already been checked, skip it. + if (done.count(cbr.blocks) && done.at(cbr.blocks)[cplx+cply*WIDTH]) { continue; } - GameBoard immnext {cbr}; - immnext.tick(cpx, cpy); - if (immnext.blocks != cbr.blocks) + // Use a flood fill to find a set of positions accessible to the player + // without modifying the board state, as well as a set of positions adjacent + // to the flood that /will/ modify the board state. + board_type flood; + std::deque front; + front.push_front(cpl); + flood[cplx+cply*WIDTH] = true; + + std::set edges; + + while (!front.empty()) { - if (done.count(std::make_tuple(cpx, cpy, immnext)) == 0) + coord frontLoc = std::move(front.front()); + front.pop_front(); + + // Iterate over the positions 4-adjacent to the current one. + for (coord& fc : std::list{ + {std::get<0>(frontLoc) - 1, std::get<1>(frontLoc) }, + {std::get<0>(frontLoc) + 1, std::get<1>(frontLoc) }, + {std::get<0>(frontLoc) , std::get<1>(frontLoc) - 1}, + {std::get<0>(frontLoc) , std::get<1>(frontLoc) + 1}, + }) { - search.push_front(std::make_tuple(cpx, cpy, immnext, cns)); + wrap(std::get<0>(fc), std::get<1>(fc)); + int fcx = std::get<0>(fc); + int fcy = std::get<1>(fc); + + // If this position is already in the flood, skip it. + if (flood[fcx+fcy*WIDTH]) + { + continue; + } - continue; + // If the player could not move into this position, skip it. + if (cbr.isObstructed(fcx, fcy)) + { + continue; + } + + // If this position is adjacent to the event, then the board is + // solvable. + if (((fcx == 15) && ((fcy == 14) || (fcy == 16))) || + ((fcy == 15) && ((fcx == 14) || (fcx == 16)))) + { + exists = true; + break; + } + + // Check if the player moving would cause any positions 8-adjacent to + // the start or end positions to change. This is more efficient than + // copying the board state and then running tick. + bool changed = false; + for (int dy = -1; dy <= 1; dy++) + { + for (int dx = -1; dx <=1; dx++) + { + if (dx == 0 && dy == 0) + { + continue; + } + + int cpldx = cplx + dx; + int cpldy = cply + dy; + wrap(cpldx, cpldy); + + if (cbr.isObstructed(cpldx, cpldy) != + applyNeighbors( + cpldx, + cpldy, + cbr.blocks, + fcx, + fcy)) + { + changed = true; + break; + } + + int fcxdx = fcx + dx; + int fcydy = fcy + dy; + wrap(fcxdx, fcydy); + + if (cbr.isObstructed(fcxdx, fcydy) != + applyNeighbors( + fcxdx, + fcydy, + cbr.blocks, + fcx, + fcy)) + { + changed = true; + break; + } + } + + if (changed) + { + break; + } + } + + // If moving to this position would change the board state, add it to + // the set of edges; otherwise, add it to the flood and the flood front. + if (changed) + { + edges.insert(fc); + } else { + flood[fcx+fcy*WIDTH] = true; + front.push_back(fc); + } + } + + if (exists) + { + break; } } - std::vector> dirchanges {{cpx-1,cpy}, {cpx,cpy-1}, {cpx+1,cpy}, {cpx,cpy+1}}; - std::sort(std::begin(dirchanges), std::end(dirchanges), [] (const std::pair& lhs, const std::pair& rhs) { - int lhd = sqrt(pow(15 - lhs.first, 2.0) + pow(15 - lhs.second, 2.0)); - int rhd = sqrt(pow(15 - rhs.first, 2.0) + pow(15 - rhs.second, 2.0)); + if (exists) + { + break; + } - return lhd > rhd; - }); + // Add the flood to the set of checked positions for this board state. + done[cbr.blocks] |= flood; - for (auto& dirchange : dirchanges) + // Add the edges to the search queue. + for (const coord& newLoc : edges) { - GameBoard next {cbr}; - int npx = cpx + dirchange.first; - int npy = cpy + dirchange.second; - wrap(&npx, &npy); + GameBoard nextState1 = cbr; + nextState1.tick(std::get<0>(newLoc), std::get<1>(newLoc)); - if (!next.isObstructed(npx, npy)) + // Assume that the player will not move while the board is changing, so + // tick the board until it either stops changing, or it reaches a state + // that it has already been in (in the case of alternating systems). + std::unordered_set pastStates; + pastStates.insert(nextState1.blocks); + + while (nextState1.updateable.any()) { - next.tick(npx, npy); + nextState1.tick(std::get<0>(newLoc), std::get<1>(newLoc)); - if (done.count(std::make_tuple(npx, npy, next)) == 0) + if (pastStates.count(nextState1.blocks)) { - search.push_front(std::make_tuple(npx, npy, next, cns+1)); + break; } + + pastStates.insert(nextState1.blocks); + } + + if (!done.count(nextState1.blocks) || + !done.at(nextState1.blocks) + [std::get<0>(newLoc) + std::get<1>(newLoc)*WIDTH]) + { + search.emplace_back(std::move(nextState1), newLoc, cns+1); } } } - if (exists) - { - return done.size(); - } else { - return 0; - } + return exists; } std::string GameBoard::dump() const diff --git a/util.cpp b/util.cpp index 5ccfe51..9fcdbbd 100644 --- a/util.cpp +++ b/util.cpp @@ -2,22 +2,22 @@ #include "mazeoflife.h" #include -void wrap(int* x, int* y) +void wrap(int& x, int& y) { - if (*x < 0) + if (x < 0) { - *x = WIDTH-(0-*x); - } else if (*x >= WIDTH) + x = WIDTH+x; + } else if (x >= WIDTH) { - *x = *x-WIDTH; + x = x-WIDTH; } - if (*y < 0) + if (y < 0) { - *y = HEIGHT-(0-*y); - } else if (*y >= HEIGHT) + y = HEIGHT+y; + } else if (y >= HEIGHT) { - *y = *y-HEIGHT; + y = y-HEIGHT; } } diff --git a/util.h b/util.h index 365a759..0e1fa2e 100644 --- a/util.h +++ b/util.h @@ -5,7 +5,7 @@ #ifndef UTIL_H #define UTIL_H -void wrap(int* x, int* y); +void wrap(int& x, int& y); TTF_Font* loadFont(int size); const char* getDataFile(); SDL_Texture* loadImage(SDL_Renderer* renderer, std::string file); -- cgit 1.4.1