Generating A Maze

This small tutorial is really insightful if you want to generate mazes... and believe me, they are definitely worth learning. The concepts are so simple, you'll be creating all sorts of cool maze games in no time - 2D and 3D ones ;)

Starting Simple

As usual, I always like to start simple...and sort of add things for a reason, rather than just show you the code and let you decipher it.

The following givesus a minimal working implementation of a basic window setup.

<?php
// maze.cs

// Well we want our program to be in a GUI window, so we need to inherit
// from Form, which is in the library 'System.Windows.Forms'.
class MazeWindow : System.Windows.Forms.Form
{
    // Our program entry point.
    static void Main()
    {
    }
}

// maze.cs

// Well we want our program to be in a GUI window, so we need to inherit
// from Form, which is in the library 'System.Windows.Forms'.
class MazeWindow : System.Windows.Forms.Form
{
    // Our program entry point.
    static void Main()
    {
    }
}

Screenshot of the basic window - only empty to start with - the starting point - we'll draw the maze inside this window.

Of course that code compiles okay... and is a nice starting point... it doesn't do much yet. But you just wait... Few more lines of code and you'll be drooling on your keyboard :)

Making the Window Appear (Drawing Grid)

Now let's add the code so our window actually appears:

<?php
// maze.cs

class MazeWindow : System.Windows.Forms.Form
{
    static void Main()
    {
        //Application.Run(new MazeWindow());
        //You could put 'using System.Windows.Forms;' at the top of the
        //file, but I thought you could get a better feel this way.
        System.Windows.Forms.Application.Run(new MazeWindow());
    }
}

// maze.cs

class MazeWindow : System.Windows.Forms.Form
{
    static void Main()
    {
        //Application.Run(new MazeWindow());
        //You could put 'using System.Windows.Forms;' at the top of the
        //file, but I thought you could get a better feel this way.
        System.Windows.Forms.Application.Run(new MazeWindow());
    }
}

Compile that code, and run it up... and what do you get? You get a window, but you might notice that the command window stays open until we close our GUI window. To fix this, we need to compile it as a Windows executable:

<?php
C:>csc /t:winexe maze.cs

C:>csc /t:winexe maze.cs

Adding Helper Functions

Now we'll add helper member functions to our maze.cs file:

<?php
// maze.cs

public class MazeWindow : System.Windows.Forms.Form
{
    // Well you usually insert a method function called InitializeCompents
    // here, where you would setup your window...title text, message
    // handlers etc. And gets called from the constructor.
    private void InitializeComponent()
    {
        // Lets set our window, size. 300 by 300 sound okay?..hmmm
        this.Size = new System.Drawing.Size(300,300);
        // And give it a snazzy title, for the menu bar of our window.
        this.Text = "MazeWindow";
    }

    //The constructor! Which of course, is called after Main :) And sets up
    //our lovely window for us.
    public MazeWindow()
    {
        InitializeComponent();
    }

    static void Main()
    {
        System.Windows.Forms.Application.Run(new MazeWindow());
    }
}

// maze.cs

public class MazeWindow : System.Windows.Forms.Form
{
    // Well you usually insert a method function called InitializeCompents
    // here, where you would setup your window...title text, message
    // handlers etc. And gets called from the constructor.
    private void InitializeComponent()
    {
        // Lets set our window, size. 300 by 300 sound okay?..hmmm
        this.Size = new System.Drawing.Size(300,300);
        // And give it a snazzy title, for the menu bar of our window.
        this.Text = "MazeWindow";
    }

    //The constructor! Which of course, is called after Main :) And sets up
    //our lovely window for us.
    public MazeWindow()
    {
        InitializeComponent();
    }

    static void Main()
    {
        System.Windows.Forms.Application.Run(new MazeWindow());
    }
}

Next we need to add graphics functionality to draw our maze:

<?php
// maze.cs

public class MazeWindow : System.Windows.Forms.Form
{
    private void InitializeComponent()
    {
        this.Size = new System.Drawing.Size(300,300);
        this.Text = "MazeWindow";
        
        // The function which will be responsible for painting our window, when it
        // needs it... either because the content has changed...or you covered it
        // up and then returned the focus to it.
        this.Paint += new System.Windows.Forms.PaintEventHandler(this.MazeWindow_Paint);
    }

    // Our member function, which will handle the painting of our window..
    // So each time our window needs repainting, windows calls this function.
    private void MazeWindow_Paint(object sender, System.Windows.Forms.PaintEventArgs e)
    {
        // Well I thought I'd show you a couple of the possibly hundreds and
        // hundreds of .net library functions for graphics. We clear the screen
        // and draw a simple line.
        System.Drawing.Graphics g = e.Graphics;
        g.FillRectangle(System.Drawing.Brushes.Blue, ClientRectangle);
        g.DrawLine(System.Drawing.Pens.Green, 0, 0, 100, 100);
    }

    // ... rest of the code ...
}

// maze.cs

public class MazeWindow : System.Windows.Forms.Form
{
    private void InitializeComponent()
    {
        this.Size = new System.Drawing.Size(300,300);
        this.Text = "MazeWindow";

        // The function which will be responsible for painting our window, when it
        // needs it... either because the content has changed...or you covered it
        // up and then returned the focus to it.
        this.Paint += new System.Windows.Forms.PaintEventHandler(this.MazeWindow_Paint);
    }

    // Our member function, which will handle the painting of our window..
    // So each time our window needs repainting, windows calls this function.
    private void MazeWindow_Paint(object sender, System.Windows.Forms.PaintEventArgs e)
    {
        // Well I thought I'd show you a couple of the possibly hundreds and
        // hundreds of .net library functions for graphics. We clear the screen
        // and draw a simple line.
        System.Drawing.Graphics g = e.Graphics;
        g.FillRectangle(System.Drawing.Brushes.Blue, ClientRectangle);
        g.DrawLine(System.Drawing.Pens.Green, 0, 0, 100, 100);
    }

    // ... rest of the code ...
}

Maze Generation Architecture

We'll split the code into three files:

• maze.cs - Main window code
• generatemaze.cs - Maze generation logic
• mazecell.cs - Individual cell handling

If you need access to the full code - it can be downloaded here: Download Source Code

maze.cs

<?php
// maze.cs
// uses generatemaze.cs, and generatemaze.cs uses mazecell.cs
// so at the command prompt to compile you would need to do:
// C:>csc /t:winexe maze.cs generatemaze.cs mazecell.cs

public class MazeWindow : System.Windows.Forms.Form
{
    GenerateMaze TheMaze = new GenerateMaze();

    private void InitializeComponent()
    {
        // You can change your default window size here
        this.Size = new System.Drawing.Size(300,320);
        this.Text = "MazeWindow";
        this.Paint += new System.Windows.Forms.PaintEventHandler(this.MazeWindow_Paint);
        
        // Initialize our maze, and generate it.
        TheMaze.Create(this.Left, this.Top, 
                      ClientRectangle.Width, ClientRectangle.Height);
        TheMaze.Generate();
    }

    private void MazeWindow_Paint(object sender, System.Windows.Forms.PaintEventArgs e)
    {
        System.Drawing.Graphics g = e.Graphics;
        g.FillRectangle(System.Drawing.Brushes.Blue, ClientRectangle);
        TheMaze.Draw(g);
    }

    // ... rest of the code ...
}

// maze.cs
// uses generatemaze.cs, and generatemaze.cs uses mazecell.cs
// so at the command prompt to compile you would need to do:
// C:>csc /t:winexe maze.cs generatemaze.cs mazecell.cs

public class MazeWindow : System.Windows.Forms.Form
{
    GenerateMaze TheMaze = new GenerateMaze();

    private void InitializeComponent()
    {
        // You can change your default window size here
        this.Size = new System.Drawing.Size(300,320);
        this.Text = "MazeWindow";
        this.Paint += new System.Windows.Forms.PaintEventHandler(this.MazeWindow_Paint);

        // Initialize our maze, and generate it.
        TheMaze.Create(this.Left, this.Top,
                      ClientRectangle.Width, ClientRectangle.Height);
        TheMaze.Generate();
    }

    private void MazeWindow_Paint(object sender, System.Windows.Forms.PaintEventArgs e)
    {
        System.Drawing.Graphics g = e.Graphics;
        g.FillRectangle(System.Drawing.Brushes.Blue, ClientRectangle);
        TheMaze.Draw(g);
    }

    // ... rest of the code ...
}

generatemaze.cs

<?php
// generatemaze.cs
using System.Collections; // used for ArrayList (our Stack)

public class GenerateMaze
{
    // A double array of maze cells, which is empty.
    MazeCell[,] Cells = null;
    MazeCell CurrentCell = null;
    int iDimension;

    public void Create(int x, int y, int width, int height)
    {
        // You can change this to a more detailed map
        int iCellSize = 15;
        // Assume width = height
        iDimension = (width-x)/iCellSize;
        
        // First thing is first, we need to create our array of cells
        Cells = new MazeCell[iDimension, iDimension];
        
        // Lets loop through them all and set some default values
        for(int j=0; j<iDimension; j++)
            for(int i=0; i<iDimension; i++)
            {
                Cells[i,j] = new MazeCell();
                Cells[i,j].Column = j;
                Cells[i,j].Row = i;
                Cells[i,j].iCellSize = iCellSize;
            }
        
        CurrentCell = Cells[0,0];
    }

    // This will generate our maze....
    // Now believe me, at first you'll not see the real magic, of how it starts
    // at the top left corner and generates a random maze path to the bottom
    // right. How it does this, is with the aid of a stack.
    public void Generate()
    {
        int iVisitedCells = 1;
        int iTotalCells = iDimension*iDimension;
        
        Stack CellStack = new Stack();
        CellStack.Clear();
        
        while(iVisitedCells < iTotalCells)
        {
            ArrayList AdjacentCells = GetCellNeighbors(CurrentCell);
            
            if( AdjacentCells.Count > 0 )
            {
                int iRandomCell = MazeCell.TheRandom.Next(0, AdjacentCells.Count);
                MazeCell theCell = (MazeCell)AdjacentCells[iRandomCell];
                CurrentCell.KnockDownWall(theCell);
                CellStack.Push(CurrentCell);
                CurrentCell = theCell;
                iVisitedCells++;
            }
            else
            {
                // Has no walls, so we don't need it :)
                CurrentCell = (MazeCell)CellStack.Pop();
            }
        }
    }

    // It takes a cell that we pass to the function, and we do a bit of smart
    // logic to determine if its within our array boundaries... greater than
    // 0 and less than the array dimensions, iDimension.
    private ArrayList GetCellNeighbors(MazeCell aCell)
    {
        ArrayList Neighbors = new ArrayList();
        
        for(int countRow=-1; countRow<=1; countRow++)
            for(int countCol=-1; countCol<=1; countCol++)
            {
                if( (aCell.Row + countRow < iDimension)&&
                    (aCell.Column + countCol < iDimension)&&
                    (aCell.Row + countRow >= 0)&&
                    (aCell.Column + countCol >= 0)&&
                    ((countCol==0) || (countRow==0))&&
                    (countRow != countCol) )
                {
                    if( Cells[aCell.Row+countRow, aCell.Column+countCol].HasAllWalls() )
                    {
                        Neighbors.Add( Cells[aCell.Row+countRow, aCell.Column+countCol] );
                    }
                }
            }
        
        return Neighbors;
    }

    public void Draw(System.Drawing.Graphics g)
    {
        // We loop through all the cells and draw them
        for(int j=0; j<iDimension; j++)
            for(int i=0; i<iDimension; i++)
            {
                Cells[i,j].Draw(g);
            }
    }
}

// generatemaze.cs
using System.Collections; // used for ArrayList (our Stack)

public class GenerateMaze
{
    // A double array of maze cells, which is empty.
    MazeCell[,] Cells = null;
    MazeCell CurrentCell = null;
    int iDimension;

    public void Create(int x, int y, int width, int height)
    {
        // You can change this to a more detailed map
        int iCellSize = 15;
        // Assume width = height
        iDimension = (width-x)/iCellSize;

        // First thing is first, we need to create our array of cells
        Cells = new MazeCell[iDimension, iDimension];

        // Lets loop through them all and set some default values
        for(int j=0; j<iDimension; j++)
            for(int i=0; i<iDimension; i++)
            {
                Cells[i,j] = new MazeCell();
                Cells[i,j].Column = j;
                Cells[i,j].Row = i;
                Cells[i,j].iCellSize = iCellSize;
            }

        CurrentCell = Cells[0,0];
    }

    // This will generate our maze....
    // Now believe me, at first you'll not see the real magic, of how it starts
    // at the top left corner and generates a random maze path to the bottom
    // right. How it does this, is with the aid of a stack.
    public void Generate()
    {
        int iVisitedCells = 1;
        int iTotalCells = iDimension*iDimension;

        Stack CellStack = new Stack();
        CellStack.Clear();

        while(iVisitedCells < iTotalCells)
        {
            ArrayList AdjacentCells = GetCellNeighbors(CurrentCell);

            if( AdjacentCells.Count > 0 )
            {
                int iRandomCell = MazeCell.TheRandom.Next(0, AdjacentCells.Count);
                MazeCell theCell = (MazeCell)AdjacentCells[iRandomCell];
                CurrentCell.KnockDownWall(theCell);
                CellStack.Push(CurrentCell);
                CurrentCell = theCell;
                iVisitedCells++;
            }
            else
            {
                // Has no walls, so we don't need it :)
                CurrentCell = (MazeCell)CellStack.Pop();
            }
        }
    }

    // It takes a cell that we pass to the function, and we do a bit of smart
    // logic to determine if its within our array boundaries... greater than
    // 0 and less than the array dimensions, iDimension.
    private ArrayList GetCellNeighbors(MazeCell aCell)
    {
        ArrayList Neighbors = new ArrayList();

        for(int countRow=-1; countRow<=1; countRow++)
            for(int countCol=-1; countCol<=1; countCol++)
            {
                if( (aCell.Row + countRow < iDimension)&&
                    (aCell.Column + countCol < iDimension)&&
                    (aCell.Row + countRow >= 0)&&
                    (aCell.Column + countCol >= 0)&&
                    ((countCol==0) || (countRow==0))&&
                    (countRow != countCol) )
                {
                    if( Cells[aCell.Row+countRow, aCell.Column+countCol].HasAllWalls() )
                    {
                        Neighbors.Add( Cells[aCell.Row+countRow, aCell.Column+countCol] );
                    }
                }
            }

        return Neighbors;
    }

    public void Draw(System.Drawing.Graphics g)
    {
        // We loop through all the cells and draw them
        for(int j=0; j<iDimension; j++)
            for(int i=0; i<iDimension; i++)
            {
                Cells[i,j].Draw(g);
            }
    }
}

mazecell.cs

<?php
// mazecell.cs
using System; // used for Random

public class MazeCell
{
    // Each cell, has to keep track of who is is...
    public int Column;
    public int Row;
    
    // And this determines which walls this cell has.
    public int[] Walls = new int[4]{1, 1, 1, 1}; // left, top, right, bottom
    public int iCellSize;

    // Nice simple function, we draw the walls of our cell. Check if it has
    // a wall, then render it... if not we just skip it.
    public void Draw(System.Drawing.Graphics g)
    {
        int iCellSize = 12;
        
        if(Walls[0] == 1) // left
            g.DrawLine(System.Drawing.Pens.Green, Row*iCellSize, Column*iCellSize, 
                      (Row+1)*iCellSize, Column*iCellSize);
        
        if(Walls[1] == 1) // top
            g.DrawLine(System.Drawing.Pens.Green, Row*iCellSize, Column*iCellSize, 
                      Row*iCellSize, (Column+1)*iCellSize);
        
        if(Walls[2] == 1) // right
            g.DrawLine(System.Drawing.Pens.Green, Row*iCellSize, (Column+1)*iCellSize, 
                      (Row+1)*iCellSize, (Column+1)*iCellSize);
        
        if(Walls[3] == 1) // bottom
            g.DrawLine(System.Drawing.Pens.Green, (Row+1)*iCellSize, Column*iCellSize, 
                      (Row+1)*iCellSize, (Column+1)*iCellSize);
    }

    // Simple function that checks if our cell has all 4 walls.. if not then it
    // returns false.
    public bool HasAllWalls()
    {
        for(int i=0; i<4; i++)
        {
            if(Walls[i] == 0)
                return false;
        }
        return true;
    }

    // This is used to pick a random side with a wall.
    private static long Seed = DateTime.Now.Ticks;
    static public Random TheRandom = new Random( (int)MazeCell.Seed);

    public void KnockDownWall(MazeCell theCell)
    {
        int iWallToKnockDown = FindAdjacentWall(theCell);
        Walls[iWallToKnockDown] = 0;
        
        int iOppositeWall = (iWallToKnockDown + 2)%4;
        theCell.Walls[iOppositeWall] = 0;
    }

    // Now if we remove a wall from a cell, we need to remove the parallel 
    // wall on the adjoining cell. As each cell has 4 walls... so if we
    // take a wall down to connect two cells, we need to remove the walls
    // from both cells. This function, returns the wall of the next
    // cell that needs removing.
    public int FindAdjacentWall(MazeCell theCell)
    {
        if( theCell.Row == Row )
        {
            if( theCell.Column < Column)
                return 0; // left
            else
                return 2; // right
        }
        else
        {
            if( theCell.Row < Row )
                return 1; // top
            else
                return 3; // bottom
        }
    }
}

// mazecell.cs
using System; // used for Random

public class MazeCell
{
    // Each cell, has to keep track of who is is...
    public int Column;
    public int Row;

    // And this determines which walls this cell has.
    public int[] Walls = new int[4]{1, 1, 1, 1}; // left, top, right, bottom
    public int iCellSize;

    // Nice simple function, we draw the walls of our cell. Check if it has
    // a wall, then render it... if not we just skip it.
    public void Draw(System.Drawing.Graphics g)
    {
        int iCellSize = 12;

        if(Walls[0] == 1) // left
            g.DrawLine(System.Drawing.Pens.Green, Row*iCellSize, Column*iCellSize,
                      (Row+1)*iCellSize, Column*iCellSize);

        if(Walls[1] == 1) // top
            g.DrawLine(System.Drawing.Pens.Green, Row*iCellSize, Column*iCellSize,
                      Row*iCellSize, (Column+1)*iCellSize);

        if(Walls[2] == 1) // right
            g.DrawLine(System.Drawing.Pens.Green, Row*iCellSize, (Column+1)*iCellSize,
                      (Row+1)*iCellSize, (Column+1)*iCellSize);

        if(Walls[3] == 1) // bottom
            g.DrawLine(System.Drawing.Pens.Green, (Row+1)*iCellSize, Column*iCellSize,
                      (Row+1)*iCellSize, (Column+1)*iCellSize);
    }

    // Simple function that checks if our cell has all 4 walls.. if not then it
    // returns false.
    public bool HasAllWalls()
    {
        for(int i=0; i<4; i++)
        {
            if(Walls[i] == 0)
                return false;
        }
        return true;
    }

    // This is used to pick a random side with a wall.
    private static long Seed = DateTime.Now.Ticks;
    static public Random TheRandom = new Random( (int)MazeCell.Seed);

    public void KnockDownWall(MazeCell theCell)
    {
        int iWallToKnockDown = FindAdjacentWall(theCell);
        Walls[iWallToKnockDown] = 0;

        int iOppositeWall = (iWallToKnockDown + 2)%4;
        theCell.Walls[iOppositeWall] = 0;
    }

    // Now if we remove a wall from a cell, we need to remove the parallel
    // wall on the adjoining cell. As each cell has 4 walls... so if we
    // take a wall down to connect two cells, we need to remove the walls
    // from both cells. This function, returns the wall of the next
    // cell that needs removing.
    public int FindAdjacentWall(MazeCell theCell)
    {
        if( theCell.Row == Row )
        {
            if( theCell.Column < Column)
                return 0; // left
            else
                return 2; // right
        }
        else
        {
            if( theCell.Row < Row )
                return 1; // top
            else
                return 3; // bottom
        }
    }
}

How It Works

Once you see how this amazing piece of code works, you'll be a changed person... well, not too changed I hope :)

Its secret to how it works is the stack... as we set our little maze generator off on its path, and its randomly going left and right... but always keeping track of where its come from. Eventually it will get stuck! As it requires a side that its turning into to have 4 sides. So it keeps popping off values on the stack until it reaches a neighbor with 4 sides.... then off it goes again creating a new path.

But we know it will get stuck... so it goes back up the stack again..pop'ing off values until it reaches another neighbour with 4 sides... then it goes down that path. Now if you repeat this process, as I've shown in (1), (2)...to (5) in the diagram on the right, you'll see how it manages to create a unique path from (0,0) top left to (6,6) bottom right in the diagram on the right.

Compilation

To compile all three files together:

<?php
C:>csc /t:winexe maze.cs generatemaze.cs mazecell.cs

C:>csc /t:winexe maze.cs generatemaze.cs mazecell.cs

Step by Step

The algorithm works using a stack to keep track of the path:

1. It starts at the top-left cell (0,0)
2. It checks neighboring cells that still have all four walls intact
3. It randomly picks one of these neighbors, knocks down the wall between them
4. It pushes the current cell onto the stack and moves to the new cell
5. When it gets stuck (no unvisited neighbors), it pops cells from the stack until it finds a cell with unvisited neighbors
6. This process continues until all cells have been visited

The stack ensures that the algorithm always has a path back to previous cells when it hits dead ends, creating a perfect maze with exactly one path between any two points.

Advert (Support Website)

Visitor: