[HN Gopher] Wilson's Algorithm
       ___________________________________________________________________
        
       Wilson's Algorithm
        
       Author : FromTheArchives
       Score  : 37 points
       Date   : 2025-10-11 13:35 UTC (9 hours ago)
        
 (HTM) web link (cruzgodar.com)
 (TXT) w3m dump (cruzgodar.com)
        
       | andrehacker wrote:
       | 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
        
       | drob518 wrote:
       | 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/
        
       | bigjobby wrote:
       | This is what I come to HN for. Bravo
        
         | leakycap wrote:
         | Was it the example or the text for you?
        
       | tromp wrote:
       | Wilson's algorithm is based on so-called loop-erased random walks
       | [1].
       | 
       | [1] https://en.wikipedia.org/wiki/Loop-erased_random_walk
        
       | jmpeax wrote:
       | The description of the algorithm is frustratingly confusing.
       | 
       | "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?
        
       ___________________________________________________________________
       (page generated 2025-10-11 23:00 UTC)