Zannick
commented
8 months ago Replacing move_to with the A version resulted in a 7-8% speedup of the "load_routes" benchmark, which seems promising. Replacing first_spot_with_locations_after_actions with its A version (that allows for any number of actions repeated) results in the "can_win_from_scratch" benchmark hanging indefinitely, whereas it averages 15ms previously.
Potentially, we can reintroduce the limitation on global actions, but it's harder to make use of the shared expand functions if we include them in the heap--possibly we just introduce another map (keyed by Context which could be expensive), or indirect the heap input through provided lambdas...
We have two greedy-search stages, which both use the same code. The first is the initial greedy search to establish an upper bound--which is usually quickly beaten by the main search. The second is the greedy thread in the main search, which searches for the fastest route to each remaining location as the first one by using a greedy search that removes all other remaining locations.
This stems mainly from the use of
expandandfirst_spot_with_locations_after_actions.expandgenerates a mapping of every reachable spot with a context object.first_spot_with_locations_after_actionsgenerates a list of contexts to try along with a set of used actions, and this is fairly exponential if it doesn't find something on the first pass.When we have a specific location goal in mind, we can use A*: The priority queue metric is elapsed time plus min distance to the spot plus the location time. "Min distance" is a challenge, though, due to actions and warps not accounted for. Thankfully, we don't need to measure the metric for the initial context, so we can perform those once and then measure from there--I assert that we can still use those actions and warps afterward.
Here's what we're looking at:
expandandmove_towith an iterator to reachable spots. Each timenext()is called to get a new spot, the previous one is used to step further and insert into the queue. Potentially we should also be able to modify during iteration by inserting new elements (i.e. the results of actions/locations) in which case this is just a priority queue wrapper with peek.HashSet<SpotId>inexpandavoids backtracking, but it can miss out on subtle side effects like visiting map tiles or resetting rooms. To handle that, we'd have to useHashSet<T>, and hopefully the lazy iteration keeps the usage still lower thanexpandto the entire map does for now.first_spot...with the A* algorithm, but it needs to keep track ofused_globalsas usual.