Generating mazes

In an attempt to create a video game, I came across the problem of creating a maze (see figure).

Like in most games you need to go from point A to point B via a number of corridors.

Now my problem was to find a good algorithm to create mazes, and after some research on the Internet I found several of them (see wikipedia for an explanantion) .

My first attempt was to use the simpelst algorithm , being the Depth-first search algorithm.

The algorithm goes as follows :

1, Initialize a grid full of walls
2, Start at a particular cell and call it the "exit."
3, Mark the current cell as visited, and get a list of its neighbors. For each neighbor, starting with a randomly selected neighbor:
If that neighbor hasn't been visited, remove the wall between this cell and that neighbor, and then recurse with that neighbor as the current cell.

So to implement this , I'll developed a recursive method (uses more memory and in a later state I can use a stack to avoid recursion).

In objective-C the implementation looks like this (very premature source code of the maze creation program (with animated GUI) can be downloaded here) :

step 1 : Initialize a grid

for ( x = 0 ; x <>
{

for ( y = 0 ; y <>
{
cell = [MazeCell fullCell] ;
[cell x: x ] ;
[cell y: y] ;
[maze atX: x atY: y put: cell]
}
}

A MazeCell is an object that contains four 'wall's' (a wall is here a BOOL that is true or false dending on the fact if the wall is their or not.

Step 2 : the actual generation of the maze

- (void) walkCells: (MazeCell *) aCell
{
int x ;
int y ;

NSMutableSet *neighbors ;
MazeCell *cell1 ;
NSEnumerator *enumerator ;

[aCell visited: YES] ;


x = [aCell x];
y = [aCell y];

neighbors = [NSMutableSet set] ;
if ( x > 0 ) [neighbors addObject: [maze atX: (x-1) atY: y ]] ;

if ( y > 0 ) [neighbors addObject: [maze atX: (x) atY: (y-1) ]] ;

if ( x <>

if ( y <>


enumerator = [ neighbors objectEnumerator] ;

while ( (cell1 = [enumerator nextObject] ) != nil )
{

if ( [cell1 visited] == NO )
{
if ( [cell1 x] == (x-1) )
{
[cell1 rightWall: NO] ;
[aCell leftWall: NO] ;
}

if ( [cell1 x] == (x+1) )
{
[aCell rightWall: NO] ;
[cell1 leftWall: NO] ;
}
if ( [cell1 y] == (y-1) )
{
[cell1 upWall: NO] ;
[aCell downWall: NO] ;
}

if ( [cell1 y] == (y+1) )
{
[aCell upWall: NO] ;
[cell1 downWall: NO] ;
}


[self walkCells: cell1] ;

}
}


}


A little explanation is needed here , in the beginning of the method you see that I build a list of the neighbours of cell.
Now it is important that the list is build in a random order, so therefor I use a NSMutableSet as datastructure. The position in the set depends on the hash that is generated for the object that is inserted.
In my case these objects are of type MazeCell.
So the trick to get them in random order was to implement the hash method on MazeCell and this hash method just returns a random number.