Wilson's Algorithm(cruzgodar.com)
cruzgodar.com
Wilson's Algorithm
https://cruzgodar.com/applets/wilsons-algorithm/
10 comments
I always had problems understanding algorithms from such descriptions. Even from pseudocode I find it difficult to understand. What I usually do is search for an implementation, even in a language I am not familiar with is still better. When you have code you can run it, test it, debug it - not so much with descriptions and pseudocode.
This page has similar visualizations and explanations of multiple (wildly different, in some cases) maze generation algorithms. It’s hypnotic to watch them run.
https://professor-l.github.io/mazes/
https://professor-l.github.io/mazes/
Any discussion about Maze algorithms cannot be complete without a reference to the 1982 endless Maze algorithm used in the "Entombed" Atari game.
Many great articles about this can be found like:
https://www.gamesthatwerent.com/2024/01/the-endless-maze-alg...
https://ieee-cog.org/2021/assets/papers/paper_215.pdf
Many great articles about this can be found like:
https://www.gamesthatwerent.com/2024/01/the-endless-maze-alg...
https://ieee-cog.org/2021/assets/papers/paper_215.pdf
Here is one article in an excellent series of articles on make generation:
https://weblog.jamisbuck.org/2011/1/20/maze-generation-wilso...
https://weblog.jamisbuck.org/2011/1/20/maze-generation-wilso...
Wilson's algorithm is based on so-called loop-erased random walks [1].
[1] https://en.wikipedia.org/wiki/Loop-erased_random_walk
[1] https://en.wikipedia.org/wiki/Loop-erased_random_walk
[deleted]
many examples of of maze generation algorithms (with source code) here.
https://www.jamisbuck.org/mazes/
i bought his book totally worth it http://mazesforprogrammers.com/
i bought his book totally worth it http://mazesforprogrammers.com/
"Now pick another random black dot to start from and color it white too. From this black dot" from which black dot, the white one?
"single step in a random direction, coloring the new dot white and drawing a line between the two dots". How big of a step is we need to draw a line? Ok, so where not talking about pixels, and where drawing black and white dots on a background of... let's imagine grey?
"backtrack along your path until you’re back at the dot that you were trying to color white" does this algorithm ever terminate in any tractible time?