FRESH

Hacker News

Maze Algorithms (2017)

177 points by surprisetalk

by tromp

3 subcomments

A maze generator in the shape of a maze whose corridors spell a 4-letter word:

    char*M,A,Z,E=40,J[40],T[40];main(C){for(*J=A=scanf(M="%d",&C);
    --            E;             J[              E]             =T
    [E   ]=  E)   printf("._");  for(;(A-=Z=!Z)  ||  (printf("\n|"
    )    ,   A    =              39              ,C             --
    )    ;   Z    ||    printf   (M   ))M[Z]=Z[A-(E   =A[J-Z])&&!C
    &    A   ==             T[                                  A]
    |6<<27<rand()||!C&!Z?J[T[E]=T[A]]=E,J[T[A]=A-Z]=A,"_.":" |"];}

Generates a maze on the fly after entering the desired height of the maze. This compiled fine back in 1988 when I submitted it to the IOCCC (having rediscovered Eller's algorithm). Modern C compilers don't allow constant strings to be overwritten, which can be avoided by changing the first line to

    char M[3],A,Z,E=40,J[40],T[40];main(C){for(*J=A=scanf("%d",&C);

The code is explained in detail at https://tromp.github.io/maze.html

by nickevante

0 subcomment

For anyone interested in this, Jamis Buck's book 'Mazes for Programmers' is a masterpiece of the genre.
My personal favorite distinction is between the Recursive Backtracker (which creates long, winding corridors with few dead ends which is great for tower defense games) vs. Prim's Algorithm (which creates lots of short cul-de-sacs which is better for roguelikes). The bias of the algorithm dictates the feel of the game more than the graphics do.

by bonsai_spool

1 subcomments

Mike Bostock had several very lovely visualizations back on the D3.js site which I can't find. Here's a cool blogpost he wrote: https://bost.ocks.org/mike/algorithms/#maze-generation

by kamens

3 subcomments

I used Jamis' book extensively to build this AI tool for generating custom mazes of any shape! https://kamens.com/blog/generating-custom-mazes-with-ai

by jtolmar

0 subcomment

Lovely page. Reminds me of the venerable Think Labyrinth (https://www.astrolog.org/labyrnth/algrithm.htm) page, but the live demos add a lot.
My favorite maze algorithm is a variant of the growing tree algorithm - each time you carve a cell, add it to a random one of N lists. When choosing a cell to visit, pop the last cell off the first non-empty list. It's considerably faster than the standard tree algorithm, but more importantly, changing N has a dramatic impact on the texture of the maze (compare 1 2 4 8 etc on a decently large maze).

by rawxtl

0 subcomment

I still remember the days when I started out programming.. I used simply copy and write code from TheCodingTrain's challenge videos. And the recursive backtracking algorithm was the first project I took on by myself coding it in java while only looking at how it works from his explanation.

by 89netraM

1 subcomments

I've built a few maze generators based on Jamis' book. The one I'm most proud of is this one https://xn--sberg-lra.net/maze/irregular?size=5&entryCount=1 that generates SVG mazes with sort of irregular lines.

by snorbleck

1 subcomments

Awesome resource. I recently (in the past week) created a maze game. I used Claude (sonnet 4.5) for the most part, but some things, like images, were created with ChatGPT. I may do a blog about it if anyone is interested in the inner-workings and my thought process from concept to vibecoded. I am by no means a game dev, was just curious about what it would take to create unique single solution mazes with some game-like components thrown in, and trying it with the assistance of AI. It turned out somewhat retro. Now go get lost!
https://lorelabyrinth.entropicsystems.net/weekly

by dang

2 subcomments

Related:
Maze Generation: Recursive Division (2011) - https://news.ycombinator.com/item?id=42703816 - Jan 2025 (12 comments)
Maze Algorithms (2011) - https://news.ycombinator.com/item?id=23429368 - June 2020 (22 comments)
Representing a Toroidal Grid - https://news.ycombinator.com/item?id=10608476 - Nov 2015 (2 comments)
Maze Generation: Recursive Backtracking - https://news.ycombinator.com/item?id=4058525 - June 2012 (1 comment)
Maze Generation: Weave mazes - https://news.ycombinator.com/item?id=4052856 - June 2012 (3 comments)
Maze-generation algorithms, with JS demos - https://news.ycombinator.com/item?id=2190017 - Feb 2011 (9 comments)
Generating random mazes with the Growing Tree algorithm (w/ Javascript demo) - https://news.ycombinator.com/item?id=2148348 - Jan 2011 (6 comments)
Maze Generation: Wilson's algorithm - https://news.ycombinator.com/item?id=2123695 - Jan 2011 (11 comments)
Maze Generation: Kruskal's Algorithm - https://news.ycombinator.com/item?id=2062999 - Jan 2011 (9 comments)
Maze Generation: Eller's Algorithm - https://news.ycombinator.com/item?id=2048752 - Dec 2010 (9 comments)
Also:
Wilson's Algorithm - https://news.ycombinator.com/item?id=45549017 - Oct 2025 (9 comments)
Maze Tree - https://news.ycombinator.com/item?id=7746822 - May 2014 (38 comments)
Solving a Maze with D3.js - https://news.ycombinator.com/item?id=7631864 - April 2014 (19 comments)
Think Labyrinth: Maze Algorithms - https://news.ycombinator.com/item?id=10101728 - Aug 2015 (10 comments)
Practical algorithms and code optimization: maze generation - https://news.ycombinator.com/item?id=5431561 - March 2013 (10 comments)
Maze Algorithms - https://news.ycombinator.com/item?id=157266 - April 2008 (1 comment)
Others?

by dfajgljsldkjag

1 subcomments

I've always known about algorithms that solve mazes, but never about actually making them. It's interesting seeing all these algorithms and how the mazes they generate look different.

by ginko

0 subcomment

It feels like many of the more complicated algorithms produce worse mazes (long horizontal/vertical walls, many 1-2 square dead ends next to another) than basic recursive backtracking.

by bricks96

0 subcomment

Here's a Google Sheets Maze Generator that's pure formula and no script. This post has got me thinking how I might format the formula to be shaped like a maze. https://tinyurl.com/SheetsMazeGenerator

by OscarCunningham

1 subcomments

Is it known which algorithms produce 'difficult' mazes? I'm imagining you could run all the maze solving algorithms against all the maze generating algorithms many times, and then calculate what the Nash equilibrium would be if the solver is trying to minimise expected time and the generator is trying to maximise it.

by richard_chase

0 subcomment

This is the kind of stuff I come here for.

by ZuzuDuck

0 subcomment

This makes me nostalgic, when i started to programming i tried to create ultimate generating maze algorithm and use it in some game. But my solutions was really naive.

by jaberjaber23

0 subcomment

seconding the jamis buck book, its one of the few programming books i actually finished. the way he explains each algorithm with visualizations makes it stick