on to the notion of procedural levels and already recognize itsvalue. Rogue(Troy and Wichman, 1980), The Elder Scrolls II: Daggerfall(Bethesda Softworks, 1996)and DiabloCopyright (c) 2013 IEEE. Personal use is permitted. For any other purposes, permission must be obtained from the IEEE by emailing pubs-permissions@ieee.org.This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI10.1109/TCIAIG.2013.2290371, IEEE Transactions on Computational Intelligence and AI in GamesIEEE TRANSACTIONS ON COMPUTATIONAL INTELLIGENCE AND AI IN GAMES3(Blizzard Entertainment, 1998)are some of the better known early examples of this relationship between PCGand dungeons. However, that original momentum is not quite apparent in more complex current adventure gamesand RPGs, which are still very successful genres. We reckon that this backlog can be largely overcome by theapplication of many current state-of-the-art research results surveyed here.This survey aims at providing an overview of dungeon-generation methods, with a special focus on their mainscientific challenge: how these methods can be controlled. The remainder of the paper is organized as follows;Section II gives a more detailed introduction to procedural dungeon generation methods and how they can becontrolled. Sections III through VI elaborate on specific methods that are relevant for procedural dungeon generation,classified into Cellular Automata (III), Generative Grammars (IV), Genetic Algorithms (V), and Constraint-Based(VI). Section VII analyzes other related work which, although not directly related to dungeons, could improvedungeon generation. Section VIII contains an overview and discussion of the surveyed methods. Finally, Section IXprovides concluding remarks.II. CONTROLLING PROCEDURAL DUNGEON GENERATIONIn most adventure games and RPGs, dungeons basically consist of several rooms connected by hallways. Whilethe term dungeon originally refers to a labyrinth of prison cells, in games it may also refer to caves, caverns, or(abandoned) human-made structures. Beyond geometry and topology, dungeons include non-player-characters (e.g.monsters to slay, princesses to save), decorations (typically fantasy-based) and objects (e.g.treasures to loot).Typically, dungeon generation refers to the generation of the topology, geometry and gameplay-related objects ofthis type of levels. While generation of non-player-characters, decorations (and even ambient effects, like lightningand music) are themselves topics of PCG research, they fall outside the scope of this survey.A typical dungeon generation method consists of three elements:1)A representational model: an abstract, simplified representation of a dungeon, providing a simple overview ofthe final dungeon structure.2) A method for constructing that representational model.3) A method for creating the actual geometry of a dungeon from its representational model.Most surveyed research describes the method of constructing the representational model, but does not providequite as much detail in their method for mapping the model to the actual geometry of the dungeon. Unfortunately,this step is often neglected by researchers in their publications. However, it is understandable, since this is typicallya less sophisticated step than the generation of abstract representational models. Therefore this survey mostly focuseson the representational model and its generation.A very important element in any procedural method is thecontrolit provides over the output and its properties.We refer to control as the set of options that a designer (or programmer) has in order to purposefully steer the levelgeneration process, as