Depth First Maze Generator (and solver)

Today I brought home my baby after a little over 4 months in the hospital and I also finished this maze generator while mama fed her. :)

I've been considering creating a resource out of this but I don't have the time to take it further and create a more full featured implementation. I also considered running a little contest to see who could create the fastest solver in script only but, again, due to lack of time, I decided to just put it out in the forums.

What it is?

This is a depth first maze generator and solver based on the pseudo code on this page. It will create a perfect maze from a t2dTileLayer. The maze is always solve-able via only one path from any two cells (hence, perfect maze) in the maze. The depth first algorithm is perfect for this kinda thing.

The solver will begin at the start cell specified by the user, work its way through the maze to the goal and if it meets a dead end, it will backtrack to the last intersection and go on its way again. The beauty of the depth first approach using a stack is that the backtrack code is, well automatic. Pretty cool!

The code is rather long, so I'm only going to post the juicy parts and a link to the whole project. There is some fancy bit shifting going on to draw the right borders on the maze and some in the solver as well to find open neighboring cells.

When you run the project, green is the path, red is backtracked and black is uncharted territory.

I hope someone finds it useful, fun, whatever... Do with it as you please.

Project files:

Download the TGB 1.7.5 project here.

Cool solver code:

My favorite part was the solver, so I'll post that here. :)

function Maze::solveMaze(%this, %start, %goal)
{
   $solveStartTime = getRealTime();
   echo("Solving Maze.");

   %maxX = %this.getTileCountX();
   %maxY = %this.getTileCountY();
   %this.solved.totalCells = %maxX * %maxY;
   
    //create a stack to store cells   
   %this.solved.cellStack = new ScriptObject(Stack);   
   
   %this.solved.currentCell = %start;
   
   %this.solved.visitedCells = 1;
   
   while(%this.solved.currentCell !$= %goal)
   {     
      %this.solved.neighbors = new ScriptObject(Stack);
      
      %curX = getWord(%this.solved.currentCell, 0);
      %curY = getWord(%this.solved.currentCell, 1);
      
      //mark cell visited       
      %this.solved.setStaticTile(%curX, %curY, greenBoxImageMap, 0);     
      %this.solved.setTileCustomData(%curX, %curY, 1);      
      
      //find all neighbors of CurrentCell that are accessible
      //making sure not to overflow the tilemap     
      if( %curX > 0 )
      {
         //if the cell to the left has no right wall
         if( ( %this.walls( %curX - 1, %curY ) & 2 ) == 0 && 
            %this.solved.getTileCustomData(%curX - 1, %curY) != 1)
         {
            %newCell = %curX - 1 SPC %curY;
            %this.solved.neighbors.push(%newCell);
         }
      }
      
      if( %curX < %maxX - 1 )
      {
         //if the cell to the right has no left wall
         if( ( %this.walls( %curX + 1, %curY ) & 8 ) == 0 && 
            %this.solved.getTileCustomData(%curX + 1, %curY) != 1)
         {
            %newCell = %curX + 1 SPC %curY;
            %this.solved.neighbors.push(%newCell);
         }
      }
            
      if( %curY > 0 )
      {
         //if the cell above has no bottom wall
         if( ( %this.walls( %curX, %curY - 1) & 4 ) == 0 && 
            %this.solved.getTileCustomData(%curX, %curY - 1) != 1)
         {
            %newCell = %curX SPC %curY - 1;
            %this.solved.neighbors.push(%newCell);
         }
      }
      
      if( %curY < %maxY - 1 )
      {
         //if the cell below has no top wall
         if( ( %this.walls( %curX, %curY + 1 ) & 1 ) == 0 && 
            %this.solved.getTileCustomData(%curX, %curY + 1) != 1)
         {
            %newCell = %curX SPC %curY + 1;
            %this.solved.neighbors.push(%newCell);
         }
      }
      
      //if one or more found 
      if( %this.solved.neighbors.length() > 0 )
      {
         //get the next neighbor
         %tempCell = %this.solved.neighbors.pop();

         //push CurrentCell location on the CellStack  
         %this.solved.cellStack.push(%this.solved.currentCell);

         //make the new cell CurrentCell  
         %this.solved.currentCell = %tempCell;
      } 
      else
      {
         %this.solved.setStaticTile(getWord(%this.solved.currentCell, 0), getWord(%this.solved.currentCell, 1), redBoxImageMap, 0);
         %this.solved.currentCell = %this.solved.cellStack.pop();         
      }      
   }   
   
   echo("Solved in" SPC getRealTime() - $solveStartTime SPC "ms.");   
}

See guys... TorqueScript is still cool! Damn you C#!!!

`Patrick