path: root/gamestate.cpp

#include "gamestate.h"

#include <SDL_ttf.h>

#include <algorithm>
#include <bitset>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <memory>
#include <random>
#include <set>
#include <sstream>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include "highscore.h"
#include "hs_state.h"
#include "hslist.h"
#include "mazeoflife.h"
#include "titlestate.h"
#include "util.h"

using board_type = std::bitset<WIDTH * HEIGHT>;

void setRendererAliveColor(SDL_Renderer* renderer, int level) {
  switch ((level / 10) % 5) {
    case 0:
      SDL_SetRenderDrawColor(renderer, 0, 0, 0, 255);
      break;  // Black
    case 1:
      SDL_SetRenderDrawColor(renderer, 255, 0, 0, 255);
      break;  // Red
    case 2:
      SDL_SetRenderDrawColor(renderer, 0, 255, 0, 255);
      break;  // Green
    case 3:
      SDL_SetRenderDrawColor(renderer, 85, 85, 85, 255);
      break;  // Dark Gray
    case 4:
      SDL_SetRenderDrawColor(renderer, 255, 0, 255, 255);
      break;  // Magenta
  }
}

void setRendererDeadColor(SDL_Renderer* renderer, int level) {
  switch ((level / 10) % 5) {
    case 0:
      SDL_SetRenderDrawColor(renderer, 255, 255, 255, 255);
      break;  // White
    case 1:
      SDL_SetRenderDrawColor(renderer, 255, 192, 203, 255);
      break;  // Pink
    case 2:
      SDL_SetRenderDrawColor(renderer, 0, 255, 255, 255);
      break;  // Cyan
    case 3:
      SDL_SetRenderDrawColor(renderer, 170, 170, 170, 255);
      break;  // Light Gray
    case 4:
      SDL_SetRenderDrawColor(renderer, 255, 128, 0, 255);
      break;  // Orange
  }
}

void incrementIfNeighbor(int x, int y, const board_type& temp, int playerx,
                         int playery, int& tick) {
  int nx = x;
  int ny = y;

  wrap(x, y);

  if (!((nx != x) && (ny != y))) {
    if ((temp[x + y * WIDTH]) || ((playerx == x) && (playery == y)) ||
        ((x == 15) && (y == 15))) {
      ++tick;
    }
  }
}

bool applyNeighbors(int x, int y, const board_type& temp, int playerx,
                    int playery) {
  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);
  }
}

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);
      }

      if (solve(playerx, playery)) {
        break;
      } else {
        std::cout << "Impossible board: " << playerx << "," << playery << ","
                  << dump() << std::endl;
      }
    }
  }

  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);
        }
      }
    }

    oldx_ = playerx;
    oldy_ = playery;

    updateable_.reset();

    for (int y = 0; y < HEIGHT; y++) {
      for (int x = 0; x < WIDTH; x++) {
        if (((x == 15) && (y == 15)) || (!tempdateable[x + y * WIDTH])) {
          continue;
        }

        blocks_[x + y * WIDTH] = applyNeighbors(x, y, temp, playerx, playery);

        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);
            }
          }
        }
      }
    }
  }

  void render(SDL_Renderer* renderer, int level) const {
    SDL_Rect block;
    block.w = 16;
    block.h = 16;

    for (int y = 0; y < HEIGHT; y++) {
      for (int x = 0; x < WIDTH; x++) {
        block.x = x * 16;
        block.y = y * 16;

        if (blocks_[x + y * WIDTH]) {
          setRendererAliveColor(renderer, level);
        } else {
          setRendererDeadColor(renderer, level);
        }

        SDL_RenderFillRect(renderer, &block);
      }
    }
  }

  bool isObstructed(int x, int y) const {
    return blocks_[x + y * WIDTH] || (x == 15 && y == 15);
  }

  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];
      }
    }

    return false;
  }

  using coord = std::tuple<int, int>;

 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);
        }
      }
    }

    blocks_[15 + 15 * WIDTH] = false;
  }

  bool 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).
    {
      GameBoard original = *this;

      std::unordered_set<board_type> 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 = std::move(search.front());
      search.pop_front();

      GameBoard& cbr = std::get<0>(cur);
      coord& cpl = std::get<1>(cur);
      int cns = std::get<2>(cur);

      // If it has been over 100 generations, give up.
      if (cns > 100) {
        continue;
      }

      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;
      }

      // 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 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;
        }
      }

      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_);

        while (nextState1.updateable_.any()) {
          nextState1.tick(std::get<0>(newLoc), std::get<1>(newLoc));

          if (pastStates.count(nextState1.blocks_)) {
            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);
        }
      }
    }

    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;
    }

    return output.str();
  }

  board_type blocks_;
  board_type updateable_;
  int oldx_;
  int oldy_;
};

std::unique_ptr<State> startNewLevel(int level,
                                     std::unique_ptr<GameBoard> board,
                                     int playerx, int playery);

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;
      }
    }

    // Display the level number
    setRendererDeadColor(game.renderer.get(), level_);
    SDL_RenderClear(game.renderer.get());

    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()));

    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);

    SDL_RenderCopy(game.renderer.get(), disptext.get(), NULL, &pos);
    SDL_RenderPresent(game.renderer.get());

    // Do 50 gens of Conway
    std::unique_ptr<GameBoard> board =
        std::make_unique<GameBoard>(game, level_, playerx, playery);

    // Wait a bit
    SDL_Delay(500);

    // Start the level
    return startNewLevel(level_, std::move(board), playerx, playery);
  }

 private:
  int level_;
};

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) {}

  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);
            }

            break;
          }
        }

        if (trymove && move(to_x, to_y)) {
          return std::make_unique<LoadGameState>(level_ + 1);
        }
      }
    }

    SDL_Delay(5);

    return nullptr;
  }

 private:
  bool move(int x, int y) {
    wrap(x, y);

    // Are we at the event?
    if ((x == 15) && (y == 15)) {
      return true;
    }

    // Can we even go there?
    if (!board_->isObstructed(x, y)) {
      playerx_ = x;
      playery_ = y;
    }

    return false;
  }

  int level_;
  std::unique_ptr<GameBoard> board_;
  int playerx_;
  int playery_;
};

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);
}

std::unique_ptr<State> GameState::operator()(Game&) {
  return std::make_unique<LoadGameState>(0);
}