xnaFan's Blog

A small maze generator for use in .net.

I am currently in the process of learning how to code 3D graphics in XNA 4.0.  It’s a lot of fun – and I’ve gotten pretty far with just boxes covered by different textures. However I thought that it would be fun to have a small mazegame – where you’re running around as a bewildered labrat inside the maze. For that I would need to have a random maze generated each time.
So I Googled around, found some tips, and coded a mazegenerator.

After that I took the time to comment the code  and wrap it up. So if you don’t care about the inner workings, you can just add a reference to my DLL and get mazes like this:

//get a MazeCreator ready to make 9x9 mazes that start at 1,1
MazeCreator creator = new MazeCreator(9, 9, new Point(1, 1));
byte[,] maze1 = creator.CreateMaze();
byte[,] maze2 = creator.CreateMaze();
byte[,] maze3 = creator.CreateMaze();

Update - thanks to the anonymous commenter below, you can now get the point in the maze furthest from the starting point:)

If you want to know where the position in the maze that is furthest from the starting point is, you can ask the MazeCreator object after you have created the maze:

//get a MazeCreator ready to make 9x9 mazes that start at 1,1
MazeCreator creator = new MazeCreator(9, 9, new Point(1, 1));
byte[,] maze1 = creator.CreateMaze();
Point furthestPosition = creator.FurthestPoint;

Basics of maze creation

The basic algorithm of creating a maze is as follows (pseudocode)

Start at a valid starting point in the maze - then:
as long as there are still tiles to try
{
  excavate the square we are on
  get all valid neighbors for the curent tile
  if there are any interesting looking neighbors to branch off to(*)
  {
    remember the current tile, by putting it in a list of potential branch-offs (stack)
    move on to a random of the neighboring tiles
  }
  else
  {
    we are at a dead-end
    toss this tile out, thereby returning to the previous tile in the stack
  }
}

 

(*) and they are valid for whatever rules you have for your maze

(Longer writeup here: http://en.wikipedia.org/wiki/Maze_generation_algorithm)

Take a look at the animated gifs on this page, and try to follow along with the steps. I have chosen to use complete tiles for walls, but you could as well have neighboring tiles with a thin wall between in your own implementation.

The MazeCreator also has a MazeChanged event that signals every time a new tile has been excavated. This makes it easy to monitor the progress, either by inspecting the Maze property (byte[,]) or by calling the maze’s ToString representation:

LEGEND

X = wall

.  = tile which still needs to be checked

0 = tile being excavated

* = the point furthest from the beginning

[space] = tile which is done (no more neighbors to check)

The animated gif above was created by using gOODiDEA’s NGif component – here you can see that I subscribe to the event MazeChanged and add a new Bitmap to the AnimatedGifEncoder for every new tile excavated in the maze:

//create mazes of sizes 11 through 22
for (int size = 10; size < 12; size ++ )
{

    //make a new mazecreator
    _creator = new MazeCreator(size, size, new Point(1, 1));

    //figure out a savepath with a logical name containing width and height
    string gifPath = string.Format("c:\\maze_{0:00}x{0:00}.gif", size);

    //output status to console
    Console.WriteLine("Creating " + gifPath);

    //subscribe to the mazechanged event
    //to get a fresh bitmap on every new tile excavated
    _creator.MazeChanged += new EventHandler<PointEventArgs>(CreatorMazeChanged);

    //create the animated GIF
    _gifEncoder = new AnimatedGifEncoder();
    _gifEncoder.SetDelay(100);  //in milliseconds
    _gifEncoder.SetRepeat(0);   //yes - repeat (-1 is NO)
    _gifEncoder.SetQuality(1); //for generating palette - 1 is best, but slowest
    _gifEncoder.Start(gifPath); //where to save the maze
    var maze = _creator.CreateMaze();   //create a maze
    _gifEncoder.Finish();               //end
                
    //show the animated gif    
    Process.Start(gifPath);
    Console.WriteLine("Furthest point: " + _creator.FurthestPoint);
}

Class diagram and code

Here you can download the project which displays how to use the MazeGenerator, and see the public members of the MazeCreator. If you only want random mazes and don’t care for anything else, just grab the zipped DLL.

 Code with sample project

 Just the DLL

 Just the MazeCreator.cs (right-click and choose “Save as…” to save)

More sample mazes 

11 x 11            13 x 13           15 x 15

Tags: c#, Maze creation algorithm

This entry was posted on Saturday, March 17th, 2012 at 22:21 and is filed under Codesamples. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.