Generating A Maze.
This small tutorial is with reference to
http://www.mazeworks.com/mazegen/mazetut/
http://www.gamespp.com/cgi-bin/resource.cgi?cSharpMazeGenerationProgram
Which I've based this tutorial on... and beleive me, they are definetly worth
taking a look at... As its such a simple concept, you'll be creating all sorts
of cool Maze games in time...2D and 3D :)
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.
| Code: |
|
// 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()
{
}
} |
Of course that code compiles okay... and is a nice starting point... of
course it doens't do much yet. But you just wait... Few more lines of code
and you'll be drewling on your keyboard. :)
Now lets add the code, so that our window actually appears... a simple
window.
| Code: |
|
// 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()
{
//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 this:
| But you run the program... by double clicking
on it... and you might notice, that the dos (command window) stays open
until we close our baby GUI window that we created. So whats up with
that? How do we get ride of that command window... Its not very
professional is it...
As the default settings for csc compiler, are to generate a command
prompt exe.... so to change this, we type
'C:>csc /t:winexe maze.cs'
At the prompt to generate a windows .net exectuable. |
 |
On we must go, now we'll add a few other helper member
functions to our maze.cs file, so its more like what the vs wizard would
generate:
| Code: |
|
// 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'.
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();
}
// Our program entry point.
static void
Main()
{
//Application.Run(new MazeWindow());
is what you would usually see..
//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());
}
} |
Of course we have now added a constructor, and a member
function which we we'll call to setup all our default window variables.
Like the window caption, its starting size... and anything else we might want to
add will be placed in InitializeComponent() function.
But we are still missing a few important things before we
can begin on our maze... which is the graphics part...drawing lines etc... How
do we possibly do this? Well we use another helper .net library, and
inform our windows class which member function we want to call when we need to
repaint our window:
| Code: |
|
// 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'.
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";
//<NEW * NEW * NEW * NEW * NEW * NEW *
NEW * NEW * NEW * NEW * NEW * NEW>
// 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);
}
//<NEW * NEW * NEW * NEW * NEW * NEW * NEW * NEW *
NEW * NEW * NEW * NEW>
// Our member function, which will handle the
painting of our window..
// So each time our window needs repainting,
windows calls this function.
// Which we set in InitilizeComonents()..
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);
}
// Our class constructor!
public MazeWindow()
{
InitializeComponent();
}
// Our program entry point.
static void
Main()
{
//Application.Run(new MazeWindow());
is what you would usually see..
//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());
}
} |
It sure has grown our code hasn't it... but beleive me, it
only looks that large, because of all the comments in it. If you took out
the comments, you'd have a program that generates a window in a few lines of
code...
To keep things simple, I've ignored things like the
overridden Dispose function and threads... but we'll add them later.
Thats enough of our maze.cs code... we will put the actual
code that generates the maze in another file called "generatemaze.cs" ...
And we'll call it from our maze.cs class when we need to render it.
| Well its not much, but its a step closer to our goal of
generating a maze.... We could randombly just go through each cell and
remove a side here and there... BUT, it wouldn't be a maze... we want to get
from the top left, to the bottom right... a secret path :)
Hopefully you understand whats going on here.... just drink your coffee
slowly and take deep breaths, and I'm sure you'll be okay :)
Our 3 Files will be
{maze.cs} - {generatemaze.cs}
- {mazecell.cs} |
 |
| Code: |
|
// maze.cs
// uses generatemaze.cs, and generatemaze.cs uses mazecell.cs
// so at the command prompt ot compile you would need to do:
// C:>csc /t:winexe maze.cs generatemaze.cs mazecell.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'.
public
class MazeWindow : System.Windows.Forms.Form
{
//<NEW * NEW * NEW * NEW * NEW * NEW * NEW * NEW *
NEW * NEW * NEW * NEW>
GenerateMaze TheMaze = new GenerateMaze();
// 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 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);
//<NEW * NEW * NEW * NEW * NEW * NEW *
NEW * NEW * NEW * NEW * NEW * NEW>
// Initilize our maze, and generate
it.
TheMaze.Create(this.Left,
this.Top, 300, 300);
TheMaze.Generate();
}
// Our member function, which will handle the
painting of our window..
// So each time our window needs repainting,
windows calls this function.
// Which we set in InitilizeComonents()..
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);
//<NEW * NEW * NEW * NEW * NEW * NEW *
NEW * NEW * NEW * NEW * NEW * NEW>
TheMaze.Draw(g);
}
// Our class constructor!
public MazeWindow()
{
InitializeComponent();
}
// Our program entry point.
static void
Main()
{
//Application.Run(new MazeWindow());
is what you would usually see..
//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());
}
} |
| Code: |
|
// generatemaze.cs
public
class GenerateMaze
{
// A double array of maze cells, which is empty.
MazeCell[,] Cells = null;
int iDimension = 20;
// We call this to set up the size of our maze etc
public void
Create(int x, int
y, int width, int
height)
{
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;
}
}
// This will generate our maze
public void
Generate()
{
}
// And of course, we need to draw our maze... :)
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);
}
}
} |
| Code: |
|
// mazecell.cs
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
// 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);
}
} |
Thats all the parts of our final program. I could
have kept it all as one single file... maze.cs... but I think you get lost in
the code easily. And now that I've added the few functions to MazeWindow
class in maze.cs, we dont' really need to change anything now...just add in the
final parts to GenereateMaze and MazeCell classes.
How it will work is like this, we create an two dimensional
array of MazeCells in GenerateMaze class... we initialize them all so each cell
knows where it belongs. Then later we can let each cell draw itself.
The Code that does all the work will be in Generate, which will actually
Generate our random path, by using a Stack, and a bit of trickery :)
Now running the above code, all we would see is a grid....
as we havn't removed any of the cell walls, or made any attempt to create a
maze.
---------------------------------------------------------------------------------------------------------------------------------------------------------------
{Comments/Code}
---------------------------------------------------------------------------------------------------------------------------------------------------------------
| DownloadSourceCode |
 |
| On the right shows a simple screen shot of the
working code, each time you run the program, you should have a different
grid. There isn't any extra code, that will resize the grid to the
window etc, as the code has been kept sweet and simple. So hopefully
you'll be able to tinker with it and see a million ways that you can improve
and modify it to your hearts content :) |
No real changes to maze.cs, but I thought I'd show the
whole code anyhow :)
| Code: |
|
// maze.cs
// uses generatemaze.cs, and generatemaze.cs uses mazecell.cs
// so at the command prompt ot compile you would need to do:
// C:>csc /t:winexe maze.cs generatemaze.cs mazecell.cs
// Again, its only a tutorial code, so to keep its kept to its simplest.
// If you wanted to the maze to resize when you resize the window, that
// would be further work.
// 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'.
public
class MazeWindow : System.Windows.Forms.Form
{
GenerateMaze TheMaze = new GenerateMaze();
// 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()
{
// You can change your default window
size here, so you can see a larger
// maze, but with the same complexity
//<*CHANGE * CHANGE * CHANGE * CHANGE
* CHANGE * CHANGE * CHANGE * CHANGE>
// Lets set our window, size. 300 by
320 sound okay?..hmmm
this.Size =
new System.Drawing.Size(300,320);
// I've got that 20, as you have the
title bar at the top..
// And give it a snazzy title, for the
menu bar of our window.
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);
//<NEW * NEW * NEW * NEW * NEW * NEW *
NEW * NEW * NEW * NEW * NEW * NEW>
// Initilize our maze, and generate
it.
TheMaze.Create(this.Left,
this.Top,
ClientRectangle.Width, ClientRectangle.Height);
TheMaze.Generate();
}
// Our member function, which will handle the
painting of our window..
// So each time our window needs repainting,
windows calls this function.
// Which we set in InitilizeComonents()..
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);
TheMaze.Draw(g);
}
// Our class constructor!
public MazeWindow()
{
InitializeComponent();
}
// Our program entry point.
static void
Main()
{
//Application.Run(new MazeWindow());
is what you would usually see..
//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());
}
} |
| Code: |
|
// 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;
// This is set in Create(..),
int iDimension;
// We call this to set up the size of our maze etc
public void
Create(int x, int
y, int width, int
height)
{
// You can change this to a more
detailed map, for example make it a 5
// and see what you get...its a super
complex map... of course, you
// should resize your window so you
can see the detail.
//<*CHANGE * CHANGE * CHANGE * CHANGE
* CHANGE * CHANGE * CHANGE * CHANGE>
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 beleive 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.
// A review of how it works, goes like this, we
will visit every single
// cell at least once (e.g. iTotalCells in the
while loop).
// First we start with our starting Cell[0,0]...
the top left, and we check
// the surounding cells... and we want to know of
all the one's with 4 walls
// only. We do this with our function,
GetCellNeighbors, and this will return
// the cells that have the 4 walls...whether it be
1 or 4... As we have just
// started for example in the top left, there
would be 2 cells...can't go up
// or left, as where in the top corner.
// Then off goes our little worm...picking a
random value...moving along
// and each time, pushing its old cell positions
on the stack as it goes
// along... and it will get stuck sooner or
later... so now its only choice
// is to retrace its path back using the stack...
poping off values until
// it can go down another different path.
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
dont' 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.
// Then we call the cell function, HasAllWalls,
which will tell us, if this
// cell has 4 walls, and if so, add it to the list
:)
private ArrayList GetCellNeighbors(MazeCell
aCell)
{
ArrayList Neighbors = new
ArrayList();
for(int
countRow=-1; countRow<=1; countRow++) // -1 ->
0 -> 1
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;
}
// And of course, we need to draw our maze... :)
public void
Draw(System.Drawing.Graphics g)
{
for(int
j=0; j<iDimension; j++)
for(int
i=0; i<iDimension; i++)
{
Cells[i,j].Draw(g);
}
}
} |
| Code: |
|
// mazecell.cs
using
System; // used for Random
public
class MazeCell
{
public int
Column;
public int
Row;
public int[]
Walls = new int[4]{1,
1, 1, 1}; // left, top, right, bottom
// 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;
else
return 2;
}
else
{
if( theCell.Row < Row )
return 1;
else
return 3;
}
}
} |
| Once you see how this amazing piece of code works, you'll be
a changed person.... well not to 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 poping 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.
|
 |
|
