Lecture
Maze (Anc. Greek λαβύρινθος) — a structure (usually in two- or three-dimensional space) consisting of confusing paths to an exit (and/or paths leading to dead ends).
Among the ancient Greeks and Romans, a labyrinth referred to a more or less extensive space consisting of numerous halls, chambers, courtyards, and passages arranged according to a complex and confusing plan, with the purpose of confusing an uninitiated person and preventing them from finding a way out. In a broader sense, a labyrinth can represent a deadlock situation or a matter from which it is very difficult to find a way out.
It is believed that if you traverse a maze while keeping one hand on one of its walls, the maze will always be solved, although this is not always true: in a maze with disconnected walls, this method may not work.
Eller's algorithm — is a mathematical generator that allows creating mazes in which there is a single path between every two points, meaning the mazes contain no cycles. Compared to other generators, this algorithm is one of the fastest and requires a small amount of RAM — proportional to the length of the maze's row. It only needs to store the last generated row in memory, which allows generating mazes with an unlimited number of rows.
Eller's algorithm is an algorithm for generating a perfect maze. A maze is considered perfect if it has no closed or looped sections, and there is exactly one path from any point to any other point.
The algorithm is a loop that adds new rows. A row contains the same number of cells, which is arbitrarily set at the beginning. Cells belong to sets, which are used to control the possibility of passage between cells. At the moment the current row is generated, cells belonging to the same set are connected to each other, while cells from different sets are located in parts of the maze isolated from one another. In general, the maze's walls are generated randomly, but subject to certain rules that guarantee the absence of loops.
Description of the algorithm
Create the first row. No cell will be part of any set.
Assign a unique set to each cell that doesn't belong to a set.
Create right-hand borders, moving from left to right:
Randomly decide whether to add a border or not
If the current cell and the cell to the right belong to the same set, create a border between them (to prevent loops)
If you decide not to add a border, merge the two sets that the current cell and the cell to the right belong to.
Create bottom borders, moving from left to right:
Randomly decide whether to add a border or not. Make sure that every set has at least one cell without a bottom border (to prevent isolated regions)
If a cell is alone in its set, do not create a bottom border
If a cell is the only one in its set without a bottom border, do not create a bottom border
Decide whether you will continue adding rows or want to finish the maze
If you want to add another row, then:
Output the current row
Remove all right-hand borders
Remove cells with a bottom border from their set
Remove all bottom borders
Continue from step 2
If you decide to finish the maze, then:
Add a bottom border to every cell
Moving from left to right:
If the current cell and the cell to the right are members of different sets, then:
Remove the right-hand border
Merge the sets of the current cell and the cell to the right
Output the final row
Generating and solving a maze using the depth-first graph search method. Illustration of the algorithm's operation.
| 1. Create the initial matrix. |  |
| 2. Choose the starting point. |  |
| 3. Move to a random neighboring unvisited cell, as long as such cells exist. |  |
| 4. If there are no unvisited neighboring cells, backtrack through the stack |  |
| 5. There are unvisited neighboring cells. Move to a random unvisited neighboring cell. |  |
| 6. No unvisited cells left. The maze is generated. |  |
Let's proceed step by step, first generating the initial matrix that the algorithm will work with.
For convenience, let's agree that all cell types are defined in an enumeration.
int maze[height][width]; //create the matrix - a two-dimensional array
for(i = 0; i < height; i++){
for(j = 0; j < width; j++){
if((i % 2 != 0 && j % 2 != 0) && //if the cell is odd in x and y,
(i < height-1 && j < width-1)) //and lies within the maze walls
maze[i][j] = CELL; //then it is a CELL
else maze[i][j] = WALL; //otherwise it is a WALL.
}
}
Now that all the preparations are done, we can proceed to generation.
typedef struct cell{ //structure storing a cell's coordinates in the matrix
unsigned int x;
unsigned int y;
} cell;
typedef struct cellString{
cell* cells;
unsigned int size;
} cellString;
These structures will greatly simplify exchanging information between functions.
The code snippet responsible for generation:
cell startCell = {1, 1}
cell currentCell = startCell;
cell neighbourCell;
do{
cellString Neighbours = getNeighbours(width, height, maze, startPoint, 2);
if(Neighbours.size != 0){ //if the cell has unvisited neighbours
randNum = randomRange(0, Neighbours.size-1);
neighbourCell = cellStringNeighbours.cells[randNum]; //pick a random neighbour
push(d.startPoint); //put the current point on the stack
maze = removeWall(currentCell, neighbourCell, maze); //remove the wall between the current and neighbouring points
currentCell = neighbourCell; //make the neighbouring point the current one and mark it visited
maze = setMode(d.startPoint, d.maze, VISITED);
free(cellStringNeighbours.cells);
}
else if(stackSize > 0){ //if there are no neighbours, go back to the previous point
startPoint = pop();
}
else{ //if there are no neighbours and no points on the stack, but not all points have been visited, choose a random unvisited one
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 abstracted from theory, as they say, «even a child could handle it».
So as not to overload the article, the code of the functions used in the excerpt above is placed under a spoiler.
The getNeighbours function returns an array of a cell's unvisited neighbours
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++){ //for each direction
if(d[i].x > 0 && d[i].x < width && d[i].y > 0 && d[i].y < height){ //if it does not go beyond the boundaries of the maze
unsigned int mazeCellCurrent = maze[d[i].y][d[i].x];
cell cellCurrent = d[i];
if(mazeCellCurrent != WALL && mazeCellCurrent != VISITED){ //and is not visited / is not a wall
cells.cells[size] = cellCurrent; //write it into the array;
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; //wall coordinates
target.y = first.y + addY;
maze[target.y][target.x] = VISITED;
return maze;
}
Formal algorithm (for a north-east bias):
Pros:
Cons:
Pros:
Cons:
Formal algorithm:
Pros:
Cons:
Formal algorithm:
Pros:
Cons:
Maze generation and solving algorithms are widely used in various areas of real life. Here are a few examples:
Indoor navigation: Robots and self-driving cars use maze-traversal algorithms for navigation inside buildings. This can be useful in large shopping malls, warehouses, medical facilities, and other locations.
Obstacle detection: Obstacle-avoidance algorithms help vehicles avoid collisions with obstacles in real time, which is critical for ensuring safety in densely populated areas.
Logistics and warehousing: Automated warehouse systems can use maze-traversal algorithms to optimize the routes for moving goods or transport robots inside a warehouse.
Robot assembly: Maze-traversal algorithms can help robots assemble complex devices where precise and optimal movement between different components is required.
These examples highlight the wide range of fields in which maze-generation and maze-traversal algorithms can be useful for solving various problems.
Maze-generation and maze-traversal algorithms are a powerful tool that finds application in a wide variety of real-world fields. As an important element of modern technology, they make it possible to solve complex problems in autonomous vehicles, industry, medicine, the gaming industry, computer security, energy, and architecture.
Maze generation can be used to create unique scenarios in video games, optimize warehouse operations, analyze network security, and even design architectural solutions. On the other hand, maze-traversal algorithms are important for robot navigation inside buildings, real-time obstacle avoidance, and for automating processes in surgery and industry.
These algorithms are not only capable of effectively solving problems in specific fields, but also possess versatility, which makes them an important component of various technological research efforts and applications in the modern world
Comments