A new maze algorithm optimized for Redstone

[@Riv_Falcon]

The demonstration at the end perfectly captured the spirit of “Wanna watch me do it again?”

[@zackbuildit88]

The funny thing is, this is actually completely compatible with origin shift, you could generate your "first pass" with this method and then run origin shift on the result, choosing a random cell to be the origin (preferably a non-border one to avoid boring mazes with very little changing), and then running origin shift for maybe just a number of iterations equal to 1/4th of boardsize, and then you now have a maze that can be both reasonably fast and also extremely varied

[@divy1211]

the water and flow analogy for Binary tree maze generation is so beautiful, and the idea to use space filing curves is amazing. Awesome video!

[@caspermadlener4191]

The biggest drawback of any redstone maze is when it takes a lot of time to generate while it can't be played. You and your friends can only play it once until everybody has to leave, for it to scramble. I would have thought that origin shift was the only solution to this. I would have been wrong. This is insane.

[@Sucralose2]

As a non-programmer but a huge fan of mazes and labyrinths this is a really interesting way to view mazes. I've seen the water-filled mazes videos and even a couple of those simulations of particles and waves solving mazes, but it's just so fascinating that you can model a solution or a solution attempt with a height map and it looks like a river. I wonder what a proper labyrinth could look like though, one with the entrance inside the maze instead of on the edge, with "island" walls that you can't follow to the exit, and the edges of the maze could have traps obviously that would be modelled as water flowing out of the maze (but not indicating victory just loss of water?). I wonder if there could ever be multiple "flows" of water? sorry if this sounds dumb

[@DqwertyC]

You could make a more open maze with this method by adding a small chance that a room will open up into more than one of the cells 'lower' than it. I'm not entirely sure what that would look like, but that would introduce loops/islands while still guaranteeing every cell is accessible

[@Pystro]

@@DqwertyC The extra paths don't even have to go "downhill". As long as the first connection goes downhill, you'll guarantee full connectedness; and beyond that you can do whatever you want.

[@darksentinel082]

This is some really clever stuff. Well done!!! Visualizing the algorithm as water flow makes the generalization process simpler and make so much more sense

[@Mnnvint]

Thank you for telling be about the Gilbert curve! I have been looking for generalizations to rectangles for many years.

[@Nikoline_The_Great]

Wow. This will be ideal for generating massive mazes on a normal computer too. It is effectivelt maximally efficient for parralel computation if you find a good way of generating the space filling curve effectively. Very well done.

[@inv41id]

Well, for a 2^n by 2^n grid filled by a Hilbert curve you can quite simply calculate the index in n steps... now to just figure out if you can calculate multiple steps at once with some fancy bitwise tricks

[@ThinkWithGames]

Cool to see a fellow maze enthusiast! May I recommend linking part 1 in the description?

[@DqwertyC]

Thanks for the suggestion!

[@3njooo]

Can't wait for the third video! This series is awesome

[@KindOfWitch]

fr

[@choonyongtan5671]

Thats insanely fast

[@c0der23]

That's a very cool algorithm, I wonder if there are any recognizable patterns in the mazes that it generates...

[@RaPsCaLLioN1138]

'wanna watch me generate a maze?' love that

[@captainluma7991]

THIS IS GENIUS

[@caoliva]

this is insanely cool

[@simonwillover4175]

6:45 you can use bitwise operators in this part to calculate the exact value by just looking at each square individually.

[@hanelyp1]

If every cell can be computed independently, using a pseudo-random based on the coordinate of the cell and a seed value, the maze could be generated as traversed. Use a height calculated from the coordinate and you can even have a "zero storage" maze, where all that needs to be remembered is your current cell and the random seed. Perfect for an infinite maze.

[@Shack263]

Let's goooo 😎 I was just thinking about this series!

[@WaterDroplet02]

i find it extremely funny that, in the process of attempting to develop a quality maze algorithm optimized enough to be effectively made with redstone, you ended up also making a quality maze algorithm that's just super optimized and fast in general, judging by the noises of the other maze algorithmists in the comments

[@ArtificialDjDAGX]

feel like you could expand upon this by making use of the other ideas you had to create a massive maze made out of segments, so you're more or less linking up smaller mazes that use all of these types of algorithms. I mean, having the center of a maze utilize the second-to-last idea would be a great way to distinguish it from the other parts.

[@BadlyOrganisedGenius]

What a cool algorithm! I'd imagine it works with any space-filling curve, so you could increase the number of possible mazes by finding a way to randomize the curve. That may be a bridge too far when it comes to ease of implementation though, so for redstone purposes this algorithm already seems pretty close to ideal. Great stuff!

[@timmygilbert4102]

Bro, it's procedural river generator ❤ now we can have river that actually flow correctly 👌

[@flockofwingeddoors]

fantastic and engaging video!

[@blockybeggar6423]

That is amazing

[@Pystro]

Interestingly, you aren't even limited to using space filling curves for the "heights". The only condition you have is that all cells except for one have at least one neighbor with a lower index (which then probably should be called an elevation rather than an index). Oh, and two neighboring cells have to have different values - but that's often of trivial; for example when even/odd values form a checkerboard pattern. You can for example generate such a height map by taking an existing maze, choosing a random origin point and calculating every cell's distance (along the paths) from that point. The indices of the cells can be pre-calculated from a fixed maze (if you just want to make it slightly less obvious how the maze is generated). Or you can use the maze generated in the previous run. The only downside with that is that the new maze will be quite similar to the previous one. But if you iterate generating a maze from the previous maze an infinite amount of times, you'll probably even get the property that all mazes are equally likely. Fun fact: If you take the taxicab distance from a corner you get back to the binary tree algorithm; And if you take the taxicab distance from the center you get the midpoint tree algorithm.

[@DqwertyC]

I had thought of something similar (using another maze as the heightmap for generating a new maze), but hadn't considered moving the origin between iterations. If the origin stays in a fixed location, I'm pretty sure the maze eventually devolves into a 'mid'-point tree, regardless of the starting state

[@Pystro]

@@DqwertyC Correct, if the origin stays in place, then you will eventually devolve into a mid-point tree. And while we're talking about devolving: The Hilbert Curve is technically one special case of a maze that a binary split algorithm (with a slightly modified order of the splits) can generate. Which makes it seem like you should technically have more possible mazes if you generate your heightmap from a "binary split" maze than if you used a Hilbert curve.

[@Pystro]

Another interesting (but not very challenging) arrangement of heights that I realized was possible after writing the initial comment: With the spiral heightmap, you're iterating over each edge of the remaining central "square" portion, and assigning heights that always decrease in counter-clockwise direction. This gives you 4 "pizza slices" where you're effectively running the binary tree generation. If you instead *alternate* the direction between clockwise and counter-clockwise on even/odd distances from the outer edge, or if you *randomly chose* between clockwise and counter-clockwise progression for each edge, then you'd effectively be running a sidewinder-like generation in each pizza slice.

[@AllExistence]

You said each cell is independent, but you still generate one by one?

[@LuveelVoom]

Great video! Could cellular automata algorithms be used for minecraft-suitable maze generation? Each cell operates with only local behavior

[@DqwertyC]

There are a couple of automata that can generate mazes, but they don't always generate connected mazes. There is a cool maze solving automata I may highlight at some point, though

[@Aurarora]

amogus in the thumbnail 💀

[@coppertones7093]

the only complaint is that the musical chime is too repetitive