Maze Generator in C#

I was recently talking with Marc about some potentially interesting challenges in robotics programming that we could implement using the Microsoft Robotics Studio 1.5 Simulator.  We discussed a number of scenarios that ranged from simple to insanely hard.  One of the more approachable challenges he proposed involved having a simple, autonomous robot navigate through a maze. 

This has actually been explored within MSRS 1.5 by the community to various degrees.  Here is an impressive sample from Ben Axelrod that let's you load any image file and construct a 3D environment from it (including mazes if the image is that of a maze).  Trevor Taylor has expanded upon that sample and it's really quite impressive.  But while there are many interesting samples available for MSRS 1.5 which can be used to construct 3D environments from files, I didn't find anything that actually generated a maze. 

Maze Explorer in Windows Forms

I thought about the problem a few nights ago and decided it would be fun to develop an automated maze generator in C# and then to build a Maze Simulator sample for MSRS 1.5 that constructs this maze using 3D shapes within the Robotics Studio Simulator. I implemented a maze generator in a couple of hours using a depth-first search algorithm and very basic data structures in C#.  I built a class library for the maze itself and a viewer as a Windows Forms application. 

Some screen shots are below:

Maze Creation Algorithm

The depth-first-search algorithm I used goes something like this:

1. Start at the exit cell (chosen at random on the edge)
2. Set the current cell to visited.  For each neighbor, starting with a randomly selected neighbor:
   1. If this neighbor has not been visited, remove the wall between the current cell and the this neighbor
   2. Recursively call the Maze routine with this neighbor as the new current cell

I admit the code has not been optimized for execution time, space, or efficiency-- I just used a 2-dimensional array that represented walls with bit flags.  My algorithm also uses the stack, so it's sufficient for creating a 150x150 maze or so will work in release mode, but not much larger.  I could have stored backtracking in the maze output to remove the stack overflow problem in large mazes, but that's left as a future exercise.

Windows Form Client

I built a simple Windows Form client that display the maze bitmap that was generated.  I basically display an image inside a PictureBox, and I render to the image to reduce redraws.  I used rectangles for all walls because the 2D layout needs to map into the MSRS 1.5 3D Simulation environment.  Rendering in 2D with lines will not translate well into this 3D world.  There are some special cases in rendering in 2D which I handle when drawing certain walls, such as elongating them to compensate for empty corners, but this is for the rending only.

Next Steps

I'm working on implementing a Maze Simulation project for the MSRS 1.5 environment now.  I've basically taken one of the Simulation Tutorials and stripped it down for use.  I plan on adding the Maze class library to the project and then rendering the maze in 3D instead of 2D.  This will be a little tedious, especially given the duality of the visual and the physics engine layer.  When this is done, I'll add a virtual robot instance to the maze and allow it to navigate via the dashboard.

Comments

• Anonymous
  January 10, 2008
  PingBack from http://msdnrss.thecoderblogs.com/2008/01/10/maze-generator-in-c/

• Anonymous
  January 11, 2008
  Are you considering releasing the source code for the maze generator? I'd love a chance to play around with that code.

• Anonymous
  January 11, 2008
  In my last post , I described the maze generator I developed in C#.  This was trivial to build as

• Anonymous
  January 11, 2008
  Yes, my plan is to release the source on Codeplex.  I have some clean-up to do before I am ready to release it, but only minor stuff.  I am also checking with the Robotics Team before I share it out -- they might want to expand on it and make it a sample or something.  In that case, the source would still be there, but under their samples directory and not Codeplex.  -Scott

• Anonymous
  January 11, 2008
  In my last post , I described the maze generator I developed in C#.  This was trivial to build as

• Anonymous
  January 12, 2008
  The comment has been removed