"Another simple algorithm for rectangular mazes, recursive division, works as follows. Begin with a rectangular space with no walls. Call this a chamber. Build at random points two walls that are perpendicular to each other. These two walls divide the large chamber into four smaller chambers separated by four walls. Choose three of the four walls at random, and open a one cell-wide hole at a random point in each of the three. Continuing in this manner recursively, until every chamber has a width of one cell in either of the two directions, one can easily generate interesting mazes that avoid the ease of solution of binary tree mazes." - Wikipedia
http://en.wikipedia.org/wiki/Maze_generation_algorithm
I took the quote from Wikipedia, however I generated the animated gif to share the process. I have developed animation for all the algorithms and solvers I am working on, it helps me think about the problems.
Posts
Recursive division is interesting, however dividing each area with a cross and adding doors in 3 of the walls is unnecessarily complex, and it also results in blemishes of sections of parallel passages. Cleaner/simpler is to just randomly divide each area once horizontally or vertically. See the "recursive division" section in http://www.astrolog.org/labyrnth/algrithm.htm#perfect for details.
ReplyDelete