Shortest Walk in a Dungeon Graph

摘要

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.