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 find the true shortest path, at least in terms of fewest checked locations. True shortest-path in terms of playtime is actually quite complicated – we’d have to model the skill of the individual and the travel time between locations (which might change depending on your inventory state). It’s totally possible that the player is able to perform glitches or sequence breaks outside the official rules. There are myriad such tricks, making it incredibly difficult to create the correct abstraction. So, we’ll settle on fewest locations checked as our definition of shortest path.
However, when I went about building this, I ran into a complexity problem, so let’s walk through it.
The Problem
I really should have foreseen the issue – I neglected to analyze the complexity of my graph generation algorithm. We know the solution search using BFS is efficient at O(|V| + |E|), which is really all I was thinking about when detailing the item-location graph above. But, I failed to consider just how many inventory states are relevant to an ALttPR playthrough. It’s not just items – we have to consider keys as well!
So, let’s do a little math, just on the items you might collect in your inventory. It’s not even important to consider keys at this point, the problem becomes apparent even without it. Luckily, we can discard consumables like bombs and arrows.
27 binary items (either you have it or you don't, like Hookshot, Mirror, Hammer, Moon Pearl, etc.)
5 progressive items (Sword, Bow, Glove, Shield, Mail) -- we must consider every level + the default (usually None, but Green in the case of mail)
Then our key-less inventory state space is given by:
(2 ^ 27) x 5 swords x 3 mails x 3 gloves x 3 bows x 4 shields
Which is a whopping 72 billion states. And remember, that’s not including keys or dungeon rewards like Crystals or Pendants – all of those matter, too! The crux of the issue becomes: every item we need to consider at least doubles the inventory state space.
To make matters worse, in my original graph each inventory state node has an edge between a unique copy of every location node, so we’d effectively multiply 72 billion (or more) by around 278 locations. Admittedly we could trim that down to only creating a new location node if the location is reachable and has not already been collected, but I consider that a micro-optimization and the point still stands that the inventory state space is too large from the start.
The Solution
For the solution we’re going to continue using a modified BFS algorithm, but instead of considering all possible paths separately, we’ll compress them into a smaller inventory state space. We’ll do that by setting our next inventory state to include all reachable items. So, we’ll start with an EMPTY inventory state, then the frontier will be all reachable locations from that inventory state. We’ll disregard anything that isn’t a progression item, and collect everything else that is. With that new state, we can consider the next frontier, and so on.
The nice thing about this is that each frontier is a fixed size, at most 278 locations. And since the inventory is monotonically increasing in size after each frontier (as long as the game is able to be beaten), we know we must collect at least one item at each step. That gives us worst case 2782 or 77,284 iterations over locations, roughly 9 orders of magnitude smaller than the original naive approach. Notice as well that since our runtime is not determined by the number of items in the inventory, we can consider every possible item at no cost, including keys and dungeon rewards!
Once we have an inventory state that satisfies all goal state rules, we can stop, since we know the shortest-path inventory state must be a subset of the current inventory state, although we’re not able to determine it yet.
The Tradeoffs
There is a downside – we don’t know the true shortest path with this approach. We can apply a heuristic by culling out any inventory items that aren’t actually required. The BFS inventory compression algorithm first finds the maximum inventory at the moment we reach the goal state. We then iterate every item, tentatively remove it, and check if removing this item makes the game uncompletable. If it does, we re-add that item to our inventory. If not, we carry on without that item. This gives a small, but not necessarily minimal, inventory state for which the game is still completable.
I think this is fine. If you look at https://github.com/sporchia/alttp_vt_randomizer this is a similar methodology they use to generate a playthrough. Like I mentioned before, this is an incomplete abstraction anyway since it doesn’t account for how fast players actually play the game. It might also send you to really distant locations or avoid an item that can make you go faster (perhaps literally faster, like Pegasus Boots, which aren’t alwasy required). It also skips anything that isn’t strictly necessary, like sword upgrades or health. These upgrades offer real time savings, but may not be required by the logical ruleset the randomizer employs.
Long story short, if you can beat the game following only locations in one of these playthroughs – kudos to you. You’re better than I am at Zelda.
That’s all for now. Thanks for reading!