Brian Johnston - Optimizing Speedrunning Routes using the Shortest Path Problem

Optimizing Speedrunning Routes using the Shortest Path Problem

Brian Johnston / bjohnston2@bellamine.edu / Faculty Advisor: William Fenton

Completing a task as quickly as possible can be modeled by the shortest path problem. When attempting to complete a game as fast as possible, known as speedrunning, applying the shortest path problem will come up with an optimal solution. Based on criteria set out before the algorithm begins, we will create a route and estimation of time for a given speedrun based on a graph of a given game. Using multiple criteria as the weights of each edge can give multiple optimal routes for any given graph, depending on what kind of player is attempting to speedrun the game in question, varying the degrees of skill and how much random chance actions are desired. The algorithm is also built to handle changes to the graph, whether weights are changed or new edges and nodes are created or are destroyed. Overall, the algorithm will produce a route and estimated time of completion that will give a player a route to follow for the graph provided.