Tuesday, March 19, 2013

Labyrinth algorithm illustrated

I post here a step-by-step version of the maze generator, keeping only the "classic" maze version. Click on "generate" to see how the algorithm works :

It is inspired by the DFS algorithm. It can be seen as a miner digging into the rock cells, always choosing the next direction at random (using pseudo random number generation). You can see the current position of the miner (green square) and the "little stones" (pink squares) he drops in order to keep track of his last path.

I used the following fundamentals rules to process the DFS:
  • the miner always digs the cells two at a time
  • the miner never digs a cell if it communicates to a previous dug cell
  • the miner always tries every directions before give-up and coming back
Maybe it could be interesting to tweak or relax some of these rules to generate some different maze patterns.

No comments:

Post a Comment