www.xbdev.net xbdev - software development
Tuesday September 17, 2019
home | about | contact | Donations

     
 

Programming..

With C# and .Net...

 


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.

 

 

 

 

 

 

 

 

 

 
 Visitor: 9534626  { 209.237.238.175 } Copyright (c) 2002-2017 xbdev.net - All rights reserved.
Designated tutorial and software are the property of their respective owners.