Generating Mazes

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

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

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

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

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