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

Yeah, the recursive backtracker is my favorite. Nicer results, and its very flexible. The other algorithms that I'm going to review are interesting for various reasons, and you can learn a lot about the structure and "essence" of graphs by implementing them, but they aren't as generally useful for maze generation as the recursive backtracker.

I have a hunch that you could change its appearance substantially by tweaking the probability of connecting sets and connecting vertically.

Yeah, I submitted that one the other day as well as I find the whole topic interesting, but it didn't any traction.

Yeah, the recursive backtracker's my favorite as well, plus the algorithm can be multi-purpose. I most recently used it to solve winning positions in a Hex assignment that was due in a couple hours.

In fact, I just remember implementing a pygame maze app a few years ago that I should really update... http://www.pygame.org/project-PyMaze-733-.html (picture on the page).

Edit: Ha, my first paragraph is very similar to jamis'...

Good-looking mazes are not necessarily fun to wander in. The important bit in a maze is the topology, imho, with navigation coming in second (turns can be painful, thin walls can be misleading, corridors can be trivial, etc) and appearance third.

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.