Generating and solving a maze using the depth-depth search method

In this article we will discuss the simplest in the implementation of the algorithm of generating the "ideal" maze and its application for finding the way.

We consider an algorithm based on backtracking, which allows you to create labyrinths without cycles, having a single path between two points. The algorithm is not the fastest, rather demanding of resources, compared with the Euler or Kruskal algorithm , but very simple to implement and allows you to create branched mazes with very long dead-end branches.
')
Interested - I ask under the cat.

In the Russian-language Internet there is very little information on the algorithms for generating labyrinths, which was the reason for writing this article.
Code samples in the C language, as well as the full source code of the project on GitHub, are available under the GNU GPLv3 license.
Links to English-speaking resources and the project can be found at the end of the article.

Algorithm Description

Note: it is assumed that initially each cell has walls on all four sides, which separate it from its neighboring cells.

1. Make the starting cell current and mark it as visited.
2. As long as there are unvisited cells.
1. If the current cell has unvisited "neighbors"
1. Push current cell to stack
2. Choose a random cell from the adjacent
3. Remove the wall between the current cell and the selected
4. Make the selected cell current and mark it as visited.
2. Otherwise, if the stack is not empty
1. Pull the cell out of the stack.
2. Make it current
3. Otherwise
1. Select a random unvisited cell, make it current and mark it as visited.

You probably noticed that when condition 3 is fulfilled, the finished maze is most likely to have an isolated area.
This condition is included in the algorithm as an exception, in practice, during normal operation of the algorithm and the correct input data, it never holds.

Implementation

As mentioned above, it is assumed that at the beginning of the algorithm, all cells are separated by walls.

Illustration of the algorithm

0 <- Initial matrix.

one. <- Choose the starting point of the starting point.

2.1. <- We move to a random unvisited neighbor while there are any.

2.2. <- There are no unvisited neighbors. Go back through the stack until there are no unvisited neighbors.

2.1. <- Unvisited neighbors are there. Move to a random unvisited neighbor.

2 <- No unvisited cells. Labyrinth generated.

Program code

Getting to the most interesting.

We begin to act in order and first generate the initial matrix with which the algorithm will work.
For convenience, let's agree that all cell types are specified in the listing.

int maze[height][width]; //  -   for(i = 0; i < height; i++){ for(j = 0; j < width; j++){ if((i % 2 != 0 && j % 2 != 0) && //    x  y, (i < height-1 && j < width-1)) //        maze[i][j] = CELL; //   else maze[i][j] = WALL; //    . } } 

Now that all the preparations have been made, we can proceed to the generation.

 typedef struct cell{ //,      unsigned int x; unsigned int y; } cell; typedef struct cellString{ cell* cells; unsigned int size; } cellString; 

Structures will greatly simplify life when exchanging information between functions.

The code snippet responsible for generating:

 cell startCell = {1, 1} cell currentCell = startCell; cell neighbourCell; do{ cellString Neighbours = getNeighbours(width, height, maze, startPoint, 2); if(Neighbours.size != 0){ //      randNum = randomRange(0, Neighbours.size-1); neighbourCell = cellStringNeighbours.cells[randNum]; //   push(d.startPoint); //     maze = removeWall(currentCell, neighbourCell, maze); //       currentCell = neighbourCell; //        maze = setMode(d.startPoint, d.maze, VISITED); free(cellStringNeighbours.cells); } else if(stackSize > 0){ //  ,     startPoint = pop(); } else{ //      ,     ,     cellString cellStringUnvisited = getUnvisitedCells(width, height, maze); randNum = randomRange(0, cellStringUnvisited.size-1); currentCell = cellStringUnvisited.cells[randNum]; free(cellStringUnvisited.cells); } while(unvisitedCount() > 0); 

As you can see, the implementation of the algorithm is simple and abstract from the theory, as they say, “even a child can handle it”.
In order not to overload the article, the code of the functions used in the above passage, under the spoiler.


So now we have a labyrinth generator that can build intricate mazes, the size of which is limited only by the size of the RAM.

As a result, we can get something like this:


Generation works, now it’s small: to find a way out in such a labyrinth.

There are a few more pathfinding algorithms than generation algorithms, and some of them, if readers are interested, I will cover in the following articles, but for now we will be content with what we have and “go through” the maze with the same algorithm.

And it is still easier to simplify, since we no longer need to remove the walls.

Backtracking path search algorithm:
1. Make the starting cell current and mark it as visited.
2. Until the exit is found
1. If the current cell has unvisited "neighbors"
1. Push current cell to stack
2. Choose a random cell from the adjacent
3. Make the selected cell current and mark it as visited.
2. Otherwise, if the stack is not empty
1. Pull the cell out of the stack.
2. Make it current
3. Otherwise there is no way out.

The exit point, like the starting point, can be any point of the maze that is not a wall.
Traditionally, the exit should be "pressed" to one of the walls, but in fact it can be anywhere.
All the same, in this case, the “entrance” and “exit” are just two points between which it is necessary to find a path.

The criterion for finding the "exit" is very simple: it is enough to compare the coordinates of the current point and the coordinates of the "output": if they are equal, the path between the starting and output points is found.

Let's see what happened:


That's all that is needed for the simplest implementation of a random maze generator.

For those who are interested, the full source code of the project on GitHub: Maze Generator and Solver (offscreen rendering)

Sources

1. Walter D. Pullen: Think Labyrinth.
2. Wikipedia: Maze generation algorithm.