Shortest Walk in a Dungeon Graph
DOI :
https://doi.org/10.32473/flairs.37.1.135299Mots-clés :
Procedural Generation, Shortest Walk, Dungeon Graph, Heuristic, NP-CompleteRésumé
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.
Téléchargements
Publié-e
Comment citer
Numéro
Rubrique
Licence
(c) Tous droits réservés Christopher Durham, Chris Alvin 2024
Cette œuvre est sous licence Creative Commons Attribution - Pas d'Utilisation Commerciale 4.0 International.