|
|
|
|
|
|
|
Author Rank :
|
|
|
Page Views :
|
28578
|
|
Downloads :
|
1113
|
|
Rating :
|
Rate it
|
|
Level :
|
Beginner
|
|
|
|
|
Download
Files:
|
|
|
|
|
|
|
|
|
|
|
Figure 1 - A sample generated maze using a 50 x 50 grid
Did you ever get the feeling that cubicles were laid out with the idea that there could be no escape? (Must be I am a bit overworked these days). Today's article focuses on how to generate a maze using the depth first search algorithm. This is a very simple but clever algorithm that creates a maze by randomly stripping one available wall between two cells for every cell in the grid. The steps to the algorithm are as follows:
- Pick any random cell in the grid (In this implementation we use the upper left hand corner.)
- Find a random neighboring cell that hasn't been visited yet.
- If you find one, strip the wall between the current cell and the neighboring cell.
- If you don't find one, return to the previous cell.
- Repeat steps 2 and 3 (or steps 2 and 4) for every cell in the grid.
Note: A good place to visit to understand this algorithm is the MazeWorks site.
Having examined the algorithm, I was able to come up with a set of classes that would help me implement it. Below is the design for the Maze Generator Application. The Application allows you to generate a maze of any grid dimension and grid cell size. It also allows you to print and print preview the grid:
Figure 2 - Maze Generation Application Reverse engineered using the WithClass 2000 UML Tool
As you can see from the UML design, the Maze class generates the maze and contains a collections of Cells to work the algorithm. Each cell contains an array of 4 walls which can be "knocked down" by setting an element in the array to zero. The code for implementing the Depth First Search is shown below. It increments the total number of cells visited in a while loop and completes when the VisitedCells equals the n x n number of grid cells. As stated in the algorithm, first it gets a list of neighboring cells with 4 walls intact and picks one of them at random (if a neighbor exists). It then knocks down a wall between the current cell and the randomly chosen cell. The current cell is pushed onto a stack and the randomly chosen cell becomes the new current cell. If no adjacent neighbors exist with 4 walls intact, the previous cell is popped off the stack and made the current cell.
public void Generate()
{
while (VisitedCells < TotalCells)
{
// get a list of the neighboring cells with all 4 walls intact
ArrayList AdjacentCells = GetNeighborsWithWalls(CurrentCell);
// test if a cell like this exists
if (AdjacentCells.Count > 0)
{
// yes, choose one of them, and knock down the wall between it and the current cell
int randomCell = Cell.TheRandom.Next(0, AdjacentCells.Count);
Cell theCell = ((Cell)AdjacentCells[randomCell]);
CurrentCell.KnockDownWall(theCell);
CellStack.Push(CurrentCell); // push the current cell onto the stack
CurrentCell = theCell; // make the random neighbor the new current cell
VisitedCells++; // increment the # of cells visited
}
else // No adjacent cells that haven't been visited, go back to the previous cell
{
CurrentCell = (Cell)CellStack.Pop();
}
}
}
Conclusion
Mazes are fun to solve, but are also a good background for graphic games. In my next article I'll attempt to combine the eater game with the maze generation. Enjoy some aMazing Puzzles in C# and .NET.
|
|
Comment Request!
Thank you for reading this post. Please post your feedback, question, or comments about this post
Here.
|
|
|
|
|
Login
to add your contents and source code to this article
|
|
|
|
|
|
|
|
|
|
|
|
Mike Gold
Michael Gold is President of Microgold Software Inc., makers of the WithClass UML Tool. His company is a Microsoft VBA Partner and Borland Partner. Mike is a Microsoft MVP and founding member of C# Corner. He has a BSEE and MEng EE from Cornell University and has consulted for Chase Manhattan Bank, JP Morgan, Merrill Lynch, and Charles Schwab. Currently he is a senior developer at Finisar Corp. He has been involved in several .NET book projects, and is currently working on a book for using .NET with embedded systems.
He can be reached at mike@c-sharpcorner.com
|
|
|
|
|
|
|
|
|
C# Consulting is founded in 2002 by the founders of C# Corner. Unlike a traditional
consulting company, our consultants are well-known experts in .NET and many of them
are MVPs, authors, and trainers. We specialize in Microsoft .NET development and
utilize Agile Development and Extreme Programming practices to provide fast pace
quick turnaround results. Our software development model is a mix of Agile Development,
traditional SDLC, and Waterfall models.
|
|
Click here to learn more about C# Consulting. |
|
|
|
|
|
|
|
Introducing MaxV - one click. infinite control. Hyper-V Hosting from MaximumASP.
Finally – a virtual platform that delivers next-generation Windows Server 2008 Hyper-V virtualization technology from a managed hosting partner you can truly depend on. Visit www.maximumasp.com/max for a FREE 30 day trial. Hurry offer ends soon.
Climb aboard the MaxV platform and take advantage of High Availability, Intelligent Monitoring, Recurrent Backups, and Scalability – with no hassle or hidden fees.
As a managed hosting partner focused solely on Microsoft technologies since 2000, MaximumASP is uniquely qualified to provide the superior support that our business is built on. Unparalleled expertise with Microsoft technologies lead to working directly with Microsoft as first to offer IIS 7 and SQL 2008 betas in a hosted environment; partnering in the Go Live Program for Hyper-V; and product co-launches built on WS 2008 with Hyper-V technology.
|
Dynamic PDF
ceTE software specializes in components for dynamic PDF generation and manipulation. The DynamicPDF™ product line allows you to dynamically generate PDF documents, merge PDF documents and new content to existing PDF documents from within your applications.
|
Nevron Chart for .NET 2010.1 Now Available
The leading .NET charting control now features PDF, Flash and Silverlight export, visualization of large datasets and more. Deliver true charting functionality to your BI, Scorecard, Presentation or Scientific apps. Download evaluation now.
|
ASP.NET 4 Hosting
Get 2 Months Free of ASP.NET Hosting for Only $4.95/month! Receive FREE MS SQL and MySQL Databases Including ASP.NET 4/3.5, MVC 3.0, Silverlight 4, Windows 2008/IIS 7.0 Plus FREE IIS 7 Modules. Host UNLIMITED ASP.NET Web Sites – Click Here!
|
|
|
|
|
|
|
|
|
|
|
|
|