"Topological Rules for Dungeon Generation"

Supervised by A.Simons

Abstract

A compact rule-based encoding of dungeon levels for computer adventure games is presented. The rules effect topological transformations on a graph representation of a dungeon, a system of rooms and connecting corridors, populated with challenges, puzzles and treasures. A major feature is the way in which the nonterminal nodes of the graph abstract over the rest of the dungeon level, such that the paired elements of a threat defending a treasure, and a key solving a puzzle may be introduced at single points, but subsequently become physically separated in the dungeon. Nodes in the graph may eventually be refined as single fixed places, or as whole substructures within the dungeon. The random application of transformation rules generates dungeons of different topological structure and with different levels of nested puzzles.