What School Didn't Tell You About Mazes

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.
Patreon: / mattbatwings
Discord: / discord
My socials: linktr.ee/mattbatwings
This is submission for the Summer of Math Exposition some.3b1b.co/
Animations were created using Manim www.manim.community/
‪@captainluma7991‬'s video: • Ever Changing Redstone...
More Maze Generation:
A detailed series of many algs, my personal favorite - weblog.jamisbuck.org/2010/12/...
Wikipedia page - en.wikipedia.org/wiki/Maze_ge...
-------------------------
0:00 Introduction
0:25 Maze Definition
2:22 Perfect Mazes
4:22 Graphs and Trees
6:00 Generation Algorithms
8:35 Origin Shift
11:35 Sponsor
Music by Vincent Rubinetti
Download the music on Bandcamp:
vincerubinetti.bandcamp.com/a...
Stream the music on Spotify:
open.spotify.com/playlist/3zN...
This video was sponsored by Brilliant

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

[@growmode5015]

You cooked in this video

[@SukiYaki1904]

why was this posted this 6 days ago

[@CoolioGamingz]

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

[@growmode5015]

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

[@lucadoanpaetzelt]

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

[@youssemohamed1059]

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

[@aghaalipatrickstar]

I don't think he's a minecraft player he just love math so he make redstone systems

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

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

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

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

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

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

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

[@RaPsCaLLioN1138]

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

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

[@kayyyraa]

3mattbat1wings

[@thatcatthatalwayseatsyourc1493]

3matt1batt

[@0xABADCAFE]

Winning

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

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

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

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

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

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

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

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

[@Lazauya]

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

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

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

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

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

[@Matteo-dk1ee]

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

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

[@geochonker9052]

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

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

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

[@Flupus]

Hello mattbat, love your content bro. Keep uploading!

[@lugui]

your inspiration on the 3B1B videos is really good

[@fuze9923]

This video is really great, I learned a few things that I always wanted to know and few new other useful stuff, thanks for the video ☺️

[@hjagu1323]

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

[@theminecraft4202]

your visualizations are really clean and nice to look at

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

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

[@infernopyromaniac]

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

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

[@johnchessant3012]

That origin shift method is so cool!

[@hears__]

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

[@Air_Raider]

Great video! Maze generation has always fascinated me. I hope you make a video on maze solving too. Btw, I also saw the ever changing maze video by CaptainLuma, when it came out. The origin shift algorithm reminds me somewhat of Langton’s Ant, probably because both are based on wandering points.

[@lucadoanpaetzelt]

This video is really awesome, i really enjoy watching it, thx for the high quality content Matt, and you should start making shorts. lol

[@lucadoanpaetzelt]

Lol, i was viewer like, um, 450 something.

[@kingwolf4805]

I love maths content like that ! Continue like that 🔥🔥

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

[@Mateo-zi8ub]

The animations are great, and everything was clearly explained. Good job!

[@justonechessguy]

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

[@delxmos]

I randomly stumbled upon CaptainLuma’s video about his Origin Shift algorithm yesterday And that’s great for you to give him some visibility

[@cmentch]

This video is Amazing! Keep up the great work!

[@fretzT_T]

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

[@funkdefied1]

What an INCREDIBLE twist at the end

[@questionman5]

Wow your videos have really gotten good! Mind sharing what you used to make the visuals?

[@mattbatwings]

Manim

[@siesmec4356]

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!

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

[@domin3k535]

i am just shocked that a weak ago i was also serching for the maze generation in minecraft and it was the same film that you brought to your video and i am in love with thios video of like just explaining those things that you normally wouldn't search for. Minecraft redstone builders are just of limits.

[@Miju001]

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

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

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

[@FreakinRocket]

What did you use to animate all of this? Such a great video!

[@Misstborn]

I just watched Luma's video about origin shift the other day! It was really neat

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

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

[@cdkw8254]

Steping out of the redtone but still bringing quality content. Great!

[@mikiteti1681]

Awesome, coded it right away 😁

[@oro5421]

Wow, that’s cool! Thanks! I like SoME very much, it creates so much good content

[@LesslyPoint]

Loved this a lot

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

[@vlad_makes_stuff]

Love the video! Wish I was taught this before!

[@lollygagger1]

It has been 4 minutes, you haven't learned anything yet.

[@firewalk1293]

I really love learning about these math/programming concepts

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

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

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

[@gigog27]

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

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

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

[@psyonide1394]

One of the best visualization of DFS I’ve seen

[@carlosbom]

woww, love it!!

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

[@nevernether3368]

This is fascinating

[@SupersuMC]

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

[@starin4870]

yess mattbatwings DSA vids :o

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

[@tomgriffiths_net]

This video is a-maze-ing

[@willnoyes7019]

Super cool I like seeing you not do redstone computer for a change

[@Ramp4ge28]

You should do more math videos

[@itzspiro6047]

So Matt, why is HAK only generating when landing on a generated path and not starting on aj empty path and looking if there is a generated path from a previous iteration next to it? Then connecting to it? I feel like this would be benefitial in computing power. The ram usage might be more due to storing an extra variable for generation (current or previous which can theoretically be 1 binary per Square) but i feel like it would be better. Or does an algorithm like this already exist? If it doesn't exist I'm calling it HAKS. standing for HAK - Simplified

[@ayushinamdar2570]

I'm here an hour after release, lovin it already

[@mcl_playz]

8:35 griffpatch made a similar thing. it was for path finding tho

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

[@choonyongtan5671]

Lets go, new mattbatwings video

[@Mxolqi]

This is a really cool video. Also kind of a shock because it has been 2024 for long enough to already get a new SoME You make nice videos that teach me some fun computer science/math things :3

[@toxicfire72]

THANK YOU FOR MAZE ALGORITHM!!!! THIS IS ONE THING I WANTED TO CODE BUT WAS TOO LAZY TO CODE IT 😭

[@VivianAttler]

i love your videos 3blue1brown! keep up the cool topics!

[@AalapShah12297]

A random thought that I had: will the origin-shift algorithm eventually generate every possible maze of a given size? If we can think of a series of origin shifts to generate any NxN target maze from any NxN starting maze - then it is proved. One plausible method to generate a given maze from any starting maze seems to repeatedly use orgin-shift and have the origin trace the path of the target maze like a DFS search would. Then: 1. Every edge in the target maze would get generated at some point during the process. (This happens when the origin is traced across this ege.) 2. Any edge from the target maze would never get erased after being traced for the last time in the process. ( I am unable to prove this so far - I am not even sure if it's true.) If someone can prove that 2 is true then it means that we have generated all the edges of the target maze (and we would have deleted all the non-edges of the target maze too, as any tree with N^2 vertices has exactly N^2-1 edges). So origin-shift will eventually generate every possible maze for the given grid size.

[@friedmule5403]

I do really like your video. I am just not sure if I'll agree with your definitions. If you make mazes that have closed loops inside, do you just make it even harder, since you can now just not follow a simple rule like "keep to the left at all time". A maze can also consist of several nested mazes that can be inside each other or intertwining paths. Mazes do also have to a start and an end point, they can be of any shape, the path can be any type of lines. I would say a maze is a path from start to end with lots of dead ends.

[@Ellisha2488]

Yes! More people speaking about origin shift! I saw that video by luma some time ago and implemented that algorithm in Geometry Dash for my next level. It's really good for games I think, and I hope it gets spread around widely :)

[@guestIdk-ni9hb]

Please, please, *please*, keep making this stuff. This kind of easy-to-understand, yet really interesting content, is *amazing*. Unrelated, but here's an idea: make pacman using a moving maze.

[@NK-61]

oh my god awhile ago I tried to make a redstone maze with the hunt and kill algorithm except I never fully understood it until this video this is the best explanation I’ve found so far tysm

[@IQdog-dj4sq]

i think a very good idea for an educational video on minecraft is the relation between N vs NP and seed finding

[@IRLtwigstan]

I actually knew the algorithm cause I wanted to make a maze generating tool and did some research. When I came across with redstoner with a new maze generation idea. Finally something I actually have info on.