the { buckblogs :here }: Maze Generation: Eller's Algorithm

Eller's algorithm for generating potentially infinite mazes in linear time:

@chaered, it actually does not matter how you define “placed in the maze.” By definition, every cell in the maze must be reachable by every other cell, so regardless of where you are placed, there will be a shortest path to any other cell you designate. And since a shortest path will never include loops (since loops can be trivially removed from the path), any path between two cells will be “direct” (in the sense that the path will never intersect itself). Also, when I’ve said “retrace steps”, I’m not talking about encountering a dead-end and doing an about-face. To reuse your T-shaped maze, imagine a loop at the bottom, making something like a lowercase b with a crossbar at the top. You could start at the top-left, turn right, walk all the way down, around the loop, back up, turn right, and exit at the top-right. All without encountering a dead-end, and yet for part of th...

Full article: http://weblog.jamisbuck.org/2010/12/29/maze-generation-el...