Which Maze Algorithm is best for Minecraft?

[@cheesybrik]

The fact a whole new (and genuinely quite useful) maze generation algorithm was made specifically for Minecraft is the type of computer science I wanna see more of

[@DqwertyC]

You should definitely keep an eye out for the rest of this series then. I've been teasing it for a bit now, but the end result is a new algorithm designed for redstone that can generate a 16x16 maze in about a second

[@CloudPhase]

@@DqwertyC It's funny because for an actual normal computer a 16x16 maze in a second is catastrophically bad, but for minecraft that's actually really impressive

[@electra_]

For Origin Shift, you could start the maze with a simple algorithm like the binary tree to give it a half-decent maze in the "uncompleted" parts instead of those being obviously unfinished straight lines.

[@DqwertyC]

Yup, this is a good tweak for the start! I think the primary strength of origin shift is the "constantly shifting" aspect, so in most use cases the starting state doesn't actually matter too much

[@ABaumstumpf]

@@DqwertyC It would make the time till a large maze is somewhat finished drastically shorter at the cost of having another fully-fledged maze-algorithm that only jumpstarts the thing.

[@inv41id]

@@ABaumstumpf I'm not sure if I'd consider the binary tree a fully-fledged maze algorithm... It's so simple to build in redstone that you can generate the entire maze in an instant.

[@ABaumstumpf]

@@inv41id it is crude but it does produce a full maze that is a far better starting-position than just lines given that even if you would stop the origin-shift after a very short time you would not be left with an unsolvable maze nor with all those empty straight tunnels.

[@conure512]

I watched the whole thing. this was fascinating. Your idea of using Origin Shift while the player was actively running it is pure evil-genius energy. Imagine telling someone to enter the maze (no top-down view) and then just not telling them that the maze was constantly changing lmaooo

[@DqwertyC]

The idea of having someone in the maze while it's changing was actually part of Captain Luma's original pitch. The real power play would be to have a second player intentionally moving the origin to try to get their opponent as lost as possible

[@pocarski]

@@DqwertyC Make two players each solve their own maze. Player 1's position is Player 2's origin, and vice versa.

[@zackbuildit88]

​@@pocarskithat's genius. You're genius

[@sage5296]

@@DqwertyC Gotta use skulk sensors to keep the origin away from the player so they never realize it's changing

[@Red1984AnimalFarm]

oh god, this is going to make me fall down a rabbit hole of maze generation algorithms

[@WannabeMarysue]

binary division looks fun, because the way it generates in cells would make it easy to signal to the player when they're making progress from a first person perspective. one of the problems with first person mazes is poor signalling of progress, and ability to get 'turned around'. you could even colour code the cells, for maximum player feedback.

[@DqwertyC]

I hadn't even considered that angle! I actually already have a redstone maze for binary division, and the circuitry is color coded by layer, but I could see coloring the walls or cells being a nice addition to the maze itself

[@LordHonkInc]

I remember seeing the video where CaptainLuma came up with the Origin Shift algo (before the name was even finalized), so seeing people refer to it alongside these much older and more sophisticated algos feels like hearing somebody prove Einstein's general relativity theorem by finding gravitational waves and going "oh yeah, I remember hearing him talk about that in that one Berlin pub in 1916"

[@edwardg117]

I made a maze generator with a databack a few years ago. Though I wanted lots ot loops and dead space as the game I was trying to create with it needed those. It worked by placing a starting cell and 4 cells on each side. Each cell that gets created had an armor stand in the middle to represent the position of the cell, and an additional armor stand at the edge of each side of the cell (called connectors). Every tick the process would pick one cell and choose bettween 1-3(weighted based on distance from start compared to max size limit) connectors to become paths, with all remaining connectors becomming noPaths. If the number of paths it chose does not equal the ammout it can make, and there are floors remaining, it turns itself into a staircase and generates another staircase below it. Each new path creates a new cell next to it (if no new cell, else convert that cell's connector to a path), it then instructs that cell to have it's connectors check for adjacent paths or noPaths and change it's connectors to match. The cell would then delete itself and any paths, leaving only noPaths so an future cell knows not to generate a path there. At the end there would be a bunch of cells that made it to the size limit, the generator would then loop around the outside of the maze and connect them to make two to three edge cells one giant loop. At the end, any noPaths remaining is a wall I could put a feature or objective on/in and I would pick those randomly, then delete all armor stands (excepting the start) from that level. So when it's finished generating the whole maze there are multiple floors, with denser corridors in the middle with more loops and dead ends, with larger loops running around the outside. It was a fun learning project but it only works for a maze of limited size. It'd be cool to implement one that could work for infinite size and be less concerned about how big a cell is.

[@pleaserespond3984]

Combine Binary Tree with Origin Shift. Binary Tree already generates mazes where cells naturally point towards the origin, then you can run Origin Shift for a short while to jumble it up. Should give you best quality mazes at a fraction of the time and not be hard to implement in redstone as BT is trivial.

[@tminusboom2140]

I would like to suggest the Aldous-Broder Wilson Minus Algorithm. Start with Aldous-Broder. Every time the algorithm enters a square that has no unvisited neighbors, it begins again at a random unvisited square. Instead of looking at a proportion of total visited squares, it changes to Wilsons after the no unvisited neighbors triggers a set number of times, which would need to be set based on the scale of the map in question. For your smaller mazes, I would use a number around 3, where the larger one would have 8. In formulating an official standard for how many times the cycle should repeat, I would suggest a logarithmic value based on the total number of squares in the maze.

[@RaPsCaLLioN1138]

very happy to see more maze content

[@ABaumstumpf]

What about the inside-feel of a maze? it might look horrendously bad from the top, but if you are inside and don't know the characteristics? could also be the other way around: Looking good but not nice to be in.

[@DqwertyC]

That's an interesting point. I'm not entirely sure how I would go about this - I can do math on average dead end length, average number of branches etc., but that wouldn't capture the entire subjective feel of solving the maze

[@AidenErickson-w4z]

​@@DqwertyCsometimes you just have to go about it experimentally

[@scrambo6182]

Wow! Interesting content, good voiceover, well put together demonstrations. Subscribed!

[@bcmpinc]

These are maze generation algorithms where you have a grid of rooms and decide whether they are connected. There's another set of maze generation algorithms that work on a grid of cells and you decide whether each cell is free or a wall. Those might be easier to make and more visually appealing in Minecraft. My favorite states with the border walks and all interior cells free, then repeatedly picks a free cell with no neighboring walls. Picks a direction. Then moves in that direction placing walls until it hits another wall. To make it more organic, you can randomly go a bit to the side every step. This gives mazes where the path goes a bit back and forth rather than in a more or less straight line to the end (as with kruskal and prims algorithms).

[@thealientree3821]

I like how it feels like Wilson’s Algorithm was having a character arc.

[@3njooo]

Actually such an underrated video, very intereyting topic and great editing quality, I hope this gets more popular.

[@bruex2277]

This was much more entertaining than I expected it to be! Love your voice btw, it's really soft

[@shayden7227]

I hate how great channels like this are not popular but stuff like skibidi tolet has people foaming at the mouth

[@lelaleasl]

I like recursive division, cus it makes the maze feel like it has "biomes" places where the maze behaves and feels very differently

[@sutsuj6437]

Great video! Your channel seems like a hidden gem. Subscribed! Also, for the more complex to implement algorithms, it's probably worth it to just build a Redstone computer, since they require a lot of central coordination.

[@DqwertyC]

It's the eternal conflict of Computer Engineering. Custom hardware will ultimately always be faster for a specific use case, but will it actually be enough of an improvement to be worthwhile

[@typicwhisper6569]

Recursive Division can produce much better mazes if it always makes the wall on the shorter direction. It also has more randomness than Binary Division.

[@DqwertyC]

That's an interesting tweak. Another possibility I considered is weighting the choice to choose near the center of the room without necessarily choosing the halfway point, trying to avoid those long parallel corridors. I don't agree that more randomness is inherently better - it just means a larger number of possible mazes. If we make a tweak that doubles the number of mazes, but most of those mazes are bad, we've lowered the average output of the algorithm.

[@xonroy7061]

I think this is the best video of the year

[@Speed001]

I appreciate this objective ranking of minecraft maze making algorithms/j

[@jokerofspades-xt3bs]

Origin shift seems like a perfect tool for a Minotaur style shifting maze. Maybe using command blocks to create a giant floating golden cube as the curser of the algorithm (above player height so it doesn’t just crush them).

[@bredcataw]

That was... Informative. Thanks, DqwertyC!

[@somdudewillson]

10:10 I'm not a redstone expert, but I'm pretty sure you could do this with a big box of unique items (one for each wall) and building wall circuitry with item filters. Simply send out the unique items in a random order without replacing them, and you are now randomly selecting walls and tracking the unvisited set. Once you're out of items, you're done. The cells _would_ need to track which 'accesible group' they're a part of as well, but I think you could have each cell contain an internal counter that matches the highest number it's seen to track that 'accesibility' (and have a special condition state for 'never been grouped' and initialize each new group with a random number).

[@DqwertyC]

This could work for selecting walls. Maybe a circuit that sends out a pulse to connected cells could be used to see if cells are already connected? Both of those systems sound like they would take a long time though...

[@somdudewillson]

@@DqwertyC Checking if cells are connected can be done with a simple comparison - as I briefly mentioned in my original comment. More detailed explanation: * Each cell tracks an internal 'connectivity group'. * Two cells with the same value are connected - i.e. there exists a path from one to the other. * Each cell's connectivity group is randomized (so you do need sufficient range on this number to avoid collisions). * When cell gets a new neighbor or a cell's neighbor has their group number change, check if the neighbor's group is higher than your own - if so, set yours equal to theirs. (I have no idea how hard this would be to build with redstone, this is just an adaptation of a traditional pathfinding optimization technique to be highly parallel and with no global state.)

[@doggfite]

I wish I remember who did it, but I swear that someone already implemented this algorithm in Minecraft some number of months ago, either this year or last. I'm going to have to see if I can find the video now

[@bowfuz]

hi! i have an in-progress python maze game that uses origin shift, and with the help of my friend, we found an excellent fix for the ever-lasting corridors in larger mazes: hijack the random walk every few thousand steps, and force it to walk to a specific location (and force it to follow the maze and not change any walls, this can be done as simply as following the directed graph from point B to A, making a list of the path, and then reversing that list of steps (turning ups into downs, lefts into rights, and reversing the order of the elements on the list), and moving the origin according to that reversed list), and define a regularly spaced lattice of locations based on the maze's dimensions. the algorithm picks from this list of new locations (in order, not randomly, though it probably doesn't matter), takes the origin there, and then does, maybe, 10000 random walk steps. it makes a really consistent coverage of the maze, and doesn't leave any corridors :3

[@DqwertyC]

That's a nifty fix! I don't know how feasible that sort of change would be in Minecraft, but I could see that being helpful in other applications

[@bowfuz]

@@DqwertyC i've thought it through a bit, the process of going from A to B doesn't seem too tricky in my mind, just have a stack whose individual registers are directly readable from the outside. the generating lattice "checkpoints" as i call them, may be just a process of- well alright it's fairly complicated, but it's just integer math ultimately, that and looping x3

[@noahbarlow1646]

@@DqwertyC My first thought is to kinda cheat the path, as a compromise between unbiased maze generation and simplicity. Look at each direction the origin can go and pick the one that brings you closer to the checkpoint (you don't actually have to calculate the distance since there's a clear transition point at each diagonal), then if you hit a dead end (which is easy to detect cause it's a node with only one exit) you break through the dead end. It's need to be tested to say how many dead ends you'll hit on average, but it shouldn't be too bad and doesn't have the same issue as just drawing a straight line there.

[@vsikifi]

All these algorithms generate singly connected mazes that can be solved trivially by following one wall. Multiply connected mazes require the solver to actually memorize where he has been to avoid running in a loop.

[@Andrew-jh2bn]

As long as the maze starts and ends on the side, it can always be solved by following one wall. Now if you end in the middle, then yes you're correct.

[@segfaultdev]

Awesome video! What if, in a redstone Origin Shift implementation, you add a vertical line detector, which keeps track of when there is a vertical corridor of at least some length X, and stop the algorithm once it no longer finds one? A neat way you could implement that is by having some vertical redstone lines paired with each maze cell (so it drops one level every cell it moves upward or downward), and then, on every wall that splits vertical lines (visually horizontal walls), you force the cell immediately above and below to signal level 15, and then you only have to detect if, in any of the cells in the entirety of the maze, there is a signal level below a certain threshold Y. If space per cell isn't that much of a concern, it sounds like something that should at most add just one point in complexity, but it guarantees good mazes given enough time to satisfy the condition. I will leave it to the redstoners to decide upon its complexity though, as I don't know that well what I'm talking about :/

[@GameJam230]

6:04 This could actually be a useful property to have if you started with it and then used a few generations Origin Shift to make it a little more varied, since they already maintain the “everything points to the root node” property you need to start with for it to work. This is under the assumption that you didn’t want to use origin shift for a constantly changing maze, but instead for generating a static maze by changing little pieces of a base one. Although, I don’t imagine Prim’s Algorithm would be particularly easy to build in Minecraft like Original Shift was.

[@DqwertyC]

@RaPsCaLLioN1138 has a cool modified Prim's algorithm that sort of works in reverse. Each tick, all the unvisited cells choose a random direction, and if the direction they choose is part of the maze, they connect to it

[@GameJam230]

@ I see! Couldn’t that lead to loops forming though? Or when you say “part of the maze” do you just mean “within the bounds of the maze but not connected to it yet”?

[@DqwertyC]

@GameJam230 by part of the maze I mean connected to the maze already. You won't run into loops, because each cell only points into one other cell, and the origin doesn't point anywhere. I'd recommend taking a look at the original videos, they go into a lot more detail on why it all works

[@GameJam230]

@@DqwertyC oh that’s because I misread. I thought you said all VISITED cells choose a random direction. THAT would lead to loops

[@AkivaB]

About Wilson's algorithm you can just make cells connected to their neigbors and make it so they take a signal then randomly srlect its direction If you hiy an active (non finalized) cell just shut of the redstone to reset up to it

[@DqwertyC]

I think I can sort of see how this would work... Still a lot of global signals that might be a pain, but this would work for the loop-erased random walk

[@AkivaB]

@DqwertyC you can also optimize it by using a random seed for the first 2 points and activating many cells at the same time allowing them to merge if needed (though there's the danger of a signal turning and hitting another signal causing problems).

[@Hlebuw3k]

These all seem to be "simple" maze generators. They don't generate loops, and because of that all the mazes can be beaten by simply following any wall until the exit. Are there any "complex" maze generators? I think it would be easy to add a chance to remove random walls after these algorithms finish generating the "simple" mazes. Also, what if the cells are not symetrical? Or to get from one cell to a neighbouring cell, the corridors that result from taking down walls have variation in length?

[@roderik1990]

I believe just having either the entrance or exit be somewhere in the centre of the maze would already defeat the wall following tactic.

[@Hlebuw3k]

@@roderik1990 There is only 1 path in the entire maze, so no, it would not.

[@DqwertyC]

Most of these algorithms come from graph theory, and are concerned with forming spanning trees, which is why they don't have loops. From what I can find, the general consensus for generating mazes with loops is "just generate a maze without loops and remove some walls" life you suggested. Since most of these algorithms come from graph theory, they don't actually care about the size or shape of the room, just which rooms are potential neighbors. Any of the algorithms that just care about choosing random cells or random neighbors would work on a hex grid, or a bunch of tetronimo shaped rooms, or to connect neighboring spots on a giraffe if you wanted really weird shaped rooms

[@jimiwills]

That was really interesting ❤

[@brycehawken1833]

I’ve always made binary division, the downside is the lowest level has dead end that are obvious. The maybe upside is if you don’t see the large view it’s really hard to solve because you can’t tell if you have visited this area before because it locally all looks the same

[@vigenere-key_kokabuterimon]

What about ones for 3d mazes? Mazes with multiple levels that you're also traversing up and down. One that not only challenges you horizontally but also vertically.

[@DqwertyC]

The neat thing about most of these is that they can be expanded to 3d (or higher, I suppose) by just adding more layers above and below. Anytime we "choose a random neighbor," we choose between six directions instead of just 4

[@Luilu]

Very good explanation

[@PLMMJ]

I feel like, if you need to do more painting stuff, you should have all the paintings lined up in your inventory and bring them to your hotbar when it's their turn. Then you would spend less time and mot have to re-check paintings.

[@sayethwe8683]

All of these algorithms generate simple mazes - that is, no loops will be formed and all walls are connected to each other. you could theoretically create a complex maze just by deleting some extra walls randomly.

[@MiaaaaaChan]

I don't quite get Origin Shift from your explanation. You say we 'repeat this process' but never explain the process, how does moving the origin change walls?

[@hamzamotara4304]

I think that you could almost totally eliminate redstone complexity via generating a maze with an external program, and using a programmable redcoder for a simple cell shifting mechanism, no? The single major flaw would be it no longer being automatic, but it would allow high quality mazes to be made fast.

[@the_furf_of_july4652]

Would it be possible to do a different hybrid of aldous-broder-wilson? Rather than having an arbitrary threshold to switch from one to the other, have both methods run at once/alternating steps. The odds of both methods getting stuck at once would be lower, and the transition would be more gradual and convenient. My main concern is if this would still meet the same maze quality result.

[@Adowrath]

One thing I was wondering about the Hunt and Kill, although it's likely not applicable to building it in Redstone: Wouldn't tracking the bounds of the generated part of the maze (so min & max in all dimensions) eliminate a huge overhead when hunting for new cells to continue on? And there's probably more effective techniques that could be used to improve hunt performance (e.g. if there's a stretch > 10 cells or so that's filled in, write that in a list of skips or something, or similarly for higher dimensions). Great video nonetheless, of course!

[@hydroxa4330]

I feel like some of these algorithms were rated unfairly for redstone difficulty, as some of the ones you ranked quite low I could envision a circuit for pretty quickly. I feel Origin Shift is very easy to build, but you basically cant parallelise it so it's worse for time complexity

[@DqwertyC]

Do you have any specific examples? I'm definitely not a redstone expert, and there may be possibilities I didn't take into account

[@hydroxa4330]

@DqwertyC the one that stuck out the most was Eller's algorithm. I'm not a redstoner myself, so I could be missing something, however: You could link up the cells left to right, randomly placing a wall as you go as long as the next tile isn't active. On the 2nd pass where you link the rows, you have a redstone line acting like a flag to indicate that a path upwards has not yet been made for this row, which increases the odds of generating the vertical wall. When it hits a wall, the line gets re-activated, and you go again. If the line is still active when you hit a wall, you place a vertical path there before moving to the next tile. This is also very parallelizable, as you can create all the rows at the same time, then bridge all the rows at the same time as a 2nd pass. Imo the main challenge there would be keeping it small, but the actual circuitry itself would be relatively simple in comparison to some of the other mazes talked about here.

[@josephtaylor4115]

Great video

[@lexiu6036]

wouldn't it be possible to enhance the Origin Shift by picking a new origin at random among unvisited cells after certain amount of time (number of shifts)? and finish the process when, let's say, all cells are visited? I don't know how would that work with redstone though

[@DqwertyC]

From a Redstone perspective randomly selecting a single cell is pretty intensive - Rapscallion had to invent a whole new randomizer setup for his Prim's algorithm maze, and that only runs once to choose the starting cell. I'm also not sure how to go about rebasing the entire maze with Redstone. This might work in other, non-Minecraft applications, though

[@WilcoVerhoef]

What about parallelisation, could you have multiple "random walkers" all flipping origins on their own?

[@lexiu6036]

@@WilcoVerhoef oh, that sounds like a more reasonable alternative, I think

[@arturovi]

great video :))

[@daveidk]

Dont forget about maze-generating cellular automata like Mazectric :3

[@DqwertyC]

Mazectric is really cool, but it isn't guaranteed to generate a spanning tree where all cells are connected to the maze. I actually tried developing my own automata that did generate perfect mazes, but it just turned into Prim's algorithm with extra steps. There is a really cool maze solving automata that destroys the rest of the maze and only leaves the solution behind that I might do a video on at some point

[@danielrhouck]

If you run origin shift for long work does it approach uniform spanning tree? Does it actually *reach* uniform spanning tree with the right stopping condition (eg. if you stop the origin has visited each cell you get a uniform spanning tree)?

[@DqwertyC]

I'm not certain, since the math behind the proofs is beyond me, but I think it would be for the same reasons Aldous-Broder is

[@wompastompa3692]

Running a maze while origin shift is also running sounds really interesting, anyone know of any applications of this?

[@nimiugn]

Quality video!

[@lelaleasl]

How about Wilson's, without erasing the loops. It wont make a tree, and sometimes theres gonna be loops (but i think thats interesting for gameplay) but it would be a lot faster

[@Anistuffs]

What about 3d mazes though?

[@DqwertyC]

Turns out most of those are the same - most of these algorithms only care about a cell's neighbors, so if we just say those neighbors include two vertical neighbors as well, we're good to go. The same could be said about generating mazes on a hex grid as well

[@JoaoVitorBarg]

20min of the video i understood that the greena were the maze and the black were the walls😂

[@HildeTheOkayish]

I think growing tree could be made easier by instead of counting the path length you use a random chance to end the path. It doesn't seem like the actual length of the path is that important. As for detecting when you are done it may be easier to check in mincraft if all cells have a path in them rather then if they have been visited. There is no reason to visit each remaining cell at the end of the generation and it's simple to just have each cell that hasn't had any interaction send a signal down 1 single wire.

[@DqwertyC]

That's actually a really cool idea, and would probably feel a bit more organic. The passage length could still be essentially tunable by changing what that probability is, but it would introduce a lot more variety

[@HildeTheOkayish]

@@DqwertyC thanks :p

[@KorraOne]

That was my first thought for the growing tree too. Although instead of a random chance to end the path resulting in a logarithmic distribution always biasing shorter paths (you could add a constant to stop length 1 paths). I would use a random function to generate the length and then go to that length. This has the advantages that you could make a standard distribution of path lengths set on say 5. Basically instead of logarithmic randomness you could have linear or standard or whatever you want.

[@mediocrelogarithm5538]

⁠​​⁠The problem is it would still need the counter used for growing tree, but instead of a fixed number for length, it’s a random number. The random chance to end path doesn’t need the counter, so it’s a tradeoff between difficulty of implementation and maze quality.

[@lotsoflambdas]

ME controller:

[@KensaKunVRC]

9:29 erm…

[@1FISH]

I wish I could tolerate your voice.