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.