2D maze generation algorithms...

[dreamerman]

I'm currently playing with some maze generation algorithms for my logic/puzzle game pack, didn't see any such topic here on forum, so I thought that sharing this could be a good idea. Some maze generation examples available on web have nice visualization, just hope that my would be sufficient to show how each algorithm work. Project includes implementation of several most common maze generation algorithms like: Binary Tree, Sidewinder, Hunt&Kill, DFS/Backtracker, Eller, Prim, Growing Tree. Some were modified to add difficulty variation - mostly length of walk in current direction.
One major addition would be bridges (paths above/beneath another), those simple algorithms have limited possibilities for that, and needs to be used in combination or as addition to some other techniques - like regions, pre-calculating bridge positions and so on. Last algorithm - Growing Tree has basic bridge logic implemented.

One thing that code can be a little messy, most time I use Javascript for such prototyping and code was ported to GLB to share on forum (GLB is also target/final language). Feel free to modify, and new functions.

Controls:
-+ -> switch algorithm
[] -> change map width
<> -> change map height
space -> generate maze
escape -> end

[bigsofty]

Cool stuff! 

Where did you get all those various maze generating algorithms?

Thank you Dreamerman!

[erico]

Superb! I made a few generators before but they are more like a stage generator than a maze generator and is quite the rogue thing, if I used any know algo, I don´t know which
Yours is much more competent, I will be taking a look this week.
Worry not about beauty on generator...the numbered array they generate is the more important piece.
On another thread I made a 3d dungeon crawler, which lead me to think of what you said about crossovers or tunnels, it is probably a whole different kind of beast and I would not know where to start. Thanks for sharing!

[dreamerman]

Where did you get all those various maze generating algorithms?

for me most understandable and competent sources were those:
https://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap.html
https://professor-l.github.io/mazes/
https://www.astrolog.org/labyrnth/algrithm.htm
I didn't implement all of algorithms found on those websites as not all were optimal/interesting and could be used as base for something more in game based environment.

@erico
Generally I also do something different from classic algorithms, or rather don't care which things from particular method are useful in current situation, as level generation is kind a different thing and needs more complex solutions. Some example can be multi-stage generation with way-points navigation using A-star pathfinding and so on.
Bridges/tunnels can be done in several ways, depending on what is required in game, either pre-calculate their positions and use some modified algorithm or place them in main loop using some markers (tiles counter from last bridge and similar) as I made in last algorithm in attached code (Growing Tree) - yet this implementation isn't best, bridges aren't evenly distributed on whole map.

[Ian Price]

Noice

[dreamerman]

Just for testing I have added modified version of Prim algorithm to generate more straightforward maze - tiles can be either empty/passable or blocked, it may simplify uses in some cases and shows how easily it can be modified.
Another thing that could be interesting for more complex algorithms are tunnels, yet it would complicate drawing, as such should be easy to differentiate from dead ends - just matter of proper sprites.

[Qedo]

Very interesting dreamerman here there is to study hard 
I didn't think there were so many algorithms on this topic
Thanks so much for sharing

[dreamerman]

There are more of them but quite similar, some completely inefficient, and some have slightly different use cases like mazes on infinite maps, but it's good to see how they works and adopt something from them to proper game oriented code.
Of course more interesting are different shapes of cells and grid itself, for example circular maze - polar grids, but this would require vector drawing routines, I know that there was some small lib for that here on forum, but at moment I've other priorities. Yet I will try to add some simplified maze generation routine for 3d cube, it shouldn't be hard.