Perfect Maze Generator

Unknown Reply 10:06 AM

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.
01create a CellStack (LIFO) to hold a list of cell locations
02set TotalCells = number of cells in grid
03choose a cell at random and call it CurrentCell
04set VisitedCells = 1
05 
06while 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 
18endWhile
Here it this..the source code :
view sourceprint?
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 
011void init_maze(int maze[MAX][MAX]);
012void maze_generator(int indeks, int maze[MAX][MAX], int backtrack_x[CELL], int bactrack_y[CELL], int x, int y, int n, int visited);
013void print_maze(int maze[MAX][MAX], int maze_size);
014int is_closed(int maze[MAX][MAX], int x, int y);
015 
016int 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 
042void 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 
056void 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 
136void 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 
151int 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}

Related Posts

Programming 668957514931006805
Comments
0 Comments
Facebook Comments by Media Blogger

Post a Comment

Newer Post Older Post Home item

Search

Ikuti Channel Youtube Aku Yaa.. Jangan Lupa di subscribe. Terima kasih.

Popular Posts

Translate