Maze Generation: Eller's Algorithm

JamisBuck's other maze generation algorithm, based on backtracking (http://weblog.jamisbuck.org/2010/12/27/maze-generation-recur...) seems to create more esthetical mazes.

    (user@pasta) /home/user/prj/ruby $ ruby backtrack-maze.rb 20 20
     _______________________________________
    | |_____   _   _  |  _____|    _|  ___  |
    |_  |   |_  |_  |___|  _____|  ___  | | |
    | |___|_  |___| |   |  _|   |_|   |___| |
    |  _______|  _  | |___|  _|_____|___  | |
    |_  |  ___  | | | |   |_______  |   |_  |
    |  _|___  | |  _| |_|_    |   |___|_  | |
    |_____  |_| |___|_______| |_| |  _____| |
    |_   _|_  |  _   _|   |  _|   | |   |_  |
    |  _|  ___|___|  ___|___|_  | |___|_  | |
    |  ___|_   _  |___   _______| |   | | |_|
    |_  |    _|_  |_____|  _  |  _| |_  |_  |
    | | | |_|   |___  |  _|  _|_____|_   _| |
    | | |   | | |___  | | |_  |  ___  | |  _|
    | | |_|___| |   |___|  _|___|   | | |_  |
    | |_____  |  _| |___     ___| |___|___| |
    |   |_  | | | |___  | |___  |_______  | |
    | |_   _| |_  |   | |___  |  _____|  _| |
    |_  |_|  _|_____| |___  | |_________|_  |
    |  _|  _|  ___  |_|   | | |   |  ___  | |
    |_________|_________|___|___|___|_______|
    backtrack-maze.rb 20 20 3751362624
    
    (user@pasta) /home/user/prj/ruby $ ruby eller-maze.rb 20 20
     _______________________________________
    |_  |  _|_  | | |_  |  ___       ___    |
    | | |  _  | | | |_____|  _|_|_|_|  _| |_|
    | | |   |    _       _| |  _| | | |_  | |
    | | | |_| |   | | |     | |  _| |___    |
    | | |   |_|_|_|_| |_| |_|  _|    ___| |_|
    | | | |_|  ___   ___|_________|___| |  _|
    |_  |  _|___| | |_____   _|_    |  _| | |
    |_______  | |_   _| |  _| |_  | |_     _|
    |_  | | |___  |  _  | | | |___| | | |___|
    |_  |    _|___| |___  |___  | | | | |  _|
    |  _| |_______| |  _|_|  _| | | |___    |
    | |_____  |  _| | |  _| | |    _| |_  | |
    | |  _|    ___| |_    |_    | |_  | |_| |
    |_    |_| | | |_    |_| |_|_| | | | | | |
    |_  | | | |  _| |_| |  _  | | | | | | | |
    |_  |_|  _| |  _|  _| | |_|_  |_____    |
    |_____   _|_    | | | |  _| |    _|_  |_|
    | | |  _   _  |  ___  |      _| |_  |_  |
    |_  |_|___  | |   |___  |_|_|___| | | | |
    |___________|_|_|_____|_________________|
    eller-maze.rb 20 20 873996890

My favourite maze-generating algorithm: consider the graph with one node per cell and edges for all the places where there can be, or not be, walls. Now construct a random spanning tree for the graph, and remove the walls corresponding to edges of the spanning tree. Finally, choose two leaves of the tree (for bonus points, two leaves that are maximally far apart; for even more bonus points, interpret "far apart" in a way that tries to maximize the difficulty of finding the path between them) and label them "start" and "end".

How do you construct a random spanning tree? One way is to use Kruskal's algorithm with random weights on the edges. See http://www.mccaughan.org.uk/software/make-maze-1.02.tar.gz for an implementation and http://www.mccaughan.org.uk/software/mazes/90x100.ps for a typical maze it generates.

(I first saw this algorithm on a web page of Olin Shivers, who had a nice Scheme implementation. Nice, but slow and memory-hungry. Mine does roughly the same as his, but in reasonably tightly-written C and with some neat tricks to make the output compact.)

Nice algorithm! I've just written a little Javascript implementation, because it looked fun: http://s3.boskent.com/mazes/eller.html

Tomorrow I’ll make it into a little interactive game.

That is some really nicely written (read as: readable) code. I'm impressed.