Simple Maze Generation using Coldfusion

As a kid, I always loved to solve mazes as well as try to create them using graph paper and a trusty #2 pencil. My mazes were never terribly complex but that did't matter, they were fun to build and fun to try and solve. Fast forward 20+ years and I still enjoy mazes but had not't given much thought in way of creating them.

Luckily I ran across Jamis Buck's blog, the { buckblogs :here } and was amazed to see all of the different algorithms that could be used to create mazes. Jamis does an awesome job of putting the algorithms into simple terms with lots of pictures, a visual demo (in JS) and some code samples in ruby. His post inspired me to try my hand at implementing some in Coldfusion.

I started with the Recursive Backtracking algorithm, which at a high level it goes something like this:

• Start with a grid of cells representing the maze
• Choose a cell to start with an mark it as being visited
• Randomly choose one of it's neighboring cells (N, E, S or W)
• If that cell has not been visited yet,
  • Knock down the wall between it
  • Add this new cell to the stack
  • Choose one of it's random neighbors and repeat the process
• If the cell has already been visited
  • Pop it from the stack and back track to the previous cell
• Continue the process of randomly walking between neighbors until all cells have been visited

This algorithm fits well using recursion, but as you can guess there is the potential for StackOverflowExceptions when the grid gets very large. In the worst case scenario, the longest "walk" could include all cells. An alternative however is to manually manage the traversal by implementing your own "call stack" and looping over it until all calls have been completed(and thus all cells have been visited).

The following snippet shows how you would implement the algorithm using an iterative approach.

** The code for this was written to be compatible with Railo, thus the method signatures do not look as complete as Adobe's CF9 implementation

Out of the algorithms that Jamis covered, this was one of the fastest and also the easiest to implement. In my next post, I will cover Kruskal's algorithm which builds a randomized (minimum) spanning tree

Here is the working code for this example: Coldfusion Maze Generation Code

Updated: Here is a 35 x 35 cell maze generated from the from the above code.

• Posted by andy matthews on Feb 08, 2011 at 8:35 AM
  
  No demo or screenshots of the final product?
  
  
• Posted by jalpino on Feb 14, 2011 at 6:20 PM
  
  Yeah i guess an example or demo would be nice. =)
  
  I updated the post with a sample maze created from the code. Shamefully, I haven't back ported my example to work on the (really old) version of CF my shared hosting is on. The best I have for a demo is the code that you can download and run locally.
  
  

 

Leave Feedback

Name

Email

Email will not be displayed

Website

( Optional )

Feedback

Post your feedback, HTML will not be rendered, only plain text.

Security

Answer the math problem below.

=

Subscribe

Receive emails when others submit comments