Try mutating solutions to get other solutions or partial progress

Zannick commented 4 months ago

For example, if we visit the same spot 3 times (i.e. 2 loops), can we move the first loop to occur at the later visit? The idea is to move potentially-related components together so it becomes easier for the search to find a smoother path. Similar to #160 but not specific to minimizing.

Some ideas for what we can do and recreate_store the full or partial route in the db:

Loop reordering
Keep failed minimizes
Trie search allowing for some number of failed matches

Zannick commented 4 months ago

7318ce69c43429f72d921eb2d97af7ee50b72c1a is related to this (oops).

Zannick commented 3 months ago

New idea try_reroute:

We make an index list into the list of states from a solution, specifically of just the steps that acquired an item. Then we pick two item steps A and B (by some criteria, e.g. being in the same area or region) that aren't adjacent in this index list, and we try to reorder the states to get A and B adjacent. The process would look like:

Start from the state of the item immediately before A (call it A-1).
access_location_after_actions to move to the item immediately after A (A+1).
For A+2 until B-1, we can try_replay but if it fails we should access_location_after_actions to attempt another route to the location. (We should allow for any step and not just location however.)
access_location_after_actions to get A.
access_location_after_actions to get B.
Replay the remaining steps.

Possibly we should also get B then A to have an alternate version of the route.

One caveat: we need a way to determine whether this is not possible. If we can do so beforehand, we still need to run this algorithm to produce the new route. access_location_after_actions does not have a way to determine impossibility--it only terminates by running out of choices (typically by hitting an upper bound).

We could observe specifically the route from A to B in order to see if the changes from A are used, and we could restrict the analysis such that it gives us no false negatives (allowing us certainty that we can do it), but the false positives would be annoying, because we couldn't confirm whether we can work around the usage (to use a slower route) without attempting it anyway.

Perhaps the upper bound on step X in A+1...B-1 would be the original time to reach X, and then the last few steps just use the original time for B, so we always aim for a faster overall time.

Zannick commented 3 months ago

Mutating solutions as they come in proved to be excessive load in the early stages #170. Independent of the previous idea, we could run the mutation on only the top results, or even just periodically after we clean out the solution collector. Simply running the minimize command while the search was running resulted in a better solution (and still left in at least one unnecessary location, which surprised me).

Zannick commented 3 months ago

To save time, we can predetermine which locations are ones we'd like to see collected in such an adjacent manner. The puzzle is, how do we determine those? In some cases we anticipate there will be pairs and other times we may have larger clusters, perhaps ordered or unordered.

Same region? Too broad, and yet would exclude some cases nearby across the border.
Same area? Would include items you have to go to another area to get.
Shortest path between them has no warps? Would exclude the warps we like that move across dimensions without moving across the map.
Shortest path between them has no warps that change coordinates?
Shortest path between them is max two areas? Probably a little too broad with warps.
For A and B, shortest path from any other C to A passes close to B?
For A and B, shortest paths from any other C to A and B form a specific kind of triangle?
Some notion of overlap of all the shortest paths to A?
Just simply come up with a total ordering of paths to A and determine a cutoff?
Take a certain radius around A based on the nearest locations by distance and choose some subset of the ones in that radius?
Some other established graph clustering algorithm

Zannick commented 3 months ago

https://leidenalg.readthedocs.io/en/stable/intro.html seems very promising so far, I've been playing around with just getting a visualization or list of the partitions.

Zannick commented 3 months ago

Here's the result of a handful of test partitioning schemes on an AV2 item that's part of the inspiration for this, removing all the ones that produce singletons:

{'mod': (7,
         ['Irikar__Basement_Pipes__Left_Vertical_Pipe',
          'Irikar__Basement_Pipes__High_Pipe',
          'Irikar__Midwest__Left_Platform_Dest',
          'Irikar__Midwest__Right_Platform_Start',
          'Irikar__Midwest__Tablet_Platform',
          'Irikar__Beach_Save__Top_Platform',
          'Irikar__Beach__Cache']),
 'rb.5': (15,
          ['Irikar_Breach__Hover_Room__Bottom',
           'Irikar__Hub__Sat_Tower_Top_Ledge',
           'Irikar__Hub__Ruined_Hallway_By_Well',
           'Irikar__Hub__Ruined_Hallway_Atop_Well',
           'Irikar__Hub__SW_Building_Top_Platform',
           'Irikar__Hub__Collapsed_Column',
           'Irikar__Sight_Room__Item_Pedestal',
           'Irikar__Basement_Pipes__Left_Vertical_Pipe',
           'Irikar__Basement_Pipes__High_Pipe',
           'Irikar__Midwest__Left_Platform_Dest',
           'Irikar__Midwest__Right_Platform_Start',
           'Irikar__Midwest__Tablet_Platform',
           'Irikar__Beach_Save__Top_Platform',
           'Giguna__Clouds__Cache',
           'Irikar__Beach__Cache']),
 'rb2': (7,
         ['Irikar__Basement_Pipes__Left_Vertical_Pipe',
          'Irikar__Basement_Pipes__High_Pipe',
          'Irikar__Midwest__Left_Platform_Dest',
          'Irikar__Midwest__Right_Platform_Start',
          'Irikar__Midwest__Tablet_Platform',
          'Irikar__Beach_Save__Top_Platform',
          'Irikar__Beach__Cache']),
 'rber.5': (11,
            ['Irikar__Hub__Ruined_Hallway_By_Well',
             'Irikar__Hub__Ruined_Hallway_Atop_Well',
             'Irikar__Hub__SW_Building_Top_Platform',
             'Irikar__Hub__Collapsed_Column',
             'Irikar__Basement_Pipes__Left_Vertical_Pipe',
             'Irikar__Basement_Pipes__High_Pipe',
             'Irikar__Midwest__Left_Platform_Dest',
             'Irikar__Midwest__Right_Platform_Start',
             'Irikar__Midwest__Tablet_Platform',
             'Irikar__Beach_Save__Top_Platform',
             'Irikar__Beach__Cache'])}

These were all produced very fast, and since our goal isn't to be perfect but to have a decent selection of nearby locations, this is a great solution that doesn't involve inventing our own algorithms. Potentially we can even use multiple of these to have layers of wider communities.

As for the results we have here, the groups of size 7 and 11 are the ones we look at naturally when we look at routing this side of Irikar. The 15 is a little too wide for a single route to use, mainly because it contains 2 separate stages that we'd do in Irikar, plus the separate cache in Giguna that we'd get before doing the second of these segments, but that could make it pretty great for a second layer. I will look through the rest of the results to see what works more throughout the map.

Additionally, the original idea was to use these for trying to combine disparate steps together when they're otherwise close by, but we could also use this to limit the greedy steps that will spend lots of time trying to access every possible remaining location. Instead, we could attempt all locations in these communities, plus the nearest one or two outside.

Zannick commented 3 months ago

One additional issue is that some of these partitions are probabilistic, so they can change between runs slightly. Ideally we use an algorithm where that's not prone to happening, fix the random factor, and/or increase the number of iterations to improve the partition.

Zannick commented 3 months ago

It's a little annoying that we might have actions that collect items, but we can make do in a couple of ways. We can add a check for whether an action might collect something (detecting whether $visit is called ($collect or $add_item also work)). And then we check whether an action or location is in a community is checking whether its spot is in the community. Getting the list of remaining locations in a community is getting the list of locations and paring down by whether it's in the community and unvisited.

Zannick commented 3 months ago

I'm not sure how well this will work when we aren't properly searching for how to do an action that gets us items. In AV2's case, it's possible that we need to perform another action first before we can do that action. Addressing this will require making an analogue for access_location_after_actions for actions (or making it a little more generic, which I think will require making a steiner graph node category for action[^1]). #179 would probably be better. And trying to remove them could actually fail more often as we'd most likely skip the action on the way to the next location.

[^1]: Although... we might be able to make the objective a Spot plus require an Accessible in the algorithm. The distinction now would be that we use canon id for locations, not the specific location itself.

Zannick commented 3 months ago

Here's an AV2 diff the mutate endpoint provided against the best output of the search algorithm from a few days ago:

--- original [3781766ms]
+++ best [3745818ms (-35948ms)]
@@ -123,8 +123,6 @@
 ! Do Ebih > Ebih East > Lower Moving Platform > Activate Lift
   Move... to Ebih > Ebih East > Moving Platform
 ! Do Ebih > Ebih East > Moving Platform > Activate Ride
-  Move... to Ebih > Ebih East > East Ledge
-* Collect Under_Siege from Ebih > Ebih East > East Ledge > Note
   Move... to Ebih > Ebih East > East 9
   Take exit Ebih > Ebih East > East 9 ==> Observation Tower Room > West 9 (1)
   Move... to Ebih > Observation Tower Room > West 10
@@ -1138,36 +1136,26 @@
   Move... to Menu > Kiengir Map > Ebih West Upper
   Take exit Menu > Kiengir Map > Ebih West Upper ==> Ebih > Ebih West > Upper Save (1)
   Move... to Ebih > Ebih West > East 7
-! Do Become Indra
   Take exit Ebih > Ebih West > East 7 ==> Waterfall > West 7 (1)
   Move... to Ebih > Waterfall > East 7
   Take exit Ebih > Waterfall > East 7 ==> Ebih East > West 7 (1)
+  Move... to Ebih > Ebih East > East Ledge
+* Collect Under_Siege from Ebih > Ebih East > East Ledge > Note
   Move... to Ebih > Ebih East > Lower Moving Platform
 ! Do Ebih > Ebih East > Lower Moving Platform > Activate Ride
 * Collect Health_Fragment from Ebih > Ebih East > Dispenser > Vend
-! Do Become Drone
   FastTravelKiengirwarp to Menu > Kiengir Map > Ebih East Health
-  Move... to Menu > Kiengir Map > Giguna Ruins Top
-  Take exit Menu > Kiengir Map > Giguna Ruins Top ==> Giguna > Ruins Top > Save Point (1)
-! Do Become Indra
-  Move... to Giguna > Ruins Top > Switch
-  Move... to Giguna > Ruins Top > Rooftop East
-  Move... to Giguna > Ruins Top > Rooftop Gutter
-  Take exit Giguna > Ruins Top > Rooftop Gutter ==> Ruins East > Pillar (1)
-  Move... to Giguna > Ruins East > East 9
-  Take exit Giguna > Ruins East > East 9 ==> Giguna Northeast > West 9 (1)
+  Move... to Menu > Kiengir Map > Giguna Northeast
+  Take exit Menu > Kiengir Map > Giguna Northeast ==> Giguna > Giguna Northeast > Save Point (1)
   Move... to Giguna > Giguna Northeast > West 10
   Take exit Giguna > Giguna Northeast > West 10 ==> Carnelian > East 10 (1)
   Move... to Giguna > Carnelian > Switch
 ! Do Giguna > Carnelian > Switch > Open Door
   Move... to Giguna > Carnelian > Vault
 * Collect Carnelian_Ring from Giguna > Carnelian > Vault > Item
-  Move... to Giguna > Carnelian > Switch
-  Move... to Giguna > Carnelian > East 10
-! Do Become Drone
-  Take exit Giguna > Carnelian > East 10 ==> Giguna Northeast > West 10 (1)
-  FastTravelKiengirwarp to Menu > Kiengir Map > Giguna Northeast
-  Move to Menu > Kiengir Map > Irikar Hub
+  FastTravelKiengirwarp to Menu > Kiengir Map > Carnelian Ring
+  Move... to Menu > Kiengir Map > Ebih West Lower
+  Move... to Menu > Kiengir Map > Irikar Hub
   Take exit Menu > Kiengir Map > Irikar Hub ==> Irikar > Hub > Save Point (1)
   Move... to Irikar > Hub > West Rim
   Move... to Irikar > Hub > East Rim
@@ -1210,34 +1198,26 @@
   Move... to Giguna > Cache > Upper Ledge
   Move... to Giguna > Cache > Pit
 * Collect Health_Fragment from Giguna > Cache > Pit > Item
-  Move... to Giguna > Cache > Upper Ledge
-  Move... to Giguna > Cache > West
-  Take exit Giguna > Cache > West ==> Labyrinth > East 22 (1)
-  Move... to Giguna > Labyrinth > Ledge 22
+  FastTravelKiengirwarp to Menu > Kiengir Map > Giguna Cache
+  Move... to Menu > Kiengir Map > Giguna Labyrinth
+  Move... to Menu > Kiengir Map > Irikar Midwest
+  Take exit Menu > Kiengir Map > Irikar Midwest ==> Irikar > Midwest > Save Point (1)
+  Move... to Irikar > Midwest > Right Platform Start
+* Collect Big_Flask from Irikar > Midwest > Right Platform Start > Flask
+  FastTravelKiengirwarp to Menu > Kiengir Map > Irikar Mid-air Flask
+  Move... to Menu > Kiengir Map > Giguna Labyrinth
+  Take exit Menu > Kiengir Map > Giguna Labyrinth ==> Giguna > Labyrinth > Save Point (1)
   Move... to Giguna > Labyrinth > Door Ledge
 ! Do Become Indra
 ! Do Giguna > Labyrinth > Door Ledge > Open Door
+  Move... to Giguna > Labyrinth > Portal Stand
 ! Do Become Drone
-  Move... to Giguna > Labyrinth > Middle Brick
-! Do Move Portal Here
-  Portalwarp to Giguna Breach > Labyrinth > Middle Brick
+  Portalwarp to Giguna Breach > Labyrinth > Save Point
   Move... to Giguna Breach > Labyrinth > Lower Tier West
   Move... to Giguna Breach > Labyrinth > Lower Tier East
   Move... to Giguna Breach > Labyrinth > Pipe Cache
 * Take hybrid exit Giguna Breach > Labyrinth > Pipe Cache > Flask Collection Skip, collecting Flask
   BreachSavewarp to Giguna Breach > Labyrinth > Save Point
-  ExitBreachwarp to Giguna > Labyrinth > Portal Stand
-  FastTravelKiengirwarp to Menu > Kiengir Map > Nano Lattice 1
-  Move... to Menu > Kiengir Map > Irikar Midwest
-  Take exit Menu > Kiengir Map > Irikar Midwest ==> Irikar > Midwest > Save Point (1)
-  Move... to Irikar > Midwest > Right Platform Start
-* Collect Big_Flask from Irikar > Midwest > Right Platform Start > Flask
-  FastTravelKiengirwarp to Menu > Kiengir Map > Irikar Mid-air Flask
-  Move... to Menu > Kiengir Map > Giguna Labyrinth
-  Take exit Menu > Kiengir Map > Giguna Labyrinth ==> Giguna > Labyrinth > Save Point (1)
-  Move... to Giguna > Labyrinth > Door Ledge
-  Move... to Giguna > Labyrinth > Middle Brick
-  Portalwarp to Giguna Breach > Labyrinth > Middle Brick
   Move... to Giguna Breach > Labyrinth > Lower Tier West
   Move... to Giguna Breach > Labyrinth > Lower Tier East
   Move... to Giguna Breach > Labyrinth > Middle Tier Ledge

Summary:

Under Siege is collected later.
A couple of unnecessary changes into Indra and back are removed.
Some fast travel segments are improved.
The Big Flask in Irikar Midwest is reordered to be later, where it benefits from having a closer warp point. The item immediately following it is the flask in Giguna Labyrinth, which was previously immediately before it. The route into that area seems more efficient. The route that followed the original collection of that Irikar Flask goes back into the Giguna Labyrinth breach, so this appears to be one success!

Zannick commented 3 months ago

I also noticed a few issues with savewarping that have to be addressed separately...

Zannick commented 3 months ago

This is working very well now, thanks to #184 handling this in the background. Overall now, the search was able to bring the best time down about 200s in a very reasonable time!

Zannick / logic-graph

Try mutating solutions to get other solutions or partial progress #163