An algorithm for generating a dungeon

### Basic idea

The basic idea of the generator is to start at the center and iteratively add a square adjacent to the current square. If the algorithm gets stuck it restarts from a random other square that has been added to the dungeon. This algorithm is essentially Prim’s Randomized maze algorithm.

- $(cur_{x},cur_{y})←(⌊w/2⌋,⌊h/2⌋)$.
**while**maze not full enough**do***Find a new spot***repeat****if**$itterations of repeat-loop≥4$**then***Select a new starting point***if**$P=∅$**then****DONE**

**else**- $(cur_{x},cur_{y})←$ random element of $P$.

- $(cur_{x},cur_{y})←$ random element of $P$.

- $(sugest_{x},sugest_{y})←$ Random neighbour of $(cur_{x},cur_{y})$
- $neighbours_{direct}←$ number of direct (up, down, left, right) neighbours that are in the dungeon.
- $neighbours_{diagonal}←$ number of diagonal neighbours that are in the dungeon.

**until**$grid[sugest_{x},sugest_{y}]=0$ and $neighbours_{diagonal}≤1$ and $neighbours_{direct}≤2$

*add the spot to the grid*

$grid[sugest_{x},sugest_{y}]←1$.*add the spot to the list of starting points*

$P←P∪(sugest_{x},sugest_{y})$.*Continue from this point*

$(cur_x,cur_y)←(sugest_x,sugest_y)$.

### Implementation

My implementation of this algorithm in C++ is pretty mush a direct translation of the algorithm above. See my CppMaze repo on BitBucket.

#### BingoSet

To select a random neigbour I use a BingoSet witch is a collection that has a `pop`

function that returns a random element. It’s a kind of stack without an order. It works by storing the elements in a dynamic array (the `ArrayList`

kind). When an element is requested an element at a random index is returned and it is replaced with the last element of the array. This ensures amortized constant time for working with `BingoSet`

.

#### Modifiers

To add rooms, walls and items, I use a an abstract `MazeModifier`

class that is a friend of the `Maze`

class. Implementations of this class get notified before and after maze generation. When notified these classes set cells on the grid as occupied and such.

### Time-complexity

It is always interesting to analyze the time-complexity of an algorithm. the amount of work that we expect is $O(width⋅height)$ since that is the size of what we want to create. if we look at the algorithm, we see that each cell is analyzed at most twice to find a next spot. Analyzing takes constant time due to the upper bound on the repeat loop. Thus, we find z time-complexity of $O(width⋅height)$.