Writing a BFS Shortest-Path (with Heuristics) Solver for ALttPR

This is the conclusion to my previous posts about Mudora and randomized A Link to the Past – Reverse Engineering A Link to the Past Randomizer and I Analyzed 28k+ Randomized ALttP ROMs So You Don’t Have To. Today I’ll be talking about writing a shortest-path solver for ALttPR in Mudora, similar to what you might find on the spoiler log for a game generated on alttpr.com. Where We Left Off In a previous post I talked about wanting to write a solver for A Link to the Past Randomizer. I had the idea to represent the game state as a 2-color graph with alternating colors where the first color is inventory states and the second is a list of locations. Consider a small, three-item contrived example: This is a bit simplified since we aren’t talking about different item placement rulesets or other types of randomization like entrance shuffle or keysanity which shuffles dungeon items, like keys. If we had this inventory-location graph, it would be super simple to just run BFS over the graph and…