3 ms·
JamisBuck's other maze generation algorithm, based on backtracking (http://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking http://weblog.
by Luyt 16y ago
JamisBuck'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.