Shortest Walk in a Dungeon Graph
DOI:
https://doi.org/10.32473/flairs.37.1.135299Palabras clave:
Procedural Generation, Shortest Walk, Dungeon Graph, Heuristic, NP-CompleteResumen
With games like No Man’s Sky and Diablo IV, procedural generation of content in games is ever-increasing. Heuristics are needed to assess the goodness of generated content. Using Nintendo’s The Legend of Zelda as inspiration, we formalize the idea of a dungeon graph: a graph consisting of ‘locked’ edges in which ‘keys’ are acquired from specific nodes. We then introduce the Shortest Dungeon Walk Problem as well as a solution to this problem in the context of a dungeon graph and reduce Traveling Salesperson Problem in polynomial time to the Shortest Dungeon Walk Problem and conclude that Shortest Dungeon Walk Problem is NPComplete. We then assess practical performance of the shortest walk algorithm using the first eight dungeons
in the Legend of Zelda.
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
Derechos de autor 2024 Christopher Durham, Chris Alvin
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial 4.0.