Generating Mazes (opens in new tab)

(healeycodes.com)

153 pointsitsjloh1y ago31 comments

31 comments

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

remram1y ago

This segfaults for me somehow.

tromp1y ago

See https://tromp.github.io/pearls.html for suggested changes to make thus run with modern compilers.

mysterydip1y ago

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

lloydatkinson1y ago

I also really recommend this book. I've been working through it over the last few months and expanding it and I've still got a lot of book to go! Really fun, interesting, and a great change from some of the usual work.

I've been posting my progress with it on mastodon. Generating animated GIFs of the generation and traversal to solve it has been a whole fun sub-topic I've been working on too. I render each computation step to a PNG, and get ffmpeg to build GIFs or MP4s.

https://mastodon.social/@lloydjatkinson/media

The same author also has a book on raytracing. My wife got me both books for Christmas and I didn't realise just how much building/hacking/creativity/fun I'd get out of them.

kragen1y ago

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

YeGoblynQueenne1y ago

>> however, in rogue, and in wmaze, walls occupy a whole grid cell.

I think I know what you mean and I had the same kind of problem: pretty much evey maze-generation algorithm assumes the map is initially a grid of cells with four walls and proceeds by removing those walls one-by-one, systematically.

The problem you had, and that I had in my project, is that your grid is made up of single characters, say like this:

  ■ ■ ■ ■
  ■ ■ ■ ■
  ■ ■ ■ ■
  ■ ■ ■ ■

Where "■" is a wall. It is not clear how you can "remove a wall" from this grid. If you just replace each wall character with a floor character, say, "□", you have removed _four_ walls, not just one. Then if you use any of the standard maze-generation algos you end up with "maze snow", like this:

  □ □ □ ■ □ □ □ □ 
  □ ■ □ □ □ ■ □ ■ 
  □ □ □ ■ ■ □ ■ □ 
  □ ■ □ □ □ □ □ □ 
  □ □ □ ■ □ ■ □ ■ 
  □ ■ □ □ □ ■ □ □ 
  □ □ □ ■ □ □ □ ■ 
  □ ■ □ □ □ ■ □ □

One way to work around this that I found online is to implicitly pad every wall with an extra character, so that for example, if you carved a two-step path starting at the top-left corner of the fully blocked maze above and going to the right, it would look like this:

  ■ ■ ■ ■
  □ □ ■ ■
  ■ ■ ■ ■
  ■ ■ ■ ■

Instead of like this:

  □ □ ■ ■
  ■ ■ ■ ■
  ■ ■ ■ ■
  ■ ■ ■ ■

I didn't like that because it effectively halves the dimensions of every maze. So I had a cunning plan and came up with an alternative that models an agent moving through a grid representing a maze and "discovering" the maze as it goes, as usual, but with some constraints that ensure the maze never loops back to itself. I'm working in Prolog so you might find it as hard to read my code as I found it to read your Forth :) but it's here anyway:

https://github.com/stassa/ijclr_2024_experiments/blob/6cf3cc...

The idea is that, at any timestep, an agent navigating a grid is observing the following cells, with the agent centered on 1/1:

  0/0  1/0  2/0
  0/1 >1/1< 2/1
  0/2  1/2  2/2

Where the cells in this 3 × 3 grid (I call it an "observation matrix") are populated at random, with wall or floor tiles, which may result e.g. in an observation matrix like this:

  □ ■ ■  
  □ @ ■ 
  ■ ■ ■

With the agent as a '@'. Now it's obvious that if the agent moves one step up it will create a four-cell open-space, a "plaza", like so (there's a floor tile under the agent now):

  □ @ ■  
  □ □ ■ 
  ■ ■ ■

So in this case you don't let the agent move up, only right, or down (it probably came from the left so you don't let it go back that way or it will enter a military oscillation: right-left-right-left-right... ). In a similar way you can avoid looping (it gets a bit complicated but you can find the logic in my comments in maze_generator.pl linked above).

Then it's a matter of moving through a fully-blocked initial grid cell-by-cell and laying down "observation matrices" at random, while respecting the anti-plaza and anti-looping constraints. You have to restart the process from a wall cell in a "hunt-and-kill" fashion every time it reaches a dead end to complete the maze but you get mazes that look like this (for a 40 × 40 maze):

  □ ■ □ □ □ □ ■ ■ □ □ □ ■ ■ ■ ■ □ □ □ ■ □ □ □ □ □ □ □ □ ■ ■ □ □ □ □ □ ■ □ □ □ □ □ 
  □ ■ □ ■ ■ □ ■ □ □ ■ □ □ ■ ■ □ □ ■ □ □ □ ■ ■ ■ ■ ■ ■ □ ■ □ □ ■ ■ ■ □ ■ □ ■ ■ □ ■ 
  □ ■ □ ■ ■ □ □ □ ■ ■ ■ □ ■ □ □ ■ ■ ■ □ ■ ■ □ □ □ □ ■ □ □ □ ■ ■ □ ■ □ ■ ■ ■ □ □ □ 
  □ ■ □ □ ■ □ ■ ■ ■ □ ■ □ ■ □ ■ ■ □ ■ □ ■ □ □ ■ ■ □ ■ ■ ■ ■ ■ □ □ ■ □ □ ■ □ □ ■ □ 
  □ ■ ■ □ ■ ■ ■ □ □ □ ■ □ □ □ ■ ■ □ ■ □ ■ ■ □ □ ■ ■ ■ □ □ □ ■ □ ■ ■ ■ □ □ □ ■ ■ □ 
  □ ■ ■ □ □ ■ □ □ ■ □ ■ ■ ■ □ □ □ □ ■ □ □ ■ ■ □ □ ■ ■ □ ■ □ □ □ □ ■ ■ ■ ■ ■ ■ ■ □ 
  □ □ ■ ■ □ ■ □ ■ ■ □ □ □ ■ ■ ■ ■ ■ ■ ■ □ □ ■ ■ □ □ ■ ■ ■ ■ □ ■ □ □ □ □ □ ■ ■ ■ □ 
  ■ □ □ ■ □ □ □ ■ ■ ■ ■ □ □ ■ ■ □ □ □ ■ ■ □ □ ■ ■ □ □ ■ ■ □ □ ■ ■ ■ ■ ■ □ □ ■ ■ □ 
  ■ ■ □ ■ ■ ■ □ ■ □ □ ■ ■ □ ■ □ □ ■ □ ■ ■ ■ □ □ ■ ■ □ □ ■ □ ■ ■ ■ □ □ ■ ■ □ ■ □ □ 
  □ □ □ □ □ □ □ ■ ■ □ □ □ □ ■ □ ■ ■ □ ■ □ ■ ■ □ □ ■ ■ □ ■ □ □ □ ■ □ ■ ■ □ □ □ □ ■ 
  □ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ ■ ■ □ ■ □ □ ■ ■ □ □ ■ □ ■ ■ ■ □ □ □ ■ ■ ■ ■ ■ ■ ■ 
  □ ■ ■ □ □ □ □ □ ■ □ □ □ □ ■ E ■ ■ □ ■ ■ □ □ ■ ■ □ ■ □ □ ■ ■ ■ ■ □ □ ■ ■ □ ■ □ □ 
  □ ■ □ □ ■ ■ ■ □ □ □ ■ ■ □ ■ □ ■ ■ □ ■ ■ ■ □ □ ■ □ ■ ■ □ □ □ ■ ■ ■ □ □ ■ □ □ □ ■ 
  □ ■ □ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ □ □ □ ■ □ □ □ ■ ■ □ □ □ □ ■ ■ ■ □ □ □ ■ ■ □ ■ ■ □ ■ ■ 
  ■ ■ □ ■ □ ■ ■ □ □ □ □ ■ ■ ■ ■ ■ ■ □ ■ □ □ □ □ ■ ■ ■ ■ ■ □ □ ■ □ ■ ■ □ □ □ □ □ □ 
  □ □ □ ■ □ □ □ □ ■ □ ■ ■ ■ □ □ □ ■ ■ ■ ■ ■ ■ ■ ■ □ ■ ■ □ □ ■ ■ □ □ ■ ■ ■ ■ ■ ■ □ 
  □ ■ ■ ■ □ ■ ■ ■ ■ □ □ ■ □ □ ■ □ □ ■ □ □ □ ■ ■ □ □ □ □ □ ■ ■ ■ ■ □ □ □ □ ■ ■ ■ □ 
  □ ■ □ ■ □ □ ■ □ ■ ■ □ □ □ ■ ■ ■ □ □ □ ■ □ ■ □ □ ■ □ ■ ■ ■ □ □ ■ □ ■ ■ □ □ ■ □ □ 
  □ ■ □ ■ ■ □ □ □ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ ■ □ ■ ■ □ □ ■ ■ ■ □ ■ □ ■ ■ ■ □ ■ □ ■ 
  □ ■ □ □ ■ ■ ■ □ □ □ ■ □ □ ■ ■ □ □ ■ ■ □ □ ■ □ □ ■ ■ □ □ ■ ■ □ □ □ □ □ ■ □ ■ □ □ 
  □ ■ ■ □ □ □ ■ □ ■ □ □ □ ■ ■ □ □ ■ ■ □ □ ■ ■ ■ □ □ ■ ■ □ □ ■ ■ ■ ■ ■ □ ■ □ ■ ■ □ 
  ■ ■ ■ ■ □ ■ ■ ■ ■ ■ ■ □ ■ □ □ ■ ■ ■ □ ■ ■ ■ ■ ■ □ □ ■ ■ □ □ □ □ □ ■ □ ■ □ ■ □ □ 
  □ □ ■ ■ □ ■ □ □ □ □ ■ □ □ □ ■ ■ ■ □ □ □ ■ ■ ■ ■ ■ □ □ ■ ■ ■ ■ ■ □ ■ ■ ■ □ ■ □ ■ 
  ■ □ □ □ □ ■ □ ■ ■ □ ■ ■ ■ □ □ □ ■ ■ ■ □ □ □ □ □ ■ ■ □ □ ■ □ □ ■ □ □ ■ ■ □ ■ □ ■ 
  ■ ■ □ ■ □ ■ □ □ ■ □ □ □ ■ ■ ■ □ ■ □ ■ ■ ■ □ ■ □ □ ■ ■ □ □ □ ■ ■ ■ □ □ ■ ■ ■ □ □ 
  □ □ □ ■ ■ ■ ■ □ ■ ■ ■ □ □ □ ■ □ □ □ □ □ ■ □ ■ ■ S □ ■ ■ ■ □ □ □ ■ ■ □ □ □ ■ ■ □ 
  □ ■ ■ ■ ■ □ □ □ ■ □ ■ ■ □ ■ ■ ■ ■ ■ ■ □ ■ □ ■ ■ ■ □ □ □ ■ ■ ■ □ ■ ■ ■ ■ □ □ □ □ 
  □ ■ ■ □ □ □ ■ ■ ■ □ □ ■ □ □ □ □ □ □ ■ □ ■ □ □ □ ■ □ ■ □ ■ □ ■ □ □ □ ■ ■ □ ■ ■ ■ 
  □ ■ □ □ ■ ■ ■ □ □ □ ■ ■ ■ □ ■ ■ ■ □ ■ □ ■ ■ □ ■ ■ □ ■ □ □ □ ■ ■ ■ □ □ ■ ■ ■ ■ □ 
  □ ■ □ ■ ■ □ ■ ■ □ ■ ■ □ ■ □ ■ □ ■ ■ ■ □ ■ □ □ □ ■ □ ■ □ ■ □ □ ■ ■ ■ □ □ ■ ■ □ □ 
  □ ■ □ □ ■ □ ■ ■ □ ■ ■ □ □ □ □ □ ■ □ □ □ ■ ■ ■ □ ■ ■ ■ □ ■ ■ □ □ ■ ■ ■ □ □ ■ □ ■ 
  □ ■ ■ □ □ □ ■ □ □ □ ■ ■ ■ ■ ■ □ □ □ ■ ■ ■ □ ■ □ □ □ ■ □ □ ■ ■ □ ■ □ ■ ■ □ ■ □ ■ 
  □ □ ■ ■ ■ □ ■ □ ■ □ □ ■ □ □ ■ ■ ■ ■ ■ □ □ □ ■ □ ■ □ ■ ■ □ □ ■ □ ■ □ ■ ■ □ ■ □ □ 
  ■ □ □ □ ■ □ □ □ ■ ■ □ ■ ■ □ ■ □ ■ □ □ □ ■ □ ■ ■ ■ □ □ ■ ■ □ ■ □ □ □ ■ ■ □ ■ ■ □ 
  ■ ■ □ ■ ■ ■ ■ ■ ■ ■ □ □ □ □ ■ □ □ □ ■ ■ ■ □ □ ■ ■ ■ □ □ ■ ■ ■ □ ■ □ □ ■ □ □ ■ □ 
  ■ ■ □ □ □ □ □ □ □ ■ ■ ■ ■ □ ■ ■ □ ■ ■ □ ■ ■ □ □ □ ■ ■ □ □ □ ■ ■ ■ ■ □ ■ ■ □ □ □ 
  ■ ■ □ ■ □ ■ ■ ■ □ □ □ □ ■ □ □ □ □ ■ □ □ □ ■ ■ ■ □ □ ■ ■ ■ □ □ ■ ■ □ □ □ ■ ■ ■ □ 
  ■ □ □ ■ □ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ ■ ■ ■ □ ■ ■ □ □ □ ■ ■ □ □ ■ ■ ■ ■ ■ □ ■ □ 
  □ □ ■ ■ □ □ ■ □ □ □ ■ ■ □ □ □ □ ■ ■ □ ■ □ □ □ ■ ■ □ ■ □ □ ■ ■ □ □ ■ ■ □ □ □ ■ □ 
  □ ■ ■ ■ ■ □ □ □ ■ □ □ □ □ ■ ■ □ □ □ □ □ □ ■ □ □ □ □ ■ ■ □ □ ■ ■ □ □ □ □ ■ □ □ □

Oh and you randomly place the S[tart] and E[nd] tiles of course. And you know generated mazes are always solvable because you solve them to generate them (like with DFS etc).

But note that in the maps you get this way there are blocked-out regions, "clumps" of wall tiles. There may be a better set of constraints that gets rid of those, but the result was good enough for my needs and I didn't bother.

And of course you can use the same technique to solve a maze and even do a bit of SLAM (Simultaneous Localisation and Mapping) by placing observation matrices in an expanding grid as the agent moves in an initially unseen map. OK, TMI, I'm stopping here.

kragen1y ago

this is awesome! and the maze it produced looks great! yeah, the halving-dimensions thing is a form of what i did in the golang thing i linked

i'm pretty comfortable with prolog, and i'll take a look at your code later :)

1 more reply

zazaulola1y ago

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

efilife1y ago

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

YeGoblynQueenne1y ago

Yeah, it's confusing. The standard maze generation algorithms start with a fully-blocked grid where each cell has four walls, then proceed to punch holes through one wall at a time. This is basically the same procedure as solving a maze, except when solving a maze you only move between cells that already have holes punched between them. So a solver is really a generator run backwards.

Think of it as an automaton: it can both accept and generate a string. The string here is the path through the maze.

But I think the main, shall we say, contribution of the article is the method they use to find the farthest two points on a maze, that they then set as the entry and exit point of the maze. It's at the end of the article, after the discussion of their preferred method to generate a maze.

SynnVoid1y ago

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 .

Arcorann1y ago

> 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...

KingOfCoders1y ago

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

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

kragen1y ago

these are pretty! are they from depth-first search?

KingOfCoders1y ago

Thanks! I sadly no longer remember and have the code no longer it seems.

jkcxn1y ago

I had fun generating isometric mazes

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

devnull31y ago

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).

bollu1y ago

what definition of "fair" was reached upon?

devnull31y ago

Under pressure, I suggested the following:

1. Only one solution (or path in this case) should exist

2. No loops (meaning the valid solution does not cross it-self)

3. The length of false path from correct path should not be more than 4

1 more reply

jnurmine1y ago

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

blue11y ago

There's a whole book devoted to that, titled "10 PRINT CHR$(205.5+RND(1));:GOTO 10"

jnurmine1y ago

Nice, it's a free download too. Thanks!

1 more reply

fjfaase1y ago

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

at_a_remove1y ago

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.

utdiscant1y ago

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.

samstave1y ago

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.)

y421y ago

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...

j / k navigate · click thread line to collapse

31 comments

tromp1y ago

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

remram1y ago

This segfaults for me somehow.

tromp1y ago

See https://tromp.github.io/pearls.html for suggested changes to make thus run with modern compilers.

mysterydip1y ago

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

lloydatkinson1y ago

https://mastodon.social/@lloydjatkinson/media

The same author also has a book on raytracing. My wife got me both books for Christmas and I didn't realise just how much building/hacking/creativity/fun I'd get out of them.

kragen1y ago

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

YeGoblynQueenne1y ago

>> however, in rogue, and in wmaze, walls occupy a whole grid cell.

The problem you had, and that I had in my project, is that your grid is made up of single characters, say like this:

  ■ ■ ■ ■
  ■ ■ ■ ■
  ■ ■ ■ ■
  ■ ■ ■ ■

  □ □ □ ■ □ □ □ □ 
  □ ■ □ □ □ ■ □ ■ 
  □ □ □ ■ ■ □ ■ □ 
  □ ■ □ □ □ □ □ □ 
  □ □ □ ■ □ ■ □ ■ 
  □ ■ □ □ □ ■ □ □ 
  □ □ □ ■ □ □ □ ■ 
  □ ■ □ □ □ ■ □ □

  ■ ■ ■ ■
  □ □ ■ ■
  ■ ■ ■ ■
  ■ ■ ■ ■

Instead of like this:

  □ □ ■ ■
  ■ ■ ■ ■
  ■ ■ ■ ■
  ■ ■ ■ ■

https://github.com/stassa/ijclr_2024_experiments/blob/6cf3cc...

The idea is that, at any timestep, an agent navigating a grid is observing the following cells, with the agent centered on 1/1:

  0/0  1/0  2/0
  0/1 >1/1< 2/1
  0/2  1/2  2/2

Where the cells in this 3 × 3 grid (I call it an "observation matrix") are populated at random, with wall or floor tiles, which may result e.g. in an observation matrix like this:

  □ ■ ■  
  □ @ ■ 
  ■ ■ ■

With the agent as a '@'. Now it's obvious that if the agent moves one step up it will create a four-cell open-space, a "plaza", like so (there's a floor tile under the agent now):

  □ @ ■  
  □ □ ■ 
  ■ ■ ■

  □ ■ □ □ □ □ ■ ■ □ □ □ ■ ■ ■ ■ □ □ □ ■ □ □ □ □ □ □ □ □ ■ ■ □ □ □ □ □ ■ □ □ □ □ □ 
  □ ■ □ ■ ■ □ ■ □ □ ■ □ □ ■ ■ □ □ ■ □ □ □ ■ ■ ■ ■ ■ ■ □ ■ □ □ ■ ■ ■ □ ■ □ ■ ■ □ ■ 
  □ ■ □ ■ ■ □ □ □ ■ ■ ■ □ ■ □ □ ■ ■ ■ □ ■ ■ □ □ □ □ ■ □ □ □ ■ ■ □ ■ □ ■ ■ ■ □ □ □ 
  □ ■ □ □ ■ □ ■ ■ ■ □ ■ □ ■ □ ■ ■ □ ■ □ ■ □ □ ■ ■ □ ■ ■ ■ ■ ■ □ □ ■ □ □ ■ □ □ ■ □ 
  □ ■ ■ □ ■ ■ ■ □ □ □ ■ □ □ □ ■ ■ □ ■ □ ■ ■ □ □ ■ ■ ■ □ □ □ ■ □ ■ ■ ■ □ □ □ ■ ■ □ 
  □ ■ ■ □ □ ■ □ □ ■ □ ■ ■ ■ □ □ □ □ ■ □ □ ■ ■ □ □ ■ ■ □ ■ □ □ □ □ ■ ■ ■ ■ ■ ■ ■ □ 
  □ □ ■ ■ □ ■ □ ■ ■ □ □ □ ■ ■ ■ ■ ■ ■ ■ □ □ ■ ■ □ □ ■ ■ ■ ■ □ ■ □ □ □ □ □ ■ ■ ■ □ 
  ■ □ □ ■ □ □ □ ■ ■ ■ ■ □ □ ■ ■ □ □ □ ■ ■ □ □ ■ ■ □ □ ■ ■ □ □ ■ ■ ■ ■ ■ □ □ ■ ■ □ 
  ■ ■ □ ■ ■ ■ □ ■ □ □ ■ ■ □ ■ □ □ ■ □ ■ ■ ■ □ □ ■ ■ □ □ ■ □ ■ ■ ■ □ □ ■ ■ □ ■ □ □ 
  □ □ □ □ □ □ □ ■ ■ □ □ □ □ ■ □ ■ ■ □ ■ □ ■ ■ □ □ ■ ■ □ ■ □ □ □ ■ □ ■ ■ □ □ □ □ ■ 
  □ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ ■ ■ □ ■ □ □ ■ ■ □ □ ■ □ ■ ■ ■ □ □ □ ■ ■ ■ ■ ■ ■ ■ 
  □ ■ ■ □ □ □ □ □ ■ □ □ □ □ ■ E ■ ■ □ ■ ■ □ □ ■ ■ □ ■ □ □ ■ ■ ■ ■ □ □ ■ ■ □ ■ □ □ 
  □ ■ □ □ ■ ■ ■ □ □ □ ■ ■ □ ■ □ ■ ■ □ ■ ■ ■ □ □ ■ □ ■ ■ □ □ □ ■ ■ ■ □ □ ■ □ □ □ ■ 
  □ ■ □ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ □ □ □ ■ □ □ □ ■ ■ □ □ □ □ ■ ■ ■ □ □ □ ■ ■ □ ■ ■ □ ■ ■ 
  ■ ■ □ ■ □ ■ ■ □ □ □ □ ■ ■ ■ ■ ■ ■ □ ■ □ □ □ □ ■ ■ ■ ■ ■ □ □ ■ □ ■ ■ □ □ □ □ □ □ 
  □ □ □ ■ □ □ □ □ ■ □ ■ ■ ■ □ □ □ ■ ■ ■ ■ ■ ■ ■ ■ □ ■ ■ □ □ ■ ■ □ □ ■ ■ ■ ■ ■ ■ □ 
  □ ■ ■ ■ □ ■ ■ ■ ■ □ □ ■ □ □ ■ □ □ ■ □ □ □ ■ ■ □ □ □ □ □ ■ ■ ■ ■ □ □ □ □ ■ ■ ■ □ 
  □ ■ □ ■ □ □ ■ □ ■ ■ □ □ □ ■ ■ ■ □ □ □ ■ □ ■ □ □ ■ □ ■ ■ ■ □ □ ■ □ ■ ■ □ □ ■ □ □ 
  □ ■ □ ■ ■ □ □ □ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ ■ □ ■ ■ □ □ ■ ■ ■ □ ■ □ ■ ■ ■ □ ■ □ ■ 
  □ ■ □ □ ■ ■ ■ □ □ □ ■ □ □ ■ ■ □ □ ■ ■ □ □ ■ □ □ ■ ■ □ □ ■ ■ □ □ □ □ □ ■ □ ■ □ □ 
  □ ■ ■ □ □ □ ■ □ ■ □ □ □ ■ ■ □ □ ■ ■ □ □ ■ ■ ■ □ □ ■ ■ □ □ ■ ■ ■ ■ ■ □ ■ □ ■ ■ □ 
  ■ ■ ■ ■ □ ■ ■ ■ ■ ■ ■ □ ■ □ □ ■ ■ ■ □ ■ ■ ■ ■ ■ □ □ ■ ■ □ □ □ □ □ ■ □ ■ □ ■ □ □ 
  □ □ ■ ■ □ ■ □ □ □ □ ■ □ □ □ ■ ■ ■ □ □ □ ■ ■ ■ ■ ■ □ □ ■ ■ ■ ■ ■ □ ■ ■ ■ □ ■ □ ■ 
  ■ □ □ □ □ ■ □ ■ ■ □ ■ ■ ■ □ □ □ ■ ■ ■ □ □ □ □ □ ■ ■ □ □ ■ □ □ ■ □ □ ■ ■ □ ■ □ ■ 
  ■ ■ □ ■ □ ■ □ □ ■ □ □ □ ■ ■ ■ □ ■ □ ■ ■ ■ □ ■ □ □ ■ ■ □ □ □ ■ ■ ■ □ □ ■ ■ ■ □ □ 
  □ □ □ ■ ■ ■ ■ □ ■ ■ ■ □ □ □ ■ □ □ □ □ □ ■ □ ■ ■ S □ ■ ■ ■ □ □ □ ■ ■ □ □ □ ■ ■ □ 
  □ ■ ■ ■ ■ □ □ □ ■ □ ■ ■ □ ■ ■ ■ ■ ■ ■ □ ■ □ ■ ■ ■ □ □ □ ■ ■ ■ □ ■ ■ ■ ■ □ □ □ □ 
  □ ■ ■ □ □ □ ■ ■ ■ □ □ ■ □ □ □ □ □ □ ■ □ ■ □ □ □ ■ □ ■ □ ■ □ ■ □ □ □ ■ ■ □ ■ ■ ■ 
  □ ■ □ □ ■ ■ ■ □ □ □ ■ ■ ■ □ ■ ■ ■ □ ■ □ ■ ■ □ ■ ■ □ ■ □ □ □ ■ ■ ■ □ □ ■ ■ ■ ■ □ 
  □ ■ □ ■ ■ □ ■ ■ □ ■ ■ □ ■ □ ■ □ ■ ■ ■ □ ■ □ □ □ ■ □ ■ □ ■ □ □ ■ ■ ■ □ □ ■ ■ □ □ 
  □ ■ □ □ ■ □ ■ ■ □ ■ ■ □ □ □ □ □ ■ □ □ □ ■ ■ ■ □ ■ ■ ■ □ ■ ■ □ □ ■ ■ ■ □ □ ■ □ ■ 
  □ ■ ■ □ □ □ ■ □ □ □ ■ ■ ■ ■ ■ □ □ □ ■ ■ ■ □ ■ □ □ □ ■ □ □ ■ ■ □ ■ □ ■ ■ □ ■ □ ■ 
  □ □ ■ ■ ■ □ ■ □ ■ □ □ ■ □ □ ■ ■ ■ ■ ■ □ □ □ ■ □ ■ □ ■ ■ □ □ ■ □ ■ □ ■ ■ □ ■ □ □ 
  ■ □ □ □ ■ □ □ □ ■ ■ □ ■ ■ □ ■ □ ■ □ □ □ ■ □ ■ ■ ■ □ □ ■ ■ □ ■ □ □ □ ■ ■ □ ■ ■ □ 
  ■ ■ □ ■ ■ ■ ■ ■ ■ ■ □ □ □ □ ■ □ □ □ ■ ■ ■ □ □ ■ ■ ■ □ □ ■ ■ ■ □ ■ □ □ ■ □ □ ■ □ 
  ■ ■ □ □ □ □ □ □ □ ■ ■ ■ ■ □ ■ ■ □ ■ ■ □ ■ ■ □ □ □ ■ ■ □ □ □ ■ ■ ■ ■ □ ■ ■ □ □ □ 
  ■ ■ □ ■ □ ■ ■ ■ □ □ □ □ ■ □ □ □ □ ■ □ □ □ ■ ■ ■ □ □ ■ ■ ■ □ □ ■ ■ □ □ □ ■ ■ ■ □ 
  ■ □ □ ■ □ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ ■ ■ ■ □ ■ ■ □ □ □ ■ ■ □ □ ■ ■ ■ ■ ■ □ ■ □ 
  □ □ ■ ■ □ □ ■ □ □ □ ■ ■ □ □ □ □ ■ ■ □ ■ □ □ □ ■ ■ □ ■ □ □ ■ ■ □ □ ■ ■ □ □ □ ■ □ 
  □ ■ ■ ■ ■ □ □ □ ■ □ □ □ □ ■ ■ □ □ □ □ □ □ ■ □ □ □ □ ■ ■ □ □ ■ ■ □ □ □ □ ■ □ □ □

Oh and you randomly place the S[tart] and E[nd] tiles of course. And you know generated mazes are always solvable because you solve them to generate them (like with DFS etc).

kragen1y ago

this is awesome! and the maze it produced looks great! yeah, the halving-dimensions thing is a form of what i did in the golang thing i linked

i'm pretty comfortable with prolog, and i'll take a look at your code later :)

1 more reply

zazaulola1y ago

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

efilife1y ago

YeGoblynQueenne1y ago

Think of it as an automaton: it can both accept and generate a string. The string here is the path through the maze.