PNNL

Abstract

In this paper, we propose two different algorithms; Span* and Growth, for dungeon generation that could be used in a game. Dungeon generation pertains to the creation of a two dimensional array representing a map of (x, y) coordinates. Each coordinate represents a tile on the map that can be either a floor tile or a wall tile. We can then create a room by grouping sets of floor tiles and create paths between the rooms by connecting each room with a line of floor tiles. Each of our proposed algorithms achieves a different kind of map style. We compared both algorithms in terms of average runtime and number of rooms. Our comparisons show that there are large trade-offs in terms of resulting style, runtime, as well as number of rooms generated between the two methods.