Difference between revisions of "What is a speedrun?"

Revision as of 00:09, 23 April 2014

Introduction

Whether people realize it or not, there is an ongoing debate about what it means to "speedrun" a game. This is most evident through comments on media articles detailing events or significant records, where a chorus of voices are willing to cry foul or otherwise about the runs at hand due to use of glitches or otherwise. Regardless of the state of speedrunning or how many categories exist for a given game, arguments for or against typically go in circles because it is a battle of subjective opionions versus subjective opinions. This article attempts to take an objective and scientifically-focused approach to describing what a speedrun is and to justify why runners play the way they do.

Optimization Problems

To borrow from wikipedia a bit:

"In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete variables is known as a combinatorial optimization problem. In a combinatorial optimization problem, we are looking for an object such as an integer, permutation or graph from a finite (or possibly countable infinite) set."

In other words, given a set of available tools, one attempts to construct the best solution. "Best" in this sense depends on the goal at hand. For example, consider a network of connected nodes called a graph. Given a starting and ending location, one can find an arbitrary path between the start and end. If the goal is to get from the start to the end in the fewest hops, then you optimize according to the length of the path. Thus this is called the "shortest path problem". See if you can find the shortest path in the example below.

Real problems are rarely so simple, however. Consider that instead of any given hop having the same impact, a weighting is assigned to each link. Given this new information, can you find the shortest path in the new example?

The image below shows the shortest path. Many readers may have selected a different path based on the new weighting information. In that case, they are now solving a different optimization problem; that is, they solved for the minimum weight path. This means that they changed the goal based on the information they were given, however the original goal to reach the end in the fewest hops remained the same. This is a trap that many people can fall into subconsciously because they want to make use of everything they have been provided. I will revisit this concept later on in the article.

Speedrunning and Optimization

Speedruns are all about optimization. Finding a faster way to accomplish goals, a better route, a more efficient method of movement: all are part of the approach in achieving a good speed run. But how does this play into my earlier description of optimization problems? Games are hardly so simple as to be described as a graph or network, right?

Not exactly. Let's peel back what it means to play a game for a bit. Video games, at their core, are just computer programs. When a human plays a game, they are feeding instructions to the program to act on. We perceive this as a continuous interaction where our inputs from a controller instantly affect game operation. In reality however, the program works in stepped increments and only checks whether you are providing inputs at the beginning of each step. This rate is typically about 60 Hz (or 50 Hz for older PAL systems) so that the program's video output rate can match the refresh rate of the display device. A single step is referred to as a "frame" in both the technical and speedrunning sense.

This means that during a single second of gameplay, you can provide 60 sets of input to the program and influence its processing. This means that whether you're holding every button or no buttons, the game is continuing to process 60 sets of input each second. This is where we can start to draw a connection between playing a game and a graph. Consider a special type of graph called a tree, where an initial node connects to many subsequent nodes that represent changes in state due to differences in input.

Let's set this up in an example. Let's say you're playing a game with only two buttons, A and B. In each frame, you can press nothing, press A, press B, or press A and B. This gives a total of 4 transition possibilities, so you could move into one of four different states in the next frame. From each of those states you can move into 4 other states, and so on. This turns into a very big space very quickly. In just a single second, 4^60 possible paths are created. To put that in perspective, it would take the fastest supercomputer in the world at least 700 billion years to search every path and find the best one. And that's only if it can be completed within a second; what about if it takes several minutes to reach the end? The growth rate is even faster as you add more buttons and directions.

Completing a speedrun is not quite that complex since playing games is not a blind process; we have an idea of where the end is and what we need to do to get there. This trims a huge portion of the search space; we know better than to keep walking into a wall, for example. While the search space has been reduced, it still is quite large, however. Factor in the limits of human reflexes and you have a search space that will probably never be truly conquered without tool assistance. At the core, this is what a speedrun is: an attempt to optimize the path through a game by completing it in the fewest frames possible. I will hold on to this definition and refer back to it a few times in the remaining sections.

Constraints

Something I have avoided bringing up in the prior sections is any mention of additional constraints on the given goal. Constraints always exist, but there is a distinct difference between implicit and explicit constraints. Implicit constraints are limitations imposed by the medium itself. My goal of reaching the top of a skyscraper as quickly as possible is limited by the fact that gravity prevents me from flying and I am hindered by my body's limited supply of stamina. These are examples of implicit constraints: limitations imposed upon your actions by the medium itself.

Explicit constraints are instead limitations imposed by the player to fulfill secondary goals. Secondary goals are exactly that: goals separate from the main goal that have some inherent worth in completing. For example, imagine that you're shopping for a new TV. The primary goal is to get a screen as big as possible. This is simple enough: choose the biggest screen. A secondary goal, however, is to not spend more than you have budgeted. In this situation you may have to pass on the biggest screen and instead settle on a smaller one that is within your budget. This is an explicit constraint because nothing is necessarily stopping you from buying the largest TV available (you can take out a loan if need be), but it makes sense to not spend everything you have to achieve the primary goal.

In the context of speedrunning, implicit constraints are imposed by the game environment. You can't start the game with full power-ups because that's just not how it's programmed. Falling in a pit will kill you. Those are the "rules" of the game, so to speak. Explicit constraints describe optional objectives, which are better translated into "categories" of speedruns. These include 100%, glitchless, low%, and any other applicable category for a game. Categories exist when the case without limitations (referred to in general as "any%") is uninteresting or effectively solved, or where there is significant incentive to achieve the secondary goal.

Glitches and You

One point of controversy that comes up again and again is the utilization of glitches in speedruns. Many viewers have an expectation that speedruns clear the game using only the tools intentionally given by the developers. This is an explicit constraint on the run brought on by an internal perception of the game. This by itself is not inherently wrong or incorrect, but it is based on an attachment to the game. Speedruns in the unconstrained case are separated from this in that the game itself is no longer regarded as a game, but is instead the medium. The "game" then becomes the optimization problem, while the medium is just a set of implicit constraints. In this sense, there is no such thing as a glitch, provided that nothing external to the medium impacts it.

In the case that explicit constraints prevent the use of glitches, there are still a few points to clarify. First of all, it is quite difficult to objectively classify what is and is not a glitch. A glitch or bug in the technical sense is when a program achieves an unexpected state as a result of programming errors. A glitch is fairly apparent when a calculator program fails to calculate 2 + 2 correctly, but is not as clear when mapped to a complex program such as a game. In some cases it may not be apparent what the original intention for a function was. A famous example is the original Street Fighter 2, in which consecutive hits were not meant to connect but in some specific cases could be chained together. This was not the original intention according to the developers, but it formed the basis for the "combo" systems seen in every fighting game since.

I will try to illustrate these points a little better through some examples. In the situations below I have set up a Rush Hour board. The overall goal of Rush Hour is to move the Red Car out of the board by moving the other vehicles. Horizontally-long vehicles can only move horizontally, while vertically-long vehicles can only move vertically. The Red Car can move in any direction so long as there is empty space. No two vehicles can occupy the same tile at the same time. Vehicles cannot pass through the perimeter wall, and only two tiles of the wall are open as the puzzle Exit. Can you solve this board? Turn it into an optimization problem: what's the fewest moves you can complete the board in?

This problem seems straightforward. There's only a small number of vehicles to move in order to complete the puzzle, and it can be done in relatively few turns. However, there is more than meets the eye. Consider that you find a hole beneath the two trucks in the top left. This hole is big enough to fit the Red Car, thus allowing it to exit the board. Using the hole accomplishes the optimization goal of removing the Red Car from the board in fewer turns than possible otherwise.

In the above case, it's obvious that the programmer made a mistake when setting up the board, believing that the player would never have any reason to move the two trucks. This "new Exit" is different from the intended exit, but going through it still achieves the end goal of leaving the board. But what differentiates a glitch and an oversight? Consider this new board in which the hole has been patched. Given all of the implicit constraints, there are some parts that are no clearly defined. For example, why can't you move the middle horizontal trucks out of the Exit and then have the Red Car follow?

In this case, there is nothing fundamentally wrong with the board. All of the implicit constraints are applied, and none are broken or circumvented. However, nothing in the implicit constraints forbids other vehicles from moving through the Exit. This would be a case of a programmer oversight, but there is no fault or problem in the code. This can still be labeled as a glitch, but in reality many of these oversights exist throughout normal play of games. Whether the players realize it or not is a different matter. This is what makes it difficult to declare "glitchless" as a blanket category when the distinction between a "glitch" and a "trick" is not immediately clear.

Category Abundance

Why are there so many categories, and why are they arbitrary?

Conclusion & Final Words

Hopefully this made sense.