Generation and solution of the maze using the method of searching in depth in the graph

image

This article will discuss the simplest algorithm for generating the “ideal” maze and its application for finding the path.

We will consider a backtracking-based algorithm that allows you to create labyrinths without cycles, having a single path between two points. The algorithm is not the fastest, rather demanding on resources, in comparison with the Euler or Kruskal algorithm , but it is very simple to implement and allows you to create branchy mazes with very long dead-end branches.

Interested - please, under cat.

There is very little information on the labyrinth generation algorithms on the Russian-language Internet, which was the reason for writing this article.
C code samples as well as the full source code for the GitHub project are available under the GNU GPLv3 license.
Links to English-language resources and the project you will find at the end of the article.

Algorithm description

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

1. Make the initial 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 the current cell onto the stack
    2. Select a random cell from the neighboring ones
    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 will most likely 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 initial data, it is never satisfied.

Implementation

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

Algorithm Operation Illustration

 0.     image  <- The initial matrix.

 1.     image  <- Choose the starting point of the starting point.

 2.1. image  <- We move to a random unvisited neighbor, while there are those.

 2.2. image  <- Not visited neighbors. We go back along the stack until there are no uninvited neighbors.

 2.1. image  <- There are unvisited neighbors. We move to a random unvisited neighbor.

 2.     image  <- No cells not visited. Labyrinth generated.

Program code

Getting to the fun part.

Let's start in order and first generate the initial matrix with which the algorithm will work.
For convenience, we agree that all types of cells are specified in the enumeration.

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 are done, you 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 cope."
In order not to overload the article, the code of the functions used in the above passage is under the spoiler.

Function code
The getNeighbors function returns an array of unvisited cell neighbors

cellString getNeighbours(unsigned int width, unsigned int height, int** maze, cell c){
    unsigned int i;
    unsigned int x = c.x;
    unsigned int y = c.y;
    cell up = {x, y - distance};
    cell rt = {x + distance, y};
    cell dw = {x, y + distance};
    cell lt = {x - distance, y};
    cell d[4]  = {dw, rt, up, lt};
    unsigned int size = 0;
    cellString cells;
    cells.cells = malloc(4 * sizeof(cell));
    for(i = 0; i < 4; i++){ //для каждого направдения
        if(d[i].x > 0 && d[i].x < width && d[i].y > 0 && d[i].y < height){ //если не выходит за границы лабиринта
            unsigned int mazeCellCurrent = maze[d[i].y][d[i].x];
            cell     cellCurrent     = d[i];
            if(mazeCellCurrent != WALL && mazeCellCurrent != VISITED){ //и не посещена\является стеной
                cells.cells[size] = cellCurrent; //записать в массив;
                size++;
            }
        }
    }
    cells.size = size;
    return cells;

The removeWall function removes the wall between two cells:

mazeMatrix removeWall(cell first, cell second, int** maze){
    short int xDiff = second.x - first.x;
    short int yDiff = second.y - first.y;
    short int addX, addY;
    cell target;
    addX = (xDiff != 0) ? (xDiff / abs(xDiff)) : 0;
    addY = (yDiff != 0) ? (yDiff / abs(yDiff)) : 0;
    target.x = first.x + addX; //координаты стенки
    target.y = first.y + addY;
    maze[target.y][target.x] = VISITED;
    return maze;
}

First, the difference value of the coordinates of the second and first points is calculated. Obviously, the value can be either negative, or positive, or 0.

It is necessary to find the coordinates xy so that when added to the coordinates of the first point, the coordinates of the wall are obtained.

Since we know for sure that the vector of the difference between the wall coordinates and the first point is either (| 1 |, 0) or (0, | 1 |), we can use this.

Thus, the additive for x coordinates with xDiff! = 0 will be equal to xDiff / | xDiff |, with xDiff = 0, zero. For y, respectively.
Having received the additives for x and y, we easily calculate the coordinates of the wall between the first and second cells and assign the cell to these coordinates visited.

So, now we have a maze 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:

Labyrinths. Caution traffic!
  100x100
image
  500x500
image

Generation is working, now it’s small: to find a way out in such a maze.

There are several more search algorithms than generation algorithms, and some of them, if there is interest of readers, I will cover in the following articles, but for now we will be content with what we have and we will “go through” the labyrinth with the same algorithm.

And it’s simplified even more, since we no longer need to remove the walls.

Backtracking path search algorithm:
1. Make the initial cell current and mark it as visited.
2. No way out yet
  1. If the current cell has unvisited “neighbors”
    1. Push the current cell onto the stack
    2. Select a random cell from the neighboring ones
    3. Make the selected cell current and mark it as visited.
  2. Otherwise, if the stack is not empty
    1. Pull the cage out of the stack
    2. Make it current
  3. Otherwise there is no way out

The output 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, “entry” and “exit” are just two points between which you need 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 “exit”: if they are equal, the path between the start and the exit points is found.

Let's see what happened:

Solved mazes. Traffic!
Red indicates the path, blue - visited cells.
  100x100
image

image
  500x500
image

image
  8000h8000
image

image

8000h8000 in original resolution (16000px, 30MB):
yadi.sk/i/YS0ImN-PhoLcZ
yadi.sk/i/YZjzwPu5hoLcd

That's all you need 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)

Attention!
OSMesa is not supported by some drivers on unix-based, and on Windows it is not supported at all , so for those who are unlucky with OS / hardware, I can propose you to familiarize yourself with an adjacent project: Maze Generator and Solver
The same algorithms are implemented in both projects. but the first draws in memory and displays a sequence of png-images, and the second on the screen.
Build cd build && ../configure && make, if it’s inconvenient, there is a QtCreator project file in the src folder.

Sources

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

Also popular now: