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

[@lycanea]

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.

[@RaPsCaLLioN1138]

very happy to see more maze content

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

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

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

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

[@scrambo6182]

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

[@addymant]

A couple things of note, one of which you probably have already learned since this video: First, Origin Shift is just Reverse-Aldous-Broder with the addition of a very poor starting maze, and if you allow it to run until the origin has visited every vertex, it will generate a uniformly distributed spanning tree, so the maze quality ought to be the highest. There's little reason to treat this maze as having a region of potential scores, when the exact same idea of a starting maze could be applied to every other algorithm. Second, Aldous-Broder-Wilson hybrid (which I've also seen called Houston's) surprisingly does not generate a uniform spanning tree! You can confirm this by creating a graph with 4 vertices, where 3 of the vertices are each connected to other two, and the 4th vertex is connected to only one of the other vertices. There are three spanning trees with this graph, so each should have an equal probability of a third. However, if you switch from Aldous-Broder to Wilson's once the maze has 2 vertices, one of those spanning trees will occur with a probability of less than just 0.32, with the other two each occurring with a probability of just greater than 0.34.

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

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

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

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

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

[@xonroy7061]

I think this is the best video of the year

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

[@TypicWhisper]

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.

[@theevilcottonball]

How about tweaking recursive division to allow the removal of more walls than just one (ideally randomly and proportional to the length of division)

[@theevilcottonball]

Or how about dividing with a random walk from one wall to another. (Can be made faster by eliminating the direction that points to the starting wall.) And then removing a single wall of that new division.

[@DqwertyC]

@theevilcottonball That's would lead to much more natural mazes, but would increase a lot of computational complexity. With straight walls, a 'room' is just a pair of start and end coordinates, but with this, each room would have to be stored as the set of all cells in the room. Detecting when a room can no longer be divided would also be harder. That said, this would be a great modification for drawing a maze by hand!

[@theevilcottonball]

​@@DqwertyCYes it requires storing a room as a set of cells. Regarding the time complexity, I don't think it would be that bad, if you remove the backward direction. If you think it will go up and down amd not move forward though in the worst case (on average it is a third chance of going forward, but since its random it might not, you can force it to move forward every n steps to tackle even the worst case time complexity).

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

[@shayden7227]

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

[@thealientree3821]

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

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

[@McGoomba]

27:48 "It's kinda tricky to score- O R I G I N S H I F T"

[@lelaleasl]

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

[@PendragonDaGreat]

Aldous Broder could get a significant speedup (at the cost of computational and redstone complexity) if you add a conditional check where if you just step into a cell without changing anything, step back to the previous cell and see if any of the moves would be valid. If there are no valid moves remove that cell from the list of potential cells to visit in the future. Since the set of valid to enter cells is going to be decreasing over time I think this would also guarantee that the maze will complete, something that the version you showed may not.

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

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

[@iamsushi1056]

I feel like a cross between recursive division and binary division where it uses weighted probability based on distance to center and more likely to have the next division running perpendicular the longer/wider the room is could be an interesting concept to explore. Nightmare to redstone though

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

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

[@margaret233]

Your voice is so soothing that it a-maze-s me

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

[@bredcataw]

That was... Informative. Thanks, DqwertyC!

[@Speed001]

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

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

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

[@BRH0208]

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

[@jimiwills]

That was really interesting ❤

[@haniyasu8236]

Kruskal's Algorithm _does_ sound bad. (Especially with the "keep track if they are connected" bit), but it feels like there should be some clever way to have a dynamic network of redstone connections that could be used to test if two points are connected together or not yet. Like imagine that as you lower walls, it connects redstone lines together, so if you power a cell, it powers every other cell connected to it. That way, you could do a connectivity test of sorts, kinda like you would do with a multimeter IRL. Of course.. I feel like this could be very slow since you'd probably need repeaters, adding a fair bit of delay to each test, but it feels like it would work? You'd know more than me, but it doesn't sound any more brutal than doing the hunt and kill algorithm imho (Ngl, that one in particular sounds _insane_ to me). I'm happy to be shown wrong about this though, someone let me know if I'm missing anything.

[@DqwertyC]

I've been thinking about this, and I think you're correct. It would also be possible (even easier, probably) to detect if there's a connection within N cells, which could in turn be used to create a maze that intentionally adds loops (i.e. it could open a wall if there's not already a connection within 12 steps, and this would create little islands of disconnected walls within the maze)

[@haniyasu8236]

@@DqwertyC Okay cool! Glad my intuition is (probably) not way off. Also, I'm now realizing that you could probably just use instant repeaters to lower the time for the tests lol... (Don't know how I didn't think of that initially). Heck, I vaguely remember there being a design for a compact instant two-way repeater somewhere on the wiki that could be useful for this as well. And yeah! I do suppose decaying the signal each cell could be pretty straightforward to do too. Though, I'm curious what your idea for it is since I can't quite think of how to do that beyond relying on signal strength, which would decay really quickly if the cell sizes were any bigger than like 2 or so.

[@DqwertyC]

@@haniyasu8236 My general idea would be to have different layers - i.e. an input on any side on layer 3 outputs in all directions on layer 4. Just add as many layers as you want to change the complexity of the maze - more layers would mean fewer, larger loops

[@wompastompa3692]

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

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

[@themathhatter5290]

18:00 Very Hilbert curve-esque, not very good maze; it's just a bunch of U's and C's welded together.

[@alphahawk325]

Wow I expected i would get bored and click off but this is actually quite interesting

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

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

[@jeredLopez]

I got addicted to sorting algorithms and now this?

[@AldoInza]

Could you seed Origin Shift with a Hilbert Curve?

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

[@willcorff]

Now what if you combined all the maze algorithms?

[@Luilu]

Very good explanation

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

[@AldoInza]

Art is limitations

[@wellhotdog4925]

Can you tell me why Kruskal's Algorithm does not generate closed loop regions?

[@DqwertyC]

If opening a wall would generate a loop, those cells must already be connected. When the algorithm checks a wall, it leaves it closed if the cells are already connected. So, anytime a loop would be generated by opening a wall, the algorithm leaves that wall closed

[@1e1001]

i feel like wilson's algorithm would be easier to implement than you're giving it credit for, although i can't really be bothered to prove that and do it lol

[@hydroxu]

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

[@hydroxu]

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

[@theevilcottonball]

What about cellular automata?

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

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

[@josephtaylor4115]

Great video

[@arturovi]

great video :))

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

[@nimiugn]

Quality video!

[@blakewallace8925]

Is this Java or bedrock

[@JoaoVitorBarg]

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

[@KensaKunVRC]

9:29 erm…

[@lotsoflambdas]

ME controller:

[@Ty-Jack]

Cool

[@1FISH]

I wish I could tolerate your voice.