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.

1. $({\text{cur}}_x,{\text{cur}}_y)\leftarrow \left(\lfloor w/2\rfloor ,\lfloor h/2\rfloor \right)$.
2. while maze not full enough do
   1. Find a new spot
      • repeat
        1. if $\text{itterations of repeat-loop}\ge 4$ then
           Select a new starting point
           1. if $P=\varnothing$ then
              • DONE
           2. else
              • $({\text{cur}}_x,{\text{cur}}_y)\leftarrow$ random element of $P$.
                
        2. $({\text{sugest}}_x,{\text{sugest}}_y)\leftarrow$ Random neighbour of $({\text{cur}}_x,{\text{cur}}_y)$
        3. ${\text{neighbours}}_{direct}\leftarrow$ number of direct (up, down, left, right) neighbours that are in the dungeon.
        4. ${\text{neighbours}}_{diagonal}\leftarrow$ 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$
   2. add the spot to the grid
      $\text{grid}[{\text{sugest}}_x,{\text{sugest}}_y]\leftarrow 1$.
   3. add the spot to the list of starting points
      $P\leftarrow P\cup ({\text{sugest}}_x,{\text{sugest}}_y)$.
   4. Continue from this point
      $(\text{cur}\_x,\text{cur}\_y)\leftarrow (\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})$.