Wilson's Algorithm

https://cruzgodar.com/applets/wilsons-algorithm/

58•FromTheArchives•3mo ago

Comments

andrehacker•3mo ago

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•3mo ago

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•3mo ago

This is what I come to HN for. Bravo

leakycap•3mo ago

Was it the example or the text for you?

tromp•3mo ago

Wilson's algorithm is based on so-called loop-erased random walks [1].

[1] https://en.wikipedia.org/wiki/Loop-erased_random_walk

jmpeax•3mo ago

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?

realaleris149•3mo ago

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.

fn-mote•3mo ago

Here is one article in an excellent series of articles on make generation:

https://weblog.jamisbuck.org/2011/1/20/maze-generation-wilso...

butlersean•3mo ago

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/

OpenCiv3: Open-source, cross-platform reimagining of Civilization III

The Waymo World Model

How we made geo joins 400× faster with H3 indexes

Show HN: Look Ma, No Linux: Shell, App Installer, Vi, Cc on ESP32-S3 / BreezyBox

Monty: A minimal, secure Python interpreter written in Rust for use by AI

Show HN: I spent 4 years building a UI design tool with only the features I use

Dark Alley Mathematics

Microsoft open-sources LiteBox, a security-focused library OS

Sheldon Brown's Bicycle Technical Info

Hackers (1995) Animated Experience

Show HN: If you lose your memory, how to regain access to your computer?

Delimited Continuations vs. Lwt for Threads

An Update on Heroku

Unseen Footage of Atari Battlezone Arcade Cabinet Production

PC Floppy Copy Protection: Vault Prolok

Show HN: ARM64 Android Dev Kit

How to effectively write quality code with AI

Why I Joined OpenAI

Show HN: R3forth, a ColorForth-inspired language with a tiny VM

Learning from context is harder than we thought

Introducing the Developer Knowledge API and MCP Server

I spent 5 years in DevOps – Solutions engineering gave me what I was missing

Female Asian Elephant Calf Born at the Smithsonian National Zoo

Understanding Neural Network, Visually

I now assume that all ads on Apple news are scams

FORTH? Really!?

WebView performance significantly slower than PWA

Zlob.h 100% POSIX and glibc compatible globbing lib that is faste and better

I'm going to cure my girlfriend's brain tumor

Evaluating and mitigating the growing risk of LLM-discovered 0-days