Classical labyrinth generation algorithms. Part 1: introduction

Foreword

Writing an article led me to the almost complete lack of materials in Russian about labyrinth generation algorithms. On Habré, from what is generally on the topic, two articles can be noted: one and two . The value and benefits of which is only the second. In the first, just a translation of the formal algorithm and a small explanation of it. Which, of course, not bad, but very poorly and does not cause the desire to study the topic further.



If you like my article, I will continue to write about various algorithms. We will look at two of the most primitive and simple cases - the generation of a binary tree and Sidewinder, which, in its essence, is just a slightly modified version of a binary tree with one noticeable plus. CAUTION TRAFFIC .

')

I will give one piece of advice - do not peek into the code until you write your implementation. You will get much more pleasure and benefit from fixing bugs and finding errors than if you simply translate from one language to another.



Seriously. Listen to the advice. You, truly, will spend more time, but it costs. For example, because of a couple of errors, I had a very funny generator of “alien” texts, which can be used in various Sci-Fi games to create text. I hope you study the topic for yourself and do not hurry anywhere.



PS:



I will use the term " bias ", assuming English bias. Those. addiction of the algorithm to directivity in any direction. For example, the right offset - the algorithm generates mazes with long right passes.



The coloring of the labyrinths occurs relative to the distance from the extreme left corner of the field to a certain cell. The farther from the initial coordinate - the darker the color will be.



An ideal maze is a maze in which one cell is connected to another by one single path. In other words, spanning tree.

Binary tree algorithm

Description :



The very first and easiest algorithm in the understanding, which I will consider. Its essence lies in paving the way in a random direction from each cell of the field: in my implementation, either upward or to the right (depending on the offset chosen by you). We process only 1 cell per unit of time, therefore, we can generate mazes of infinite size, keeping only the final result (maze) without the need to store any side information.



This generation method has two side effects:



1. Labyrinths have a strong diagonal displacement and no dead ends in its direction. Look at the screenshots above and you will see that each of the corridors tends to the right upper cell, and, as a result, it has exactly one path to it, and there is no dead end anywhere on the path:



2. Two empty corridors on the sides of the maze. When the algorithm “digs through” to the end of the row / column, it has no choice but to continue the path in one single direction, creating empty “borders”.



By the way, the name does not just coincide with the data structure. The result of his work is a random binary tree, in which from each cell (vertex) there is exactly 1 path towards the root (parent vertex), and, accordingly, exactly 1 path to any other cell. As a result, any cell has no more than 3 connections with its neighbors.



Formal algorithm (for northeast offset):

1. Select the starting cell;
2. Choose a random direction for paving the way. If a neighboring cell in this direction extends beyond the field, dig a cage in the only possible direction;
3. Go to the next cell;
4. Repeat 2-3 until all cells are processed;

Pros :

• Simple implementation;
• High speed;
• The ability to generate endless labyrinths;

Cons :

• Low complexity of the pattern;
• Strong offset diagonally;
• No deadlocks on the offset;
• The monotony of the generated mazes;

Algorithm "Sidewinder"

Description :



The algorithm with the untranslatable name Sidewinder is very similar in its work to the binary tree algorithm, in that there is no characteristic bias along the diagonal, one empty corridor and a cell, we consider not individually, but sets. Labyrinths are obtained with a predominantly vertical or horizontal displacement (depending on the implementation), with no dead ends in their direction. Compared with its more primitive fellow, the displacement is not so noticeable and more like a “spiral” that smoothly replaces vertical and horizontal corridors.



As for side effects, Sidewinder creates only one empty corridor on one side, instead of two. Starting the creation of sets from the first row of the field, we do not have the opportunity to dig up the path, since we are in the most extreme vertical position and trying to go higher will result in going beyond the field boundaries. But even if we organize sets without going vertically, we will create several regions isolated from each other.



For example: 9 cells of the first row can be divided into three sets, between which walls are located. Each set of the second row will dig through the path to one of the three “blocks” above. The third row will pave the way for the "blocks" of the second. And so on until the end of the field. As a result, we will have 3 branched, isolated from each other vertical areas, which is not suitable for a perfect maze, in which from each point of the field there is exactly 1 way to any other.



Formal algorithm (for standard offset):

1. Select the starting row;
2. Select the starting cell of the row and make it current;
3. Initialize empty set;
4. Add the current cell to the set;
5. Decide whether to pave the right;
6. If laid, then go to the new cell and make it current. Repeat steps 3-6;
7. If not paved, choose a random cell of the set and pave the way up from there. Go to the next row and repeat 2-7;
8. Continue until each row has been processed;

Pros :

• The ability to generate endless labyrinths;
• Only 1 empty corridor;
• A more complex picture, unlike the binary tree algorithm;

Cons :

• More confusing implementation;
• No deadlocks on the offset;
• Strong vertical displacement;

Epilogue

I hope you liked the article and you learned new knowledge about the primitive procedural generation of labyrinths. I chose the two most simple ones in the implementation and operation of the algorithm, so that it would be easier for newbies to “touch” the topic and see if they want to study it further. It is important for me to know whether people like Habrahabr are interested in such articles and whether to continue writing them. For readers, I still have at least 9 classic algorithms worth considering. Some of them are random wanderings around the field, such as, for example, the Prima or Wilson algorithm, some require more resources for work, as they work with graphs, for example, Eller and Kruskal, and some maintain a middle ground. But this is not the end - I have such things in my sleeve as: polar (round) labyrinths, generation of labyrinths on different grids (hexes, triangles, etc.), masking labyrinths in inscriptions and forms, 2.5D labyrinths and 3D, theory labyrinths, statistical comparison of algorithms, combined generation algorithms. In the end, we still have a huge variety of variations of the types of labyrinths. For example, now we are considering ideal algorithms, in which from each point there is exactly one path to any other. But there are also those that allow one cell to have several paths for any other! For example, Quake, Doom, and other shooters in the emerging genre used such algorithms to generate levels, according to some rumors.



Therefore, if you liked the article, the topic, and you want to see them further - then please write about it in the comments. Also, I will be very happy to any criticism, both technically and in linguistic and stylistic.