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.

- (\text{cur}_x,\text{cur}_y) \gets \left(\lfloor w/2 \rfloor,\lfloor h/2 \rfloor\right).
**while**maze not full enough**do***Find a new spot***repeat****if**\text{itterations of repeat-loop} \ge 4**then***Select a new starting point***if**P = \emptyset**then****DONE**

**else**- (\text{cur}_x,\text{cur}_y)\gets random element of P.

- (\text{cur}_x,\text{cur}_y)\gets random element of P.

- (\text{sugest}_x,\text{sugest}_y) \gets Random neighbour of (\text{cur}_x,\text{cur}_y)
- \text{neighbours}_{direct} \gets number of direct (up, down, left, right) neighbours that are in the dungeon.
- \text{neighbours}_{diagonal} \gets number of diagonal neighbours that are in the dungeon.

**until**\text{grid}[\text{sugest}_x,\text{sugest}_y] = 0 and \text{neighbours}_{diagonal} \le 1 and \text{neighbours}_{direct} \le 2

*add the spot to the grid*

\text{grid}[\text{sugest}_x,\text{sugest}_y] \gets 1.*add the spot to the list of starting points*

P \gets P \cup (\text{sugest}_x,\text{sugest}_y).*Continue from this point*

(\text{cur}_x,\text{cur}_y) \gets (\text{sugest}_x,\text{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(\text{width} \cdot \text{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(\text{width} \cdot \text{height}).