path: root/src/tracker_state.cpp

#include "tracker_state.h"

#include <list>
#include <map>
#include <mutex>
#include <set>
#include <sstream>
#include <tuple>

#include "ap_state.h"
#include "game_data.h"

namespace {

struct TrackerState {
  std::map<int, bool> reachability;
  std::mutex reachability_mutex;
};

enum Decision { kYes, kNo, kMaybe };

TrackerState& GetState() {
  static TrackerState* instance = new TrackerState();
  return *instance;
}

class StateCalculator;

struct StateCalculatorOptions {
  int start;
  bool pilgrimage = false;
  StateCalculator* parent = nullptr;
};

class StateCalculator {
 public:
  StateCalculator() = default;

  explicit StateCalculator(StateCalculatorOptions options)
      : options_(options) {}

  void Calculate() {
    std::list<int> panel_boundary;
    std::list<Exit> flood_boundary;
    flood_boundary.push_back({.destination_room = options_.start});

    bool reachable_changed = true;
    while (reachable_changed) {
      reachable_changed = false;

      std::list<int> new_panel_boundary;
      for (int panel_id : panel_boundary) {
        if (solveable_panels_.count(panel_id)) {
          continue;
        }

        Decision panel_reachable = IsPanelReachable(panel_id);
        if (panel_reachable == kYes) {
          solveable_panels_.insert(panel_id);
          reachable_changed = true;
        } else if (panel_reachable == kMaybe) {
          new_panel_boundary.push_back(panel_id);
        }
      }

      std::list<Exit> new_boundary;
      for (const Exit& room_exit : flood_boundary) {
        if (reachable_rooms_.count(room_exit.destination_room)) {
          continue;
        }

        bool valid_transition = false;

        Decision exit_usable = IsExitUsable(room_exit);
        if (exit_usable == kYes) {
          valid_transition = true;
        } else if (exit_usable == kMaybe) {
          new_boundary.push_back(room_exit);
        }

        if (valid_transition) {
          reachable_rooms_.insert(room_exit.destination_room);
          reachable_changed = true;

          const Room& room_obj = GD_GetRoom(room_exit.destination_room);
          for (const Exit& out_edge : room_obj.exits) {
            if (out_edge.type == EntranceType::kPainting &&
                AP_IsPaintingShuffle()) {
              continue;
            }

            if (out_edge.type == EntranceType::kSunwarp &&
                AP_IsSunwarpShuffle()) {
              continue;
            }

            new_boundary.push_back(out_edge);
          }

          if (AP_IsPaintingShuffle()) {
            for (const PaintingExit& out_edge : room_obj.paintings) {
              if (AP_GetPaintingMapping().count(out_edge.id)) {
                Exit painting_exit;
                painting_exit.destination_room = GD_GetRoomForPainting(
                    AP_GetPaintingMapping().at(out_edge.id));
                painting_exit.door = out_edge.door;

                new_boundary.push_back(painting_exit);
              }
            }
          }

          if (AP_IsSunwarpShuffle()) {
            for (int index : room_obj.sunwarps) {
              if (AP_GetSunwarpMapping().count(index)) {
                const SunwarpMapping& sm = AP_GetSunwarpMapping().at(index);

                Exit sunwarp_exit;
                sunwarp_exit.destination_room =
                    GD_GetRoomForSunwarp(sm.exit_index);
                sunwarp_exit.door = GD_GetSunwarpDoors().at(sm.dots - 1);

                new_boundary.push_back(sunwarp_exit);
              }
            }
          }

          if (AP_HasEarlyColorHallways() && room_obj.name == "Starting Room") {
            new_boundary.push_back(
                {.destination_room = GD_GetRoomByName("Outside The Undeterred"),
                 .type = EntranceType::kPainting});
          }

          if (AP_IsPilgrimageEnabled()) {
            if (room_obj.name == "Hub Room") {
              new_boundary.push_back(
                  {.destination_room = GD_GetRoomByName("Pilgrim Antechamber"),
                   .type = EntranceType::kPilgrimage});
            }
          } else {
            if (room_obj.name == "Starting Room") {
              new_boundary.push_back(
                  {.destination_room = GD_GetRoomByName("Pilgrim Antechamber"),
                   .door =
                       GD_GetDoorByName("Pilgrim Antechamber - Sun Painting"),
                   .type = EntranceType::kPainting});
            }
          }

          for (int panel_id : room_obj.panels) {
            new_panel_boundary.push_back(panel_id);
          }
        }
      }

      flood_boundary = new_boundary;
      panel_boundary = new_panel_boundary;
    }
  }

  const std::set<int>& GetReachableRooms() const { return reachable_rooms_; }

  const std::map<int, Decision>& GetDoorDecisions() const {
    return door_decisions_;
  }

  const std::set<int>& GetSolveablePanels() const { return solveable_panels_; }

 private:
  Decision IsNonGroupedDoorReachable(const Door& door_obj) {
    bool has_item = AP_HasItem(door_obj.ap_item_id);

    if (!has_item) {
      for (const ProgressiveRequirement& prog_req : door_obj.progressives) {
        if (AP_HasItem(prog_req.ap_item_id, prog_req.quantity)) {
          has_item = true;
          break;
        }
      }
    }

    return has_item ? kYes : kNo;
  }

  Decision IsDoorReachable_Helper(int door_id) {
    const Door& door_obj = GD_GetDoor(door_id);

    if (!AP_IsPilgrimageEnabled() && door_obj.type == DoorType::kSunPainting) {
      return AP_HasItem(door_obj.ap_item_id) ? kYes : kNo;
    } else if (door_obj.type == DoorType::kSunwarp) {
      switch (AP_GetSunwarpAccess()) {
        case kSUNWARP_ACCESS_NORMAL:
          return kYes;
        case kSUNWARP_ACCESS_DISABLED:
          return kNo;
        case kSUNWARP_ACCESS_UNLOCK:
          return AP_HasItem(door_obj.group_ap_item_id) ? kYes : kNo;
        case kSUNWARP_ACCESS_INDIVIDUAL:
        case kSUNWARP_ACCESS_PROGRESSIVE:
          return IsNonGroupedDoorReachable(door_obj);
      }
    } else if (AP_GetDoorShuffleMode() == kNO_DOORS || door_obj.skip_item) {
      if (!reachable_rooms_.count(door_obj.room)) {
        return kMaybe;
      }

      for (int panel_id : door_obj.panels) {
        if (!solveable_panels_.count(panel_id)) {
          return kMaybe;
        }
      }

      return kYes;
    } else if (AP_GetDoorShuffleMode() == kSIMPLE_DOORS &&
               !door_obj.group_name.empty()) {
      return AP_HasItem(door_obj.group_ap_item_id) ? kYes : kNo;
    } else {
      return IsNonGroupedDoorReachable(door_obj);
    }
  }

  Decision IsDoorReachable(int door_id) {
    if (options_.parent) {
      return options_.parent->IsDoorReachable(door_id);
    }

    if (door_decisions_.count(door_id)) {
      return door_decisions_.at(door_id);
    }

    Decision result = IsDoorReachable_Helper(door_id);
    if (result != kMaybe) {
      door_decisions_[door_id] = result;
    }

    return result;
  }

  Decision IsPanelReachable(int panel_id) {
    const Panel& panel_obj = GD_GetPanel(panel_id);

    if (!reachable_rooms_.count(panel_obj.room)) {
      return kMaybe;
    }

    if (panel_obj.name == "THE MASTER") {
      int achievements_accessible = 0;

      for (int achieve_id : GD_GetAchievementPanels()) {
        if (solveable_panels_.count(achieve_id)) {
          achievements_accessible++;

          if (achievements_accessible >= AP_GetMasteryRequirement()) {
            break;
          }
        }
      }

      return (achievements_accessible >= AP_GetMasteryRequirement()) ? kYes
                                                                     : kMaybe;
    }

    if ((panel_obj.name == "ANOTHER TRY" || panel_obj.name == "LEVEL 2") &&
        AP_GetLevel2Requirement() > 1) {
      int counting_panels_accessible = 0;

      for (int solved_panel_id : solveable_panels_) {
        const Panel& solved_panel = GD_GetPanel(solved_panel_id);

        if (!solved_panel.non_counting) {
          counting_panels_accessible++;
        }
      }

      return (counting_panels_accessible >= AP_GetLevel2Requirement() - 1)
                 ? kYes
                 : kMaybe;
    }

    for (int room_id : panel_obj.required_rooms) {
      if (!reachable_rooms_.count(room_id)) {
        return kMaybe;
      }
    }

    for (int door_id : panel_obj.required_doors) {
      Decision door_reachable = IsDoorReachable(door_id);
      if (door_reachable == kNo) {
        const Door& door_obj = GD_GetDoor(door_id);
        return (door_obj.is_event || AP_GetDoorShuffleMode() == kNO_DOORS)
                   ? kMaybe
                   : kNo;
      } else if (door_reachable == kMaybe) {
        return kMaybe;
      }
    }

    for (int panel_id : panel_obj.required_panels) {
      if (!solveable_panels_.count(panel_id)) {
        return kMaybe;
      }
    }

    if (AP_IsColorShuffle()) {
      for (LingoColor color : panel_obj.colors) {
        if (!AP_HasItem(GD_GetItemIdForColor(color))) {
          return kNo;
        }
      }
    }

    return kYes;
  }

  Decision IsExitUsable(const Exit& room_exit) {
    if (room_exit.type == EntranceType::kPilgrimage) {
      if (options_.pilgrimage || !AP_IsPilgrimageEnabled()) {
        return kNo;
      }

      if (AP_GetSunwarpAccess() != kSUNWARP_ACCESS_NORMAL) {
        for (int door_id : GD_GetSunwarpDoors()) {
          Decision sub_decision = IsDoorReachable(door_id);
          if (sub_decision != kYes) {
            return sub_decision;
          }
        }
      }

      std::vector<std::tuple<int, int>> pilgrimage_pairs;
      if (AP_IsSunwarpShuffle()) {
        pilgrimage_pairs = std::vector<std::tuple<int, int>>(5);

        for (const auto& [start_index, mapping] : AP_GetSunwarpMapping()) {
          if (mapping.dots > 1) {
            std::get<1>(pilgrimage_pairs[mapping.dots - 2]) = start_index;
          }
          if (mapping.dots < 6) {
            std::get<0>(pilgrimage_pairs[mapping.dots - 1]) =
                mapping.exit_index;
          }
        }
      } else {
        pilgrimage_pairs = {{6, 1}, {8, 3}, {9, 4}, {10, 5}};
      }

      for (const auto& [from_sunwarp, to_sunwarp] : pilgrimage_pairs) {
        StateCalculator pilgrimage_calculator(
            {.start = GD_GetRoomForSunwarp(from_sunwarp),
             .pilgrimage = true,
             .parent = this});
        pilgrimage_calculator.Calculate();

        if (!pilgrimage_calculator.GetReachableRooms().count(
                GD_GetRoomForSunwarp(to_sunwarp))) {
          return kMaybe;
        }
      }

      return kYes;
    }

    if (options_.pilgrimage) {
      if (room_exit.type == EntranceType::kWarp ||
          room_exit.type == EntranceType::kSunwarp) {
        return kNo;
      }
      if (room_exit.type == EntranceType::kCrossroadsRoofAccess &&
          !AP_DoesPilgrimageAllowRoofAccess()) {
        return kNo;
      }
      if (room_exit.type == EntranceType::kPainting &&
          !AP_DoesPilgrimageAllowPaintings()) {
        return kNo;
      }
    }

    if (room_exit.type == EntranceType::kSunwarp) {
      if (AP_GetSunwarpAccess() == kSUNWARP_ACCESS_NORMAL) {
        return kYes;
      } else if (AP_GetSunwarpAccess() == kSUNWARP_ACCESS_DISABLED) {
        return kNo;
      }
    }

    if (room_exit.door.has_value()) {
      return IsDoorReachable(*room_exit.door);
    }

    return kYes;
  }

  StateCalculatorOptions options_;

  std::set<int> reachable_rooms_;
  std::map<int, Decision> door_decisions_;
  std::set<int> solveable_panels_;
};

}  // namespace

void RecalculateReachability() {
  StateCalculator state_calculator({.start = GD_GetRoomByName("Menu")});
  state_calculator.Calculate();

  const std::set<int>& reachable_rooms = state_calculator.GetReachableRooms();
  const std::set<int>& solveable_panels = state_calculator.GetSolveablePanels();

  std::map<int, bool> new_reachability;
  for (const MapArea& map_area : GD_GetMapAreas()) {
    for (size_t section_id = 0; section_id < map_area.locations.size();
         section_id++) {
      const Location& location_section = map_area.locations.at(section_id);
      bool reachable = reachable_rooms.count(location_section.room);
      if (reachable) {
        for (int panel_id : location_section.panels) {
          reachable &= (solveable_panels.count(panel_id) == 1);
        }
      }

      new_reachability[location_section.ap_location_id] = reachable;
    }
  }

  {
    std::lock_guard reachability_guard(GetState().reachability_mutex);
    std::swap(GetState().reachability, new_reachability);
  }
}

bool IsLocationReachable(int location_id) {
  std::lock_guard reachability_guard(GetState().reachability_mutex);

  if (GetState().reachability.count(location_id)) {
    return GetState().reachability.at(location_id);
  } else {
    return false;
  }
}