Description
Today's project harkens back to days when we used to love mazes... (Okay, I still do, but that's besides the point).
C# Maze Generator and Solver
Introduction
This demo creates and solves mazes using the BreadthFirst and DepthFirst searches. It can be very useful in demonstrating these algorithms.
Background
This article assumes you have a basic knowledge of VC#.NET. A little bit knowledge of pointers, recursion, and GDI+ graphics is appreciated, too.
We will frequently use the Stack and Queue data structures. As reminders, recall that the stack is FirstInLastOut (FILO), while the queue is FirstInFirstOut (FIFO).
The Maze Generation
DepthFirst Search and BreadthFirst Search are very useful approaches in many applications. One of them is creating/solving mazes. To generate a maze with DFS, we have this simple algorithm:
 Have all walls in your maze intact (not broken).
 Choose a random start point, push it into the stack. Call this initial square 'current square'.
 Repeat while the stack is not empty:
 Get list of all neighboring squares to the current square where those neighbors have all their walls intact (unvisited).
 If there are neighbors (i.e., List.Count > 0):
 Choose one of the neighbors at random. Call it 'temp'.
 Knock the wall between 'temp' and the current square.
 Push the current square into the stack.
 Make the current square equals 'temp'.
 Else if there are no neighbors, pop a square from the stack. Make current square equal to it.
After executing this algorithm, you will have a 'prefect maze' which indicates that your maze doesn't have 'dead ends' (i.e., unreachable squares) and has a single solution.
BFS generation is the same except the stack that will be replaced with a queue.
If the generation is with DFS, the program will choose a random wall and knock it, then it moves to the new square. When it reaches an edge (or visited cell), it backs again to the nearest "UNVISITED" square.
When generation is with BFS, program will knock the wall in a way similar to DFS, but BFS uses queue, causing to finish near squares first before the far ones. In contrast, DFS uses stack, which causes it to finish far first then back to near.
The Maze Solving
Again, DFS and BFS have many helpful applications. We will now use them to solve the maze they created, as in the following backtracking algorithm:
Have an empty list for the found path. Call it 'foundPath'.
function DFS(Cell start) : Boolean
if start is equal to the maze end
Add start to 'foundPath'
Mark start as visited
Return true
Else if start is visited already
Return false
Else:
Mark start as visited
For each neighbor of start
If the wall between start and neighbor is knocked
Recursively call DFS function with the neighbor
If the call returns true
Add start to 'foundPath'
Return true
If you reached this point, return falseThis algorithm finds path to the maze end. When it returns true, it adds the current location to 'foundPath', causing all other calls in the stack to return true and add their current locations, too. At finish, we will have a complete list of squares between begin and end.
However, we won't use those recursive versions, since they may cause a
StackOverFlowException
when the calls are too many for that stack. We will instead use the same algorithms but iteratively (i.e., with a loop). Instead of making every recursive call, add its 'start' to 'foundPath', and we will have a pointer to the previous one (as we will see later in the article).The same is about BFS, but again, we will use a queue rather than a stack.
For generation, DFS searches at random. When it reaches an edge, it backs to the nearest (UNVISITED) square and repeats the process until it finds the end.
On the other hand, BFS searches the near squares first. When it reaches an intersection, it divides into two tracks and discovers the near squares. The process is repeated until the end is found.
We have a third method that traverses the maze, the righthand rule. It considers "putting" your right hand on the wall, never leaving it. Even if the way will be longer, you'll absolutely reach the end, or back again to the beginning if there is no end. We are sure, however, that we have a path to the end, since we are using BFS/DFS that gives perfect mazes. In the righthand rule, we will consider only traversing the maze without finding the path.
Let's take a peek at the project (which ran for me the first time with no problems).
The maze generation happens here;
private void backgroundWorker1_DoWork(object sender, DoWorkEventArgs e) { object[] args = e.Argument as object[]; int value = (int)args[0]; bool solving = (bool)args[1]; if (!solving) { this.maze.Generate(this.pictureBoxDraw.Width / value, (this.pictureBoxDraw.Height  value) / value, (int)args[2]); } else { this.maze.Solve((int)args[2]); this.hasSolution = true; } this.pictureBoxDraw.Invalidate(); } public void Generate(int width, int height, int method) { this.working = true; this.initailze(this.maze, width, height); this.mazePen.Dispose(); this.mazePen = this.unitX < 5 ? new Pen(Brushes.WhiteSmoke, 1) : new Pen(Brushes.WhiteSmoke, 3); if (method == 0) this.depthFirstSearchMazeGeneration(this.maze, this.width, this.height); else this.breadthFirstSearchMazeGeneration(this.maze, this.width, this.height); this.working = false; } private void depthFirstSearchMazeGeneration(Cell[,] arr, int width, int height) { Stack<Cell> stack = new Stack<Cell>(); Random random = new Random(); Cell location = arr[this.random.Next(height), this.random.Next(width)]; stack.Push(location); while (stack.Count > 0) { List<Point> neighbours = this.getNeighbours(arr, location, width, height); if (neighbours.Count > 0) { Point temp = neighbours[random.Next(neighbours.Count)]; this.currentGenerateLocation = temp; this.knockWall(arr, ref location, ref arr[temp.Y, temp.X]); stack.Push(location); location = arr[temp.Y, temp.X]; } else { location = stack.Pop(); } Thread.SpinWait(this.Sleep * sleepPeriod); } this.makeMazeBeginEnd(this.maze); }
Once you have a maze, you can then have the program solve it too...
public unsafe void Solve(int method) { this.solving = true; // initialize this.foundPath.Clear(); this.unvisitAll(this.maze); // selecting the method if (method == 0) { if (this.height * this.width < 40 * 80) fixed (Cell* ptr = &this.begin) this.depthFirstSearchSolve(ptr, ref this.end); else this.iterativeDepthFirstSearchSolve(this.begin, this.end); } else if (method == 1) this.breadthFirstSearchSolve(this.begin, this.end); else if (method == 2) this.iterativeRightHandRuleSolve(this.begin, Directions.Right); this.solving = false; }
More episodes in this series
32feet.NET, Bluetooth and .Net Gadgeteer
Related episodes
Successful Software Project Management Styles
Skirmish Mode in Star Trek Legacy for the Xbox 360
ICSE 2011: Conversation with Baris Aktemur
CES 2014: HandsOn with the Panasonic FZM1 7" Rugged Toughpad Tablet
Application Restart and Recovery on Windows 7 in Native Code
The Discussion

I stopped reading the code at:
this
.initailze

nice

have other algorithm?
Comments closed
Comments have been closed since this content was published more than 30 days ago, but if you'd like to continue the conversation, please create a new thread in our Forums, or Contact Us and let us know.