Bringing out the Big Guns

This whole time I have been working on my maze project, I have been avoiding maze creation algorithms. Why? Because I must use a computer and understand the code to create a maze. My personal level of experience in this field is low so I said to myself that I would focus on maze solving rather than maze creation. However, I was looking today and I found someone explaining the basic code for the generation of a perfect maze. It looks like the same format that I used to program the vex bots! I was not completely lost. As such, I decided to share with you all so that you too could relish in my excitement.

The Depth  First Search Algorithm is basically the simplest maze generation algorithm  I figure it be a perfect place for me to start. You begin with a grid like this.

1) Start at a random cell in the grid.  

2) Look for a random neighbor cell you haven't been to yet.  

3) If you find one, move there, knocking down the wall between the cells. If you don't find one, back up to the previous cell.  

4) Repeat steps 2 and 3 until you've been to every cell in the grid.

Simple yes?

The code for this looks like: 

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  

This might make no sense to you, but to me it looks quite familiar. So, thats my adventure for this week. See you all next week. The semester is ending soon so study hard!