Perfect Maze Generator

Posted: March 29, 2009 in C/C++, Programming
Tags: , ,

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.

create a CellStack (LIFO) to hold a list of cell locations
set TotalCells = number of cells in grid
choose a cell at random and call it CurrentCell
set VisitedCells = 1

while VisitedCells < TotalCells find all neighbors of CurrentCell with all walls intact if one or more found choose one at random knock down the wall between it and CurrentCell push CurrentCell location on the CellStack make the new cell CurrentCell add 1 to VisitedCells else pop the most recent cell entry off the CellStack make it CurrentCell endIf endWhile [/sourcecode] Here it this..the source code : [sourcecode language='java'] #include
#include
#include
#include

#define MAX 61 // 30 * 2 + 1
#define CELL 900 // 30 * 30
#define WALL 1
#define PATH 0

void init_maze(int maze[MAX][MAX]);
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);
void print_maze(int maze[MAX][MAX], int maze_size);
int is_closed(int maze[MAX][MAX], int x, int y);

int main(void)
{
srand((unsigned)time(NULL));

int size;
int indeks = 0;
printf(“MAZE CREATOR\n\n”);
printf(“input (0 ~ 30): “);
scanf(“%d”, &size);
printf(“\n”);
int maze[MAX][MAX];
int backtrack_x[CELL];
int backtrack_y[CELL];

init_maze(maze);

backtrack_x[indeks] = 1;
backtrack_y[indeks] = 1;

maze_generator(indeks, maze, backtrack_x, backtrack_y, 1, 1, size, 1);
print_maze(maze, size);

getch();
return 0;
}

void init_maze(int maze[MAX][MAX])
{
for(int a = 0; a < MAX; a++) { for(int b = 0; b < MAX; b++) { if(a % 2 == 0 || b % 2 == 0) maze[a][b] = 1; else maze[a][b] = PATH; } } } 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) { if(visited < n * n) { int neighbour_valid = -1; int neighbour_x[4]; int neighbour_y[4]; int step[4]; int x_next; int y_next; if(x - 2 > 0 && is_closed(maze, x – 2, y)) // upside
{
neighbour_valid++;
neighbour_x[neighbour_valid]=x – 2;;
neighbour_y[neighbour_valid]=y;
step[neighbour_valid]=1;
}

if(y – 2 > 0 && is_closed(maze, x, y – 2)) // leftside
{
neighbour_valid++;
neighbour_x[neighbour_valid]=x;
neighbour_y[neighbour_valid]=y – 2;
step[neighbour_valid]=2;
}

if(y + 2 < n * 2 + 1 && is_closed(maze, x, y + 2)) // rightside { neighbour_valid++; neighbour_x[neighbour_valid]=x; neighbour_y[neighbour_valid]=y + 2; step[neighbour_valid]=3; } if(x + 2 < n * 2 + 1 && is_closed(maze, x + 2, y)) // downside { neighbour_valid++; neighbour_x[neighbour_valid]=x+2; neighbour_y[neighbour_valid]=y; step[neighbour_valid]=4; } if(neighbour_valid == -1) { // backtrack x_next = backtrack_x[indeks]; y_next = backtrack_y[indeks]; indeks--; } if(neighbour_valid!=-1) { int randomization = neighbour_valid + 1; int random = rand()%randomization; x_next = neighbour_x[random]; y_next = neighbour_y[random]; indeks++; backtrack_x[indeks] = x_next; backtrack_y[indeks] = y_next; int rstep = step[random]; if(rstep == 1) maze[x_next+1][y_next] = PATH; else if(rstep == 2) maze[x_next][y_next + 1] = PATH; else if(rstep == 3) maze[x_next][y_next - 1] = PATH; else if(rstep == 4) maze[x_next - 1][y_next] = PATH; visited++; } maze_generator(indeks, maze, backtrack_x, backtrack_y, x_next, y_next, n, visited); } } void print_maze(int maze[MAX][MAX], int maze_size) { for(int a = 0; a < maze_size * 2 + 1; a++) { for(int b = 0; b < maze_size * 2 + 1; b++) { if(maze[a][b] == WALL) printf("#"); else printf(" "); } printf("\n"); } } int is_closed(int maze[MAX][MAX], int x, int y) { if(maze[x - 1][y] == WALL && maze[x][y - 1] == WALL && maze[x][y + 1] == WALL && maze[x + 1][y] == WALL ) return 1; return 0; } [/sourcecode] source : http://home.att.net/~srschmitt/script_maze_generator.html
http://www.mazeworks.com/mazegen/mazetut/index.htm

Comments
  1. Toni says:

    Thank you, I looking for this.
    But, I used opengl to display my maze. Can u help me solve perfect maze using opengl?

    • letrungkien7 says:

      The Maze generator code is irrelevant to how to display it in opengl.
      This code did help you solve perfect maze, using opengl or not.
      You can use this code, get the output and just learn how to draw lines in opengl, you will be fine.
      I guess you only need function to display cells.
      I know some opengl stuffs, if you still struggle with it, I may help.

  2. fulgor says:

    Which licence is your source code for maze generation ?

  3. EvilNando says:

    why are u setting the size to (size * 2 + 1)?

  4. Tom Do says:

    How would you be able to deploy a DFS or BFS algorithm to find the path through the maze?

    • azer89 says:

      yes of course, you can use the same technique to find the solution path

      • Tom Do says:

        Oh i meant like having the maze already generated, then using the BFS algorithm to solve the already generated maze. I am really new to c++ and i was just wondering even if this question seems quite newb. sorry if this is a really obivous question.

  5. Tom Do says:

    What i mean is that, the BFS or DFS algorithm display the quickest path from start to finish. How would that be implemented with the maze already generated from this.

  6. Tom Do says:

    haha nvm! i got it :D thanks for ur help!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s