How to Go Fast : (Ways to Model and Approach Speedrun Routing Algorithmically)

Speedrunning in general means to go fast in a video game. This simple concept has an immense impact on the ways players engage with games. The inherent aspect of optimization within this esports niche makes it a good application field of optimization methods. This work gives an overview of speedrunning as an esports discipline. Prior works on this subject are discussed and assessed and relevant nomenclature is introduced. Using this information, routing --- the procedure of planning a speedrun --- is picked up as a graph optimization problem. Nintendo's iconic game The Legend of Zelda: Ocarina of Time from 1998 is used as a working example to assess previous works and to explore more of this mainly uncharted field of research.To do so, the process of speedrun modeling is conducted as exhaustive as possible within the limits of a work like this. All relevant steps to obtain a faithful model are lined out. This procedure yields a partial game graph with 6764 nodes and approx. 321,022 edges --- some uncertainty included. Current pathfinding techniques are discussed and assessed regarding their applicability to the presented speedrun routing problem. The resulting graph model and algorithmic approaches present a good reference to identify the most promising points of improvement. Challenges, flaws and possible solutions to still standing problems are discussed and assumptions from prior works are assessed. Finally, further tracks of scholarly and community work in this area are suggested and possible extensions to the approach are lined out. It is shown that speedrun routing is not a trivial shortest path problem that can be solved with conventional methods. Furthermore, it is made clear that different games can have vastly differing routing circumstances. Assumptions of other works have been assessed using a working example and many interesting challenges and fields of further study and research in the field of speedrunning have been identified. Some probabilistic pathfinding methods and current works on AI agents for games pose interesting approaches which can be extended on by utilizing the findings of the presented work. Specialized modeling and optimization techniques have to be employed in order to have a positive effect on the speedrunning community.