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

Thank you, I looking for this.

But, I used opengl to display my maze. Can u help me solve perfect maze using opengl?

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.

Which licence is your source code for maze generation ?

feel free to use my code :)

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

assumed u have a x b size of maze, u need a + 1 and b + 1 of walls, so size of array should be (size * 2 + 1)

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

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

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.

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.

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