### Author Topic: 2D maze generation algorithms...  (Read 81 times)

#### dreamerman

• Global Moderator
• Dr. Type
• Posts: 430
##### 2D maze generation algorithms...
« on: 2022-Aug-02 »
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
« Last Edit: 2022-Aug-02 by dreamerman »
Check my source code editor for GLBasic - link Update: 20.04.2020

#### bigsofty

• Community Developer
• Prof. Inline
• Posts: 2768
##### Re: 2D maze generation algorithms...
« Reply #1 on: 2022-Aug-03 »
Cool stuff!

Where did you get all those various maze generating algorithms?

Thank you Dreamerman!
« Last Edit: 2022-Aug-03 by bigsofty »
Cheers,

Ian.

“It is practically impossible to teach good programming style to students that have had prior exposure to BASIC.  As potential programmers, they are mentally mutilated beyond hope of regeneration.”
(E. W. Dijkstra)

#### erico

• Community Developer
• Prof. Inline
• Posts: 4411
##### Re: 2D maze generation algorithms...
« Reply #2 on: 2022-Aug-03 »
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

• Global Moderator
• Dr. Type
• Posts: 430
##### Re: 2D maze generation algorithms...
« Reply #3 on: 2022-Aug-03 »
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.

Check my source code editor for GLBasic - link Update: 20.04.2020