A simple maze creation algorithm ( C99 and raylib )

There are a number of different ways you can create a maze, often each algorithm will produce a maze with specific properties. The main features of the algorithm I’m going to describe aside from the fact its simple, is that the maze is both open (any point can be reached from any other) and that there are no loops.

Each maze cell has a common data structure (which is defined as its own type). The information for what walls a cell has are encoded using binary into a single integer, arbitrarily the North East South and West walls are represented by the numbers 1,2,4 and 8 respectively. While in theory you only need two walls per cell (say North and West). I decided to give each cell 4 walls. By having 16 textures 1 for each possible combination of walls by numbering the textures apropratly we can find the correct texture. For example if we have a cell with a north(1) and south(5) wall I know that texture 5, is the one to draw.

Again for convenience I’d given each cell a flag to say they the cell is on the visited list (more later on this). While not of any real utility there is also a record of the number of walls the cell has, this is updated when the walls are updated and is purely used so I could see a highlight of junctions leading to dead end sections of the maze.

I mentioned that a list is being (ab)used to keep track of our current path, that way we can wind back to the last junction when we hit a dead end. However when we add a new node to the visited list (when entering a new unvisited cell) we have to modify its previous node pointer.

Normally when you add a new node to a linked list, typically the new node becomes the last or tail node of the list. However we need to be sure that the new path links back to where it started on the original path. This is easy to achieve by always setting a new entry on the visited list with a pointer to the last node visited (rather than a cell potentially far away at the end of the list. This obviously breaks the integrity of the lists data structure, but will allow us to back track even through a number of different junctions.

In order to keep track of where the algorithm is in the maze, its a simple matter to keep a separate pointer into the list structure. You can run this pointer back down the visited lists prev pointers, even if you’re on an isolated branch it will rejoin part way along its parent path.

The algorithm wanders around randomly, in order to do this the unvisited cells neighbouring the current cell are totalled. It will select a random unvisited cell (biased slightly to continue in the direction it was previously going). Only backing up when it can’t find an unvisited cell.

This means as it backtracks from a dead end it will often see a single unvisited cell when it rejoins the path it branched from, this way it wanders around seeking out unvisited cells.

By the time that the algorithm backtracks to the start cell, it will have visited every cell in the maze. Once complete you can find your way from any square in the maze to the start, just by following the visited list back to the start.

You can grab the code here

Leave a Reply

Your email address will not be published.