Toward a network model for Metroidvania Speed Run Routing -- Part 1

I've seen many posts and comments in various corners of the web asking

"Isn't speed run routing a kind of travelling salesman problem?"

or

"Isn't speed run routing a shortest path problem?"

Or any variant of this question. I also asked this question after taking a network flows course which used the classic network flows text by Ahuja, Magnanti, and Orlin. In that course, shortest path algorithms and max flow algorithms were discussed. I think the text explains the concepts well (after all I felt like I had some understanding after reading some of the chapters), but what especially stuck out to me were the applications. Chapter 19 is entirely dedicated to ways in which the previously described problems and algorithms can be used to frame and solve real-world problems as network problems. Some of them, taken at face value, sound like they would be able to help in routing a speed run.

• Shortest path problems seem helpful if you know you need to get from one point to another provided you have an appropriate graph model to describe the geography of the game.
• Knapsack problems see useful for finding the most optimal collection of times in order to pass a portion of the game (I have in mind the number of missile expansions collected before facing a certain Super Metroid boss).

I still don't know how these pieces might fit together to actually find an optimal route, but that's what I aim to write about here. The general question seems to be,

"how might speed running routing be formulated as a network problem or combination of network problems?"

To answer this, I'll try to provide a problem formulation and an algorithm to solve the problem of finding the optimal route for a Super Metroid speed run (I'll defer talking about which category of speed run I want to consider until more details of the network model become apparent to me). Almost certainly, this will take me a good bit of time to think about, but I want to keep a log of my thoughts using these posts. Moreover, if you know that this kind of thing has already been solved, I'd love see what you've developed or discovered.

Goals

I enjoy consuming speed running content. I especially like to hear the details of how certain strategies came to be. By trying to formulate an automated process to route runs, I think it may lead to a good idea for a tool or app to help routers.

Why focus on Metroidvania?

Besides the fact that I find them very interesting and fun to play, I think they have certain properties which will make formulating the problem easier.

To define a network model useful for solving a real-world problem, one needs to define what the nodes and edges of the network represent.

Many Metroidvanias feature discrete rooms with a finite number of "doors" between them. This seems like a good place to start as it reduces the cardinality of paths one needs to consider (one might have a hard time quantifying how many paths between point A and point B there are in an open-world game like Skyrim). This finiteness also limits the number of ways in which nodes and edges can be associated with discrete game locations or objects.

Is it possible to prove the current WR route is optimal?

Many network problems, such as the shortest path problem, can be formulated as linear programs. This is a really nice class of problems because it is known when they have unique optimal solutions and when they do not. My gut feeling is there is no way that there is a formulation of speed run routing for which it is easy to know when an optimal solution exists and when it does not (regardless of whether there is an algorithm to find it if it exists). But it's still too early to tell. Wouldn't it be a happy surprise to find that the current world record route is also the one found by the algorithm?

Caveats

The algorithm I hope to find probably won't help a runner find new exploits or skips. Out of bounds paths can be considered in this algorithm if they are known already, but the algorithm won't search for new ways to get around the world.

A awesome category of speed run are randomizers. I don't feel confident the model will be directly helpful for routing a randomize Metroidvania.

An overly simplistic start

For the purpose of exploring different ways of formulating the problem, consider the overly simplistic Metroidvania, Super Simpl Land.

• The game consists of 7 rooms labelled A to G.
• The player can travel between rooms connected with an arrow.
• The objective is to beat the final boss!
• You must collect the key in room A to pass the barrier between rooms F and G.
• There are items in room C and D.
• While you don't need items to defeat the boss, it's easier and quicker to do the fight using items.

This setup represents my idea of a minimum viable Metroidvania (though I don't think this game would be much fun to play). It includes, collectables, a barrier which requires a particular collectable (the key) to pass, and multiple paths between certain rooms.

Super Simpl land is also interesting (slightly more interesting than trivial) from the routing point of view because different strategies can be compared. For instance, if it is much faster to beat the boss with both items obtained then it is worth the extra time to go get them. An algorithm to route this game would take this into account.

A network model for Super Simpl Land

My current goal is to form a network model which is helpful for routing this silly game. To that end, the first thing that occurs to me is to let the nodes represent partial paths in the game, e.g.

B --> A --> B --> E

is a partial path the player may take on their way to the boss.
The edges represent different to represent different ways to extend a current path. For example, the partial path above could become

B --> A --> B --> E --> D

or

B --> A --> B --> E --> F

The 3 nodes and two edges would look like

So the task is set. Is this even a useful model at all? I'm not sure yet, but this is what I'll work on until the next post.