Perfect Maze Generator
a perfect maze, there is one and only one path from any point in the maze to any other point. That is, there are no inaccessible sections, no circular paths, and no open regions. A perfect maze can be generated easily with a computer using a depth first search algorithm.
A two dimensional maze can be represented as a rectangular array of square cells. Each cell has four walls. The state of each wall (north, south, east, and west) of each cell is maintained in a data structure consisting of an array of records. Each record stores a bit value that represents the state of each wall in a cell. To create a path between adjacent cells, the exit wall from the current cell and the entry wall to the next cell are removed. For example, if the next cell is to the right (east) of the current cell, remove the right (east) wall of the current cell and the left (west) wall of the next cell.
01 | create a CellStack (LIFO) to hold a list of cell locations |
02 | set TotalCells = number of cells in grid |
03 | choose a cell at random and call it CurrentCell |
04 | set VisitedCells = 1 |
05 |
06 | while VisitedCells < TotalCells |
07 |
08 | find all neighbors of CurrentCell with all walls intact |
09 | if one or more found |
10 | choose one at random |
11 | knock down the wall between it and CurrentCell |
12 | push CurrentCell location on the CellStack |
13 | make the new cell CurrentCell |
14 | add 1 to VisitedCells else |
15 | pop the most recent cell entry off the CellStack |
16 | make it CurrentCell endIf |
17 |
18 | endWhile |
001 | #include<stdio.h> |
002 | #include<conio.h> |
003 | #include<stdlib.h> |
004 | #include<time.h> |
005 |
006 | #define MAX 61 // 30 * 2 + 1 |
007 | #define CELL 900 // 30 * 30 |
008 | #define WALL 1 |
009 | #define PATH 0 |
010 |
011 | void init_maze(int maze[MAX][MAX]); |
012 | void maze_generator(int indeks, int maze[MAX][MAX], int backtrack_x[CELL], int bactrack_y[CELL], int x, int y, int n, int visited); |
013 | void print_maze(int maze[MAX][MAX], int maze_size); |
014 | int is_closed(int maze[MAX][MAX], int x, int y); |
015 |
016 | int main(void) |
017 | { |
018 | srand((unsigned)time(NULL)); |
019 |
020 | int size; |
021 | int indeks = 0; |
022 | printf("MAZE CREATOR\n\n"); |
023 | printf("input (0 ~ 30): "); |
024 | scanf("%d", &size); |
025 | printf("\n"); |
026 | int maze[MAX][MAX]; |
027 | int backtrack_x[CELL]; |
028 | int backtrack_y[CELL]; |
029 |
030 | init_maze(maze); |
031 |
032 | backtrack_x[indeks] = 1; |
033 | backtrack_y[indeks] = 1; |
034 |
035 | maze_generator(indeks, maze, backtrack_x, backtrack_y, 1, 1, size, 1); |
036 | print_maze(maze, size); |
037 |
038 | getch(); |
039 | return 0; |
040 | } |
041 |
042 | void init_maze(int maze[MAX][MAX]) |
043 | { |
044 | for(int a = 0; a < MAX; a++) |
045 | { |
046 | for(int b = 0; b < MAX; b++) |
047 | { |
048 | if(a % 2 == 0 || b % 2 == 0) |
049 | maze[a][b] = 1; |
050 | else |
051 | maze[a][b] = PATH; |
052 | } |
053 | } |
054 | } |
055 |
056 | void maze_generator(int indeks, int maze[MAX][MAX], int backtrack_x[CELL], int backtrack_y[CELL], int x, int y, int n, int visited) |
057 | { |
058 | if(visited < n * n) |
059 | { |
060 | int neighbour_valid = -1; |
061 | int neighbour_x[4]; |
062 | int neighbour_y[4]; |
063 | int step[4]; |
064 |
065 | int x_next; |
066 | int y_next; |
067 |
068 | if(x - 2 > 0 && is_closed(maze, x - 2, y)) // upside |
069 | { |
070 | neighbour_valid++; |
071 | neighbour_x[neighbour_valid]=x - 2;; |
072 | neighbour_y[neighbour_valid]=y; |
073 | step[neighbour_valid]=1; |
074 | } |
075 |
076 | if(y - 2 > 0 && is_closed(maze, x, y - 2)) // leftside |
077 | { |
078 | neighbour_valid++; |
079 | neighbour_x[neighbour_valid]=x; |
080 | neighbour_y[neighbour_valid]=y - 2; |
081 | step[neighbour_valid]=2; |
082 | } |
083 |
084 | if(y + 2 < n * 2 + 1 && is_closed(maze, x, y + 2)) // rightside |
085 | { |
086 | neighbour_valid++; |
087 | neighbour_x[neighbour_valid]=x; |
088 | neighbour_y[neighbour_valid]=y + 2; |
089 | step[neighbour_valid]=3; |
090 |
091 | } |
092 |
093 | if(x + 2 < n * 2 + 1 && is_closed(maze, x + 2, y)) // downside |
094 | { |
095 | neighbour_valid++; |
096 | neighbour_x[neighbour_valid]=x+2; |
097 | neighbour_y[neighbour_valid]=y; |
098 | step[neighbour_valid]=4; |
099 | } |
100 |
101 | if(neighbour_valid == -1) |
102 | { |
103 | // backtrack |
104 | x_next = backtrack_x[indeks]; |
105 | y_next = backtrack_y[indeks]; |
106 | indeks--; |
107 | } |
108 |
109 | if(neighbour_valid!=-1) |
110 | { |
111 | int randomization = neighbour_valid + 1; |
112 | int random = rand()%randomization; |
113 | x_next = neighbour_x[random]; |
114 | y_next = neighbour_y[random]; |
115 | indeks++; |
116 | backtrack_x[indeks] = x_next; |
117 | backtrack_y[indeks] = y_next; |
118 |
119 | int rstep = step[random]; |
120 |
121 | if(rstep == 1) |
122 | maze[x_next+1][y_next] = PATH; |
123 | else if(rstep == 2) |
124 | maze[x_next][y_next + 1] = PATH; |
125 | else if(rstep == 3) |
126 | maze[x_next][y_next - 1] = PATH; |
127 | else if(rstep == 4) |
128 | maze[x_next - 1][y_next] = PATH; |
129 | visited++; |
130 | } |
131 |
132 | maze_generator(indeks, maze, backtrack_x, backtrack_y, x_next, y_next, n, visited); |
133 | } |
134 | } |
135 |
136 | void print_maze(int maze[MAX][MAX], int maze_size) |
137 | { |
138 | for(int a = 0; a < maze_size * 2 + 1; a++) |
139 | { |
140 | for(int b = 0; b < maze_size * 2 + 1; b++) |
141 | { |
142 | if(maze[a][b] == WALL) |
143 | printf("#"); |
144 | else |
145 | printf(" "); |
146 | } |
147 | printf("\n"); |
148 | } |
149 | } |
150 |
151 | int is_closed(int maze[MAX][MAX], int x, int y) |
152 | { |
153 | if(maze[x - 1][y] == WALL |
154 | && maze[x][y - 1] == WALL |
155 | && maze[x][y + 1] == WALL |
156 | && maze[x + 1][y] == WALL |
157 | ) |
158 | return 1; |
159 |
160 | return 0; |
161 | } |
0 Comments
