1 files changed, 464 insertions, 489 deletions

@@ -8,6 +8,8 @@
 #include <fstream>
 #include <iostream>
 #include <list>
+#include <memory>
+#include <random>
 #include <set>
 #include <sstream>
 #include <tuple>
@@ -16,61 +18,13 @@
 #include <vector>
 
 #include "highscore.h"
+#include "hs_state.h"
 #include "hslist.h"
 #include "mazeoflife.h"
 #include "titlestate.h"
 #include "util.h"
 
-class GameBoard {
- public:
-  GameBoard(int level, int playerx, int playery);
-  void tick(int playerx, int playery);
-  void render(SDL_Renderer* renderer, int level) const;
-  bool isObstructed(int x, int y) const;
-  bool operator<(const GameBoard& other) const;
-
-  using coord = std::tuple<int, int>;
-
- private:
-  void initialize(int level);
-  bool solve(int playerx, int playery) const;
-  std::string dump() const;
-
-  using board_type = std::bitset<WIDTH * HEIGHT>;
-
-  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;
-};
-
-class LoadGameState : public State {
- public:
-  LoadGameState(int level);
-  State* operator()(SDL_Window* window, SDL_Renderer* renderer);
-
- private:
-  int level;
-};
-
-class PlayGameState : public State {
- public:
-  PlayGameState(int level, GameBoard* board, int playerx, int playery);
-  State* operator()(SDL_Window* window, SDL_Renderer* renderer);
-
- private:
-  bool move(int x, int y);
-  int level;
-  GameBoard* board;
-  int playerx;
-  int playery;
-};
+using board_type = std::bitset<WIDTH * HEIGHT>;
 
 void setRendererAliveColor(SDL_Renderer* renderer, int level) {
   switch ((level / 10) % 5) {
@@ -112,8 +66,8 @@ void setRendererDeadColor(SDL_Renderer* renderer, int level) {
   }
 }
 
-void GameBoard::incrementIfNeighbor(int x, int y, const board_type& temp,
-                                    int playerx, int playery, int& tick) const {
+void incrementIfNeighbor(int x, int y, const board_type& temp, int playerx,
+                         int playery, int& tick) {
   int nx = x;
   int ny = y;
 
@@ -127,545 +81,566 @@ void GameBoard::incrementIfNeighbor(int x, int y, const board_type& temp,
   }
 }
 
-State* GameState::operator()(SDL_Window* window, SDL_Renderer* renderer) {
-  return new LoadGameState(0);
-}
-
-LoadGameState::LoadGameState(int m_level) { level = m_level; }
+bool applyNeighbors(int x, int y, const board_type& temp, int playerx,
+                    int playery) {
+  int neighbors = 0;
 
-State* LoadGameState::operator()(SDL_Window* window, SDL_Renderer* renderer) {
-  char* wintitle = new char[50];
-  sprintf(wintitle, "Maze Of Life - Level %d", level);
-  SDL_SetWindowTitle(window, wintitle);
+  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);
 
-  // Randomly place the player in a corner
-  int playerx, playery;
-  switch (rand() % 4) {
-    case 0:
-      playerx = 1;
-      playery = 1;
-      break;
-    case 1:
-      playerx = 1;
-      playery = HEIGHT - 2;
-      break;
-    case 2:
-      playerx = WIDTH - 2;
-      playery = HEIGHT - 2;
-      break;
-    case 3:
-      playerx = WIDTH - 2;
-      playery = 1;
-      break;
+  if (temp[x + y * WIDTH]) {
+    return ((neighbors >= 1) && (neighbors <= 4));
+  } else {
+    return (neighbors == 3);
   }
+}
 
-  // Display the level number
-  setRendererDeadColor(renderer, level);
-  SDL_RenderClear(renderer);
-
-  TTF_Font* font = loadFont(100);
-  SDL_Color fontColor = {0, 0, 0, 0};
-  char levelnum[8];
-  sprintf(levelnum, "%d", level);
-  SDL_Surface* dispsurf = TTF_RenderText_Solid(font, levelnum, fontColor);
-  SDL_Texture* disptext = SDL_CreateTextureFromSurface(renderer, dispsurf);
-  SDL_FreeSurface(dispsurf);
-
-  SDL_Rect pos;
-  SDL_QueryTexture(disptext, NULL, NULL, &pos.w, &pos.h);
-  pos.x = 240 - (pos.w / 2);
-  pos.y = 240 - (pos.h / 2);
-
-  SDL_RenderCopy(renderer, disptext, NULL, &pos);
-  SDL_RenderPresent(renderer);
+class GameBoard {
+ public:
+  GameBoard(Game& game, int level, int playerx, int playery) {
+    for (;;) {
+      initialize(game, level);
+      updateable_.set();
+      oldx_ = playerx;
+      oldy_ = playery;
+
+      for (int i = 0; i < 50; i++) {
+        tick(playerx, playery);
+      }
 
-  // Do 50 gens of Conway
-  GameBoard* board = new GameBoard(level, playerx, playery);
+      if (solve(playerx, playery)) {
+        break;
+      } else {
+        std::cout << "Impossible board: " << playerx << "," << playery << ","
+                  << dump() << std::endl;
+      }
+    }
+  }
 
-  // Wait a bit
-  SDL_Delay(500);
+  void tick(int playerx, int playery) {
+    board_type temp{blocks_};
+    board_type tempdateable{updateable_};
+    if ((playerx != oldx_) || (playery != oldy_)) {
+      for (int dy = -1; dy <= 1; dy++) {
+        for (int dx = -1; dx <= 1; dx++) {
+          int tdx = oldx_ + dx;
+          int tdy = oldy_ + dy;
+          wrap(tdx, tdy);
+          tempdateable.set(tdx + tdy * WIDTH);
+
+          tdx = playerx + dx;
+          tdy = playery + dy;
+          wrap(tdx, tdy);
+          tempdateable.set(tdx + tdy * WIDTH);
+        }
+      }
+    }
 
-  // Start the level
-  return new PlayGameState(level, board, playerx, playery);
-}
+    oldx_ = playerx;
+    oldy_ = playery;
 
-PlayGameState::PlayGameState(int m_level, GameBoard* m_board, int m_playerx,
-                             int m_playery) {
-  level = m_level;
-  board = m_board;
-  playerx = m_playerx;
-  playery = m_playery;
-}
+    updateable_.reset();
 
-State* PlayGameState::operator()(SDL_Window* window, SDL_Renderer* renderer) {
-  SDL_Event e;
+    for (int y = 0; y < HEIGHT; y++) {
+      for (int x = 0; x < WIDTH; x++) {
+        if (((x == 15) && (y == 15)) || (!tempdateable[x + y * WIDTH])) {
+          continue;
+        }
 
-  for (;;) {
-    // Tick board
-    board->tick(playerx, playery);
+        blocks_[x + y * WIDTH] = applyNeighbors(x, y, temp, playerx, playery);
 
-    // Paint board
-    board->render(renderer, level);
+        if (temp[x + y * WIDTH] != blocks_[x + y * WIDTH]) {
+          for (int dy = -1; dy <= 1; dy++) {
+            for (int dx = -1; dx <= 1; dx++) {
+              int tdx = x + dx;
+              int tdy = y + dy;
+              wrap(tdx, tdy);
+              updateable_.set(tdx + tdy * WIDTH);
+            }
+          }
+        }
+      }
+    }
+  }
 
-    // Paint event
+  void render(SDL_Renderer* renderer, int level) const {
     SDL_Rect block;
     block.w = 16;
     block.h = 16;
-    block.x = 15 * 16;
-    block.y = 15 * 16;
-    SDL_SetRenderDrawColor(renderer, 0, 0, 255, 255);
-    SDL_RenderFillRect(renderer, &block);
-
-    // Paint player
-    block.x = playerx * 16;
-    block.y = playery * 16;
-    SDL_SetRenderDrawColor(renderer, 255, 255, 0, 255);
-    SDL_RenderFillRect(renderer, &block);
-
-    SDL_RenderPresent(renderer);
-
-    while (SDL_PollEvent(&e)) {
-      if (e.type == SDL_QUIT) {
-        return NULL;
-      } else if (e.type == SDL_KEYDOWN) {
-        switch (e.key.keysym.sym) {
-          case SDLK_LEFT:
-            if (move(playerx - 1, playery)) {
-              return new LoadGameState(level + 1);
-            } else {
-              break;
-            }
 
-          case SDLK_RIGHT:
-            if (move(playerx + 1, playery)) {
-              return new LoadGameState(level + 1);
-            } else {
-              break;
-            }
+    for (int y = 0; y < HEIGHT; y++) {
+      for (int x = 0; x < WIDTH; x++) {
+        block.x = x * 16;
+        block.y = y * 16;
 
-          case SDLK_UP:
-            if (move(playerx, playery - 1)) {
-              return new LoadGameState(level + 1);
-            } else {
-              break;
-            }
-
-          case SDLK_DOWN:
-            if (move(playerx, playery + 1)) {
-              return new LoadGameState(level + 1);
-            } else {
-              break;
-            }
-
-          case SDLK_ESCAPE:
-            SDL_SetWindowTitle(window, "");
-
-            std::ifstream exists(getDataFile());
-            if (exists) {
-              FILE* hslist = fopen(getDataFile(), "r");
-              int scores;
-              Highscore* h;
-
-              fscanf(hslist, "%d%*c", &scores);
+        if (blocks_[x + y * WIDTH]) {
+          setRendererAliveColor(renderer, level);
+        } else {
+          setRendererDeadColor(renderer, level);
+        }
 
-              if (scores < 10) {
-                fclose(hslist);
+        SDL_RenderFillRect(renderer, &block);
+      }
+    }
+  }
 
-                return new EnterHighscoreState(level);
-              } else {
-                for (int i = 0; i < scores; i++) {
-                  int namelen;
-                  char namelens[4];
-                  char* name = (char*)calloc(25, sizeof(char));
-                  int score;
+  bool isObstructed(int x, int y) const {
+    return blocks_[x + y * WIDTH] || (x == 15 && y == 15);
+  }
 
-                  fscanf(hslist, "%d", &namelen);
-                  sprintf(namelens, "%%%dc", namelen);
-                  fscanf(hslist, namelens, name);
-                  fscanf(hslist, "%d%*c", &score);
+  bool operator<(const GameBoard& other) const {
+    for (int i = WIDTH * HEIGHT - 1; i >= 0; i--) {
+      if (blocks_[i] ^ other.blocks_[i]) {
+        return other.blocks_[i];
+      }
+    }
 
-                  h = new Highscore(name, score);
-                }
+    return false;
+  }
 
-                fclose(hslist);
+  using coord = std::tuple<int, int>;
 
-                if (h->getLevel() < level) {
-                  return new EnterHighscoreState(level);
-                } else {
-                  return new DisplayAndReturnLocalHighscoreListState();
-                }
-              }
-            } else {
-              return new EnterHighscoreState(level);
+ private:
+  void initialize(Game& game, int level) {
+    for (int y = 0; y < HEIGHT; y++) {
+      for (int x = 0; x < WIDTH; x++) {
+        blocks_[x + y * WIDTH] = false;
+
+        switch (level / 10 + 1) {
+          case 1:
+            if ((x > 13) && (x < 17) && (y > 13) && (y < 17)) {
+              blocks_[x + y * WIDTH] =
+                  std::bernoulli_distribution(0.5)(game.rng);
             }
+            break;
+          case 2:
+          case 3:
+            if ((x > 12) && (x < 18) && (y > 12) && (y < 18)) {
+              blocks_[x + y * WIDTH] =
+                  std::bernoulli_distribution(0.5)(game.rng);
+            }
+            break;
+          case 4:
+          case 5:
+            if ((x > 11) && (x < 19) && (y > 11) && (y < 19)) {
+              blocks_[x + y * WIDTH] =
+                  std::bernoulli_distribution(0.5)(game.rng);
+            }
+            break;
+          default:
+            blocks_[x + y * WIDTH] = std::bernoulli_distribution(0.5)(game.rng);
         }
       }
     }
 
-    SDL_Delay(5);
+    blocks_[15 + 15 * WIDTH] = false;
   }
-}
 
-bool PlayGameState::move(int x, int y) {
-  wrap(x, y);
+  bool solve(int playerx, int playery) const {
+    std::deque<std::tuple<GameBoard, coord, int>> search;
+    std::unordered_map<board_type, board_type> done;
 
-  // Are we at the event?
-  if ((x == 15) && (y == 15)) {
-    return true;
-  }
+    // 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;
 
-  // Can we even go there?
-  if (!board->isObstructed(x, y)) {
-    playerx = x;
-    playery = y;
-  }
-
-  return false;
-}
+      std::unordered_set<board_type> pastStates;
+      pastStates.insert(original.blocks_);
 
-GameBoard::GameBoard(int level, int playerx, int playery) {
-  for (;;) {
-    initialize(level);
-    updateable.set();
-    oldx = playerx;
-    oldy = playery;
+      while (original.updateable_.any()) {
+        original.tick(playerx, playery);
 
-    for (int i = 0; i < 50; i++) {
-      tick(playerx, playery);
-    }
-
-    if (solve(playerx, playery)) {
-      break;
-    } else {
-      std::cout << "Impossible board: " << playerx << "," << playery << ","
-                << dump() << std::endl;
-    }
-  }
-}
+        if (pastStates.count(original.blocks_)) {
+          break;
+        }
 
-void GameBoard::tick(int playerx, int playery) {
-  board_type temp{blocks};
-  board_type tempdateable{updateable};
-  if ((playerx != oldx) || (playery != oldy)) {
-    for (int dy = -1; dy <= 1; dy++) {
-      for (int dx = -1; dx <= 1; dx++) {
-        int tdx = oldx + dx;
-        int tdy = oldy + dy;
-        wrap(tdx, tdy);
-        tempdateable.set(tdx + tdy * WIDTH);
-
-        tdx = playerx + dx;
-        tdy = playery + dy;
-        wrap(tdx, tdy);
-        tempdateable.set(tdx + tdy * WIDTH);
+        pastStates.insert(original.blocks_);
       }
+
+      search.emplace_front(std::move(original), coord{playerx, playery}, 0);
     }
-  }
 
-  oldx = playerx;
-  oldy = playery;
+    // Use breadth first search to find a solution.
+    bool exists = false;
+    while (!search.empty()) {
+      auto cur = std::move(search.front());
+      search.pop_front();
 
-  updateable.reset();
+      GameBoard& cbr = std::get<0>(cur);
+      coord& cpl = std::get<1>(cur);
+      int cns = std::get<2>(cur);
 
-  for (int y = 0; y < HEIGHT; y++) {
-    for (int x = 0; x < WIDTH; x++) {
-      if (((x == 15) && (y == 15)) || (!tempdateable[x + y * WIDTH])) {
+      // If it has been over 100 generations, give up.
+      if (cns > 100) {
         continue;
       }
 
-      blocks[x + y * WIDTH] = applyNeighbors(x, y, temp, playerx, playery);
+      int cplx = std::get<0>(cpl);
+      int cply = std::get<1>(cpl);
 
-      if (temp[x + y * WIDTH] != blocks[x + y * WIDTH]) {
-        for (int dy = -1; dy <= 1; dy++) {
-          for (int dx = -1; dx <= 1; dx++) {
-            int tdx = x + dx;
-            int tdy = y + dy;
-            wrap(tdx, tdy);
-            updateable.set(tdx + tdy * WIDTH);
-          }
-        }
+      // 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;
       }
-    }
-  }
-}
-
-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);
+      // 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<coord> front;
+      front.push_front(cpl);
+      flood[cplx + cply * WIDTH] = true;
+
+      std::set<coord> edges;
+
+      while (!front.empty()) {
+        coord frontLoc = std::move(front.front());
+        front.pop_front();
+
+        // Iterate over the positions 4-adjacent to the current one.
+        for (coord& fc : std::list<coord>{
+                 {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},
+             }) {
+          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;
+          }
 
-  if (temp[x + y * WIDTH]) {
-    return ((neighbors >= 1) && (neighbors <= 4));
-  } else {
-    return (neighbors == 3);
-  }
-}
+          // If the player could not move into this position, skip it.
+          if (cbr.isObstructed(fcx, fcy)) {
+            continue;
+          }
 
-void GameBoard::render(SDL_Renderer* renderer, int level) const {
-  SDL_Rect block;
-  block.w = 16;
-  block.h = 16;
+          // 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;
+          }
 
-  for (int y = 0; y < HEIGHT; y++) {
-    for (int x = 0; x < WIDTH; x++) {
-      block.x = x * 16;
-      block.y = y * 16;
+          // 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;
+              }
 
-      if (blocks[x + y * WIDTH]) {
-        setRendererAliveColor(renderer, level);
-      } else {
-        setRendererDeadColor(renderer, level);
-      }
+              int cpldx = cplx + dx;
+              int cpldy = cply + dy;
+              wrap(cpldx, cpldy);
 
-      SDL_RenderFillRect(renderer, &block);
-    }
-  }
-}
+              if (cbr.isObstructed(cpldx, cpldy) !=
+                  applyNeighbors(cpldx, cpldy, cbr.blocks_, fcx, fcy)) {
+                changed = true;
+                break;
+              }
 
-bool GameBoard::isObstructed(int x, int y) const {
-  return blocks[x + y * WIDTH] || (x == 15 && y == 15);
-}
+              int fcxdx = fcx + dx;
+              int fcydy = fcy + dy;
+              wrap(fcxdx, fcydy);
 
-void GameBoard::initialize(int level) {
-  for (int y = 0; y < HEIGHT; y++) {
-    for (int x = 0; x < WIDTH; x++) {
-      blocks[x + y * WIDTH] = false;
+              if (cbr.isObstructed(fcxdx, fcydy) !=
+                  applyNeighbors(fcxdx, fcydy, cbr.blocks_, fcx, fcy)) {
+                changed = true;
+                break;
+              }
+            }
 
-      switch (level / 10 + 1) {
-        case 1:
-          if ((x > 13) && (x < 17) && (y > 13) && (y < 17)) {
-            blocks[x + y * WIDTH] = rand() % 2;
-          }
-          break;
-        case 2:
-        case 3:
-          if ((x > 12) && (x < 18) && (y > 12) && (y < 18)) {
-            blocks[x + y * WIDTH] = rand() % 2;
+            if (changed) {
+              break;
+            }
           }
-          break;
-        case 4:
-        case 5:
-          if ((x > 11) && (x < 19) && (y > 11) && (y < 19)) {
-            blocks[x + y * WIDTH] = rand() % 2;
+
+          // 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;
-        default:
-          blocks[x + y * WIDTH] = rand() % 2;
+        }
       }
-    }
-  }
 
-  blocks[15 + 15 * WIDTH] = false;
-}
+      if (exists) {
+        break;
+      }
 
-bool GameBoard::operator<(const GameBoard& other) const {
-  for (int i = WIDTH * HEIGHT - 1; i >= 0; i--) {
-    if (blocks[i] ^ other.blocks[i]) {
-      return other.blocks[i];
-    }
-  }
+      // Add the flood to the set of checked positions for this board state.
+      done[cbr.blocks_] |= flood;
 
-  return false;
-}
+      // Add the edges to the search queue.
+      for (const coord& newLoc : edges) {
+        GameBoard nextState1 = cbr;
+        nextState1.tick(std::get<0>(newLoc), std::get<1>(newLoc));
 
-bool GameBoard::solve(int playerx, int playery) const {
-  std::deque<std::tuple<GameBoard, coord, int>> search;
-  std::unordered_map<board_type, board_type> 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).
+        std::unordered_set<board_type> pastStates;
+        pastStates.insert(nextState1.blocks_);
 
-  // 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;
+        while (nextState1.updateable_.any()) {
+          nextState1.tick(std::get<0>(newLoc), std::get<1>(newLoc));
 
-    std::unordered_set<board_type> pastStates;
-    pastStates.insert(original.blocks);
+          if (pastStates.count(nextState1.blocks_)) {
+            break;
+          }
 
-    while (original.updateable.any()) {
-      original.tick(playerx, playery);
+          pastStates.insert(nextState1.blocks_);
+        }
 
-      if (pastStates.count(original.blocks)) {
-        break;
+        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);
+        }
       }
+    }
 
-      pastStates.insert(original.blocks);
+    return exists;
+  }
+
+  std::string dump() const {
+    std::stringstream output;
+    output << std::hex;
+    for (int i = 0; i < WIDTH * HEIGHT / 4; i++) {
+      int chunk = (8 * blocks_[i * 4]) + (4 * blocks_[i * 4 + 1]) +
+                  (2 * blocks_[i * 4 + 2]) + blocks_[i * 4 + 3];
+      output << chunk;
     }
 
-    search.emplace_front(std::move(original), coord{playerx, playery}, 0);
+    return output.str();
   }
 
-  // Use breadth first search to find a solution.
-  bool exists = false;
-  while (!search.empty()) {
-    auto cur = std::move(search.front());
-    search.pop_front();
+  board_type blocks_;
+  board_type updateable_;
+  int oldx_;
+  int oldy_;
+};
 
-    GameBoard& cbr = std::get<0>(cur);
-    coord& cpl = std::get<1>(cur);
-    int cns = std::get<2>(cur);
+std::unique_ptr<State> startNewLevel(int level,
+                                     std::unique_ptr<GameBoard> board,
+                                     int playerx, int playery);
 
-    // If it has been over 100 generations, give up.
-    if (cns > 100) {
-      continue;
+class LoadGameState : public State {
+ public:
+  LoadGameState(int level) : level_(level) {}
+
+  std::unique_ptr<State> operator()(Game& game) {
+    std::ostringstream wintitle;
+    wintitle << "Maze Of Life - Level " << level_;
+    SDL_SetWindowTitle(game.window.get(), wintitle.str().c_str());
+
+    // Randomly place the player in a corner
+    int playerx, playery;
+    switch (std::uniform_int_distribution(0, 3)(game.rng)) {
+      case 0: {
+        playerx = 1;
+        playery = 1;
+        break;
+      }
+      case 1: {
+        playerx = 1;
+        playery = HEIGHT - 2;
+        break;
+      }
+      case 2: {
+        playerx = WIDTH - 2;
+        playery = HEIGHT - 2;
+        break;
+      }
+      case 3: {
+        playerx = WIDTH - 2;
+        playery = 1;
+        break;
+      }
     }
 
-    int cplx = std::get<0>(cpl);
-    int cply = std::get<1>(cpl);
+    // Display the level number
+    setRendererDeadColor(game.renderer.get(), level_);
+    SDL_RenderClear(game.renderer.get());
 
-    // 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;
-    }
+    font_ptr font = loadFont(100);
+    SDL_Color fontColor = {0, 0, 0, 0};
+    std::string levelnum = std::to_string(level_);
+    surface_ptr dispsurf = surface_ptr(
+        TTF_RenderText_Solid(font.get(), levelnum.c_str(), fontColor));
+    texture_ptr disptext = texture_ptr(
+        SDL_CreateTextureFromSurface(game.renderer.get(), dispsurf.get()));
 
-    // 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<coord> front;
-    front.push_front(cpl);
-    flood[cplx + cply * WIDTH] = true;
-
-    std::set<coord> edges;
-
-    while (!front.empty()) {
-      coord frontLoc = std::move(front.front());
-      front.pop_front();
-
-      // Iterate over the positions 4-adjacent to the current one.
-      for (coord& fc : std::list<coord>{
-               {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},
-           }) {
-        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;
-        }
+    SDL_Rect pos;
+    SDL_QueryTexture(disptext.get(), NULL, NULL, &pos.w, &pos.h);
+    pos.x = 240 - (pos.w / 2);
+    pos.y = 240 - (pos.h / 2);
 
-        // If the player could not move into this position, skip it.
-        if (cbr.isObstructed(fcx, fcy)) {
-          continue;
-        }
+    SDL_RenderCopy(game.renderer.get(), disptext.get(), NULL, &pos);
+    SDL_RenderPresent(game.renderer.get());
 
-        // 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;
-        }
+    // Do 50 gens of Conway
+    std::unique_ptr<GameBoard> board =
+        std::make_unique<GameBoard>(game, level_, playerx, playery);
 
-        // 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;
-            }
+    // Wait a bit
+    SDL_Delay(500);
 
-            int cpldx = cplx + dx;
-            int cpldy = cply + dy;
-            wrap(cpldx, cpldy);
+    // Start the level
+    return startNewLevel(level_, std::move(board), playerx, playery);
+  }
 
-            if (cbr.isObstructed(cpldx, cpldy) !=
-                applyNeighbors(cpldx, cpldy, cbr.blocks, fcx, fcy)) {
-              changed = true;
-              break;
-            }
+ private:
+  int level_;
+};
 
-            int fcxdx = fcx + dx;
-            int fcydy = fcy + dy;
-            wrap(fcxdx, fcydy);
+class PlayGameState : public State {
+ public:
+  PlayGameState(int level, std::unique_ptr<GameBoard> board, int playerx,
+                int playery)
+      : level_(level),
+        board_(std::move(board)),
+        playerx_(playerx),
+        playery_(playery) {}
 
-            if (cbr.isObstructed(fcxdx, fcydy) !=
-                applyNeighbors(fcxdx, fcydy, cbr.blocks, fcx, fcy)) {
-              changed = true;
-              break;
-            }
+  std::unique_ptr<State> operator()(Game& game) {
+    SDL_Event e;
+
+    // Tick board
+    board_->tick(playerx_, playery_);
+
+    // Paint board
+    board_->render(game.renderer.get(), level_);
+
+    // Paint event
+    SDL_Rect block;
+    block.w = 16;
+    block.h = 16;
+    block.x = 15 * 16;
+    block.y = 15 * 16;
+    SDL_SetRenderDrawColor(game.renderer.get(), 0, 0, 255, 255);
+    SDL_RenderFillRect(game.renderer.get(), &block);
+
+    // Paint player
+    block.x = playerx_ * 16;
+    block.y = playery_ * 16;
+    SDL_SetRenderDrawColor(game.renderer.get(), 255, 255, 0, 255);
+    SDL_RenderFillRect(game.renderer.get(), &block);
+
+    SDL_RenderPresent(game.renderer.get());
+
+    while (SDL_PollEvent(&e)) {
+      if (e.type == SDL_QUIT) {
+        game.should_quit = true;
+
+        return nullptr;
+      } else if (e.type == SDL_KEYDOWN) {
+        bool trymove = false;
+        int to_x = playerx_;
+        int to_y = playery_;
+
+        switch (e.key.keysym.sym) {
+          case SDLK_LEFT: {
+            trymove = true;
+            to_x--;
+            break;
           }
+          case SDLK_RIGHT: {
+            trymove = true;
+            to_x++;
+            break;
+          }
+          case SDLK_UP: {
+            trymove = true;
+            to_y--;
+            break;
+          }
+          case SDLK_DOWN: {
+            trymove = true;
+            to_y++;
+            break;
+          }
+          case SDLK_ESCAPE: {
+            SDL_SetWindowTitle(game.window.get(), "");
+
+            std::unique_ptr<HighscoreList> hslist =
+                HighscoreList::GetLocalHighscores();
+            if (hslist->addHighscore(Highscore("", level_)) <= 10) {
+              return std::make_unique<EnterHighscoreState>(game, level_);
+            } else {
+              return std::make_unique<DisplayAndReturnLocalHighscoreListState>(
+                  game);
+            }
 
-          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 (trymove && move(to_x, to_y)) {
+          return std::make_unique<LoadGameState>(level_ + 1);
         }
       }
-
-      if (exists) {
-        break;
-      }
-    }
-
-    if (exists) {
-      break;
     }
 
-    // Add the flood to the set of checked positions for this board state.
-    done[cbr.blocks] |= flood;
-
-    // Add the edges to the search queue.
-    for (const coord& newLoc : edges) {
-      GameBoard nextState1 = cbr;
-      nextState1.tick(std::get<0>(newLoc), std::get<1>(newLoc));
-
-      // 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<board_type> pastStates;
-      pastStates.insert(nextState1.blocks);
+    SDL_Delay(5);
 
-      while (nextState1.updateable.any()) {
-        nextState1.tick(std::get<0>(newLoc), std::get<1>(newLoc));
+    return nullptr;
+  }
 
-        if (pastStates.count(nextState1.blocks)) {
-          break;
-        }
+ private:
+  bool move(int x, int y) {
+    wrap(x, y);
 
-        pastStates.insert(nextState1.blocks);
-      }
+    // Are we at the event?
+    if ((x == 15) && (y == 15)) {
+      return true;
+    }
 
-      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);
-      }
+    // Can we even go there?
+    if (!board_->isObstructed(x, y)) {
+      playerx_ = x;
+      playery_ = y;
     }
+
+    return false;
   }
 
-  return exists;
-}
+  int level_;
+  std::unique_ptr<GameBoard> board_;
+  int playerx_;
+  int playery_;
+};
 
-std::string GameBoard::dump() const {
-  std::stringstream output;
-  output << std::hex;
-  for (int i = 0; i < WIDTH * HEIGHT / 4; i++) {
-    int chunk = (8 * blocks[i * 4]) + (4 * blocks[i * 4 + 1]) +
-                (2 * blocks[i * 4 + 2]) + blocks[i * 4 + 3];
-    output << chunk;
-  }
+std::unique_ptr<State> startNewLevel(int level,
+                                     std::unique_ptr<GameBoard> board,
+                                     int playerx, int playery) {
+  return std::make_unique<PlayGameState>(level, std::move(board), playerx,
+                                         playery);
+}
 
-  return output.str();
+std::unique_ptr<State> GameState::operator()(Game&) {
+  return std::make_unique<LoadGameState>(0);
 }