Indecent simple maze generation algorithm

A simple algorithm for generating perfect mazes in the most ordinary two-dimensional space. Nuff said, the rest is under the cut.

Search and frustration

I will begin without unnecessary details and preludes - in the course of my student life, I needed an algorithm for generating a rectangular maze. With a prayer on sinful lips, I plunged into the endless bowels of Google and dug up this article . The algorithm was simple and clear, it gave me the ideal, not cyclical labyrinths (from any point of the maze you can get to any other point of it, and only one way), but because of my limited programming knowledge at that time, I pulled implementation for half a year. It happened. And, frankly, was disappointed in the result. The algorithm produced more or less interesting labyrinths with a dimension less than 20, but somewhere from this point the problems started.

1. Predictability
As I did not try, it was only possible to get from the upper left corner of the maze to the upper right corner by walking along the two lower levels. That gave some opportunities, like making them something like a wide corridor, but I did not need it.

2. Memory consumption
I wrote the algorithm on the good old Pascal, which ran through the DOSBox emulator. This limited my RAM to a 64-kilobyte stump. Since I kept the maze in an array of structures that included three byte variables, the creation of a maze with a dimension greater than 150x150 without using dynamic memory was problematic.
')
3. Algorithm Imperfection
It so happened that the algorithm did not consider all possible scenarios, which led to the appearance of various unwanted artifacts.

After realizing these three points, I decided to abandon this algorithm and create my own.

Idea and implementation

So, I needed a perfect and non-cyclical labyrinth. The previous algorithm implied the construction of walls in an empty room, so I decided to go a different way, namely, to dig roads in solid ground. This will be done by a small “shrew”, which will remain for us two-dimensional coordinates. But what algorithm will drive the movements of the shrew? No! “Shrew” in our immense dungeon will drive the Great Korean Rand.

Actually, the algorithm

Denote 1 as a passage and 0 as a wall. The initial conditions are a two-dimensional array filled with zeros. The dimension of the array is any odd numbers. We assume that the upper left corner of the wall has coordinates (1; 1). The coordinates of the “shrews” are always even , it moves, respectively, only by jumps long in two elements of the array.

1. Randomly select the landing point of the “shrew” - generate random non-zero coordinates. The touchdown point is assigned the value 1.
2. Randomly choose one of the directions - up, down, left, right.
3. If after a jump in the chosen direction we find ourselves in the outer wall or in the aisle, then return to the previous item. Otherwise - we jump in the specified direction. We assign the value of 1 cell, in which they landed and jumped over.
4. If after landing we cannot take a jump (hit a dead end), then we randomly generate coordinates. Otherwise - go to the second paragraph.
5. We repeat the point above until there is a passage in the specified coordinates.

Everything is indecent simply. Sooner or later we will get stuck in the last two points. An interruption for an algorithm can be either a counter or a simple check - if there is 1 in each cell with even coordinates, then the algorithm can be safely interrupted.

Benefits:

• ease of implementation
• works with two cell states
• simple incoming and outgoing data
• works without errors in any maze size

Disadvantages:

• simple maze structure

That's all. I hope that it is useful to at least someone.

UPD

It would be logical to attach an illustration here, so here. Maze dimensions - 320x240