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

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

[@alian714]

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!

[@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

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

[@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!

[@darkener3210]

Would love to see a cell design that combined both your algorithm and the origin shift algorithm Where you can generate the initial maze with your algorithm and have the maze shift while in play using origin shift Plus being able to run origin shift for a little while on top of your look ahead would completely remove the problem of mazes being too similar

[@timmygilbert4102]

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

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

[@Pystro]

I just had an idea: What is keeping us from using the same generation algorithm on the *negative space?* I.e. generate a branching, non-looping set of *interior walls* that all connect to the outer walls eventually, instead of a branching, non-looping set of *paths* that all connect to the entrance eventually. The big advantage that I see is that with the path-based lookahead generation, it's trivial to find the entrance as long as you have a map of the generating (Hilbert) curve (not even the maze!). And that's entirely based on the fact that you're able to follow the paths, which are the directional entity. But you can't (directly) follow walls in the same way. Depending on the weights for the walls, the result may be identical to a certain set of weights for the paths. For example, binary tree walls and binary tree paths have a 1:1 relation. Zig-zag tree walls and zig-zag tree paths are related. Midpoint tree walls and midpoint tree paths are related (after all, it's just 4 binary trees stuck together). Spiral-lookahead for the paths probably has some spiral-based pyramid scheme of weights for the walls that makes the two equivalent. And there is even be a *"negative space" version of the origin shift* algorithm. Making a "negative space origin shift" algorithm would come with the huge downside that you have to allow the origin to move "into" the outer walls (the entire outer wall would probably be one position). And that implies that it can exit that perimeter from any position. If you don't allow the origin to move into the outer walls, then you'll eventually end up with a clump of walls in the center which are only connected to the outside walls in one point, and the perimeter along the outside walls would be completely walkable with exception to that one connection.

[@3njooo]

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

[@KindOfWitch]

fr

[@simonwillover4175]

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

[@choonyongtan5671]

Thats insanely fast

[@RaPsCaLLioN1138]

'wanna watch me generate a maze?' love that

[@captainluma7991]

THIS IS GENIUS

[@Shack263]

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

[@caoliva]

this is insanely cool

[@c0der23]

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

[@flockofwingeddoors]

fantastic and engaging video!

[@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!

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

[@blockybeggar6423]

That is amazing

[@vladthemagnificent9052]

Wait, can you generate a random maze and then use it as an elevation map for the next maze? after couple iterations you will get a completely random maze.

[@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

[@AllExistence]

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

[@Aurarora]

amogus in the thumbnail 💀

[@coppertones7093]

the only complaint is that the musical chime is too repetitive