8 Maze Generating Algorithms in 3 Minutes

[@skyman255]

---Time Stamps for all Algorithms-- Depth first search 0:16 Randomized Prim's Algorithm 0:33 Eller's Algorithm 0:49 Hunt-and-kill Algorithm 1:06 Binary Tree Algorithm 1:23 Randomized Kruskal's Algorithm 1:39 Sidewinder Algorithm 1:56 Aldous-Broder Algorithm 2:12

[@karlnikolasalcala8208]

Possibly the best enumeration video. No small talks, and goes immediately to the point!

[@jasontoddchampion]

Thank you for this video. It is incredibly useful, and seeing the visualization alongside the description is helpful. If there was a "useful information density" award, you deserve it.

[@ezhabebe2904]

This was so satisfying to watch man, keep up the good work!

[@TheLazyReviewer]

This is strangely relaxing!! Excellent job

[@the_green_snake4187]

This is the best formatted video i've seen

[@franzrojasayala1401]

But can it generate the path to the maze of your heart?

[@hhcdghjjgsdrt235]

single dude

[@Tricob1974]

My algorithm ("Maze Creator") is closest to the Depth First Search. It stores a number in each cell visited, giving it a 1, 2, 3, or 4 depending on what direction it moves to from there (North, East, South, and West). If a dead end is reached, any square it backtracks from is marked with a "5". These are all "guide numbers". Each cell contains one 8-bit number, and the guide number is stored in the fourth, fifth, and sixth bit of the cell's contents. The seventh and eighth bits contain "path data", where the seventh bit tells if the south path is open, while the eighth bit tells if the east path is open (To see if the west path is open, you have to check the data from the cell to west, while the cell to the north will tell you if the north path is open).

[@crayder1100]

I've been playing around with applying randomness to depth-first. During generation steps I simply give chances to do the following instead of normal depth-first'ing; jump to random unvisited cell anywhere near the path and branch from there (many more branches this way, interestingly long ones), randomly backtrack a few spaces and branch from there (again more branches but smaller ones), or randomly allow the depth-first phase then go back to the previous cell (even more branches, but this makes single and double node dead-ends more often which is fantastic for my game). Each of these three values can be adjusted and produce much better results than normal depth first. EDIT: TLDR* normal depth-first normally ends up generating a long path with very few branches to get lost in. Mine eliminates the latter.

[@klauspeter2199]

I've tried that, too :D I also like to allow some paths to extend longer in a certain direction. To me it makes the paths look more like mazes in real life, where you kind of have long hallways instead of having corners every 1 - 2 cells. It's more refreshing if you walk through the maze. I used that for a minecraft maze generator if that makes more sense.

[@crayder1100]

@@klauspeter2199 ​ I made it in JS as well so you can test it out here: (link removed because KZbin keeps deleting my comment... not sure how to share it.) You can see what the fields at the top are by clicking on them. But it's Width, Height, Random Branch Chance, and Random Stasis Chance. Branch chance make branches more likely and Stasis makes the map generate around where it is currently more often. These are important for what I was explaining above. Also if you click Calculate then Path it'll show you the longest possible path.

[@crayder1100]

​@@klauspeter2199 (ht$tp @s : / / jsf $iddl@ e$.@net/Cr@ ay $d eh/8$07 n$w 6z $ f/ @ 31/sh o @$ w) (remove spaces, @, and $ symbols, KZbin keeps deleting my comment with the link in it)

[@crayder1100]

@@klauspeter2199 Yes, all those spaces and symbols were necessary and THAT'S F**KING STUPID, @Google.

[@klauspeter2199]

@@crayder1100 is it available on your github?

[@lehase8474]

Nice visual explanation of the algorithms

[@ryanmota3280]

This is super interesting i gotta stay tuned.

[@trombonemunroe]

This video was so good I immediately subscribed! But where's Wilson's algorithm? It generates an unbiased sample from the uniform distribution over all mazes, using loop-erased random walks, not favouring either long corridors (like DFS) nor many short dead ends (like Kruskal's and Prim's algorithms). It should be included here.

[@madarauchiha3293]

This is something new! be waiting for more!

[@black-kv5ly]

This video is what I want to see. very good!!!💯💯💯

[@cakerzpit518]

This was very helpful

[@magnaviator]

so cool, thanks!

[@large_ahmed]

Is there a specific algorithm that forms a maze from a selected finnish & end ? (Within a boundry)???

[@todo1553]

i think the best way would be to generate the maze then carve a path

[@large_ahmed]

@@todo1553 cheers

[@subrezz5389]

Awesome 🔥🔥

[@dennismalone6735]

nice video!

[@white_145]

1:46 isnt it wave function collapse?

[@everlyjayag8521]

very satisfying!!!!

[@prashanthbala7368]

Love this

[@pabloyagani]

Cool vid 😁

[@LIFTTOEAT]

This is so memorizing! 👀

[@ImXyper]

I think you mean mesmerising

[@Fr3shAl3xLp]

nice video :)

[@DropShotPat]

how do i git at that repo...

[@AVADH_OJHA-gd7pu]

DPS was the best one

[@kevnar]

Any algorithm with excessive amounts of hallways a single cell long should not count as a maze. When you can clearly see it's a dead end, it's no longer a puzzle to solve. It's just a bunch of space filler. You might as well just seal those passages off and have a single path through the whole thing. You know you're a nerd when you start gatekeeping what counts as a valid maze algorithm.

[@daybydaysounds4386]

So interesting! 🧠

[@RACHOTINANDINIRACHOTINANDINI]

where is the github link?

[@lelsonmclel1207]

nice

[@amazon8549]

Wanted a tutorial.

[@raphaelcontri993]

the randomized DFS is the easiest

[@raphaelcontri993]

but the kruskall's one is the mlst beautiful to watch

[@tushardixit679]

nice