algorithmmaze

Algorithm for maze/labyrinth generation with no dead ends?

I'm looking for a maze generation algorithm that can generate a labyrinth with a single continuous path and no dead ends but only a start and end.

Like this:

maze

Image from http://www.astrolog.org/labyrnth/maze/unicursl.gif

Where do I find or go about constructing such a maze generation algorithm?

Solution

  • 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.