It happened that the topic of automatic maze creation came up at work, and when I looked it up thinking that I had never created it, an algorithm called the digging method came out immediately. It was the easiest to understand, so I decided to implement it for the time being. The following site was easy to understand, so I implemented it based on the explanation.
"Automatic maze generation algorithm"
Since there was no source code in particular, it was an implementation from scratch without a reference implementation, and I started from a state where I was extremely unsure.
I won't go into the details of the algorithm here, but the short answer is how to create a style of digging holes in the wall. Detailed explanations will be given to the above sites and other sites with detailed explanations. In terms of implementation, the entire maze is secured in a two-dimensional array, an arbitrary position in the array is randomly specified, and holes are dug in each direction starting from that position = the wall is turned into a road. Repeat the work. Automatic generation will end when all can no longer be dug.
I think that there is no problem if it is a POSIX compliant environment that can be compiled into an executable file with clang or gcc.
Compile and run
% cc maze.c
% ./a.out
There is an implementation on github. I will try the following explanation based on this source.
I always have the idea of "implementation 30%, design 60%, debugging 10%". Whether this is correct or not, you need to design it before writing the code. The rough design points here are as follows.
――How to retain data --What is the type of data? ――What kind of implementation method to use
As I've already explained, a two-dimensional array seems to be useful for generating a map of a plane. Of course, a one-dimensional array is also possible, but in that case it is necessary to calculate the scalar from the coordinates. Two-dimensional array in C language We will use a simple and intuitive two-dimensional array.
Two types of data, "wall" and "road", are assumed. Integers look good for these representations. Therefore, we use a two-dimensional array of integers. Walls and roads are constants, so let's set these constants as well. Also, since we are digging "advancing", we need an element to judge the direction of travel. This will need to be in vectors (coordinates).
The digging algorithm repeats the same task, so you will probably use either loops or recursion. It is necessary to think about the previous coordinates because the work of "If you can not dig up, go back one step" is involved. This will require either stacking or recursion. The former is a method of owning the stack, and the latter is a method of using the stack area of the program itself because it calls itself in the function. As a result, both use the stack. You will choose the one that is easy to understand or implement by yourself. In my case, I decided to use recursion.
Let's follow the implementation that I actually followed. The implementation itself is contained in one file called maze.c. At the time of writing this, it is about 97 lines. There are almost no comments during the implementation (I put it in my usual implementation).
Implement constants and variables based on your design. As for the header files to be included, list the ones that are likely to be necessary for the time being.
maze.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define WIDTH 59 /** gt or eq 5 */
#define HEIGHT 25 /** gt or eq 5 */
#define ROAD 0
#define WALL 1
int map[WIDTH][HEIGHT];
It includes stdio.h because it uses printf () etc., stdlib.h because it uses rand () etc., and time.h because it uses time () for seed of srand ().
Four constants are available. Two are map sizes. It defines the width and height (length), that is, the width and height. It seems that at least 5x5 is required to dig, so it is written in the comment. Originally, it should be necessary to judge this value, but it is not meaningful to judge the constant in the program, so it is omitted. If you do not prepare this as a constant and provide it in another form, it seems that you will need to judge the size.
The remaining two constants are the values of "road" and "wall". This may be prepared by enum.
And a two-dimensional array that holds the data. Prepare a map [] [] and record the walls and roads here. If you prepare a road or wall with an enum, this will be an enum instead of an int. map [] [] is set by the computer shop to be (probably) intuitive and easy to understand. In other words, the coordinate system is such that the upper left is map [0] [0] and map [WIDTH] [HEIGHT] is the lower right.
Prepare a vector that indicates the direction of digging. Since it is a flat surface, there are four directions (up, down, left, and right). For the coordinates, I set the structure and made it shown in this array.
maze.c
struct {
int x;
int y;
} dir[] = {
{0, -1}, /** UP */
{0, 1}, /** DOWN */
{-1, 0}, /** LEFT */
{1, 0} /** RIGHT */
};
I didn't set a constant here (I don't think it makes sense to make it a constant because it's only used in some parts such as if statements), but the subscript of dir [] goes up, 1 Is on the bottom, 2 is on the left, 3 is on the right, and so on. Since it is not constant, I add a comment.
This is an example of specifying the direction. When going up, the direction is "0", so the second-dimensional subscript of map [] [] is -1. This can be seen from the definition of the coordinate system of the map [] [] array explained earlier. As we go up, we refer to dir [0], and since the structure contains {0, -1}, that is, x = 0, y = -1, dir [0] .x, dir [0] I will take it out as .y and use it.
Now that we have all the necessary constants and variables, it's time to implement the program itself.
First, I wrote the main function first. I started writing while organizing my mind in terms of the order in which the functions are called.
main.c
int main()
{
init();
for (int i = 0; i < 3; i++) {
maze_init();
maze();
print();
}
return 0;
}
I didn't prepare it in this form from the beginning, but it's almost the same. You don't have to because the for statement is just generated three times in a row. We separated init () and maze_init () because we separated random number initialization (srand) and map initialization. If you do not include a for statement and execute it only once, there is no problem even if it coexists.
The maze () function is the starting point for creating a maze.
The print () function prints (displays) the maze.
I don't think I need any explanation, but I will write it for the time being. Init () is doing random number initialization. I think that some people should write it in main (), but please forgive it because it is an implementation style that prepares for extension by making it as functional as possible (this time there is no extension). After that, I think it is better to make it a function from the viewpoint of perspective. How to use time () and srand () is time (3), rand (3) Please see: //linuxjm.osdn.jp/html/LDP_man-pages/man3/rand.3.html).
init()
void init()
{
time_t t;
time(&t);
srand(t);
}
Initialize map [] [] with the maze_init () function. In short, it is filled with "walls".
maze_init()
void maze_init()
{
int x, y;
for (y = 0; y < HEIGHT; y++)
for (x = 0; x < WIDTH; x++)
map[x][y] = WALL;
}
This is a common way to initialize a for statement by nesting it in two stages.
print()
void print()
{
int x, y;
for (y = 0; y < HEIGHT; y++) {
for (x = 0; x < WIDTH; x++)
printf("%c", (map[x][y] == WALL) ? '#' : ' ');
printf("\n");
}
}
The display is not particularly elaborate. "#" Is displayed for walls and "(half-width blank)" is displayed for roads. This is determined by the conditional expression in printf () of the second loop and separated. For language specifications that do not have a ternary operator such as Go, you will need to use another method such as an if statement.
In addition, although the display is intended for console output here, when using other output devices such as smartphones, the output will be suitable for each. This function is for checking the implementation here.
This function is the starting point for creating a maze. Since a maze is created using recursion, we have a separate function to recurse, and the function that pulls the trigger is maze ().
maze()
void maze()
{
int x = rand_odd(WIDTH - 2);
int y = rand_odd(HEIGHT - 2);
printf("(%d, %d)\n", x, y);
make_maze(x, y);
}
The function to recurse is make_maze (). It has arguments x and y that specify from which coordinates to start digging. For coordinates, I think it is okay to create a structure (or use the structure that defines dir []) and use the structure as an argument. Here, for convenience, it is processed with 2 parameters of int.
The rand_odd () function was created to generate only odd random numbers. This is used to randomly take the generation position of the first path.
rand_odd()
int rand_odd(int mod)
{
int r = 1 + rand() % mod;
if (r % 2 == 0)
r++;
if (r > mod)
r -= 2;
return r;
}
The reason is that the only place to make a road is the odd coordinates of map [] []. I think the following simple map is easier to understand than the explanation of words.
5x5 map example
01234
0#####
1# # #
2# # #
3# #
4#####
0 to 4 in the horizontal direction indicate x of map [x] [y], and 0 to 4 in the vertical direction indicate y. The place where the road is made is always the odd position of the subscript, so it is a problem if the coordinates that are the starting point are not odd.
Returning to rand_odd (), the first if statement makes a strange judgment, and if it is even, it is incremented by +1 to make it odd. The second if statement prevents the subscript range from being exceeded. Here, it is easily set to -2 and rounded to the previous odd value. I think the implementation here could be elaborate in other ways, but it doesn't seem to make much sense, so I just implemented the rounding process in a straightforward manner.
In addition, after generating the coordinates with rand_odd (), the coordinate values are displayed with the printf () statement, but this is for confirmation, so it is not necessary.
Now, the make_maze () function that actually creates the maze. It is the essence of this program, the implementation of the algorithm itself, and the end of the explanation.
First of all, from the big picture.
make_maze()
void make_maze(int x, int y)
{
int d = rand() % 4;
int dd = d;
while (1) {
int px = x+dir[d].x*2;
int py = y+dir[d].y*2;
if (px < 0 || px >= WIDTH || py < 0 || py >= HEIGHT || map[px][py] != WALL) {
d++;
if (d == 4)
d = 0;
if (d == dd)
return;
continue;
}
map[x+dir[d].x][y+dir[d].y] = ROAD;
map[px][py] = ROAD;
make_maze(px, py);
d = dd = rand() % 4;
}
}
There is not much code. The first line of the function uses random numbers to determine the direction of digging. Since it is necessary to remember the decided direction, save it in the variable dd.
make_maze()
int d = rand() % 4;
int dd = d;
The reason you need to remember is to determine if you have tried four directions. In this implementation, direction check and switching are performed in order using numerical values from 0 to 3. That is, check in the order of 0 → 1 → 2 → 3. However, since the first direction is a random number, we do not know which value to start with. In other words, it may be judged by the pattern of 2 → 3 → 0 → 1 instead of 0 → 1 → 2 → 3. Therefore, it is necessary to record the position where you first tried to dig, and when you return to that value, you will decide that you cannot dig in all directions. It becomes the variable dd for that.
Create an infinite loop with a while statement. You can only get out of this loop when you can't dig in all four directions. This implementation uses recursion, so loop exit is a return to the function caller.
make_maze()
int px = x+dir[d].x*2;
int py = y+dir[d].y*2;
if (px < 0 || px >= WIDTH || py < 0 || py >= HEIGHT || map[px][py] != WALL) {
d++;
if (d == 4)
d = 0;
if (d == dd)
return;
continue;
}
In the first two lines of the while statement, the coordinates for judgment are calculated from the digging direction determined earlier. The values of dir [d] .x and dir [d] .y are doubled (* 2). This is an algorithm-based implementation that does not dig if there is a road beyond the position you want to dig.
The following if statement determines whether or not to actually dig. When exceeding the range of map(px < 0 || px >= WIDTH || py < 0 || py >= HEIGHT)Or if the point you want to dig is not a wall(map[px][py] != WALL)is.
As an aside, as a technique to reduce the burden of conditional processing here, there seems to be a method of leaving the entire circumference of the map as a road. In this case, the map will be one size smaller than the desired map size, so you will need to secure an array that takes the outer circumference into consideration. It's a general trade-off between processing speed and memory.
The reason why "map [px] [py] == ROAD" is not set is, for example, in case elements other than walls and roads appear. Speaking only this time, I don't think that "== ROAD" will be a potential bug because the implementation will not be extended.
If the condition of the if statement is met, it means that you could not dig in a certain direction. Therefore, switch the direction. d ++ to switch directions, and if the result is 4, set it back to 0. As a result of switching the direction, if it returns to the first position, it means that all four directions are wiped out, so you can exit the function with return. If you haven't looked in all directions yet, continue to determine if you can dig in another direction at the beginning of the while statement.
make_maze()
map[x+dir[d].x][y+dir[d].y] = ROAD;
map[px][py] = ROAD;
make_maze(px, py);
d = dd = rand() % 4;
Overwrite map [] [] with ROAD if you can dig. ROAD overwrites both the coordinates in the direction of digging and the coordinates one step ahead that you checked earlier. This is also an algorithm-based implementation.
Now that we have been able to dig safely, we will continue to dig further starting from the coordinates one step ahead. Here, the process is divided depending on whether the current coordinates are pushed onto the stack or recursion is used, but since this implementation uses recursion calls, the make_maze () function, that is, itself, is based on the newly determined coordinates. I'm calling.
When I come back from this function, it's when I couldn't dig in all four directions. In other words, if you can't dig in all four directions of (px, py) coordinates, the following code for this recursive call will be executed. Then, when returning from this function, it will be judged whether or not it can be dug in another direction starting from the coordinates before digging, and the direction will be switched, so d and dd Processing will be continued based on the value determined by the random number.
Since it was a simple algorithm, it was relatively easy to implement. Since C is a language that I'm relatively familiar with, the implementation itself took about an hour or two. I didn't have any particular code to refer to, so I didn't have any criteria for judging whether the implementation was correct, but when I compiled it, a maze suddenly appeared, so I laughed aloud (laughs).
It was just a brain teaser, so I thought it would be convenient for me as a Go monk, so I immediately [ported] it to Go (https://github.com/zurazurataicho/maze_golang). I would like to write a commentary on that when I have time.
Recommended Posts