### 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) \gets \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 = \emptyset$ then
• DONE
2. else
• $(\text{cur}_x,\text{cur}_y)\gets$ random element of $P$.
2. $(\text{sugest}_x,\text{sugest}_y) \gets$ Random neighbour of $(\text{cur}_x,\text{cur}_y)$
3. $\text{neighbours}_{direct} \gets$ number of direct (up, down, left, right) neighbours that are in the dungeon.
4. $\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$
2. add the spot to the grid
$\text{grid}[\text{sugest}_x,\text{sugest}_y] \gets 1$.
3. add the spot to the list of starting points
$P \gets P \cup (\text{sugest}_x,\text{sugest}_y)$.
4. 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})$.