Merge branch 'main' into subway

1 files changed, 315 insertions, 136 deletions

@@ -24,27 +24,150 @@ TrackerState& GetState() {
   return *instance;
 }
 
-Decision IsDoorReachable_Helper(int door_id,
-                                const std::set<int>& reachable_rooms,
-                                const std::set<int>& solveable_panels) {
-  const Door& door_obj = GD_GetDoor(door_id);
+class StateCalculator;
 
-  if (AP_GetDoorShuffleMode() == kNO_DOORS || door_obj.skip_item) {
-    if (!reachable_rooms.count(door_obj.room)) {
-      return kMaybe;
-    }
+struct StateCalculatorOptions {
+  int start;
+  bool pilgrimage = false;
+  StateCalculator* parent = nullptr;
+};
 
-    for (int panel_id : door_obj.panels) {
-      if (!solveable_panels.count(panel_id)) {
-        return kMaybe;
+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;
     }
+  }
 
-    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 {
+  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) {
@@ -58,175 +181,231 @@ Decision IsDoorReachable_Helper(int door_id,
 
     return has_item ? kYes : kNo;
   }
-}
-
-Decision IsPanelReachable_Helper(int panel_id,
-                                 const std::set<int>& reachable_rooms,
-                                 const std::set<int>& solveable_panels) {
-  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++;
+  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;
+      }
 
-        if (achievements_accessible >= AP_GetMasteryRequirement()) {
-          break;
+      for (int panel_id : door_obj.panels) {
+        if (!solveable_panels_.count(panel_id)) {
+          return kMaybe;
         }
       }
-    }
 
-    return (achievements_accessible >= AP_GetMasteryRequirement()) ? kYes
-                                                                   : 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);
+    }
   }
 
-  if ((panel_obj.name == "ANOTHER TRY" || panel_obj.name == "LEVEL 2") &&
-      AP_GetLevel2Requirement() > 1) {
-    int counting_panels_accessible = 0;
+  Decision IsDoorReachable(int door_id) {
+    if (options_.parent) {
+      return options_.parent->IsDoorReachable(door_id);
+    }
 
-    for (int solved_panel_id : solveable_panels) {
-      const Panel& solved_panel = GD_GetPanel(solved_panel_id);
+    if (door_decisions_.count(door_id)) {
+      return door_decisions_.at(door_id);
+    }
 
-      if (!solved_panel.non_counting) {
-        counting_panels_accessible++;
-      }
+    Decision result = IsDoorReachable_Helper(door_id);
+    if (result != kMaybe) {
+      door_decisions_[door_id] = result;
     }
 
-    return (counting_panels_accessible >= AP_GetLevel2Requirement() - 1)
-               ? kYes
-               : kMaybe;
+    return result;
   }
 
-  for (int room_id : panel_obj.required_rooms) {
-    if (!reachable_rooms.count(room_id)) {
-      return kMaybe;
-    }
-  }
+  Decision IsPanelReachable(int panel_id) {
+    const Panel& panel_obj = GD_GetPanel(panel_id);
 
-  for (int door_id : panel_obj.required_doors) {
-    Decision door_reachable =
-        IsDoorReachable_Helper(door_id, reachable_rooms, solveable_panels);
-    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) {
+    if (!reachable_rooms_.count(panel_obj.room)) {
       return kMaybe;
     }
-  }
 
-  for (int panel_id : panel_obj.required_panels) {
-    if (!solveable_panels.count(panel_id)) {
-      return kMaybe;
-    }
-  }
+    if (panel_obj.name == "THE MASTER") {
+      int achievements_accessible = 0;
 
-  if (AP_IsColorShuffle()) {
-    for (LingoColor color : panel_obj.colors) {
-      if (!AP_HasItem(GD_GetItemIdForColor(color))) {
-        return kNo;
-      }
-    }
-  }
+      for (int achieve_id : GD_GetAchievementPanels()) {
+        if (solveable_panels_.count(achieve_id)) {
+          achievements_accessible++;
 
-  return kYes;
-}
+          if (achievements_accessible >= AP_GetMasteryRequirement()) {
+            break;
+          }
+        }
+      }
 
-}  // namespace
+      return (achievements_accessible >= AP_GetMasteryRequirement()) ? kYes
+                                                                     : kMaybe;
+    }
 
-void RecalculateReachability() {
-  std::set<int> reachable_rooms;
-  std::set<int> solveable_panels;
+    if ((panel_obj.name == "ANOTHER TRY" || panel_obj.name == "LEVEL 2") &&
+        AP_GetLevel2Requirement() > 1) {
+      int counting_panels_accessible = 0;
 
-  std::list<int> panel_boundary;
-  std::list<Exit> flood_boundary;
-  flood_boundary.push_back({.destination_room = GD_GetRoomByName("Menu")});
+      for (int solved_panel_id : solveable_panels_) {
+        const Panel& solved_panel = GD_GetPanel(solved_panel_id);
 
-  if (AP_HasEarlyColorHallways()) {
-    flood_boundary.push_back(
-        {.destination_room = GD_GetRoomByName("Outside The Undeterred")});
-  }
+        if (!solved_panel.non_counting) {
+          counting_panels_accessible++;
+        }
+      }
 
-  bool reachable_changed = true;
-  while (reachable_changed) {
-    reachable_changed = false;
+      return (counting_panels_accessible >= AP_GetLevel2Requirement() - 1)
+                 ? kYes
+                 : kMaybe;
+    }
 
-    std::list<int> new_panel_boundary;
-    for (int panel_id : panel_boundary) {
-      if (solveable_panels.count(panel_id)) {
-        continue;
+    for (int room_id : panel_obj.required_rooms) {
+      if (!reachable_rooms_.count(room_id)) {
+        return kMaybe;
       }
+    }
 
-      Decision panel_reachable =
-          IsPanelReachable_Helper(panel_id, reachable_rooms, solveable_panels);
-      if (panel_reachable == kYes) {
-        solveable_panels.insert(panel_id);
-        reachable_changed = true;
-      } else if (panel_reachable == kMaybe) {
-        new_panel_boundary.push_back(panel_id);
+    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;
       }
     }
 
-    std::list<Exit> new_boundary;
-    for (const Exit& room_exit : flood_boundary) {
-      if (reachable_rooms.count(room_exit.destination_room)) {
-        continue;
+    for (int panel_id : panel_obj.required_panels) {
+      if (!solveable_panels_.count(panel_id)) {
+        return kMaybe;
       }
+    }
 
-      bool valid_transition = false;
-      if (room_exit.door.has_value()) {
-        Decision door_reachable = IsDoorReachable_Helper(
-            *room_exit.door, reachable_rooms, solveable_panels);
-        if (door_reachable == kYes) {
-          valid_transition = true;
-        } else if (door_reachable == kMaybe) {
-          new_boundary.push_back(room_exit);
+    if (AP_IsColorShuffle()) {
+      for (LingoColor color : panel_obj.colors) {
+        if (!AP_HasItem(GD_GetItemIdForColor(color))) {
+          return kNo;
         }
-      } else {
-        valid_transition = true;
       }
+    }
 
-      if (valid_transition) {
-        reachable_rooms.insert(room_exit.destination_room);
-        reachable_changed = true;
+    return kYes;
+  }
 
-        const Room& room_obj = GD_GetRoom(room_exit.destination_room);
-        for (const Exit& out_edge : room_obj.exits) {
-          if (!out_edge.painting || !AP_IsPaintingShuffle()) {
-            new_boundary.push_back(out_edge);
+  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;
           }
         }
+      }
 
-        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;
+      std::vector<std::tuple<int, int>> pilgrimage_pairs;
+      if (AP_IsSunwarpShuffle()) {
+        pilgrimage_pairs = std::vector<std::tuple<int, int>>(5);
 
-              new_boundary.push_back(painting_exit);
-            }
+        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 (int panel_id : room_obj.panels) {
-          new_panel_boundary.push_back(panel_id);
+      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;
+      }
     }
 
-    flood_boundary = new_boundary;
-    panel_boundary = new_panel_boundary;
+    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();