search

Zannick / logic-graph

Tools for video game logic representation and analysis, particularly routing and beatability checks for speedruns and randomizers.
MIT License
3 stars 0 forks source link

Greedy search uses too much RAM #138

Closed Zannick closed 5 months ago

Zannick commented 7 months ago

first_spot_with_locations_after_actions is using a BFS to find a location to access, but there are so many accessible spots at this point that the list fills with a few million options and becomes quite slow.

It's probably better to switch to a heap that contains (ctx, used global actions, depth).

Zannick commented 7 months ago

This is making it difficult to see if the greedy search has gotten stuck. We should institute a maximum elapsed time as well.

Zannick commented 5 months ago

Duplicated by #146