Menu
I'm looking for a maze generation algorithm that can generate mazes with no dead ends but only a start and end. Like this:
Image from http://www.astrolog.org/labyrnth/maze/unicursl.gif
Where do I find or go about constructing such a maze generation algorithm?
927
Trémaux's algorithm, invented by Charles Pierre Trémaux, is an efficient method to find the way out of a maze that requires drawing lines on the floor to mark a path, and is guaranteed to work for all mazes that have well-defined passages, but it is not guaranteed to find the shortest route.
Maze Generation Based on Randomized DFSThe algorithm starts at a given cell and marks it as visited. It selects a random neighboring cell that hasn't been visited yet and makes that one the current cell, marks it as visited, and so on.
It sounds like you want a pseudo-random space filling curve (for example, see Context-based Space Filling Curves -EUROGRAPHICS ’2000 (PDF format, 1.1 MB))
Take a look a Space-filling curve.
I suspect you could apply some randomness to the construction of one of these to achieve what you want.
147
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
