Better guarantees for greedy one-location searches

[Zannick]

Right now our sorting in access_location_after_actions is by shortest possible path to the destination spot. Unfortunately, with AV2's warps, the shortest path map is going to look very uniform: outside of an area near the goal and some save points we can warp to, the distances will be constant due to the potential to warp to the closer point. However, if we can't perform that warp, we have to use an alternate route, and unfortunately, at the distance, everywhere we move is equivalent until we stumble into the near area.

Ideally we'd use an actual shortest time to the goal but finding that is solving the greedy search step anyway--we're using the shortest path table as an A* heuristic to help us find that shortest real path to the goal.

We should extend the sort key to include additional criteria as a tiebreaker. The simplest would be straight-line distance, or we could have a normalized shortest path table that counts distance in number of Areas and/or Regions.

Straight-line distance:

• Pro: we just added coordinate support in the Rust, so we'd just have to add that to the World object, and it's easy to calculate.
• Con: We have to support spots not having coordinates--do distances to those spots compare low or high? (Maybe it doesn't matter.)
• Con: This requires a consistent coordinate system across areas and regions, such that they don't overlap. AV2 realms using the same coordinate system would be an issue, for example, except that realms that overlap are like 3d layers with respect to connections between them, so A* should be fine to route around coordinates that don't connect.

Area distance:

• Pro: Fairly simple
• Con: Subject to the same warp biases.

[Zannick]

This is continuing to be a problem. The shortest route for the newest items added to AV2 is a fast travel to a save point, but that's only eligible if the route has visited the map tile with the save point previously. Since it hasn't, the searches are getting stuck despite tests indicating that the location actually is reachable. It doesn't help that the Map has coordinates that are close by.

This step being performed has spent 30 seconds wandering around and is in the Map looking to teleport in, but obviously cannot.

At 4513518ms (elapsed=4391005 est. left=122513, since visit=29919), visited=196
Now: Menu > Kiengir Map > Uhrum West after   Move... to Menu > Kiengir Map > Uhrum West
Still needs: "[(Apocalypse_Bomb, 1), (Escape, 1), (Power_Matrix, 1), (Big_Flask, 1)]"

As I was writing this, the greedy thread finally found a solution of 4546434ms, which was instantly overtaken by another solution of 4189904ms... and after 10s the best solution is 3950092ms.

Of course, this will be a problem even after finding a solution. Mutates and regular greedy searches will continue to be impacted, usually to the point where they give up or run very slowly because we put limits on them.

[Zannick]

I think we need a distance table that doesn't take warps into account, or at least one that doesn't take edges that require map tiles into account. (The former is probably better, since we can achieve the same issue without map tiles. On the other hand, we do use warps based on data to create many similar edges at once.)

Some ideas:

1. Build a separate table entirely and prefer that sometimes.
2. Build a table without warps/edges requiring map tiles and allow extra edges anywhere necessary, including calculating min_distances. (Assuming we only use at most one new edge per path, it remains pretty simple.)
3. Build tables based on state. (Will be very expensive! But cacheable, so we won't repeatedly try to warp in as above.)
4. Build layered tables (free edges, edges that need X items, etc) so we can generalize changes without needing to cache separate tables by state combos.
5. Reverse score metric into (coordinate distance, elapsed time).
6. Remove the distance estimate: change the score metric to (elapsed time, coordinate distance).
7. Change the distance estimate to some other heuristic: (elapsed time + heuristic, coordinate distance).

[Zannick]

I note that A* works best with a consistent heuristic, and option (6) is just Dijkstra's with a tiebreaker.

The actual issue is that our A isn't getting there within the limit (it is extremely easy to generate tons of states and then wind up in the Map) and so we have to look into better solutions like fringe A. Perhaps we can try A on a no-warp table, and follow that up with a warps-allowed search that may fail, or just do the A on the no-warp table if the warps-allowed search fails, or ensure we only do at most 1 of each kind of non-base warp.

[Zannick]

Rewording the title here, as what I'm really after is more of a guarantee that a greedy thread is able to reach a destination eventually. Fringe A* might be appropriate, if not some other approach. Potentially we can have a shortest paths table with only free movement, and use that as an upper bound.