How to implement Depth First Search algorithm for maze generation

In my post last week about the Microsoft maze game tutorial I touched briefly on the method I used to generate the maze, but I didn't go into a lot of detail. Mostly I just thought the whole thing was way too cool to necessitate an in depth look. But on further consideration I thought I could be pretty fun to explain exactly what the program is doing.


 To start with, I defined a couple of enums for direction and cell types:


        enum cellType
        {
            NewWall,
            FinalWall,
            NewPass,
            FinalPass,
            Start,
            Finish
        };

        enum direction
        {
            North,
            South,
            East,
            West,
            Empty
        };


Before I get into the body of the code, I just want to preempively apologize to anyone used to seeing pretty formatting on source code snippets.  I haven't looked into how to get that look in Blogger, when I figure it out I'll seriously consider fixing this post.  The basic logic behind the depth first algorithm goes something like this:


Fill all cells with new walls.
Select starting position and mark it new passage.
While(!done)
{
   Check if adjacent cells are new walls
   If new walls found then
   {
      Select found cell at random, mark as new passage
   }
   else
   {
      Backtrack to nearest new passage
      if no adjacent new passage then
      {
         done = true
      }
   }
}
Mark start and finish cells


Here a "cell" is every [odd x, odd y] cell in a two dimensional array. The size of the array is determined by dividing the dimensions of the panel component by 20 (the labels are 20x20 px).  
  
  
private void FillWithLabels()  
{
   // cellx and celly are the working coordinates, max_x and max_y are the
   // bounds of the grid
   int cellx = 1, celly = 1,
       max_x = (panel1.Width / 20), max_y = (panel1.Height / 20);

   cellType[,] grid = new cellType[max_x,max_y];

   List<direction> validMove = new List<direction>();

   direction previousMove = direction.Empty;
   direction backTrack = direction.Empty;

   Random randomizer = new Random();
   bool done = false;

   //fill panel with labels. 
   for (int i = 0; i < max_x; i++)
   {
      for (int j = 0; j < max_y; j++)
      {
          Label tempLabel = new Label();
          tempLabel.Parent = panel1;

          int x = i * 20;
          int y = j * 20;
          Point loc = new Point(x, y);
          tempLabel.AutoSize = false;
          tempLabel.Size = new Size(20, 20);
          tempLabel.Location = loc;
          tempLabel.BackColor = Color.Blue;
          tempLabel.Name = (i.ToString() + "_" + j.ToString());
          //tempLabel.Text = tempLabel.Name;
       }
   }
   panel1.Refresh();


At this point, we have initiallized all the necessary variables and created a grid of square blue labels filling our panel. On a side note, the first version of this program didn't draw as the maze was constructed. Instead, it created the maze within the two diminsional array and then drew it all at once. Much more efficient, but since the game is super boring at least watching the maze generation process adds something interesting to the proceedings. To facilitate the necessary modification to extant labels, each label was given a name in the form of "{x coord}_{y coord}" where x and y coord are the grid coordinates for that label.

Now that the stage is set, we can start creating the maze. First, the starting grid coord is marked as new passage:

   //start creating maze, create starting tile and change label color
   grid[cellx, celly] = cellType.NewPass;
   panel1.Controls.Find((cellx).ToString() + "_" + (celly).ToString(), true)[0].BackColor = Color.Yellow;
   panel1.Refresh();

Next we start generating the maze proper. This can be done in a loop because state information is stored in the maze itself. I mention this because some implementations of the depth first search use a recursive process. The first thing the while loop does is mark all the NewWall cells as FinalWall. In all honesty, I probably could have skipped the whole NewWall vs FinalWall business, but whatever:

   while (!done)
   {
      panel1.Refresh();

      // mark the surrounding walls as final
      for (int i = -1; i <= 1; i++)
      {
         for (int j = -1; j <= 1; j++)
         {
         // make sure target cell is not out of bounds (thus null)
         if(cellx + i >= 0 && cellx + i <= max_x-1 && celly + j >= 0 
              && celly + j <= max_y - 1)
            {
               //if wall is new, make it final
               if (grid[cellx + i, celly + j] == cellType.NewWall)
               {
                  grid[cellx + i, celly + j] = cellType.FinalWall;
                  //change corresponding label color
                  panel1.Controls.Find((cellx + i).ToString() + "_" + (celly + j).ToString(), true)[0].BackColor = Color.Black;
               }
             }
          }
      }


Now we want a list of moves that are valid from the current grid coordinate, so we look in each direction, and if that is a valid move we add it to the list.

     
      // look for valid moves. Target direction should be in-bounds, 
      // not the direction we just came from, and should be 
      // unvisited (NewWall type)
      if (cellx - 2 >= 0)
      {
         if ((previousMove != direction.East || previousMove == direction.Empty)
               && grid[cellx - 2, celly] == cellType.NewWall)
            validMove.Add(direction.West);
      }

      if (cellx + 2 <= max_x - 1)
      {
         if ((previousMove != direction.West || previousMove == direction.Empty) 
               && grid[cellx + 2, celly] == cellType.NewWall)
            validMove.Add(direction.East);
      }

      if (celly + 2 <= max_y - 1)
      {
         if ((previousMove != direction.North || previousMove == direction.Empty)
               && grid[cellx, celly + 2] == cellType.NewWall)
            validMove.Add(direction.South);
      }

      if (celly - 2 >= 0)
      {
         if ((previousMove != direction.South || previousMove == direction.Empty)
               && grid[cellx, celly - 2] == cellType.NewWall)
            validMove.Add(direction.North);
      }

Now we check if we have any potiential moves.  If we do, then we pick one at random, move to that cell and break down the wall between the cells. The new cell and broken wall are marked "NewPass".  If no valid moves are found, then we need to backtrack.


      //if validMove > 0 == true, then we found a valid move!
      if (validMove.Count > 0)
      {
         // randomly select a valid move from those available
         direction Move = validMove[randomizer.Next(0,validMove.Count)];

         // select next cell based on chosed direction, 
         // knock down wall between cells
         switch (Move)
         {
            case direction.West:

            //intermediate passage is cleared
            grid[cellx - 1, celly] = cellType.NewPass;
            //change corresponding label color
            panel1.Controls.Find((cellx - 1).ToString() + "_" + (celly).ToString(), true)[0].BackColor = Color.Yellow;

            cellx = cellx - 2;

            //target cell is cleared
            grid[cellx, celly] = cellType.NewPass;
            //change target label color
            panel1.Controls.Find((cellx).ToString() + "_" + (celly).ToString(), true)[0].BackColor = Color.Yellow;

            previousMove = direction.West;
            break;
            case direction.East:

            //intermediate passage is cleared
            grid[cellx + 1, celly] = cellType.NewPass;
            //change corresponding label color
            panel1.Controls.Find((cellx + 1).ToString() + "_" + (celly).ToString(), true)[0].BackColor = Color.Yellow;

            cellx = cellx + 2;

            //target cell is cleared
            grid[cellx, celly] = cellType.NewPass;
            //change target label color
            panel1.Controls.Find((cellx).ToString() + "_" + (celly).ToString(), true)[0].BackColor = Color.Yellow;

            previousMove = direction.East;
            break;
            case direction.South:

            //intermediate passage is cleared
            grid[cellx, celly + 1] = cellType.NewPass;
            //change corresponding label color
            panel1.Controls.Find((cellx).ToString() + "_" + (celly + 1).ToString(), true)[0].BackColor = Color.Yellow;

            celly = celly + 2;

            //target cell is cleared
            grid[cellx, celly] = cellType.NewPass;
            //change target label color
            panel1.Controls.Find((cellx).ToString() + "_" + (celly).ToString(), true)[0].BackColor = Color.Yellow;

            previousMove = direction.South;
            break;
            case direction.North:

            //intermediate passage is cleared
            grid[cellx, celly - 1] = cellType.NewPass;
            //change corresponding label color
            panel1.Controls.Find((cellx).ToString() + "_" + (celly - 1).ToString(), true)[0].BackColor = Color.Yellow;

            celly = celly - 2;

            //target cell is cleared
            grid[cellx, celly] = cellType.NewPass;
            //change target label color
            panel1.Controls.Find((cellx).ToString() + "_" + (celly).ToString(), true)[0].BackColor = Color.Yellow;

            previousMove = direction.North;
            break;
         }

         // reset validMove;
         validMove.Clear();
      } 


Eventually the maze generation process will encounter a dead end, i.e. no valid moves available. When it reaches a dead end, the program needs to follow the passage it just created backward until it finds a valid move. As it backs out, it marks the passages as FinalPass. If we can't back up anymore, it's because we are back at the beginning and the process is finished.

      //No valid moves found, time to backtrack
      else
      {
         //find the direction we came from. first check to make sure
         // we stay in the range of the array
         if (cellx - 1 >= 0)
         {
            if (grid[cellx - 1, celly] == cellType.NewPass)
               backTrack = direction.West;
         }

         if (cellx + 1 <= max_x - 1)
         {
            if (grid[cellx + 1, celly] == cellType.NewPass)
               backTrack = direction.East;
         }

         if (celly + 1 <= max_y - 1)
         {
             if (grid[cellx, celly + 1] == cellType.NewPass)
                backTrack = direction.South;
         }

         if (celly - 1 >= 0)
         {
             if (grid[cellx, celly - 1] == cellType.NewPass)
                backTrack = direction.North;
         }

         //mark this cell final
         grid[cellx, celly] = cellType.FinalPass;
         //change label color
         panel1.Controls.Find((cellx).ToString() + "_" + (celly).ToString(), true)[0].BackColor = Color.White;

         // move in backtrack location, mark intermediate passage as final
         switch (backTrack)
         {
            case direction.West:
               grid[cellx - 1, celly] = cellType.FinalPass;
               //change label color
               panel1.Controls.Find((cellx-1).ToString() + "_" + (celly).ToString(), true)[0].BackColor = Color.White;
               cellx = cellx - 2;
               break;

           case direction.East:
               grid[cellx + 1, celly] = cellType.FinalPass;
               //change label color
               panel1.Controls.Find((cellx+1).ToString() + "_" + (celly).ToString(), true)[0].BackColor = Color.White;
               cellx = cellx + 2;
               break;

           case direction.South:
               grid[cellx, celly + 1] = cellType.FinalPass;
               //change label color
               panel1.Controls.Find((cellx).ToString() + "_" + (celly+1).ToString(), true)[0].BackColor = Color.White;
               celly = celly + 2;
               break;
            
           case direction.North:
               grid[cellx, celly - 1] = cellType.FinalPass;
               //change label color
               panel1.Controls.Find((cellx).ToString() + "_" + (celly-1).ToString(), true)[0].BackColor = Color.White;
               celly = celly - 2;
               break;

               default:
               //nowhere to backtrack? we're done!
               done = true;
               break;
            }
            backTrack = direction.Empty;
            previousMove = direction.Empty;
            // end of "else"
         }
         // end of "while"
      }
   //string msg = "Finished in " + count.ToString() + " moves.";
   //MessageBox.Show(msg);


The last few bits are related to the tutorial itself, so they mark out a starting and ending area and add event listeners to the labels:

   //Set start and finish areas
   grid[0, 0] = cellType.Start;
   grid[1, 0] = cellType.Start;
   grid[0, 1] = cellType.Start;
   grid[1, 1] = cellType.Start;
   panel1.Controls.Find("0_0", true)[0].BackColor = Color.Green;
   panel1.Controls.Find("1_0", true)[0].BackColor = Color.Green;
   panel1.Controls.Find("0_1", true)[0].BackColor = Color.Green;
   panel1.Controls.Find("1_1", true)[0].BackColor = Color.Green;

   grid[max_x - 1, max_y - 1] = cellType.Finish;
   grid[max_x - 2, max_y - 1] = cellType.Finish;
   grid[max_x - 1, max_y - 2] = cellType.Finish;
   grid[max_x - 2, max_y - 2] = cellType.Finish;
   panel1.Controls.Find((max_x - 2).ToString() + "_" + (max_y - 2).ToString(), true)[0].BackColor = Color.Red;

   // add event listeners to walls and finish square
   for (int i = 0; i < max_x; i++)
   {
      for (int j = 0; j < max_y; j++)
      {
         switch (grid[i, j])
         {
            case cellType.FinalWall:
               panel1.Controls.Find(i.ToString() + "_" + j.ToString(), true)[0].MouseEnter += new EventHandler(HitWall);
               break;
            
            case cellType.Finish:
               panel1.Controls.Find(i.ToString() + "_" + j.ToString(), true)[0].MouseEnter += new EventHandler(FinishMaze);
               break;
         }
      }
   }
}      


And that is pretty much it. The rest of the code is pretty much the microsoft tutorial code verbatim, so I won't repeat it here, but the maze generation is the cool part anyway.  I guess if I wanted to make it super obnoxious I could add a pacman-esque waka waka sound that plays while the maze is generated, but I think I've beat this program to death already. You can't polish a turd, and there is no amount of decoration that will make the "don't touch the walls with the mouse pointer" maze game remotely fun.