What School Didn't Tell You About Mazes

[@mattbatwings]

To try everything Brilliant has to offer-free-for a full 30 days, visit brilliant.org/mattbatwings You’ll also get 20% off an annual premium subscription.

[@GrowMode_YT]

You cooked in this video

[@SukiYaki1904]

why was this posted this 6 days ago

[@CoolioGamingz]

6 days ago, and the video is 2 minutes ☠️

[@GrowMode_YT]

​@SukiYaki1904 It was privated. You can even see Capo with a comment 6 days ago

[@lucamastermanYT]

I was like the 450th person to watch this video, its my pb

[@captainluma7991]

I'm so glad you enjoyed the algorithm! I have been a big fan of your channel for a while now, so having my work featured in your video is so cool to me. Great video Matt!

[@carterstach6034]

It is the captainluma!

[@carterstach6034]

I actually saw lumas video before this one came out lol! 8:37

[@error.418]

Great work on "origin shift!" Going to have lots of fun playing with it.

[@Anunak255]

nice

[@vibaj16]

@@carterstach6034 same

[@youssemohamed1059]

i love how matt started out as a minecraft professional redstone player to teaching us the beauty of a maze

[@error.418]

The computer science pipeline

[@spitefulginger]

@aghaalipatrickstarNo, he is. He just makes a SoME submission for 3Blue1Brown each year.

[@gylbard8237]

of math

[@TaxMax5678]

He's one of the lucky ones who do what they love

[@eneaganh6319]

He still is mainly a Minecraft KZbin, this is for SoME

[@epicboy330]

Now we need the headache video about 3D mazes

[@jindmen]

We actually do not, apart from the definition of maze as a grid, nothing else changes. That is the neat part about trees, they preserve most of the characteristics no matter how many adjacent nodes each node has :)

[@bryanfongo327]

A 3D maze would work the exact same way

[@gamingcat6668]

@@jindmen 4d :>

[@austinneilson2870]

It's a tree, which means it works the exact same in every dimension.

[@dadamaldasstuff1816]

It would work with 1d mazes too. It just wouldn't be fun.

[@muno]

That changing-maze algorithm is actually so cool. Now part of me wants to make a game with a maze just so I can implement it LOL

[@JoecountryGaming]

Agreed

[@donaldhobson8873]

The purple dot is the player (who can move freely). All the enemies are stuck chasing the player through the maze, but they are faster than you.

[@nxsus]

Gamedev moment

[@theramendutchman]

Same here; perhaps via one that's not necessarily a perfect maze or maybe never one, and you need to have the maze change in a way that reveals macguffins or the exit!

[@gralkekd1574]

The fact that now there is the actual new graph algorithm, that was invented specifically to create randomly generated mazes in Minecraft really blows my mind. Like, imagine that someday in the future there is going to be some mathematical summit, and a mathematician starts their lecture with words: "So, there's this game called Minecraft..."

[@Nevir202]

"...imagine that someday in the future there is going to be some mathematical summit, and a mathematician starts their lecture with words: "So, there's this game called Minecraft..." If that hasn't ALREADY happened, given the insane math involved in the game, I'd be shocked.

[@jursamaj]

I mean, the fact that it happened for Minecraft doesn't have any effect on the algorithm. Notice how Luma's video, and this one, made very little reference to MC. That's because the setting is irrelevant. The algorithm is what it is, in any setting.

[@gralkekd1574]

​@@jursamaj That was kinda the point. Surely, the algorithm may found its applications in very different branches of science, math is math, but without Minecraft it could have never been created. There are examples when a solution to a certain problem was found in a completely irrelevant research (I believe, Veritassium addressed something like this in his video on theory of knots, but I may be wrong).

[@Nevir202]

@@jursamaj The conditions under which new math has been created are always relevant when discussing the creation of said math. What are you talking about?

[@CorrectMyGrammarPls]

​@@Nevir202 I dont want to sound rude but math isnt created, its discovered

[@malevolentmoose]

One problem with using origin shift to generate mazes is that as long as it moves purely randomly, it might take an exteremely long time to reach some parts of the maze, if it's large enough. What I love though is that by manipulating the chances to pick the adjacent dots you could direct the root to go in certain directions or towards a specific point, effectively also creating a pathway that roughly leads that way. Then, how much you change those probabilities will affect how much the path twists and turns along the way. So, you can start from a random maze and carve paths through it, to make sure that the rough layout and structure fits your specific needs. There's just so many possibilities to modify and manipulate it, and it can be easily adapted for non-perfect, off-grid and any other mazes as well, as long as you can transform them into a graph. What I'd also note is that this isn't really an algorithm, and instead probably just an operation that takes a root directed tree and returns a root directed tree, but changed in some way. There's quite a lot of those, so someone has probably already discovered it a long time ago, just nobody's been really using it to generate or modify mazes.

[@mattbatwings]

that is very cool! this made me realize how versatile of a tool it really is.

[@_Dearex_]

Also, couldn't you just use more origin points and calculate them seperately? As each step is always a perfect maze, just throw in more origins to randomize it more quickly

[@suhaskanuganti7967]

@@_Dearex_ wait how would that work tho because if u have 2 origin points u have to consider what points go to each origin point and it may like become more complicated as u have to figure out which point refers to which origin point if u could explain it would really be appreciated also i really want veritasium to make a vid on this topic lmao

[@malevolentmoose]

​@@_Dearex_ Not really, cause you have to rearrange the tree each time you change the root so that all connections point towards it. I don't think it's possible to calculate them simultaneously, though reselecting the root once in a while is an option. Something you can do is keep a list of all unexplored dots, which then allows you to do a lot of different stuff, for example increasing the chance of moving in the direction of a cluster of unexplored dots, forcing the root to move to an unexplored dot if available (which makes it similar to a lot of maze generation algorithms), or reselecting the root as one of the unexplored dots if it's been running around the same area for too long already.

[@pmnt_]

I have to disagree with calling origin shift "not really an algorithm". Purely random movement is the core of maze generating algorithms and "taking extremely long time to reach some parts of the maze if it's large enough" is true for depth-first-search and hunt-and-kill algorithms as well. DFS is a bit faster at the cost of memory. The difference is that origin shift produces a perfect maze after every iteration, whereas DFS and HAK produce only one perfect maze after the last iteration.

[@DankeMart]

Why the hell did I not realise it was mattbatwings until the 9th minute 😭

[@Mustafa-6331]

You're not alone.

[@John17TheOGmp4]

I saw mattbatwings and I click

[@guestIdk-ni9hb]

Same; I thought this was 3b1b

[@idiot528]

@@guestIdk-ni9hb Bro how do you not remember what grants voice sounds like

[@aimaniskandar476]

same

[@p2beauchene]

I've been an algorithmics teacher for some years (after beeing a software engineer for more than 5), so I joined to learn about RedStone. I'm amazed by how much and quick I learned about algorithmics. Thanks.

[@Diamondsword85_RS]

Wow, a teacher that's learning about minecraft?! Finally someone that understands why people (at least I) like to play Minecraft.

[@p2beauchene]

​@@Diamondsword85_RS To be be clear I was a MineCtaft player way before I was a teacher, but my students were mostly gamers so the MineCraft analogies I used usualy landed.

[@p2beauchene]

@@Diamondsword85_RS Is my avatar clear enough to you ? I'd appreciate feedback.

[@p2beauchene]

One of my student even drew a Creeper on my whiteboard, minding every pixel. I was amazed and delighted.

[@A_Random_Melon_Pult]

man I wish I had a teacher as cool as you

[@Misstborn]

I'm pretty early in the video, but I just wanted to mention my favorite maze generating algorithm; the growing tree it's basically what Matt showed at about 2 minutes, drawing a path to a new cell and removing the wall that blocks that path. What's really nice about it is that by just changing 1 number, you can really change the outcome to all sorts of different things. That number being the percent chance that the next cell is adjacent to the current cell. If it's a high number, then you get long snaking pathways, whereas with a low number you get lots of short branches with numerous twists and turns.

[@SirPogsalotCreates]

"first, we need to define what a maze is." "...we're just gonna make it up"

[@mattbatwings]

welcome to all of math

[@SirPogsalotCreates]

@@mattbatwings valid

@@mattbatwings fr

[@SolunaStarlight]

The "no looping" quality of a perfect maze is very interesting to me, because it basically means that perfect mazes and braided mazes (mazes with no dead ends) are mutually exclusive, because in order to avoid dead ends you have to make the maze loop back on itself in some points.

[@illusionx1797]

not necessarily, an n×1 rectangle could be a perfect and braided maze. Also, for any grid, if you go place the start in the lower left corner, and go straight till the lower right corner, go up, continue until the left edge, etc. You would also geg a perfect and braided maze

[@BryanLu0]

​@@illusionx1797Wouldn't the ends of the rectangle be dead ends?

[@illusionx1797]

@@BryanLu0 if we place the start and ending points at the ends then no. However, as far as graph theory goes, there have to be at least two pendant vertices, which are nodes with one connection. If there are less than two, then the graph/maze has a loop. Basically, in graph theory, no looping and graphs with no "dead ends" ARE mutually exclusive, but in mazes not necessarily since we can place the end and starting points at the dead ends

[@SgtSupaman]

The only intersection between perfect mazes and braid mazes is just a singular path from start to finish, so it is trivial to the point that most would not consider it a maze (though I suppose it technically still would be). Practically speaking, yes, the two are mutually exclusive.

[@triffid0hunter]

A maze with exactly two cells adjacent to every cell except the start and end (eg a straight hallway, then twist it as you please) is both perfect and braided - but these are usually called labyrinths :P

[@RaPsCaLLioN1138]

I just came across Luma's algorithm the other day. Been working on compacting.

[@PinkPandaKatie]

I did a bit of research on maze generation many years ago when I was making a clone of the old Windows 3D Maze screensaver. The one I settled on was Kruskal, which is great at making perfect mazes because it can generate every possible one with equal probablility. All of the randomness is confined to a single shuffle: Step 1: Assign a unique number to each vertex. Step 2: Add all the potential edges to a list. Step 3: Shuffle the list. Step 4: Iterate the list: For each edge, compare the numbers of the vertices it would connect. If they are equal, skip to the next edge. If they are unequal, connect the two vertices, and change the numbers on the vertices so they are equal, as well as any connected neighbors. The way it works is that all verticies with the same number have exactly one path between them. because we don't join vertices with the same number and when we join two unconnected paths we set their vertices to the same number.

[@eagle32349]

Crazy Maze Idea: Imagine the seed for a random number generator being the coordinates of the origin and that you can "open doors" between "rooms", but each rooms is randomized based its coordinates and the origin's. Now imagine that if you enter a room and close the door behind you, the origin becomes the new room! That means, every time you close the door behind you and then open it again, you enter a completely different room which is technically at the same position as before, but is in no way related to the previous state of the room. Now imagine you created a room generator based on a number, that number you can get from the randomizers and essentially create an actually infinite and unique backrooms-like experience, but it's just a maze, with special properties, but still just a maze!

[@ShuAbLe]

I didn't get it, but is seems there is some interesting in there somewhere. mind explaining more?

[@ThomasMcMillin]

I think I get it. So in this maze, the origin is the player. And as the player moves, so does the origin. The room that you just left would then be an outward vertex, so you remove it. And eventually when this vertex is effected again, it can be randomly generated into a new type of room to create what is simultaneously an infinitely changing maze, but it also adds infinitely changing rooms within the maze. That's actually brilliant.

[@BryanLu0]

​@@ShuAbLeBasically, you can change the contents of the adjacent room by closing and opening the door. I don't actually think there are any implications for the maze, since the OP specified that the maze starts with all the doors open.

[@HakanBasbay]

3mattbat1wings

[@thatcatthatalwayseatsyourchees]

3matt1batt

[@0xABADCAFE]

Winning

[@gregorybrannin-mooser4686]

3blue1brown reference

[@MisonGD]

What’s that a 3 blue 1 brown reference

[@MisonGD]

@@gregorybrannin-mooser4686aww you beat me to it

[@JordanMetroidManiac]

That truly is a beautiful algorithm! My mind doesn’t get blown easily, but it did this time, probably because mazes are intuitively undirected trees, yet this algorithm uses directed trees to optimize what would likely have to be a brute force search on undirected trees to check if some modification to the maze preserves perfection. Thinking about it a bit longer, the brute force search on undirected trees requires a lot of calculations, but this algorithm makes all those calculations once (to determine the directions of the edges), stores those calculations as a “state”, and then reuses the state (which is equivalent to part of the brute force search) to quickly check if a modification can be made to the maze that preserves perfection.

[@arthurhill8185]

huh. that origin shift algorithm is really cool. you could shuffle the maze *while someone is inside it* and still guarantee they can find a way out, I think.

[@DqwertyC]

Yup! Or you could wire it up so someone is manually (instead of randomly) moving the origin around while someone else is trying to solve it, to make it a competitive challenge.

[@frankhooper7871]

Over 40 years ago, I wrote a program to generate a random maze on a BBC-B microcomputer. No idea now how I did it LOL

[@Matteo-dk1ee]

I saw the Captainluma's video just a week ago, it's so cool to see you talk about this alg too

[@jadengames.3662]

2:43 you just gave me an idea for a interactive 3d maze.

[@greenguydubstep]

i can see the sebastian league inspiration here

[@RubyPiec]

I myself see 3b1b inspiration tbh, but thats probs because its using Manim

[@zeldek]

lmao I wouldn't be surprised if both of them made a video about it

[@deleted_handle]

just like crabs they are all evolving into the same style.

[@sealpup3775]

I see that 😂

[@Asymmetrization]

I see zach star ​@@RubyPiec

[@SuperMaramau]

This is the first time I've seen a video of yours. I'm impressed by the quality and clarity of your explanations. Subscribed!

[@geochonker9052]

Better teacher than any college professor. Excited for the new videos!

[@davidoliver7510]

Actually a grid maze is really creative and cool. Watch Takeshis castle A grid maze. However the walls of the grid has doors in the walls. Not all sides has to have a door. Has a start. But one exit. True exit. Other exits are traps.

[@tylerbakeman]

4:00, There are some words in math that we use for similar topics. If every cell only points to at least one other cell (because we’re ignoring moving backwards), then we have a Connected, Directed Graph. Since there are no loops: (no two cells can point to the same cell), then we have a Connected Directed Acyclic Graph (typically referred to as a DAG) DAGs are types of Tree-Spreads, which means we can represent all of the Cells in that DAG, using the standard tree in comp sci. Each Cell points (has an extroverted half-edge) to at least one other cell. Typically, moving backwards in graphs makes sense on paper, so making each Edge bi-directed,,, or having an Undirected Graph could be more powerful. So, consider making the model more complicated from a connected DAG, and turning it into an connected Undirected Acyclic Graph. There is also this notion of a Partial Order... (Posets are more specific and tend to create loops)… It might be helpful to refer to if you would like to create a label for each cell, or if you wanted to index them specially. Keep in mind, all of this graph stuff is luckily in a 2D Rectangular Affine Space. So you have all of the benefits and optimizations that come with that coordinate system. So, you can potentially use Quad-Trees and Marching Squares,,, whereas in other Graphs that might not be ideal.

[@tylerbakeman]

There’s a lot of big words in there on purpose. For research opportunities. If anything, excuse my inaccuracies.

[@DqwertyC]

Thinking about mazes as directed trees is actually super helpful. Each "cell" only really needs to know one piece of information, which direction it's facing. This also makes some algorithms more efficient, or at least more lightweight. For DFS, backtracking is managed by just going back into the cell the current cell is pointing towards, and you know you're finished when you've backtracked to the starting cell. A couple years back, I made a DFS generator in Minecraft that worked using just 5 command blocks, then later made an admittedly very ugly redstone maze generator that took over 10 minutes to run, but both relied on this idea of the cell remembering the direction it was facing to handle backtracking.

[@Lazauya]

Luma's video was rec'd to me recently, and I saw this video in my feed I instantly thought of that. Neat!

[@Awes0meBadger23]

School, could you actually help me for once?

[@Arch-mv5te]

fr man

[@prohakerofficial]

No :D Instead, we are going to teach you the most useless stuff ever!

[@error.418]

School taught me maze generating algorithms, we just need more schools to care, too. It's part of most computer science curricula under an algorithms course, usually combined with learning data structures, too. (Many places will call this class DSA: Data Structures and Algorithms)

[@Arch-mv5te]

@@prohakerofficial student: man why the fuck do we need to learn why george washignton stepped for the 7593th time in 1742??? school: did you know that that computer mice are made out of plastic, and plastic is made from cellulose, coal, natural gas, salt and crude oil?

[@katakana1]

@@error.418 I learned some of that through a summer program last year, it was cool

[@jonipaliares5475]

This was actually so cool, and you sure got talent for making 3b1b style explainers!

[@keesakkermans7488]

So when comes the video 'i made a maze generater whit only redstone' coming?

[@error.418]

He pointed us to a good one in this video, by CaptainLuma. It's in the description, too.

[@hjagu1323]

Really nice too see a mattbatwing video in a kind of three blue one brown style. This video was awesome!!

[@kephalopod3054]

To solve the maze, just make a printed circuit board with the path as copper lines, apply a voltage between start and finish (use a resistor to adjust the current), and use thermal imaging to see where the current flows, ergo is the solution.

[@shalevforfor5550]

If you use recursive backtracking thingy in the frame that you touch the start point if you started from the end point you will get a list of the path of the solve of the maze

[@mertaliyigit3288]

That last algorithm can be generalized. Instead of removing the target node's pointing edge, you can remove any edge on the path that goes to the root and reverse some of the edges

[@hears__]

Keeping this video as my oral presentation for next year, tysm

[@qfurgie]

saw Luma’s videos a few weeks ago and was so impressed

[@Inspirator_AG112]

*[**06:41**]:* I think you can also make it do both directions across the edge that it hits, given that for each dot in those directions, they aren't already connected to another part of the path.

[@ThinkWithGames]

It's cool to see other people showing maze algorithms. I had done a bit with the depth first search way in the past, but that origin shift idea is cool too! Props to Luma

[@XanTheXanadul]

The day before yesterday, I submitted my uni homework about a maze game. Yesterday, I watched the video by CaptainLuma, and today the algorithm decided to show me this. Now I really want to try out this algorithm.

[@Kaepsele337]

I once did something similar. The algorithm I used was to use depth first search to create an initial maze. Those tend to be rather boring because it creates long non branching paths. To randomize it I cut a random path, which splits the tree into two new trees, but they have many points where they touch. So I choose one at random and connect the trees again. The resulting graph is still a tree. On each iteration a single wall is built and a single wall is removed.

[@wiktorkaminski5095]

If this video was posted last year, I might have used this algorithm for my maze game for my university project. I think that multiple moving points are possible. So far my paint tests shows that It is possible with few more rules. Also the additional points can be teleported/added/removed easly according to the paint test.🎨🖌

[@Romashka_Sov]

School didn't show me how to make mazes, but I liked to draw them in childhood. Though they were too simple to solve, so I added "layers" in a later ones, with a rule that states "if one path goes under another, it must not make any turns while it is below said path". I had a full note of those mazes, unfortunately my mom threw it to a trash bin one day, and I stopped drawing them. It was fun tbh, maybe I should draw some in the future

[@Type3Kiryu]

I remember some maze site from the usless web site, my strategy noted that the RNG of the maze was always going to be an asshole. The rule was that if the path ahead didn't go back on itself in the most obscene and slow way possible, touching walls with the last part of the path, it was the wrong way. It worked 90% of the time.

[@Flupus]

Hello mattbat, love your content bro. Keep uploading!

[@mitchratka3661]

YOOO I THOUGHT I RECOGNIZED THE TOPIC, bro I watched Captain Luma's maze changing algorithm video and helped him pick the name, many other people suggested it but I was (supposedly) the first to suggest "Origin Shift" as a name. Soooo happy that you did a video on it since I love your content and loved this topic

[@legendgames128]

Modified origin shift (as a maze generator): Start the root at the corner, with no connections from any cell to any other cell whatsoever. Apply the algorithm, which will add new connections from one cell to another. Stop when the root visits all cells. Or heck, why not generate the maze this way as the player is inside the maze and then keep going after? Though one of my complaints is that with every single perfect maze, it doesn't produce massive rooms like you'd see on DOOM, for example.

[@DqwertyC]

That's basically describing another algorithm known as the Aldous-Broder algorithm. The only difference with Aldous-Broder is that once a cell is visited, it doesn't get changed again, but when we visit new cells they always point into the existing visited cells. From his original video, Luma actually started trying to make an Aldous-Broder maze generator, but didn't have a way to detect when every cell was visited, then came up with this as a solution. Something cool about Aldous-Broder and (I'm assuming) Origin Shift is that they generate a Uniform Spanning Tree, which basically mean any possible maze is equally likely to be generated. Most other algorithms are biased towards specific types of mazes, such as Depth First Search generating long, windy passages and Prim's algorithm generating lots of short dead-ends.

[@traptoothpick8669]

I'm falling in love with this type of stuff again

[@tyronorxy5646]

The problem with perfect mazes is that if you know the simple exploit of hugging the wall, it looses it's fun aspect. It just becomes the chore of running this "hug the wall" algorithm. It essentially makes it too easy. Disjoint mazes on the other hand, require good memory to solve. Getting stuck in loops is basically a skill issue. Although this is likely not the player's fault, and the maze is just not designed for their skill level: Just imagine a human trying to map the Backrooms in their head. One way I see for solving such mazes (using an algorithm) is that: You write down the turns you take (left-right), and use some sort of compression algorithm to store them efficiently. If you need to backtrack (because you've hit a dead-end) you erase the turns you had to back track through.

[@AkiraTheCatgirl0]

Would disjoint mazes not be subject to the same exploit (or, rather, always solvable by the same algorithm)? If you get stuck in a loop, then you must come back to where you started, meaning you went outside the maze and thus finished it. An additional way to think about this is considering how a 'loop' is created. If a section of wall is connected to the outside, then it cannot be part of a loop. If it's not connected to the outside, then you will never hug it. Since the maze is (presumibly) finite, we will say it is n×m. Then, any sequence of nm moves must terminate in an end or have gone over a vertex of the maze multiple times.

[@tyronorxy5646]

@@AkiraTheCatgirl0 It seems to me that in your explanation the player is viewing the maze from an omniscient ("outside") perspective. Which is the exactly where disjoint mazes fail to provide difficulty. For disjoint mazes to be difficult, the player must be located inside of them, where they cannot immediately tell if a section of walls is connected to the outside or not. For simplicity I will assume that our maze is single-floor, with no diagonals: Given the above restrictions, the maze has only 6 possible path configurations, where it is not immediately obvious that you went the wrong way (aka.: it's not a dead-end): - Left L - Right L - T - I (Straight) - X (Cross-junction) This is not a a lot of variety. In order to not go around in loops, the player must identify if they have already visited a vertex, for which they can't use the configuration of paths leading out from said vertex, because the lack of variety makes the player unsure if the vertex in question is an already visited vertex or just an identical one. And even though a human's vision is not limited to just a single vertex, the maze can also possess larger identical sections. (Large mazes will do just by pure chance.) This is why the player has to continuously map the maze in some way if they wan to identify longer loops. Mapping is the "algorithm" for solving disjoint mazes (from the inside), and - unlike hugging the wall - this "algorithm" requires skill to use. This skill being either good memory, or the skill to conserve space on the paper you use to map the maze.

[@ThomasDeSwert]

here's an algorythm I made myself to generate a maze, first get the borders and the grid, then draw a line from start to finish randomly, then make branching paths trough the remaining walls, make sure you only get into each space once, boom, thats a maze

[@Herpling8]

Nice video. The origin shift algorithm is pretty nice, i didn't expected that. It can be really good for slightly changing already existing maze. For creating maze will be easier to use DFS. You can also use MST to create mazes like this. I thought you were going to use it before I saw the end :)

[@HuntCard24]

3:08 you missed your chance to say "How many options is too much options"

[@SupersuMC]

"Super-simple perfect maze" Shows an all-left-indents maze that Roller Coaster Tycoon's peeps' maze-solving algorithm struggles with.

[@johnchessant3012]

That origin shift method is so cool!

[@infernopyromaniac]

I love captain luma so glad you made a video showing off origin shift to more people!

[@Guys-s5v]

I have another method for making a tree: start by randomly walking until you hit a dead end where all the adjacent ones have been colored the same color (bear with me here), and then start a new path, and color it a different color than all the other paths. Merge the paths if they intersect and color them the same color. If a loop is created (just in case), undo your move and try another. Repeat until the board is filled. If there are still two or more differently colored paths, connect them. Use the loop procedure if a loop is created. Repeat until there is only one path. Then you're done.

[@shalevforfor5550]

He just talked about it in the video

[@EnorIII]

I was just recommended CaptainLuma's video explaining the algorithm 2 days ago, and now you made a video on it

[@remyashrym5134]

Yeah same 😅

[@raffiepro]

The specific word for that type of maze is labyrinth

[@DqwertyC]

It depends on who you ask - some people use labyrinth interchangeably with maze, while others use it as a specific type of maze with no branching paths. "Perfect Maze" is the generally accepted term for a fully connected maze without any loops.

[@Inspirator_AG112]

*[**8:18**]:* Specifically: • O(n²) for equal width and height n. • O(w • h) for width w and height h.

[@AndrewX981]

What is O function? And what is the area of the grid doing here?

[@Inspirator_AG112]

@@AndrewX981: Big-O notation.

[@DqwertyC]

It's actually worse than that overall - each individual scan of the maze is O(n^2), but the number of times we have to scan through the maze is *also* O(n^2)

[@AndrewX981]

@@DqwertyC Would that be O(n^2)^2 right?

[@paprika1716]

Origin shift only changes in a predictable location. For a more random "feeling" the origin should change randomly as well every few iterations. At least for a living maze

[@GagnesterLOL]

The french canadian minecraft zephirr have made it before 😉 but, not exactly!!! The video: Le labyrinthe de Zephirr- Version téléchargeable [2012, 12, 25]

[@remyashrym5134]

Wow tah l'époque, c'est un ancien lui 😂

[@merlin2lmml45]

I really like this kind of style you’re drifting into. Trying make all the redstoners interested in technical engineering and stuff. As long as we’ll still be seeing at least 1 redstone vid per month im fine with it i like either style. Just as kind of a feedback for how youre trying to kinda move your fanbase.

[@vNCAwizard]

There are very good reasons to have loops in a maze, given the rules for proceeding along any path.

[@AgentM124]

A few issues with the root maze. For very large mazes, you might need to run it for a very long time before it is properly randomized. Instead you could break up the maze in submazes and randomize those for a much shorter time. Then you will get a much better maze, then of course you may want to overlap the borders or the submazes for proper randomization there too. Also, it is a statistical higher chance to find changes near the root within the maze. So if you got a recent change in the maze you can kind of predict where the maze will definitely not change for a while. However, by instead picking a completely different root at random you can get less predictive changes. Though you'd have to recalculate all the directed edges.

[@FelanLP]

Everytime I create a maze, I imagine it like having zwo sides on a zwondimensional plane and both sides grow branches over and over. You can also have branches which are connected to no side but then you can walk in circles or even have two paths The goal is to find a way through both branches. Things get fun, if a second layer is introduced. Because the you can have branches that are connected to no side but still don't allow you to walk in circles. I never drew one with 3 layers though.

[@b1tw0nder]

While the root would be the node where all arrows face towards, you could call any node with only one arrow that faces away an anti root. Antiroots would just happen to be mostly dead ends with the exception of of the start and/or end potentially on those nodes.

[@Miju001]

Origin shift is such a cool concept! Thanks for bringing attention to it!

[@miltonthecat2240]

Once you start messing with larger mazes, you naturally start thinking about difficulty. One way to make a difficult maze is to maximize the blind alleys in some sense. For example, a maze with long blind alleys more time-consuming to solve than a maze with very short blind alleys. And a maze with long branching blind alleys seems more difficult to solve than a maze with long blind alleys that don't branch. If you take a finished maze and think of all the paths as connected pieces of string, then visualize pulling the floppy string out of the maze grid and splaying it out in two or three dimensions, the most difficult mazes probably resemble the root system of a tree. One can then imagine various ways of defining an optimally difficult maze for a given grid size. And then defining a maze creation algorithm to maximize some aspects of difficulty.

[@poorman-trending]

My 2¢ - loops makes a (large) maze more challenging and thus more interesting.

[@erniesulovic4734]

Labirynth is a board game where the "walls" change per turn/player. Graph Theory had some interesting parts in it when I studied it at Uni yet I am going back many years now. Discrete Maths of which Graph Theory was part of, was not really my kind of maths that I enjoyed that much. Oh btw, there is a 3D version of Labirynth which I have not gotten or played yet seems like fun

[@veikkakarvonen831]

The game should've been called Maze instead as a labyrinth only has one path by definition... Loves that game, the Finnish version was called "Muuttuva Labyrintti", "the changing labyrinth".

[@danielrhouck]

0:25 I think Iʼd take that bet (or at least bet Iʼve seen a variant of it). It looks exactly like a CaptainLuma video from 5 months ago I happen to have seen three days ago.

[@funkdefied1]

What an INCREDIBLE twist at the end

[@KatBeanGod]

ok but loops are good though unless your maze has mobs in it or loops in it, you can just always easily get to the end by always making right turns (or always making left turns)

[@matthewboyd8689]

I used to think that a maze that is a circle with one extra path that connects back to itself was something simple because I could easily see it And then I played a game that literally had that as its most complicated procedurally generated cave and proceeded to get lost completely. Deep Rock Galactic. Specifically Dreadnaught missions (possibly deep scan missions too)

[@thingymcjig788]

Ah this is interesting! A while ago I made my own maze generator which worked by starting with a grid with no walls and growing the walls in from the outside. It's interesting that you can do it both ways, either by looking at the path or the walls and completely ignoring the other and you still get a good maze!

[@divy1211]

the origin shift algorithm is amazing. I love how a game inspired someone to come up with a novel algorithm to suit their needs

[@AlexFalkenberg]

That end algorithm reminds me of conveyor-belt algorithms I've seen in the past. Still very clever.

[@fretzT_T]

Goodluck with your submission. Waiting for your redstone to computer series.

[@L3ChatNoir]

My favorite maze algorithm : Prim's algorithm Maze is literally a spanning tree. Just use random to put a weight and search the minimum spanning tree with Prim.

[@gabrielfonseca1642]

I kept thinking this was MST while watching the video. Although you probably could make it more efficient by not keeping a heap (DFS is linear time whereas Prim's is NlogN)

[@mhm6421]

Bro I literally watched CaptainLuma's video like 5 hours before this video got published?! Is this a coincidence?

[@kouroshahadzadeh5070]

Noice…

[@Misstborn]

I just watched it yesterday! Fun coincidences (or maybe it's picking up in the algorithm?)

[@zekejanczewski7275]

I tried creating an infinite maze which generates as you explore it from a seed. The trouble is how do you make a maze localized, meaning each cell only needs to extract information a bounded finite distance away from itself to generate, I don't think such an algorithm is possible, and here is my reasoning. You can always look at larger and larger sections of the maze from one point to another. Intersections need to be further and further apart from each other. A 1 million tile maze will involve you passing through a suprisingly small amount of junctions to get from one point to any other point, at the very most, 16. When you reach a certian size of maze, either you must go back retroactively and change the dencity of your junctions, or have a lower and lower amount of junctions. A technical cheat I found was to create really simple 2×2 mazes, and then arange 4 of them in a 2x2 grid, then connect them together at random junctions. Then, get a 2x2 grid of THOSE mazes, and connect them randomly with a single connection. The information is stored in the X-Y position. Meaning there isn’t really locality, where each section of maze is indistinguishable. Still, at a glance, it looks convincing.

[@thyrical]

Amazing video. I coded a perfect-maze generator in a video game recently, and it really racked my brain - visualizing it as a tree is brilliant!

[@Hubcat_]

Instead of just moving the root by 1 each iteration, which results in nearby walls always changing unless it happens to move far down the path, you could move the root to a random node (reversing the direction of edges between the old and new root points so that it's still a legitimate root) and then move it randomly like before, this would let walls change anywhere in the maze rather than being a moving point

[@Hubcat_]

You could even choose which walls you want to open up by selecting one of the nodes by the wall randomly, moving the root node there, and then moving it through the wall like in the original algorithm

[@DqwertyC]

@@Hubcat_ Yup! This is just a more computationally intensive, since you have to rebase every cell between the old origin and the new origin.

[@siesmec]

This helps a lot! Me and my friends where making a maze game using Redstone, and we couldn't find a good algorithm for us, but this one seems perfect!

[@Lampe2020]

I just realized when you said you started making a maze generator in Minecraft that you used the same music in this video as 3b1b does XD

[@purpleskrim6935]

11:12 "if there's any game-developers out there who want an ever changing maze" :me who thought of using it before hand

[@thingymcjig788]

It could be interesting to have a two-player game where one player controls the root-shifting to stop the other player reaching the goal...

[@gigog27]

The pathways are just a spanning tree of the graph of the grid! I had never thought of it that way before.

[@glenneric1]

Use a minimum spanning tree with root starting in the middle-ish, random-ish node weights and two points on opposite sides as start and end and you'd have a pretty good algorithm.

[@realityChemist]

That's crazy, I watched CaptainLuma's video on the origin shift algorithm last week after KZbin recommended it to me, but I had no idea they invented it for a Minecraft build!

[@GameJam230]

A cool fact I figured out about the origin shift algorithm while watching this is that there's actually no requirement that you ONLY change the root node to an adjacent cell in the maze, you can actually pick any cell you want, and you just recursively follow the tree until you get to the old root. Once you do, swap the direction of the last connection in that path, and finally delete any incoming connections in your new root node just like before. The only reason why choosing adjacent cells was done was because it makes it really easy to build in redstone, because the root cell stores the fact that it's the root in itself and IT is responsible for passing that off to a neighbor, which it can do in only a single iteration, but the other approach would need a separate mechanism to store the current root node and the new one so that it can facilitate the recursive search back to the root again. It also means that it takes longer to move the root further away, and it gives no benefit if you do it every single time, you'd only really want to use it once in a while between a bunch of neighboring cells being picked as a way of quickly picking a new part of the maze to affect. This would be good in situations where the algorithm updates the top and right side tons, but the bottom-left corner remains unchanged for a while, as you could just force the root to move down there for more variability. But again, that's more useful for game devs than redstoners.

[@boggers]

I think I had the same idea but backwards... or maybe I'm just not following your explanation properly? As I see it, first you pick any random node as the new root, then you traverse from the new root back to the old root, following the arrows back and flipping every arrow along the way until you get to the old root. This makes no changes to the maze layout but all arrows now point toward the new root. Then from the new root you move to an adjacent root as with the normal origin shift method.

[@GameJam230]

@@boggers Yeah, I think I added a couple extra unnecessary steps because I was considering the additional step of DELETING connections that used in the original algorithm, however it is only needed when you have to consider the possibility of opening up a wall that was closed prior (as it would create multiple paths between two given nodes, which disobeys the rules of the maze state), however this is not needed when picking a random node as the new root becaude there is already exactly one path to its location from the old root, and so you can simply follow the path and flip the directions without worrying about closing paths that were created as a result of this (as none would be). As for why I did it backwards from you, there is a very good reason. When working with trees, all non-root nodes have exactly 1 parent, so it is easier to say thisNode.parent to go UP the tree TO the old root than it is to navigate DOWN the tree FROM the old root, as you may encounter branching paths to deal with.

[@boggers]

@@GameJam230 Heh, I think we are both talking about the exact same method, traversing from old root to new root, but you omitted the part about flipping the arrows along the way in your initial description. :) This all has got me interested to dust off an old maze gen algo that I came up with a while ago.

[@GameJam230]

@@boggers Not necessarily. I'm saying traverse from the NEW root to the OLD one, opposite of how you keep saying it.

[@boggers]

@@GameJam230 oops, I did indeed flip traversal direction in my follow up comment, my first comment was correct though.

[@Gravy_Guzzler]

i did the DFS thingy in scratch while ago, and then used it to remake a tank game, your video makes me want to try maze generation or somthin like that again

[@justonechessguy]

this is the type of 3b1b stuff I'd love to see you talk about. great new vid

[@NikoKun]

Every maze I've ever built, for the sake of added challenge, always contains a loop or two.. lol

[@sethhollistah8504]

I used to hand draw mazes when I was a wee lil kid and wondered how people manage to fill entire books with them

[@AlexSanta-jl9ke]

I saw somebody use DFS to create an AI in Minecraft(that did parkour)

[@psyonide1394]

One of the best visualization of DFS I’ve seen

[@TinusBruins]

In my opinion a good maze it not a perfect maze, but one that has a loop you must traverse to get from start to finish. Thus leaving you the option route A or route B, which one is the shortest? In an ideal situation A could be half the length of B, but it shouldn't be obvious when looking top-down on a maze, as they usually do. Which really takes away the challenge. An other thing which takes the fun out of these is, that the loop takes up a too large part of the maze. Which is often done by adding an decorative image in the middle of the maze.

[@Bob-1802]

I learn about mazes at school but not in class🤗. I went to a high school using an old seminary building. Full of floors with slooping corridors and half staircases. First week new people could't find their way😎. It wasn't a boring place.

[@madpotatoe5184]

You were good at explaining redstone but your even better at explaining maths! I love this.

[@spinnychairs6724]

this is a really nice style of a video, if you did one of these for some of your complex machines im sure more people would understand them and it'd be really cool