[Apworld] Some access checking optimizations

Letter requirements in OR logic (which is the main thing OR logic is
used for) is simplified now. Any requirement within the OR logic that is
redundant with the top level requirement now has the redundant letters
removed. If a clause in a disjunction becomes empty due to this, the
disjunction can be removed. Additionally, if all of the clauses in a
disjunction are identical, then they can be merged into the top level
requirement.

I manually verified that every requirement that is affected by this
simplification looks correct.

Region objects are also now used in access checking instead of looking
up the regions by name during access checking. This is a little faster
for access checks that involve a lot of rooms, such as the Maze
Gravestone.

Finally, locations no longer check for access to the region the location
is in, and connections no longer check for access to the source region,
because these are both implied by how the graph works.

3 files changed, 90 insertions, 13 deletions

@@ -45,6 +45,18 @@ class AccessRequirements:
         self.complete_at = None
         self.possibilities = list()
 
+    def copy(self) -> "AccessRequirements":
+        reqs = AccessRequirements()
+        reqs.items = self.items.copy()
+        reqs.progressives = self.progressives.copy()
+        reqs.rooms = self.rooms.copy()
+        reqs.letters = self.letters.copy()
+        reqs.cyans = self.cyans
+        reqs.or_logic = [[other_req.copy() for other_req in disjunction] for disjunction in self.or_logic]
+        reqs.complete_at = self.complete_at
+        reqs.possibilities = self.possibilities.copy()
+        return reqs
+
     def merge(self, other: "AccessRequirements"):
         for item in other.items:
             self.items.add(item)
@@ -88,7 +100,44 @@ class AccessRequirements:
 
     def is_empty(self) -> bool:
         return (len(self.items) == 0 and len(self.progressives) == 0 and len(self.rooms) == 0 and len(self.letters) == 0
-                and not self.cyans and len(self.or_logic) == 0 and self.complete_at is not None)
+                and not self.cyans and len(self.or_logic) == 0 and self.complete_at is None)
+
+    def __eq__(self, other: "AccessRequirements"):
+        return (self.items == other.items and self.progressives == other.progressives and self.rooms == other.rooms and
+                self.letters == other.letters and self.cyans == other.cyans and self.or_logic == other.or_logic and
+                self.complete_at == other.complete_at and self.possibilities == other.possibilities)
+
+    def simplify(self):
+        resimplify = False
+
+        if len(self.or_logic) > 0:
+            old_or_logic = self.or_logic
+
+            def remove_redundant(sub_reqs: "AccessRequirements"):
+                sub_reqs.letters = {l: v for l, v in sub_reqs.letters.items() if self.letters.get(l, 0) < v}
+
+            self.or_logic = []
+            for disjunction in old_or_logic:
+                new_disjunction = []
+                for ssr in disjunction:
+                    remove_redundant(ssr)
+                    if not ssr.is_empty():
+                        new_disjunction.append(ssr)
+                    else:
+                        new_disjunction.clear()
+                        break
+                if len(new_disjunction) == 1:
+                    self.merge(new_disjunction[0])
+                    resimplify = True
+                elif len(new_disjunction) > 1:
+                    if all(cjr == new_disjunction[0] for cjr in new_disjunction):
+                        self.merge(new_disjunction[0])
+                        resimplify = True
+                    else:
+                        self.or_logic.append(new_disjunction)
+
+        if resimplify:
+            self.simplify()
 
     def __repr__(self):
         parts = []
@@ -403,6 +452,8 @@ class Lingo2PlayerLogic:
             sub_reqs = self.get_door_open_reqs(sub_door_id)
             reqs.merge(sub_reqs)
 
+        reqs.simplify()
+
         return reqs
 
     # This gets the requirements to open a door within the world. When a door is shuffled, this means having the item
@@ -11,12 +11,18 @@ if TYPE_CHECKING:
 
 
 def create_region(room, world: "Lingo2World") -> Region:
-    new_region = Region(world.static_logic.get_room_region_name(room.id), world.player, world.multiworld)
+    return Region(world.static_logic.get_room_region_name(room.id), world.player, world.multiworld)
 
+
+def create_locations(room, new_region: Region, world: "Lingo2World", regions: dict[str, Region]):
     for location in world.player_logic.locations_by_room.get(room.id, {}):
+        reqs = location.reqs.copy()
+        if new_region.name in reqs.rooms:
+            reqs.rooms.remove(new_region.name)
+
         new_location = Lingo2Location(world.player, world.static_logic.location_id_to_name[location.code],
                                       location.code, new_region)
-        new_location.access_rule = make_location_lambda(location.reqs, world)
+        new_location.access_rule = make_location_lambda(reqs, world, regions)
         new_region.locations.append(new_location)
 
     for event_name, item_name in world.player_logic.event_loc_item_by_room.get(room.id, {}).items():
@@ -25,17 +31,23 @@ def create_region(room, world: "Lingo2World") -> Region:
         new_location.place_locked_item(event_item)
         new_region.locations.append(new_location)
 
-    return new_region
-
-
 def create_regions(world: "Lingo2World"):
     regions = {
         "Menu": Region("Menu", world.player, world.multiworld)
     }
 
+    region_and_room = []
+
+    # Create the regions in two stages. First, make the actual region objects and memoize them. Then, add all of the
+    # locations. This allows us to reference the actual region objects in the access rules for the locations, which is
+    # faster than having to look them up during access checking.
     for room in world.static_logic.objects.rooms:
         region = create_region(room, world)
         regions[region.name] = region
+        region_and_room.append((region, room))
+
+    for (region, room) in region_and_room:
+        create_locations(room, region, world, regions)
 
     regions["Menu"].connect(regions["The Entry - Starting Room"], "Start Game")
 
@@ -82,14 +94,18 @@ def create_regions(world: "Lingo2World"):
             else:
                 connection_name = f"{connection_name} (via panel {panel.name})"
 
+        reqs.simplify()
+
         if from_region in regions and to_region in regions:
             connection = Entrance(world.player, connection_name, regions[from_region])
-            connection.access_rule = make_location_lambda(reqs, world)
+            connection.access_rule = make_location_lambda(reqs, world, regions)
 
             regions[from_region].exits.append(connection)
             connection.connect(regions[to_region])
 
             for region in reqs.rooms:
+                if region == from_region:
+                    continue
                 world.multiworld.register_indirect_condition(regions[region], connection)
 
     world.multiworld.regions += regions.values()
@@ -1,14 +1,15 @@
 from collections.abc import Callable
 from typing import TYPE_CHECKING
 
-from BaseClasses import CollectionState
+from BaseClasses import CollectionState, Region
 from .player_logic import AccessRequirements
 
 if TYPE_CHECKING:
     from . import Lingo2World
 
 
-def lingo2_can_satisfy_requirements(state: CollectionState, reqs: AccessRequirements, world: "Lingo2World") -> bool:
+def lingo2_can_satisfy_requirements(state: CollectionState, reqs: AccessRequirements, regions: list[Region],
+                                    world: "Lingo2World") -> bool:
     if not all(state.has(item, world.player) for item in reqs.items):
         return False
 
@@ -18,6 +19,9 @@ def lingo2_can_satisfy_requirements(state: CollectionState, reqs: AccessRequirem
     if not all(state.can_reach_region(region_name, world.player) for region_name in reqs.rooms):
         return False
 
+    if not all(state.can_reach(region) for region in regions):
+        return False
+
     for letter_key, letter_level in reqs.letters.items():
         if not state.has(letter_key, world.player, letter_level):
             return False
@@ -28,7 +32,7 @@ def lingo2_can_satisfy_requirements(state: CollectionState, reqs: AccessRequirem
             return False
 
     if len(reqs.or_logic) > 0:
-        if not all(any(lingo2_can_satisfy_requirements(state, sub_reqs, world) for sub_reqs in subjunction)
+        if not all(any(lingo2_can_satisfy_requirements(state, sub_reqs, [], world) for sub_reqs in subjunction)
                    for subjunction in reqs.or_logic):
             return False
 
@@ -37,7 +41,7 @@ def lingo2_can_satisfy_requirements(state: CollectionState, reqs: AccessRequirem
         checked = 0
         for possibility in reqs.possibilities:
             checked += 1
-            if lingo2_can_satisfy_requirements(state, possibility, world):
+            if lingo2_can_satisfy_requirements(state, possibility, [], world):
                 completed += 1
                 if completed >= reqs.complete_at:
                     break
@@ -49,5 +53,11 @@ def lingo2_can_satisfy_requirements(state: CollectionState, reqs: AccessRequirem
 
     return True
 
-def make_location_lambda(reqs: AccessRequirements, world: "Lingo2World") -> Callable[[CollectionState], bool]:
-    return lambda state: lingo2_can_satisfy_requirements(state, reqs, world)
+def make_location_lambda(reqs: AccessRequirements, world: "Lingo2World",
+                         regions: dict[str, Region]) -> Callable[[CollectionState], bool]:
+    # Replace required rooms with regions for the top level requirement, which saves looking up the regions during rule
+    # checking.
+    required_regions = [regions[room_name] for room_name in reqs.rooms]
+    new_reqs = reqs.copy()
+    new_reqs.rooms.clear()
+    return lambda state: lingo2_can_satisfy_requirements(state, new_reqs, required_regions, world)