A simple mathematical optimisation in Tool-Assisted Speedrunning

9 minute read

A few years ago, I was an active member of an online community called Tool-Assisted Speedrunning. During this time, there were many interesting mathematical topics that members discussed. I want to talk a bit about the theoretical optimisations that can be done within Tool-Assisted Speedrunning. Or at least one simple one that I proposed, which uses surprisingly little mathematics.

What is a TAS?

The short of it is that a Tool-Assisted Speedrun (TAS) is a playthrough of a video game, following a particular collection of rules that make up a category. For example, “any%” is typically the category for finishing a game, completing any number of percentage requirements.

The difference between a traditional speedrun, which is a playthrough performed by a human in real-time, and a TAS, is that the latter is performed by a machine or tool that, typically, plays back a string of inputs for each frame of the “movie” (this is the term we use to identify a full playback of inputs). This means a functional tool or emulator will feed the correct inputs every time without fail, successfully recreating the same playthrough every time. Note that some TASes can be performed on the original hardware, such as on a physical console.

The community I was once actively a part of was the Super Mario 64 TASing community. Super Mario 64 (SM64) is well known and popular within both Speedrunning and TASing communities since it has a nice balance of fun character movement, gratification upon improving a Speedrun or TAS, and by simply being a fun classic.

For me, the movement mechanics of the game make it fun to TAS. Furthermore, this same fact makes it incredibly satisfying to improve a previous world record (WR) time.

SM64 movement

The game has a collection of movement options ranging from running, long-jumping, diving, jump-diving, and slide-kicking. However, some other movement options have benefits, reducing TAS times significantly in the correct situation.

If you are holding the Jump button (A) and then press the Punch/Attack button (B), Mario performs a jump kick. I am somewhat rusty on the details, but it primarily functions much like an average jump then kick (A $\rightarrow$ B).

The critical difference in terms of movement optimisation is the press vs pre-holding the A button when executing the action.

In the game, if you are moving at speed $s$, then perform a “speed kick”, executed by pressing B while the A button is already depressed, you will perform the kick action while maintaining and conserving speed. There are a few other facts I’ve glossed over, such as a speed kick only works if the analogue stick magnitude it less than a specific value, but other than this, it isn’t essential to this explanation.

The stick magnitude is the important factor. While moving, performing a speed kick will fail if the analogue stick is above a specific magnitude (or if Mario has too low a speed, but this case will be ignored for simplicity).

The game operates so that if you hold the analogue stick in a direction, Mario will move and accelerate until hitting a maximum cap for whatever state of movement he is in at the time. If he exceeds the maximum speed cap, his speed will either decelerate or reset to the maximum if grounded, depending on his state. For example, being grounded while in a state transition typically decelerates Mario, while entering a running state will reset to the maximum cap.

A speed kick makes Mario airborne, which not only conserves speed but will continue to increase in speed indefinitely, assuming a suitable magnitude is applied to the analogue stick input. However, in his landing state, Mario decelerates in speed. Thus an infinite string of speed kick execution will eventually slow down to base speed.

Performing a speed kick has three parts: being grounded, kick execution, and kicking. While grounded, Mario will slide as he lands from a kick. In this state, holding a maximum magnitude is typically optimal, providing continuous motion and minimal deceleration. The angle doesn’t matter in this state as movement will always be in the facing direction.

Notably, having too wide an analogue-stick angle and Mario will decrease in speed due to drag, so moving perfectly into Mario’s facing angle is most optimal for minimal loss of speed.

This has been a bit to process, but it is essential background information for my first application for theoretical movement optimisation: the speed kick optimiser.

The speed kick optimiser

As mentioned, having too large a stick angle can impact the exit-speed of the movement. However, sometimes it is required that a leftward or rightward speed kick be performed. I realised that if the angle itself wasn’t too important, allowing for some degree of freedom, can we find a more optimal angle that maximises our magnitude? I should mention that this is all while keeping the analogue stick magnitude less than that maximum number I previously mentioned, required to perform a speed kick. Thus, this optimisation is likely only beneficial for the one-frame window of executing a speed kick while requiring a degree of sidewards movement - this is what makes this very much theoretical. It is very likely not a movement constraint needed to achieve an optimal movement.

My approach to the problem was to assume I only had $\Delta\theta$ degrees of freedom on either side of my desired angle $\theta$. This then became a typical trigonometry problem involving finding a pair of new triangles.

Figure 1 shows the basic diagram of the mathematics considered in this problem. There is an original direction with angle $\theta$, and another new direction of interest, where $\phi=\theta+\delta$, which is the upper limit in our degrees of freedom.

If the original line, call it $L$, is defined by a line intersecting $\left(0,0\right)$ and $\left(x,y\right)$, then we can label the new line of interest $L’$ which intersects $\left(0,0\right)$ and $\left(x’,y’\right)$.

Therefore we can now define the lines (or vectors) $L(x)=r\cos(\theta)$ and $L(y)=r\sin(\theta)$, and $L’(x’)=r\cos(\phi)$ and $L’(y’)=r\sin(\phi)$.

To recap the problem, I am interested in finding some optimal solution: a new line, $L’$ that is within $\delta$ degrees of $L$. This new line will have angle $\phi$. An optimal, or more correctly, suitable solution will minimise $\delta$ and maximises $r$. Note that the magnitude, in theory, may vary, but $r$ is the magnitude less than or equal to the upper magnitude limit. So, the original angle may have a smaller magnitude, and an optimal solution may be a degree on either side, but with a larger magnitude. This happens because, if you will recall, $x,y,x’,y’\in\mathbb{Z}$.

An optimisation algorithm which looks for suitable solutions will therefore look for all lines such that $x’ \leq r\cos(\theta+\delta)\leq x$ and $y \leq r\sin(\theta+\delta) \leq y’$.

In my application, I use the following code to list all the angles within the region:

const double r = 48; // max speed-kick magnitude
var maxX = (int) Math.Ceiling(r * Math.Cos(maxAngle) - 6);
var minX = (int) Math.Ceiling(r * Math.Cos(minAngle) + 6);
var maxY = (int) Math.Ceiling(r * Math.Sin(maxAngle) + 6);
var minY = (int) Math.Ceiling(r * Math.Sin(minAngle) - 6);

// find max Mag
var controllerList = new List<Controller>();

// the minimum and maximum angle bounds
var maxTangent = Math.Atan2(maxY, maxX);
var minTangent = Math.Atan2(minY, minX);

// list all angles in range
for (var x = 0; x <= minX; x++)
{
  for (var y = 0; y <= maxY; y++)
  {
    var theta = Math.Atan2(y, x);

    // if (x, y) is in angle bounds
    if (theta >= minTangent && theta <= maxTangent)
    {
      var c = new Controller(x, y);
      if (c.stickMag <= r)
      {
        controllerList.Add(c);
      }
    }
  }
}

Lines 3 to 7 declare $x,x’$ and $y’,y$, respectively. Note that I add or subtract 6. I do this because the N64 hardware does some stuff behind the scenes, and the inputs on the controller differ from the processed inputs used by games.

In my application, I do a slightly different approach in that I look for angles within the ranges of $\tan^{-1}\left(\dfrac{y’}{x’}\right) \leq \theta+\delta \leq \tan^{-1}\left(\dfrac{y}{x}\right)$. This is equivalent as it uses the original vector angle and angle of the maximum offset, which doesn’t require the magnitude $r$ within the range conditions. Plus, it constrains the range into one condition rather than two independent conditions, as I provided above.

This segment of code grabs all the coordinates within the range on both sides of the original vector, whereas my mathematics used only one direction for simplicity.

This application was intended to show the theoretical possibilities of how we artisans of the craft should consider these angles and magnitudes for such exact circumstances. Nowadays, TASers have other tools to automatically adjust inputs that maximise in the facing direction, which means that even if the camera spins around, the analogue stick is autonomously updated to maintain a forward movement roughly along the same vector (with some degree of error is the camera moves, due to having integer coordinates). At the time, it was an exciting look into how exactly “optimal” could be defined. Do you maximise the magnitude? Can you move the analogue stick slightly to get a minor increase in magnitude?

Take the example of this: You are in a situation where you need a semi-precise angle, and you find that $\left(45, 25\right)$ work. The magnitude is latex 51.478…, which is smaller than the maximum exclusive magnitude of 54, as seen in the code, plus 6 to get the raw analogue input. Using the application gives a few suitable results:

$x$ $y$ $\theta$ $\delta$ Magnitude $r$ (processed)
50 25 23.35556 -2.618829 47.92703
48 29 28.70595 2.731559 47.88528
49 27 26.02959 0.05519823 47.85394
50 24 22.24902 -3.72537 47.53946
49 26 24.9439 -1.030489 47.42362
48 28 27.64598 1.671581 47.41308

It is evident here that there are my results that satisfy the optimisation issue. Our magnitude was 51.47 8… (45.478 after processing), which is smaller than all the given values found by the application, and all within a minor distance of the processed angle (this data worked within two degrees freedom of the raw inputs, which is why there is a value of -3.7).

Comparison of original and optimised inputs, highlighting how indistinguishable to the eye the change is through optimisation.

Such a minor difference over long distances could potentially save one or more input frames and only marginally alter the angle of the analogue input.

This concept of optimisation by simple mathematics shows just how far some minor attention to detail can lead. This application was made in early 2019, around about the time I entered university to do a BA in Communication — a humanities degree. I didn’t have anywhere near the mathematics skills or experience in software engineering that I have attained through the years forthcoming. Such a simple concept is evident as something that can be effective in optimisation processes with minimal mathematics.