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/

Interop 2025: A Year of Convergence

JobArena – Human Intuition vs. Artificial Intelligence

Concept Artists Say Generative AI References Only Make Their Jobs Harder

Show HN: PaySentry – Open-source control plane for AI agent payments

Show HN: Moli P2P – An ephemeral, serverless image gallery (Rust and WebRTC)

The Crumbling Workflow Moat: Aggregation Theory's Final Chapter

Pax Historia – User and AI powered gaming platform

Show HN: I built a RAG engine to search Singaporean laws

Scams, Fraud, and Fake Apps: How to Protect Your Money in a Mobile-First Economy

Porting Doom to My WebAssembly VM

Cognitive Style and Visual Attention in Multimodal Museum Exhibitions

Full-Blown Cross-Assembler in a Bash Script

Logic Puzzles: Why the Liar Is the Helpful One

Optical Combs Help Radio Telescopes Work Together

Show HN: Myanon – fast, deterministic MySQL dump anonymizer

The Tao of Programming

Forcing Rust: How Big Tech Lobbied the Government into a Language Mandate

PanelBench: We evaluated Cursor's Visual Editor on 89 test cases. 43 fail

Can You Draw Every Flag in PowerPoint? (Part 2) [video]

Show HN: MCP-baepsae – MCP server for iOS Simulator automation

Make Trust Irrelevant: A Gamer's Take on Agentic AI Safety

Show HN: Sem – Semantic diffs and patches for Git

Hello world does not compile

Show HN: ZigZag – A Bubble Tea-Inspired TUI Framework for Zig

Metaphor+Metonymy: "To love that well which thou must leave ere long"(Sonnet73)

Show HN: Django N+1 Queries Checker

Emacs-tramp-RPC: High-performance TRAMP back end using JSON-RPC instead of shell

Protocol Validation with Affine MPST in Rust

Female Asian Elephant Calf Born at the Smithsonian National Zoo

Show HN: Zest – A hands-on simulator for Staff+ system design scenarios