Indecently simple implementation of indecently simple maze generation algorithm
The continuation of this article is about a very simple algorithm for generating rectangular mazes. In this article I will give my implementation of the algorithm in C ++, as well as show a few additional functions that my bored brain spawned. If you dare to continue to read, be sure to read my previous article. Looked? Well done, we continue.
Let's start from the beginning - we tighten standard libraries, we declare functions.
Still very simple, as I like. In main, we will be able to determine the dimensions of the maze in the variables height and width (recall that the size of the maze is exceptionally odd, the cost of the algorithm). These parameters can be taken out of the main and make them constants or simply global variables, the program will not suffer from this.
Actually, that's the whole main . The entire maze is easily stored in a two-dimensional dynamic array, with which we work. After executing the mazemake function, a maze is preserved in the maze array, in which 0 is the wall and 1 is the passage.
')
Let's continue, the deadend function, looking for hopeless situations for the mole - when there are already passes to all four directions.
A bit of deadend . This function returns the value true if the mole is at a dead end; otherwise, it is false . Why twice if , but not logical AND? Very simple - the first check - on the presence of a nearby external impenetrable wall. It is impenetrable for several reasons - we did this by selecting these dimensions, respectively, allocated memory for the array (memory management, any ^> ^), and you won’t really check the (-1) -th element of the array. Also, pay attention to the curly braces after the primary if - else refers to it,and another way to write it is unknown to me .
What else do you need for happiness? Next stop is mazemake .
Too easy? In general, yes, it is. To obscenity is simple. There are all the same double if , for the same reason. There is nothing to complain about. Is that a crutch in the form of a counter. If he hurts your feelings - welcome to the second chapter of our story.
We taught a mammal to make us a maze. Why not force this creation to make us a couple of rooms? After all, we are insidious sadistic scientists and do not know where to put poor little animals.
If we want to be able to make rooms and define their parameters, the code changes a little here and there. The rooms also have odd sizes.
Hmm ... No, not solid. Mushroom-shaped algorithm for finding the way in the ideal maze. That's better. Okay, less words, more code.
Honestly, even nothing to say. Just find the only path between the points and show. Is that in visual add case liveshroom: cout << "*"; break;
If you really disliked the counter in the basic algorithm, then here is an excellent alternative for you - the verification function that runs every hundred cycles:
With a leading ad handle. Successes, use on health.
Oh yeah, pictures.
Where is the code?
Let's start from the beginning - we tighten standard libraries, we declare functions.
#include<iostream> #include<cstdlib> #include<ctime> using namespace std; bool deadend(int, int, int**, int, int); // , void visual(int**, int, int); // void mazemake(int**, int, int); // const int wall = 0, pass = 1; Still very simple, as I like. In main, we will be able to determine the dimensions of the maze in the variables height and width (recall that the size of the maze is exceptionally odd, the cost of the algorithm). These parameters can be taken out of the main and make them constants or simply global variables, the program will not suffer from this.
int main(){ srand((unsigned)time(NULL)); int height = 21, width = 21; int** maze = new int*[height]; for(int i = 0; i < height; i++) maze[i] = new int[width]; mazemake(maze, height, width); visual(maze,height,width); for(int i = 0; i < height; i++) delete[] maze[i]; delete[] maze; return 0; } Actually, that's the whole main . The entire maze is easily stored in a two-dimensional dynamic array, with which we work. After executing the mazemake function, a maze is preserved in the maze array, in which 0 is the wall and 1 is the passage.
')
Let's continue, the deadend function, looking for hopeless situations for the mole - when there are already passes to all four directions.
bool deadend(int x, int y, int** maze, int height, int width){ int a = 0; if(x != 1){ if(maze[y][x-2] == pass) a+=1; } else a+=1; if(y != 1){ if(maze[y-2][x] == pass) a+=1; } else a+=1; if(x != width-2){ if(maze[y][x+2] == pass) a+=1; } else a+=1; if(y != height-2){ if(maze[y+2][x] == pass) a+=1; } else a+=1; if(a == 4) return 1; else return 0; } A bit of deadend . This function returns the value true if the mole is at a dead end; otherwise, it is false . Why twice if , but not logical AND? Very simple - the first check - on the presence of a nearby external impenetrable wall. It is impenetrable for several reasons - we did this by selecting these dimensions, respectively, allocated memory for the array (memory management, any ^> ^), and you won’t really check the (-1) -th element of the array. Also, pay attention to the curly braces after the primary if - else refers to it,
void visual(int** maze, int height, int width){ for(int i = 0; i < height; i++){ for(int j = 0; j < width; j++) switch(maze[i][j]){ case wall: cout<<"0 "; break; case pass: cout<<" "; break; } cout<<endl; } cout<<endl; } What else do you need for happiness? Next stop is mazemake .
void mazemake(int** maze, int height, int width){ int x, y, c, a; bool b; for(int i = 0; i < height; i++) // - for(int j = 0; j < width; j++) maze[i][j] = wall; x = 3; y = 3; a = 0; // while(a < 10000){ // , , , , maze[y][x] = pass; a++; while(1){ // , c = rand()%4; // , switch(c){ // case 0: if(y != 1) if(maze[y-2][x] == wall){ // maze[y-1][x] = pass; maze[y-2][x] = pass; y-=2; } case 1: if(y != height-2) if(maze[y+2][x] == wall){ // maze[y+1][x] = pass; maze[y+2][x] = pass; y+=2; } case 2: if(x != 1) if(maze[y][x-2] == wall){ // maze[y][x-1] = pass; maze[y][x-2] = pass; x-=2; } case 3: if(x != width-2) if(maze[y][x+2] == wall){ // maze[y][x+1] = pass; maze[y][x+2] = pass; x+=2; } } if(deadend(x,y,maze,height,width)) break; } if(deadend(x,y,maze,height,width)) // do{ x = 2*(rand()%((width-1)/2))+1; y = 2*(rand()%((height-1)/2))+1; } while(maze[y][x] != pass); } // . } Too easy? In general, yes, it is. To obscenity is simple. There are all the same double if , for the same reason. There is nothing to complain about. Is that a crutch in the form of a counter. If he hurts your feelings - welcome to the second chapter of our story.
Features and Dryuki
Rooms
We taught a mammal to make us a maze. Why not force this creation to make us a couple of rooms? After all, we are insidious sadistic scientists and do not know where to put poor little animals.
If we want to be able to make rooms and define their parameters, the code changes a little here and there. The rooms also have odd sizes.
void mazemake(int**, int, int, int, int, int); // const int wall = 0, pass = 1, room = 4; // ... int height = 59, width = 111, k = 30; // int rheight = 7, rwidth = 5; // ... void mazemake(int** maze, int height, int width, int k, int rheight, int rwidth){ int x, y, c, a; bool b, swap = 1; for(int i = 0; i < height; i++) for(int j = 0; j < width; j++) maze[i][j] = wall; rheight--; rwidth--; // for(int l = 0; l < k; l++){ // b = 1; while(b){ do{ // - if(rwidth%4 == 0) // , 4 x = 2*(rand()%(width/2))+1; // , else x = 2*(rand()%(width/2))+2; if(rheight%4 == 0) y = 2*(rand()%(height/2))+1; else y = 2*(rand()%(height/2))+2; } while(x < (rwidth+2) || x > (width-rwidth-2) || y < (rheight+2) || y > (height-rheight-2)); b = 0; // for(int i = (y-rheight-2); i < (y+rheight+2); i++) for(int j = (x-rwidth-2); j < (x+rwidth+2); j++) if(maze[i][j] == room) b = 1; if(b) continue; for(int i = (y-rheight/2); i < (y+rheight/2+1); i++) // for(int j = (x-rwidth/2); j < (x+rwidth/2+1); j++) maze[i][j] = room; c = rand()%4; // , // , , // rand()... , // if(c == 0) maze[y+rheight/2+1][x-rwidth/2+2*(rand()%(rwidth/2+1))] = room; if(c == 1) maze[y-rheight/2-1][x-rwidth/2+2*(rand()%(rwidth/2+1))] = room; if(c == 2) maze[y-rheight/2+2*(rand()%(rheight/2+1))][x+rwidth/2+1] = room; if(c == 3) maze[y-rheight/2+2*(rand()%(rheight/2+1))][x-rwidth/2-1] = room; // swap 90° if(swap){ rheight += rwidth; rwidth = rheight - rwidth; rheight -= rwidth; } // } } ... int deadend(int x, int y, int** maze, int height, int width){ int a = 0; // deadend , if(x != 1){ if(maze[y][x-2] == pass || maze[y][x-2] == room) a+=1; } else a+=1; ... Mushroom
Hmm ... No, not solid. Mushroom-shaped algorithm for finding the way in the ideal maze. That's better. Okay, less words, more code.
... void shroom(int**, int, int); const int wall = 0, pass = 1, liveshroom = 2, deadshroom = 3, room = 4, start = 5, finish = 6; int main(){ srand((unsigned)time(NULL)); int height = 59, width = 111, k = 30; // - int rheight = 7, rwidth = 5; // int** maze = new int*[height]; for(int i = 0; i < height; i++) maze[i] = new int[width]; mazemake(maze, height, width, k, rheight, rwidth); visual(maze,height,width); maze[1][1] = start; maze[height-2][width-2] = finish; shroom(maze,height,width); // , visual(maze,height,width); // for(int i = 0; i < height; i++) delete[] maze[i]; delete[] maze; return 0; ... void shroom(int** maze, int height, int width){ int x, y; for(int i = 0; i < height; i++) // for(int j = 0; j < width; j++) if(maze[i][j] == start){ x = j; y = i; } while(maze[y][x] != finish){ // - maze[y][x] = liveshroom; // // , , , // if(maze[y][x+1] == pass){ maze[y][x+1] = liveshroom; x+=2; continue; } if(maze[y][x-1] == pass){ maze[y][x-1] = liveshroom; x-=2; continue; } if(maze[y+1][x] == pass){ maze[y+1][x] = liveshroom; y+=2; continue; } if(maze[y-1][x] == pass){ maze[y-1][x] = liveshroom; y-=2; continue; } if(maze[y][x+1] != pass && // - , maze[y][x-1] != pass && // (x, y) maze[y+1][x] != pass && // maze[y-1][x] != pass){ maze[y][x] = deadshroom; if(maze[y][x+1] == liveshroom){ maze[y][x+1] = deadshroom; x+=2; continue; } if(maze[y][x-1] == liveshroom){ maze[y][x-1] = deadshroom; x-=2; continue; } if(maze[y+1][x] == liveshroom){ maze[y+1][x] = deadshroom; y+=2; continue; } if(maze[y-1][x] == liveshroom){ maze[y-1][x] = deadshroom; y-=2; continue; } } } for(int i = 0; i < height; i++) // , for(int j = 0; j < width; j++) if(maze[i][j] == deadshroom) maze[i][j] = pass; } } Honestly, even nothing to say. Just find the only path between the points and show. Is that in visual add case liveshroom: cout << "*"; break;
Not a crutch
If you really disliked the counter in the basic algorithm, then here is an excellent alternative for you - the verification function that runs every hundred cycles:
... x = 3; y = 3; a = 0; while(1){ a++; if(a%100 == 0) if(ended(maze, height, width)) break; maze[y][x] = pass; ... bool ended(int** maze, int height, int width){ bool b = 1; for(int i = 1; i < (height - 1); i += 2) for(int j = 1; j < (width - 1); j += 2) if(maze[i][j] == wall) b = 0; return b; } With a leading ad handle. Successes, use on health.
Oh yeah, pictures.
Look
Labyrinths of 59x111, 30-40 rooms.
A simple maze without rooms.
Rooms 5x5, showing an old bug - the doors were only in two positions on the walls.
Rooms 3x5, without SWAPO, the doors are adequately distributed.
Rooms 5x7, swap included
Demonstration of the fungus, no rooms ...
... and with 70 svapnuty rooms 3x5.
A simple maze without rooms.
Rooms 5x5, showing an old bug - the doors were only in two positions on the walls.
Rooms 3x5, without SWAPO, the doors are adequately distributed.
Rooms 5x7, swap included
Demonstration of the fungus, no rooms ...
... and with 70 svapnuty rooms 3x5.
Source: https://habr.com/ru/post/319532/
All Articles