Maze creation in C#

maze_19x19

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:

image

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.

image

 Code with sample project

 Just the DLL

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

More sample mazes  Smiley

11 x 11 maze_11x11           13 x 13 maze_13x13          15 x 15 maze_15x15

image

Tags: ,

16 Responses to “Maze creation in C#”

  1. interested Says:

    Ok, the start tile is at 1,1 - but how do you know where the end tile is?

  2. admin Says:

    That's up to you to decide :)
    If you want to, you could remove an edge tile on the opposite side and call it the exit.
    You could also just choose any arbitrary tile inside the maze, which isn't a wall.

    /Jake

  3. interested Says:

    Well you would normally want the dead end that is farther away from the start. Since the algorithm knows when it's at a dead end, maybe it could store the distance travelled in each case.

    I'll check the source anyway. Thanks.

  4. admin Says:

    That's not a bad approach, but it has the weakness that the dead end at the point with the longest path to it, might be on the middle of the board. If that is what you want, then I could definitely implement that, but I think of a maze as a "walk-in-find-the-way-out" challenge, so for me the target would logically be an "exit" out of the maze. I am guessing the objective in the game you are making is "find-the-hidden-place-in-here" - am I right?

    Kind regards - Jakob

  5. interested Says:

    Good points there. I'll consider that. My main purpose is to force the player to walk through most of the maze, so that maps take a while to complete.

    Cheers

  6. admin Says:

    I've updated the code so you can get the furthest point from the start from the MazeCreator object after each time you've created a maze :)

  7. interested Says:

    Awesome! Thank you

  8. admin Says:

    You're most welcome - thanks for the suggestion! :)

  9. Milor Says:

    Great!

    Its posible extract to .txt

    W = Wall
    E = Excaved
    S = Start
    F = furtest point

  10. Milor Says:

    I am downloading Code with sample project and rewrite, run perfect.

    Thank you!

  11. admin Says:

    Great to hear it was useful for you!
    You're welcome :)

  12. admin Says:

    Yup - I'll add some code to dump the maze to a txt file during this week :)
    Thank you for the suggestion!

    Kind regards - Jakob

  13. admin Says:

    Hi Milor :)

    If you look at the MazeCreator.ToString() method, you can see that it does almost what you want: convert the maze's state to a string.
    If you change the output to what you want for the different values, you should have a multiline String representation of your maze, which you can then save using File.WriteAllText.

    Kind regards - Jakob

  14. carlos Says:

    Excelente, funciona como lo necesitaba... muchas gracias

  15. ohiovr Says:

    Thanks for this example. I'm teaching my nephew how to program with unity and this will really help. I converted it to run in unity obviously but it was such an easy conversion and does precisely what I want. Excellent work

  16. admin Says:

    Very glad to hear it was of use to you 👍👍😊

Leave a Reply