Generating Mazes

With my 1988 IOCCC entry

    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,"_.":" |"];}

discussed in more detail in Don Libes' "Obfuscated C and Other Mysteries" [1], I turned out to have rediscovered Eller's algorithm, which only keeps one line of the maze in memory.

[1] https://tromp.github.io/maze.html

For those interested in maze generation, I highly recommend "Mazes for Programmers": http://www.mazesforprogrammers.com/

mike bostock did this fantastic visualization of maze generation algorithms a few years ago, including wilson's algorithm but not aldous–broder: https://bost.ocks.org/mike/algorithms/#maze-generation

i wrote a minimal roguelike a couple of weeks ago in forth: http://canonical.org/~kragen/sw/dev3/wmaze.fs (2-minute asciicast at https://asciinema.org/a/672405, or you can run it in gforth) and tried to generate the level as a perfect maze with an algorithm related to these, but just visiting the walls in a random order, which doesn't produce an unbiased maze

however, in rogue, and in wmaze, walls occupy a whole grid cell. so i decided to remove walls unless they either connected an open cell above to one below that it was already connected to, or an open cell to the left to one to the right that it was already connected to, because i had decided to not permit diagonal movement. but this turned out to have two unexpected effects:

1. sometimes it would connect a cell, say, to the left with one above it that it was already connected to. this results in a maze that isn't quite perfect, which i think is an improvement

2. sometimes a cell will occur with walls on all four sides of it which are not removed. this is fine unless treasure or the player spawns there, in which case the game is impossible

so i need to tweak the algorithm, but i otherwise really like the meandering mazes it produces, and i think the extra connections from point 1 above give the dungeons a desirable nonuniformity and keep the mazes from being too difficult

visiting walls in random order has the same effect as prim's algorithm with random weights (or equivalently kruskal's), but in my case obviously i broke that correspondence because my walls aren't graph arcs. i can recommend doing that on a proper graph as a perfect maze generation algorithm, which is what i did in 02018 in http://canonical.org/~kragen/sw/dev3/unimaze.go, which is much more readable, if a bit repetitive and longwinded

This article is more complete and more interactive:

https://weblog.jamisbuck.org/2011/2/7/maze-generation-algori...

Code for generating mazes in different languages can be found here:

https://rosettacode.org/wiki/Maze_generation

I don't understand. The article is about maze generation and it only talks about traversing predefined mazes. I had a similar thought after reading an article about generating sudokus. Like they were alreadt generated and the article was about creating a solver. I am surely missing something, what's the part I don't understand?

Ok, after rereading I think I'm starting to understand. The walls of the cells are generated after, based on the path the generator went through? I feel stupid for not understanding this later but will leave this in case I still don't understand something

Another good resource for maze algorithms is Walter D. Pullen's website: https://www.astrolog.org/labyrnth/algrithm.htm . The page showing his maze generations is also interesting: https://www.astrolog.org/labyrnth/maze.htm .

> I also read that starting with Aldous Broder and then switching to Wilson's Algorithm (reasoning: Aldous Broder is slow at the end, Wilson's Algorithm is slow at the start) is faster than either. However, I haven't seen proof that this combination still results in a uniform spanning tree (where all possible mazes have equal probability).

I did some searching, and the paper at [1] (2022) studies the problem. Based on the paper, a naive combination of the two algorithms can generate uniform spanning trees on complete graphs, but more work is needed for arbitrary graphs. [2] apparently cites this when discussing their hybrid maze generating algorithm, but I haven't been able to find a copy to check.

[1] https://arxiv.org/abs/2206.12378 [2] https://www.spiedigitallibrary.org/conference-proceedings-of...

I've generated mazes for the cover of my poetry book

https://www.amazon.com/Olavsweg-Gedichte-Gedanken-lyrische-I...

I had fun generating isometric mazes

https://www.reddit.com/r/proceduralgeneration/comments/kxau1...

Maze(s) triggers PTSD in me. I was asked to write a code to generate one using a 100x100 grid in an Google interview in 40 min such that it was "fair". It was for L6/L7 (IC) position. I wrote a working code and the interviewer even acknowledged that I had atleast have a working code compared to others. The actual time I had was 30 min as 10 min included upfront discussion about what "fair" means and some time after-the-code discussion on improvements.

I was rejected with lean-no-hire (or weak-no-hire .. I don't remember the exact term but basically not a strong reject).

I was very young when I first saw the Commodore C64 maze generation trick using forward slash and backward slash. The characters are randomly selected and just printed one after another, the result is a maze-like pattern.

Such a maze is probably not a real maze, not solvable always (I don't know). But it was mind-boggling back then, and still is.

There's a video here: https://www.youtube.com/watch?v=Ym2nimY1hs0

Maze generation is a fascinating topic. I also played with different maze generating algorithms and wrote a program [1] that generates SVG files that can be send to a laser-cutter. I used it to do some investigations on the statistics of different types of algorithms. I have some fascination with mazes that only have rooms with either one or three exits [2]. I used the program to create an kind of inverted maze with different heights which now hangs in my living room. [3]

[1] https://github.com/FransFaase/MazeGen

[2] https://www.iwriteiam.nl/counting.html#paper

[3] https://www.iwriteiam.nl/D2006.html#21

Somewhat adjacent, I have been interested in generating mazes of the "cave" form. Many algorithms exist here, even some cellular automata approach for a more realistic simulationist approach. However, I have been kicking around ideas to take the very irregular results from that sort of tack and then abstract them back to a nodes-and-edges parallel data structure. Which is to ask, in this grid of filled in or empty cells, which gaps are the caves, and which are the twisty little passages?

At least for games, I am starting to lean toward the idea that humans like the simulationist approaches as "feeling right," but the abstract graph is better for the machines, and that the ability to start with one and then produce the other is where we will eventually go.

Back in my early university days I did a short project (https://www.dropbox.com/scl/fi/ch33p2xaq7xavgu9uk0qv/index.p...) on how to generate "hard" mazes. While there are many algorithms to create mazes, there is no real literature (maybe for good reason) on how to create mazes that are hard for humans to solve.

Check out this cool thread:

https://news.ycombinator.com/item?id=41162505

Show HN: Visual A pathfinding and maze generation in Python *

ME: (Vine Robots and Maze Algos):

This would be neat to see applied to Vine Robots: https://youtu.be/eLVAMG_3fLg?t=153

---

Talk about the use of the pneumatic vine robots to nav rubble and caves etc - but if the vine robot could evaluate the terrain and use appropriate routing algo based on the nature of the terrain it was doing. they arent using vision necessarily in the vine robots - but if they could use terrain sensors that informed the best routing algo to use/accomplish goal that would be neat.

Another interesting thing about this would be to apply it to where vine-style micro-trenchers could know the patter of the lattice that will best be needed to accomplish whatever the stated newton bracing requirement were - then you could plop relative light foot pads onto a celestial body - then have these vine into the surface in such a way where you can begin to attach larger objects and very easily build foundations to large space structures - plus, as it maps out - you have an exact map of what your mycelium -like base foundation look like.

EDIT:

And you could grow the foundation as need - however, imagine a series of tubes maybe by these vining robots - that are later filled in (the robots) with structural hardening material -- you vine your robots into the mountain in sequences - first do a large outer lattice - and structurally brace it with whatever material - then in the center space - vine into the core and fill those with explosives and tunnel. -- then you can snake through your exploded rubble - see whats up - and deliver cables and hoses through the vine to a forward location...

A vine robot that tunnels - but its outer layer is a permeable filter and it has capillary features - but basically it unfurls into being a well and the outer material is expanded do to corrugations in the design allowing debris filters water to create a layer around the new pipe - and then capillaried up - or a pump in the core at the head of the water-wyrm.

(I need to figure out how to make some of these -- I love them.)

another Ressource about how to tackle this task in Javascript (shameless self promotion)

Read “How to create a maze with JavaScript“ by Nicky Reinert on Medium: https://medium.com/swlh/how-to-create-a-maze-with-javascript...