Blog posts

Maze generation

A typical part of roguelike games (and of roguelites, the category my game would probably find itself in, described on the same Wikipedia page) is their randomly generated dungeons. I did a quick search for maze generation algorithms and decided to use Randomized Prim’s algorithm as it did not appear too complicated.

This algorithm starts with a grid that has every cell filled. A random starting location is picked that is cleared. Then all neighbouring filled cells are added to a list. A random cell A is picked from the list and we check if it does not have at least two cleared neighbours yet. If this is indeed not the case, the cell is cleared and its filled neighbouring cells are added to the list. Cell A is removed from the list. A random cell is picked from the resulting list and we check if it does not have at least two cleared neighbours, and so on, until the list is empty.

This worked fine, except for the fact that my first implementation was better suited for grids in which walls are defined as closed edges of cells, taking up no space on the grid. Instead, in my game, a wall is itself a filled cell on the grid.

Walls are edges of cells
Walls are cells themselves

This problem and the solution were found on this Stack Overflow page. The solution is to move in steps of two cells when collecting a cell’s filled neighbours, leaving space for the walls. This gave a nice result.

Part of a maze generated by the randomized version of Prim’s algorithm

In the future I can perhaps add even more variation by adding or removing random pieces of wall to the outcome of the algorithm. The outcome of the algorithm described above is a maze where every open cell can be reached; an important requirement, when adding or removing walls, is of course for the maze to remain solvable. A pathfinding algorithm, which will at some stage be needed to help computer controlled characters find their way around the maze, could play a role here as well.