The Legend of Zelda: The Time Travelling Salesman
The travelling salesman problem is a well-known problem in computer science. The salesman needs to visit a number of cities on a map and wants to do it as fast as possible. The problem is that the cities aren’t located nicely on the map, they can be anywhere and as the number of cities to visit increases, it becomes increasingly harder to figure out the fastest path through all the cities.
What does that have to do with Zelda?
Randomizers
Randomizers are ROM hacks that randomize parts of a video game in order to deliver a new experience everytime you play. A ROM — which stands for read-only memory — refers to the game’s code that would be loaded onto a video game cartridge. In the case of the Alttp: Randomizer, it randomizes where the various items can be found. For instance, instead of getting the lamp in the chest in your house at the beginning of your game, you might instead receive a bottle, the bow or even a single rupee. So in order to complete the game, you’ll have to follow a completely different route than you would’ve done in the regular version of the game.
The hack makes sure that the game can be completed by ensuring that no item is locked behind itself or another item it would unlock. For example, you won’t find the bow behind an entrance that requires the bow or the sword that would unlock another item if that item would unlock the sword… It gets complicated fast, but what’s important is that there is always a way to progress and complete the game.
So at any one point in the game you have a number of item locations available to you and finding a key item unlocks more possible item locations. The goal is to find all the key items required to complete the game and beat the final boss. Veteran players know to go for the locations that have the highest item density but, as you might have guessed, those locations change as new items are found and depend on where you are, what your current items are and a number of other factors.
Players are constantly trying to solve a constantly changing travelling salesman problem.
If you’re familiar with the game, watching speedrunners race through a seed (they both get the same randomized world) can be fascinating:
The Alttp: Randomizer is probably my favorite but there are plenty of randomizers for other games and finding one for a game you’ve played tons can be really fun. Some of my favorite are:
- FF1 Randomizer — a Final Fantasy 1 randomizer
- FF4: Free Enterprise — a Final Fantasy 4 (FF2 in North America) randomizer in which you start with the Enterprise (airship)
- Super Metroid and A Link to the Past crossover item randomizer — as weird as it may sound, items from both games are randomized between the games and switch between them as you try to complete both
