How to calculate a perfect Super Mario speedrun?

Question

I've dedicated my time to Super Mario lately, so eventually I ended up watching some speedruns.

I thought to myself, how could one calculate the perfect set of minimal in-game movement?

I considered comparing the time needed to pass to a certain point, for example if there are two paths to take. If I wanted to write a program to measure and calculate those values for me, how would I proceed?

Answer 1

This is a shortest path problem, albeit of a strange sort.

Although usually we use pathfinding algorithms to find routes through space, where each node in the search space corresponds to a physical location, they actually work just fine on more general graphs too.

In this case, each node in the search space is one snapshot of state the game could be in on a particular frame:

• The time / number of frames elapsed since the level started
• The position and velocity of Mario in the game world
• Whether Mario is big or small (or has the fire flower, or...)
• The state of each dynamic tile in the level (broken bricks, revealed note blocks...)
• The position and velocity or AI state of each item / enemy currently being simulated (goombas, koopas, mushrooms, piranha plants, thwomps, bullet bills, projectiles)
• The time remaining on any special effects, like star power or P-switches

You start with just one node: the stat of the game on the first frame after the level has loaded. Mario and all items are at their initial spawn points.

From a given node, you can compute neighbouring nodes by evaluating what game state occurs on the next frame for each possible combination of inputs that might occur in this frame:

• Player presses nothing
• Player presses right
• Player presses left
• Player presses jump
• Player presses down
• Player presses both right & jump
• Player presses both left & jump
• ...

Now we have a start node and a way to compute neighbouring nodes, so we can start exploring the space of all possible play trajectories using graph search algorithms.

The downside is, this state space is HUGE. With just the options below, we have a branching factor of 7, more if there are additional inputs we need to include like pressing the B button for the fire flower. So the total number of states to search is (in the worst case) \$7^\text{frames}\$, which explodes exponentially.

We can rein this in if we can find a good heuristic - a way to evaluate which nodes are the best candidates for the outcome we want, closest to our goal. If our goal is to reach an x coordinate corresponding to the end of the level, then a decent heuristic is to measure Mario's x distance from that point, and divide by the maximum distance Mario can travel in one frame. That gives us our most optimistic estimate for how many frames away from our goal we are, and we can prioritize searching from nodes that are closer to that goal.

With this heuristic in hand, we can use the A* algorithm to search through the game state space to find the most optimal sequence of inputs to reach the goal in as few frames as possible.

Granted, this will still be computationally intensive. I haven't run the numbers to confirm how tractable this is. You may find you can only handle simple Mario levels in a reasonable amount of computing time, depending on how efficiently you can construct neighbouring game states and detect when a game state has already been visited by a different input sequence. But this at least gives you a framework with which you can attack the problem.