4 ms·
Maze Generation: Eller's Algorithm
- Luyt 16y agoJamisBuck's other maze generation algorithm, based on backtracking (http://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-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
- jamis 16y agoYeah, 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.
- duck 16y agoYeah, I submitted that one the other day as well as I find the whole topic interesting, but it didn't any traction.
- sblom 16y agoI have a hunch that you could change its appearance substantially by tweaking the probability of connecting sets and connecting vertically.
- Jach 16y agoYeah, 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 http://www.pygame.org/project-PyMaze-733-.html (picture on the page). Edit: Ha, my first paragraph is very similar to jamis'...
- sesqu 16y agoGood-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.
- gjm11 16y agoMy 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 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 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.)
- robinhouston 16y agoNice algorithm! I've just written a little Javascript implementation, because it looked fun: http://s3.boskent.com/mazes/eller.html http://s3.boskent.com/mazes/eller.html Tomorrow I’ll make it into a little interactive game.
- Stormbringer 16y agoThat is some really nicely written (read as: readable) code. I'm impressed.