Ofc you can call this whatever you want, it's your invention, but the computer science term for this type of algorithm is a "walk". Whatever you decide to call it, it's cool. Nice job
oooh I came late TnT My suggestions would've been 2: technical name: random walk maze generator: Rwmag marketing name: the wandering painter algorithm.
@@penguincute3564 If all nodes connect to the origin node, then you can go from any node to any other node. You can then add however many entrances or exits you'd like that are connected to a node and be assured they connect.
So, just a note about math theory that can be applied in this case. What you are describing as "perfect maze" in graph theory is called "tree". Then you have created a "rooted directed tree", and what you have called "origin" is basically a "root" of this tree. It's worth noting that edges (lines) are commonly directed from the root to other nodes in this kind of trees. You can look up the graph theory to improve complexity of a maze by playing with depth of tree and degree of nodes.
Yeah, I actually hadn't even thought about it that way, but really this is just a tree rerooting algorithm with the conditions that each current root node can only be transfered to one of four other nodes (the adjacent cells) and that the current root node must be made to point to the newly selected node.
@captainluma7991 i watched your minecraft video of the new maze design, and thought oh he using trees, however doing this without knowing about trees is really cool
a "rooted directed tree" in which all nodes point to the root (more formally, there's always exactly 1 directed path from any node to the root) is simply called an "arborescence"
This is the thing I love about algorithm design- sometimes the best solution requires changing the problem. Instead of generating a valid maze from scratch, you figured out a way to phrase the problem in a way that would allow any EXISTING valid maze to be converted into another one. Some things are just too heavy for us to lift with our hands, but add a little leverage and now you've done it.
"Origin Walk" would be a decent name for this algorithm I think, this is really quite elegant and I'm surprised nobody has come up with this yet. Very nice
Oh also, I don't know how redstone compatible it would be but you could theoretically have the random movement of the origin biased towards whatever section (you could probably just use quadrants) has the largest number of unvisited tiles, this would have it generate "new looking" mazes faster
I like your idea a lot! This would definitely be useful for large scale mazes where the algorithm is more likely to miss some spots. Thanks for watching!
@@JDZeroZero it should be relatively easy to do a variation where you do something like: each node has a "not visited" 1 bit memory, which gets set when you get to it, and the output of an adder that sums all the values in the column and the row. then you go to the one with the highest value (also biased towards not going backwards to avoid going back and forth on a line) you could probably improve it by having each row/column value average itself with the average of the two adjacent row/column (add it to itself, then add the two together.)
Your algorithm is more important than you think. Origin Shift creates an algorithm through a Markov process. The algorithm itself is a Markov Chain. What’s really interesting is that with your method, various properties of the maze can be optimized by adding an objective-function and Metropolis ratio. I know that sounds like some made up stuff, but it’s an area I’ve worked in for several years. Coming up with the initial algorithm is quite often the most difficult part of Markov Chain Monte Carlo (MCMC). I’m very impressed!
I like that you always have a solution for the maze from any starting node, due to it being an acyclic directed graph with every node ultimately leading to the root node, that's a very nice property. It can also easily be parallelized if you put the origin point on an external point of the maze, and connect it to another maze. The base mechanism is a random walk and you could easily substitute it out for many other algorithms to increase the efficiency. Most importantly it's very intuitive and easy to understand. I can see this algorithm being used for a lot of things, very inventive and cool.
This isn’t in any way meant as a criticism of this very nice video, but the Markov process described here is precisely the one invented by Aldous and Broder and used to derive the “Aldous-Broder algorithm” mentioned at the start of the video.
@@RobinHouston You're wrong, the two algorithms have similarities but they're different. It's more correct to say this algorithm takes in one arborescence and permutes it into another. An arborescence is a directed graph with a root vertex u such that, for any other vertex v, there is exactly one directed path from u to v. The Aldous-Broder algorithm generates a uniform spanning tree; a type of undirected graph. They're both generating graphs, but the algorithms are significantly different. OP's algorithm is permuting a graph. Because every step leads to a valid arborescence, OP's algorithm can be stopped at any time and you'll have a valid result. You can run it indefinitely (or as long as required), and you can start from any arborescence you want. The Aldous-Broder algorithm requires you keep track of visited nodes, and it's a random walk algorithm with a massive time complexity. You also only run it until you have a completed maze, and it can't permute the graph after it's finished. Very different
@@research417 Hey, i think you've misunderstood me. You're describing how the A-B algorithm works (which I already knew, but thanks anyway). I'm talking about _why_ it works, i.e. the proof that it generates every spanning tree with equal probability. This proof does indeed use the Markov process described here. Have you read Aldous or Broder's original papers?
Due to how the arrows point, we have a trivial way to find the origin from any point in the maze. (Yes, I know that I'm not the first commenter to point this out.) But that leads to a possible *speed up* for the algorithm: After the 3 steps at 2:20 you can relocate the origin to a new point by following the arrows from that node and reversing them along the way. This will solve the problem that your origin performs a random walk on the maze nodes, which is notoriously slow. In fact, the expected distance travelled in a random walk scales with the square root of the time taken. Or if you revert the relationship; in order to move the whole width of the maze, you'll take a time proportional to the square of the width. Or in other words, your "run it for width * height *10" should have been "run it for width^2 * height^2 * [some constant]" The random "origin-relocation step" allows the origin to travel any distance, so the algorithm should now indeed run for "width * height * some constant" time. Or you could also relocate the origin in a known pattern (go to each node in sequence). Since the origin re-location takes some time, an optimum speed up strategy would probably involve only occasionally doing that step. For example, you might split the maze into 3x3 chunks and move the origin to the center of those in sequence, and then do 9 or 18 or so of your local "origin shift" operations.
Great idea! This is a really clever solution to get some more coverage over the grid. I might have to try implementing this myself. Thanks for watching!
Unless I misunderstood the process you are describing, it will not result in any topological changes to the maze, in the following sense: If we consider the graph of nodes after forgetting the arrow directions, your path following arrow swapping update operation leaves this "forgetful" graph invariant. So you could use it as an alternative step, but not the only step. Maybe that is what you were suggesting though. The teleports would allow fast travel to another location where one could resume the random walk. In fact this operation is useful in one other regard. If we want the end of the maze to be at a specific square when the algorithm completes, we can use the operation you described to move it there. Another approach for dealing with the problem of random walks not making fast progress: You could update the maze in phases. Each phase starts with a self-avoiding random walk (we keep track of the path we followed and refuse to cross it) that ends when there is no longer a valid movement square that avoids the rest of the path in that phase. Such a walk will diffuse more into the rest of the lattice. I imagine this version might be more difficult to implement in minecraft though.
@@timseguine2 "So you could use it as an alternative step, but not the only step. Maybe that is what you were suggesting though. The teleports would allow fast travel to another location where one could resume the random walk." Yes, that's exactly my suggestion.
oooo this is really smart, I'm trying to apply this algorithm to a 2D game im making in Godot, and I keep having dead spots in the corners that never get hit by the origin even after thousands of steps might try to apply this!
this is a very cool concept, and you made it very easy to follow along with what was happening (coming from someone who's only done that one coding game in school, and stopped doing mazes when teacher stopped handing them out for assignment's). great job!
Hey, just wanted to let you know that this programming concept (separately of maze generation or graph theory) is generally called an MCMC method (Markov chain Monte Carlo). The idea is, start with some default state, and perturb it randomly enough (and enough times) that eventually you could end up anywhere in all the space of possibilities. It can be very useful! P.S., nice algorithm btw!
I remember watching a video of the arctic circle theorem so here I thought "why generate random aztec diamond through diffusion bit by bit rather than in one go?"
That's nice to know! Designed an algorithm using the same principle a while ago, but couldn't come up with a better description for it then than "kind of like a random walk". Thank you!
@@voliol8070 I get lost in YT comments sections since it seems messier / less organized to me. were you also the one I mentioned hyperrogue orb of nature to?
You can set any two nodes as the start and end. To find the solution to the maze: get the unique path form the start and the end to the "origin", if they don't overlap, then just connect the two paths and that is the solution; if they overlap, then just walk backwards form the origin until the splitting point, and you got the solution.
Hi! I've actually been inspired by your algorithm to make a video on it myself! I'm going to go more into the maths behind it. In particular, I'm going to focus on the fact that Origin Shift is actually equivalent to Aldous-Broder (or at least a hybrid version of it) under most stopping conditions! That's not to say Origin Shift isn't still very useful, obviously. And hopefully I make that clear in the video. (I know you also have a lot of other maths commenters here, but I don't think anyone else has made the same point as me yet.) But thanks for inspiring me to look more into maze algorithms. I think there's a lot of surprisingly interesting results.
The first step was genius! I have spent weeks and months thinking about how to match graph networks to mazes, but I never found a solution because I was always looking at cells with walls. Looking at the path makes things much easier. Thank you!
Computer scientist here. My friend, you have just come up with a graph theory algorithm! Well, kinda. To be a little pedantic, it's more like an operation and not really an algorithm, because it doesn't really "solve a problem"; but I think it's close enough! In computer science (and math in general) it's very important to be rigorous. And as we're working, we often stumble onto very similar problems; so, we simplify the problem to its bare bones and use standard language because it makes it easier to explain and to find out if anyone's ever done the same thing before. What you're calling a "perfect maze" is an "arborescence", which is a beautiful name to a kind of directed graph. A "directed graph" is a set of nodes and a set of arcs (arrows) that connect such nodes. And an arborescence is a directed graph in which there exists a single node v, such that for any other node u, there exists a single directed path from u to v. It's just a simplified way to state exactly the same thing as you did at 3:31, they're both valid definitions for an arborescence :) In graph theory, it's very common for a single family of objects to have multiple definitions and/or descriptions. What you're calling a "Maze Generating Algorithm" is really just an "operation that takes in an arborescence and returns another arborescence". And boy, there are a load of those. So many in fact, that I think it's EXTREMELY unlikely that nobody's erver done it before. I just don't think someone's called it a maze generating algorithm :) Oh, and by the way, we can't really state that it "works" without a formal proof. Certainly, your operation takes in an arborescence and returns a directed graph. In order to show that it really works, you'd need to prove that everything it returns is, in fact, an arborescence. I'm pretty sure it does, proving it should be quite easy. All you gotta do is show that after these 3 steps, whatever is generated fits the definition of an arborescence. Whichever definition you want, choose the easiest to work with! By the way; I personally would not call this an algorithm because an algorithm is a finite sequence of steps that solve a "problem". A "problem", too, has a rigorous definition; but in summary, it requires a finite input and a finite expected output. For example, pathfinding algorithms solve the problem which input is "a graph and two nodes of that graph" and the output is "the shortest path in the graph between these two nodes". Yours kinda doesn't have a great description of the output. Sure, the input is an arborescence, and the output is an arborescence. But, like, doing nothing solves the problem! So what exactly are you solving? I guess you could say it's a cooler version of the input arborescence; and I'm sure we can have lots of fun coming up with a definition of a cooler arborescence is :) But until then, I think it's more appropriate to just calling what you made an operation. Like squaring a number. If you want, it's lots of fun to come up with your own proofs, and it often feels like programming, but without the syntax and only the problem solving. I can try something later, but I'll leave this as an exercise to you ;)
Hi, thanks for the comment. It is cool to have my work reviewed by someone with this much knowledge in this field. Thank you for introducing me to the term "arborescence". If I ever do a follow up to this video I will definitely use this term. I don't think I'll be writing a formal proof for this thing, since I'm to inexperienced in graph theory and in writing proofs to take on the task, but if you do decide to try something then I would love to see it. Thank you for watching!
due to the random element, what's happening is that one perfect maze is being transformed into a random nearby perfect maze, in the space of all possible mazes. It's a filtered random walk.
@@captainluma7991Here is my proof: Our graph has n vertices. Requirements for our graph: it should have n-1 edges(because it is basically oriented version of a tree), there is a “root” which should be reachable from every other verticy. Let’s choose any verticy that is not a “root”, remove its outgoing edge and make an edge from previous “root” to the new one. Our first requirement holds because we removed one edge and added another one. Let’s check if we can still reach out “root” from every verticy, every verticy was either in new “root” “subtree”(it’s not a tree because it oriented but it doesn’t really matter) or not in it, every verticy which was in its “subtree” is still connected to it and every verticy that wasn’t in it is connected to our previous “root” so is also connected to our new “root”. This concludes the proof. P.S. I kinda do olympiad math, but this proof is probably not very professional written. Wish me luck on JBMO 2024 :)
This is exactly what I was looking for! I’m currently making a game in VR Chat called Attack on Streamer, a game where a lot of “viewers” work together and navigate obstacle courses while a giant “streamer” tries to sabotage them. The obstacle courses will include an easy, medium, and hard maze, though I had no clue how the streamer was going to sabotage viewers in these obstacle courses. But this algorithm is perfect! Being able to change the maze while people are inside of it is a nice sabotage without being too overpowered >:3 Thank you so much for creating this!
This aglgorithm is nice when the maze is small. I tried to recreate it and use it on large maze (50x50). If random is not on our side, the maze get a lot o horizontal lines. My though on it: 1) generate a non random perfect maze like hilbert curve. 2) add a variable "touched" set to false on each cell, when a cell is modified by the generator, set it to true 3) try to avoid touched rewrite if unecessary: if there is 2 or more neibours cells untouched then choose to go to one of them 4) try to avoid turning around: when 1 or less neibours cell is untouched, target a untouched cell ar random and only go in a direction that go to it, keep that target until there is again 2 or more untouched neibours
Thank you for watching! I really like your idea of using a Hilbert curve as a starting point to get rid of the leftover horizontal paths. That is a very clever addition.
You can also add an "origin jump" (to a random location) in addition to an "origin shift" (to an adjacent location). To do an "origin jump" you pick a new random cell in the grid and recompute the direction of the arrows around that origin, the maze itself doesn't change. Then continue shifting like before from the new origin. The really cool part about the original origin shift method is that it's so computationally effective, but interspersing a few origin jumps can potentially increase the randomness.
Instead of generating an entirely new maze, your algorithm ingeniously optimized the path through an existing perfect maze structure. A subtle yet clever manipulation of the underlying architectur. Truly impressive work!
I have been developing a maze generation program for my A level project, and this algorithm looks really cool! I will be sure to implement this and cite your video. This is really cool
Hi, I'm a developer of a maze generation library Labyrinthian. Your algorithm has truly impressed me and I've even integrated it into my library. Unlike other graph-based algorithms like Kruskal or Wilson that generate a random spanning tree from scratch, Origin Shift operates on an existing spanning tree and dynamically modifies it. In my implementation your algorithm can be used for any graph-based maze (delta, theta, sigma etc.). I start by selecting a cell (random by default) and perform a BFS from it to create the initial spanning tree (perfect maze). Then, I apply n iterations (n = 10 * mazeCellsCount by default, as per your suggestion in your video). I've observed that in certain cases, especially with delta and larger mazes, Origin Shift may not fully traverse the graph which will lead to long empty corridors. Despite this, I believe your algorithm has significant potential for enhancement or as a valuable secondary post-processing tool.
Could you create a heat map that lowers the probability that a node would be selected depending on how many times its been selected before? Then over time the untouched spots would get more attention.
@@preseasonedcookware1093 Yes, I modified the algorithm so that it stops when all cells have been visited. Then, I conducted 500 tests using a 50x50 orthogonal maze. In the default implementation, it took an average of 78,233 iterations (with a maximum of 204,425) to fully traverse the graph. However, with the heat map approach, it required only 8,134 iterations on average (with a maximum of 12,294). Additionally, I performed some benchmarks. Origin Shift performs well for relatively small mazes and even outperforms some other maze generation algorithms. However, when there is more than approximately 200 cells Origin Shift algorithm becomes the slowest one, even using heat maps.
I just coded this and it takes like no time to make, that's really cool It's convenient for the maze game I'm making, where I want each level to be a completely new maze, because I never have to reset the algorithm since I can always just run it using the last level's maze to get the new level
This is also convenient since the first run already pre-intialised into a mostly random maze, so future runs are less likely to have missing spots with fewer iterations (not that it matters for small mazes). With some tinkering, you could probably make it retain some entire zones from the previous run depending on the game.
Another cool aspect of this algorithm is you can move the origin anywhere you want to when you're done. Simply use the same algorithm but instead of moving the origin to a random neighbor you move it toward where you want it to be.
The best thing about this algorithm for me is that it can be implemented very efficiently in terms of memory use. Recursive methods can obviously use huge amounts of stack memory (although there are ways to use the heap), so for microcontrollers, this can restrict the maze size. This method can be implemented with a fixed amount of RAM, known at runtime! Nice work!
Hi, your algorithm is not just working great also your description of this algorithm is great. I have recreated your algorithm in Python and it works as expected. Appreciate it.
Initializing the maze with a less easy to traverse initial pattern might help. For example (for a maze where 0,0 is the bottom right node): Make everything point right. Override every column divisible by 2 to point down. Override every row divisible by 3 to point right. Override every column divisible by 4 to point down. Override every row divisible by 6 to point down. Override every column divisible by 8 to point down. Override every row divisible by 12 to point down. ... Make the bottom right node the origin. This will make a nice "binary" tree with lots of dead ends. And it will leave only 3 straight paths that go all the way through the maze. As a possible improvement, you could probably alternate between up and down for the powers of 2 (the columns), and alternate between right and left for the tripled powers of two (the rows), as that will then generate dead ends pointing in all directions, not just up and left.
Yeah, using an actual maze generating algorithm before applying this procedure would be the better approach than just starting with something so simplistic and waiting for the random steps to eventually reach the entire thing.
I love the dynamic changing of the maze. For the initial state, though, I'd use a minimum spanning tree algorithm such as a randomized Jarnik algorithm - with it, you could generate a maze with just one go through the nodes.
Before I opened this video I thought "hmm, I wonder if this would be useful for redstone mazes." Was not disappointed. Now I'm inspired to get back into redstone logic, I would love to try and make my own implementation of this
This is basically Aldous-Broder in reverse. If, like Aldous-Broder, you start with a disconnected graph and terminate once the graph is connected (equivalently, every vertex has been visited), you will have a uniform spanning tree. In fact, if you memorize one algorithm’s random walk and apply it to the other in reverse, the graphs are identical. This is most easily seen by giving Aldous-Broder similar arrows. When Origin Shift moves from vertex A to vertex B, it always changes A’s arrow to point at B. When Aldous-Broder moves from vertex B to vertex A, it only changes A’s arrow to point at B if this is the first encounter with A. This is a time reversal, Origin Shift choosing the newest move and Aldous-Broder choosing the oldest move. Termination gets a little funky in this equivalence. Each algorithm likely revisits its starting point, whereas it only visits its termination point once. A reverse run never revisits its starting point, and likely keeps going after what would ordinarily be its termination condition. Origin Shift reversed into Aldous-Broder takes extra steps at the end to no effect. Aldous-Broder reversed into Origin Shift takes extra steps that keep modifying the graph! The first algorithm didn’t know ahead of time that its first moves would be redundant. This is benign with no effect on the distribution. As you’ve found, the benefit of Origin Shift is that you can make incremental changes and terminate before a full randomization. Interesting find in all.
Interesting algorithm. Using the 2 conditions you mentioned there's also an alternative way that is quite similar to your approach: Starting with the grid where each node is connected to each of its neighbors. Now calculate a spanning tree (by using a random vertex at each point). Time complexity would be linear to the grid size (m x n).
A cool fact I figured out about the origin shift algorithm: 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 is good isbecause 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.
Computer Science student here, great work on the 'algorithm'! You've made quite an example of a maze generated using a digraph. I saw many others explain it splendidly in the comments so I won't bother, but I want you to know that you have a brilliant mind, great work!
First of all: excellent video, and very clever and simple algorithm, I'm writing this down. Secondly: Playing with your website for a bit, the algorithm seems to have a pretty big flaw, though not one you can't overcome. Because the direction to advance the origin is selected randomly, in larger grids the origin can move in just one area of the maze for a very long time. This means that your number of iterations (height x width x 10) is not going to work if you scale up the maze size, meaning parts of it will remain unchanged. A heat map can solve this, I think, though I couldn't tell you how to make that in Minecraft. Alternatively, multiple smaller mazes can be generated and then linked together. The linking of multiple mazes could cause loops, however... if you treat each maze chunk as a node, and run the algorithm again, you will generate a map of connections that will prevent this, keeping the large maze perfect.
> Alternatively, multiple smaller mazes can be generated and then linked together. The linking of multiple mazes could cause loops, however You probably could come up with a hierarchical/recursive approach, so that you don't get any loops. (just define start/exit to be on any two distinct edges of the bounds) not sure about how to do that in minecraft though.
Woah, that's so neat. Not only some cool maths, but also the possible Minecraft implementations! I wonder if you could just have each cell be a separate redstone mechanism that can be just glued to the four neighboring cells and scale the entire maze indefinitely this way
this could be the most practical algorithm for games because with just like a few dozen random mazes as starting points you could minimally edit them with this and players would never notice the unchanged sections once in a while so you could get away with probably 1/4 of the steps
As @teswa said, a perfect maze here is a rooted directed tree. The direction of each node is just upwards towards the root. So, in such a tree, randomly select a node (except the root of the tree). Since it is not the root node, it would have a parent. Snip that edge (between the selected node and its parent) and take the selected node along with its entire subtree out. Add the existing root as a new direct child node of the selected node. The selected node is now the root. If during the random selection, you only limit yourself to the nodes which are nearby in the grid, you get this algorithm in its entirety. Since you start with a rooted tree, and only move around subtrees, you are guaranteed a rooted tree at every step with no loops.
I really love your content and this maze generating algorithm fascinates me everytime i see , i just wanted to say thank you so much for sharing this amazing algorithm with the community , and i myself am implementing it in my maze generating game ( hope you're ok with me doing so, and if not lmk)
Great video! One suggested clarification: I was wondering why the generated mazes had multiple entrances and exits and overall looked really weird. Then I realized I was looking at the visualization as the actual maze. The pointers aren't walls! The nodes are the square cells of the maze, and the actual maze is what's essentially the dual of the graph, where you turning all the nodes into cells and form connections between walls wherever there's a pointer between two nodes.
Yeah I also found that weird, it's generally not how people visualise mazes, but once you figure it out, it's a pretty cool way to generate a maze. It's something I worked on a month or two ago, and I sort of wish I thought of this approach xD
Perhaps if the arrows were drawn really thick, implying a path you can walk on, then it would be easier to consume. I was also surprised how, even knowing the nodes were the paths, that I kept reading them as walls.
I'm only seeing this today but as many have said, very cool creation. I have seen many formal definition of what this is and also many possible improvement/addition to it so it's really cool too.
This is a very interesting algorithm, thanks for sharing it 👍One thing though, at first I was confused about the 3rd step "remove the origins node pointer", at 2:04 this step is not visible because the new red pointer already overlaps the old blue pointer. And the rest of the animation moves too quickly to see it happening. Maybe let the anmation run a few steps into the algorithm at a slower pace, because then it'll also show some non-overlapping pointers. Other than that, cool video and great explanation
I like the maze generating algorithm as it guarantees a correct maze. When additional checks are required, one can simply generate until the checks are satisfied. For example, a minimal distance to the exit, or a minimal difficulty score. This specific algorithm could be quite useful to generating 3D mazes for an Oscar cube. I've built one, a decade ago, but mine was very easy to solve, sadly.
That is great! And I can absolutely see how simple the redstone would be! Makes me wanna do it. I already wanted to have a maze somewhere, making it changeable is great!
I was making a cellular automata to do cave generation for a tile based game and I remember at one point I was generating massive sick looking mazes. Coolest bug ive ever had in game dev.
I love the concept you've developed with this. I especially like the idea of changing mazes. If I ever get time I might try implement something simpler is UE5. Thanks for sharing.
Nice work. You should throw a mail to Jamis Buck, he wrote an entire book on maze generation. I'm sure he'll be able to tell you if your approach is novel or not. I've done extensive research on the topic myself and I can't say I've come across it yet. So looks good 👍
Nice. I really like this algorithm, because it is so simple and easy to understand why it produces perfect mazes. As of the name, the "origin" you mention, looks to a root of a tree. What I do not like about perfect mazes or most algorithms in general, is that they produce a very uniform mazes. A generator that has some regions (of random size) have different character, would be more interesting. Isolated areas, long areas, loops, etc, would also be nice. (it throws simple maze solvers and they cannot solve it).
Just so you know, I built a couple of dynamic mazes in a indie game called *Zeepkist*. One was generated via an edit of your code, the other has an actual implementation of the real-time algorithm, albeit too slow to make much impact of the gameplay. I might make a pre-programmed sequence just to make the dynamic maze more interesting.
That's clever! Using steps that don't change some important quality. Reminds me of stuff from calculus (or math in general) where you have invariants such as determinant of the linear operator matrix that does not depend on the basis and
The simplicity of the mutation step and the property that it remains solvable at all times makes me think of potential board game applications... Vs board game where you and your opponent take turns moving and mutating the maze, trying to make it better for yourself, while screwing your opponent over.
This is already used in a board game I once played where after each turn you could move a block to raise or lower the path to do just that. Unfortunately i couldn't tell you the name of the game.
You can guarantee something changes every iteration by making sure the neighbouring node the origin moves to is one that does not connect directly to the origin. That way, every time you run the algorithm you get a wall being destroyed and a wall being built. That should make it a little more efficient.
Turns out that's not right. Tried doing it in my own C code and it didn't give the expected result. Making it so it can't move in the direction it just came from works though...
Following the boss fight idea... you could imagine your game character demanding a wall appears or disappears. Since you have immediate knowledge of pathing to the origin, it means you could move the origin without changing the maze to the spots on either side of the wall that is intended to be changed, and then change it. You have to think how the paths must change to impact the wall in question.
Cool idea. I feel like every arrow here should point the other way if you're going to call that node the "origin". Since this is a tree, "root" would be a more standard name.
You can actually use this to generate a maze from scratch too, however it will take a random amount of time - up to infinite time. Start without any pointers, choose one node as the origin, and repeat the steps: Move origin to a random neighbouring node and create that pointer, and then remove the new origin's pointer (if it has one)
I am a bit late to the party. But I was pleasently suprised by your solution of this problem. Other already told you that this is a "Spanning Trees" Problem. I did a bit of researh into this topic as well and usually people want to find "all solutions" not "just" one. However i think you can still profit from these other algorithms if you want to. I think yours is similar to Matusi 1998 (An Algorithm for Finding All the Spanning Trees in Undirected Graphs) and I highly suggest to read Algorithms for generating all possible spanning trees of a simple undirected connected graph: an extensive review if you want to learn more about this topic. Nevertheless good work. Both in Algorithm and video! :)
The algo (or operation as some argued in other comments) is a clever solution fitting the constraints. Still, there are 2 things that are annoying: - depending on your RNG, the root could never move into a corner of the maze leaving them straight. Switching from "10 x cell count" to "the root must have been in every cell" could fixe that while remaining straightforward to implement (memory cell for each cell and a giant or gate). - when dynamically adjusting the wall, the distance between 2 cells can change from 1 apart (single open wall between) to the entire length of the maze (the maze is a line and both tiles are the ends) in a single action. Not necessarily an issue but i can see a weak argument for "fairness". A version that cap changes in distance could avoid that but likely requires non-local knowledge.
I agree with the first point, though one of the constraints was needing to generate the maze in fixed time. One of the other comments mentioned a way to avoid entirely using a random walk during generation, which could address this issue.
This is very cool! This algorithm could be applied to not just mazes but any connected directed acyclic graph to transform them while keeping the connected and acyclic properties intact. I'm curious if there is an equivalent algorithm in graph theory. You should definitely consider writing a paper about this, if not!
a couple people have mentioned about entrances and exits, failing to retain that the lines are paths and not walls. a moment in the video where some "walls" were faded in may help them :)
A perfect maze is just one of the spanning tree of the grid, should be even simpler to implement think, you just randomly grow a tree from the start node and pick any node that touch the border, possibly with significant depth from the starting node.
It's a nice approach, but I don't like the runtime complexity. There's an algorithm that works with coloring/flagging each column and basically generating an infinite maze row by row, and at any moment it's perfect. Its operations are very similar to yours, but only in one row at a time. This gives the maze linear generation time and constant, very low space complexity.
In theory you should be able to add loops to this pretty trivially. If the initial maze has loops, those are really just a number of extra paths. I think the only process change would be in choosing the next node. If loops are present, the origin will occasionally have an outgoing path, when choosing a direction for the next origin, don't follow the outgoing path. Or if you do follow the outgoing path, don't do the add/remove step and just move.
Discovered a new channel on a video talking about an algorithm he created, already interesting My man is doing redstone, which I love And he’s also a GD player, the ultimate combo
Neat. You don't even have to reinitialize it to regenerate. That's cool as heck. My vote is to just make it after yourself, or maybe call it "Captain Luma's method". You should create a Wikipedia article on this too, bc that's honestly novel. 🤟
This feels like a more flexible version of how Berserk generated its mazes. Rather than connecting nodes, it had a 4x2 series of posts that would each have one wall coming from it in a random cardinal direction. Very fast, and makes a maze that can be navigated from and to any point.
This is really cool! I've been making a GPU compute shader raytracer with openGL, and I thought it'd be fun to make it a backrooms game. I just downloaded a model off the internet and decimated it until it ran ingame at a solid 60fps, but I think I might implement this algorithm and procedurally generate a maze. As you play, the maze will shift around you, which I think will be really disorienting and weird.
This was absolutely brilliant! 11/10 video, incredible work, I am blown away seriously 🎉. You should consider publishing this academically in a math journal, you might've broken new ground in this field. This video is going in my favorites folder!!
you could probably optimize the algorithm by restricting it from choosing the direction it just came from in the last "move". so if it makes a left, then it cant immediately follow-up with a right. if it then goes up, it can follow with a right now, but not a down. might be handy for larger mazes
I decided to go with the name "Origin Shift" Algorithm. Thank you all for the great name suggestions!
The fact that there might not be able to have an entrance and a exit.
Ofc you can call this whatever you want, it's your invention, but the computer science term for this type of algorithm is a "walk".
Whatever you decide to call it, it's cool. Nice job
@@emiliaolfelt6370honestly it makes more sense practically aswell, as thats what you do in a maze
oooh I came late TnT
My suggestions would've been 2:
technical name: random walk maze generator: Rwmag
marketing name: the wandering painter algorithm.
@@penguincute3564 If all nodes connect to the origin node, then you can go from any node to any other node. You can then add however many entrances or exits you'd like that are connected to a node and be assured they connect.
I really like the idea of the maze generating around you, I think that could be a really engaging way to have like a bossfight or something
we need someone to make a Minotaur boss with this
You could have a probability map for node selection follow the player's location so the maze changes less or more around the player.
So, just a note about math theory that can be applied in this case. What you are describing as "perfect maze" in graph theory is called "tree". Then you have created a "rooted directed tree", and what you have called "origin" is basically a "root" of this tree. It's worth noting that edges (lines) are commonly directed from the root to other nodes in this kind of trees. You can look up the graph theory to improve complexity of a maze by playing with depth of tree and degree of nodes.
Thanks for watching! I'm not too familiar with graph theory, so I will definitely look more into it.
Yeah, I actually hadn't even thought about it that way, but really this is just a tree rerooting algorithm with the conditions that each current root node can only be transfered to one of four other nodes (the adjacent cells) and that the current root node must be made to point to the newly selected node.
@captainluma7991 i watched your minecraft video of the new maze design, and thought oh he using trees, however doing this without knowing about trees is really cool
espetially the idea of an algorithm that keeps the perfectness of a maze
a "rooted directed tree" in which all nodes point to the root (more formally, there's always exactly 1 directed path from any node to the root) is simply called an "arborescence"
This is the thing I love about algorithm design- sometimes the best solution requires changing the problem. Instead of generating a valid maze from scratch, you figured out a way to phrase the problem in a way that would allow any EXISTING valid maze to be converted into another one. Some things are just too heavy for us to lift with our hands, but add a little leverage and now you've done it.
no. 😐
@@Bagwah .....what do you mean, "no"?
@@Bagwahyes 🦧
@@SunglassOrang no.
@@GameJam230 i mean no
"Origin Walk" would be a decent name for this algorithm I think, this is really quite elegant and I'm surprised nobody has come up with this yet. Very nice
Oh also, I don't know how redstone compatible it would be but you could theoretically have the random movement of the origin biased towards whatever section (you could probably just use quadrants) has the largest number of unvisited tiles, this would have it generate "new looking" mazes faster
I like your idea a lot! This would definitely be useful for large scale mazes where the algorithm is more likely to miss some spots. Thanks for watching!
@@JDZeroZero me wanting to implement it in C++ while you want to do it in redstone 😂
@@JDZeroZero it should be relatively easy to do a variation where you do something like:
each node has a "not visited" 1 bit memory, which gets set when you get to it, and the output of an adder that sums all the values in the column and the row.
then you go to the one with the highest value (also biased towards not going backwards to avoid going back and forth on a line)
you could probably improve it by having each row/column value average itself with the average of the two adjacent row/column (add it to itself, then add the two together.)
I would go more with some sort of thing about
A dynamic path find
Your algorithm is more important than you think. Origin Shift creates an algorithm through a Markov process. The algorithm itself is a Markov Chain.
What’s really interesting is that with your method, various properties of the maze can be optimized by adding an objective-function and Metropolis ratio. I know that sounds like some made up stuff, but it’s an area I’ve worked in for several years.
Coming up with the initial algorithm is quite often the most difficult part of Markov Chain Monte Carlo (MCMC). I’m very impressed!
I like that you always have a solution for the maze from any starting node, due to it being an acyclic directed graph with every node ultimately leading to the root node, that's a very nice property.
It can also easily be parallelized if you put the origin point on an external point of the maze, and connect it to another maze. The base mechanism is a random walk and you could easily substitute it out for many other algorithms to increase the efficiency. Most importantly it's very intuitive and easy to understand.
I can see this algorithm being used for a lot of things, very inventive and cool.
have you the skill to analyse it theoretically? i could be fun to publish something =)
This isn’t in any way meant as a criticism of this very nice video, but the Markov process described here is precisely the one invented by Aldous and Broder and used to derive the “Aldous-Broder algorithm” mentioned at the start of the video.
@@RobinHouston You're wrong, the two algorithms have similarities but they're different. It's more correct to say this algorithm takes in one arborescence and permutes it into another. An arborescence is a directed graph with a root vertex u such that, for any other vertex v, there is exactly one directed path from u to v.
The Aldous-Broder algorithm generates a uniform spanning tree; a type of undirected graph. They're both generating graphs, but the algorithms are significantly different.
OP's algorithm is permuting a graph.
Because every step leads to a valid arborescence, OP's algorithm can be stopped at any time and you'll have a valid result. You can run it indefinitely (or as long as required), and you can start from any arborescence you want.
The Aldous-Broder algorithm requires you keep track of visited nodes, and it's a random walk algorithm with a massive time complexity. You also only run it until you have a completed maze, and it can't permute the graph after it's finished. Very different
@@research417 Hey, i think you've misunderstood me. You're describing how the A-B algorithm works (which I already knew, but thanks anyway). I'm talking about _why_ it works, i.e. the proof that it generates every spanning tree with equal probability. This proof does indeed use the Markov process described here. Have you read Aldous or Broder's original papers?
Due to how the arrows point, we have a trivial way to find the origin from any point in the maze. (Yes, I know that I'm not the first commenter to point this out.)
But that leads to a possible *speed up* for the algorithm: After the 3 steps at 2:20 you can relocate the origin to a new point by following the arrows from that node and reversing them along the way.
This will solve the problem that your origin performs a random walk on the maze nodes, which is notoriously slow. In fact, the expected distance travelled in a random walk scales with the square root of the time taken. Or if you revert the relationship; in order to move the whole width of the maze, you'll take a time proportional to the square of the width. Or in other words, your "run it for width * height *10" should have been "run it for width^2 * height^2 * [some constant]"
The random "origin-relocation step" allows the origin to travel any distance, so the algorithm should now indeed run for "width * height * some constant" time.
Or you could also relocate the origin in a known pattern (go to each node in sequence).
Since the origin re-location takes some time, an optimum speed up strategy would probably involve only occasionally doing that step. For example, you might split the maze into 3x3 chunks and move the origin to the center of those in sequence, and then do 9 or 18 or so of your local "origin shift" operations.
Great idea! This is a really clever solution to get some more coverage over the grid. I might have to try implementing this myself. Thanks for watching!
Unless I misunderstood the process you are describing, it will not result in any topological changes to the maze, in the following sense: If we consider the graph of nodes after forgetting the arrow directions, your path following arrow swapping update operation leaves this "forgetful" graph invariant. So you could use it as an alternative step, but not the only step. Maybe that is what you were suggesting though. The teleports would allow fast travel to another location where one could resume the random walk.
In fact this operation is useful in one other regard. If we want the end of the maze to be at a specific square when the algorithm completes, we can use the operation you described to move it there.
Another approach for dealing with the problem of random walks not making fast progress:
You could update the maze in phases. Each phase starts with a self-avoiding random walk (we keep track of the path we followed and refuse to cross it) that ends when there is no longer a valid movement square that avoids the rest of the path in that phase. Such a walk will diffuse more into the rest of the lattice. I imagine this version might be more difficult to implement in minecraft though.
@@timseguine2 "So you could use it as an alternative step, but not the only step. Maybe that is what you were suggesting though. The teleports would allow fast travel to another location where one could resume the random walk." Yes, that's exactly my suggestion.
@@Pystro figures. Wanted to point out the invariant though, because it might not be obvious for everyone.
oooo this is really smart, I'm trying to apply this algorithm to a 2D game im making in Godot, and I keep having dead spots in the corners that never get hit by the origin even after thousands of steps might try to apply this!
this is a very cool concept, and you made it very easy to follow along with what was happening (coming from someone who's only done that one coding game in school, and stopped doing mazes when teacher stopped handing them out for assignment's). great job!
Hey, just wanted to let you know that this programming concept (separately of maze generation or graph theory) is generally called an MCMC method (Markov chain Monte Carlo). The idea is, start with some default state, and perturb it randomly enough (and enough times) that eventually you could end up anywhere in all the space of possibilities. It can be very useful! P.S., nice algorithm btw!
thanks
I remember watching a video of the arctic circle theorem so here I thought "why generate random aztec diamond through diffusion bit by bit rather than in one go?"
That's nice to know! Designed an algorithm using the same principle a while ago, but couldn't come up with a better description for it then than "kind of like a random walk". Thank you!
@@voliol8070 I get lost in YT comments sections since it seems messier / less organized to me. were you also the one I mentioned hyperrogue orb of nature to?
@@kaidatong1704 Nope! No Idea what that is ^^
Since the arrows also point towards the origin, if the origin was set as a "finish" then you'd also instantly get the solution with the maze. Amazing!
You can set any two nodes as the start and end. To find the solution to the maze: get the unique path form the start and the end to the "origin", if they don't overlap, then just connect the two paths and that is the solution; if they overlap, then just walk backwards form the origin until the splitting point, and you got the solution.
Damn that was surprisingly simple for the complex mazes it can make, impressive!
Hi! I've actually been inspired by your algorithm to make a video on it myself!
I'm going to go more into the maths behind it. In particular, I'm going to focus on the fact that Origin Shift is actually equivalent to Aldous-Broder (or at least a hybrid version of it) under most stopping conditions!
That's not to say Origin Shift isn't still very useful, obviously. And hopefully I make that clear in the video.
(I know you also have a lot of other maths commenters here, but I don't think anyone else has made the same point as me yet.)
But thanks for inspiring me to look more into maze algorithms. I think there's a lot of surprisingly interesting results.
I'm honored, and I look forward to it! Glad this inspired you.
i came from your video, hello!
The first step was genius! I have spent weeks and months thinking about how to match graph networks to mazes, but I never found a solution because I was always looking at cells with walls. Looking at the path makes things much easier. Thank you!
The nice thing too is that this will work in any dimension, or any type of grid. So elegant!
Computer scientist here. My friend, you have just come up with a graph theory algorithm! Well, kinda. To be a little pedantic, it's more like an operation and not really an algorithm, because it doesn't really "solve a problem"; but I think it's close enough!
In computer science (and math in general) it's very important to be rigorous. And as we're working, we often stumble onto very similar problems; so, we simplify the problem to its bare bones and use standard language because it makes it easier to explain and to find out if anyone's ever done the same thing before.
What you're calling a "perfect maze" is an "arborescence", which is a beautiful name to a kind of directed graph. A "directed graph" is a set of nodes and a set of arcs (arrows) that connect such nodes. And an arborescence is a directed graph in which there exists a single node v, such that for any other node u, there exists a single directed path from u to v. It's just a simplified way to state exactly the same thing as you did at 3:31, they're both valid definitions for an arborescence :) In graph theory, it's very common for a single family of objects to have multiple definitions and/or descriptions.
What you're calling a "Maze Generating Algorithm" is really just an "operation that takes in an arborescence and returns another arborescence". And boy, there are a load of those. So many in fact, that I think it's EXTREMELY unlikely that nobody's erver done it before. I just don't think someone's called it a maze generating algorithm :)
Oh, and by the way, we can't really state that it "works" without a formal proof. Certainly, your operation takes in an arborescence and returns a directed graph. In order to show that it really works, you'd need to prove that everything it returns is, in fact, an arborescence. I'm pretty sure it does, proving it should be quite easy. All you gotta do is show that after these 3 steps, whatever is generated fits the definition of an arborescence. Whichever definition you want, choose the easiest to work with!
By the way; I personally would not call this an algorithm because an algorithm is a finite sequence of steps that solve a "problem". A "problem", too, has a rigorous definition; but in summary, it requires a finite input and a finite expected output. For example, pathfinding algorithms solve the problem which input is "a graph and two nodes of that graph" and the output is "the shortest path in the graph between these two nodes".
Yours kinda doesn't have a great description of the output. Sure, the input is an arborescence, and the output is an arborescence. But, like, doing nothing solves the problem! So what exactly are you solving? I guess you could say it's a cooler version of the input arborescence; and I'm sure we can have lots of fun coming up with a definition of a cooler arborescence is :) But until then, I think it's more appropriate to just calling what you made an operation. Like squaring a number.
If you want, it's lots of fun to come up with your own proofs, and it often feels like programming, but without the syntax and only the problem solving. I can try something later, but I'll leave this as an exercise to you ;)
Hi, thanks for the comment. It is cool to have my work reviewed by someone with this much knowledge in this field. Thank you for introducing me to the term "arborescence". If I ever do a follow up to this video I will definitely use this term. I don't think I'll be writing a formal proof for this thing, since I'm to inexperienced in graph theory and in writing proofs to take on the task, but if you do decide to try something then I would love to see it. Thank you for watching!
due to the random element, what's happening is that one perfect maze is being transformed into a random nearby perfect maze, in the space of all possible mazes. It's a filtered random walk.
@@captainluma7991Here is my proof:
Our graph has n vertices. Requirements for our graph: it should have n-1 edges(because it is basically oriented version of a tree), there is a “root” which should be reachable from every other verticy.
Let’s choose any verticy that is not a “root”, remove its outgoing edge and make an edge from previous “root” to the new one. Our first requirement holds because we removed one edge and added another one. Let’s check if we can still reach out “root” from every verticy, every verticy was either in new “root” “subtree”(it’s not a tree because it oriented but it doesn’t really matter) or not in it, every verticy which was in its “subtree” is still connected to it and every verticy that wasn’t in it is connected to our previous “root” so is also connected to our new “root”. This concludes the proof.
P.S. I kinda do olympiad math, but this proof is probably not very professional written. Wish me luck on JBMO 2024 :)
@@MrRyanroberson1 thats an interesting way of thinking about it
would "increased entropy" be a good description of the output?
With this type of generation, you can easily pathfind, as the nodes always point towards the origin. Well done!
This is exactly what I was looking for! I’m currently making a game in VR Chat called Attack on Streamer, a game where a lot of “viewers” work together and navigate obstacle courses while a giant “streamer” tries to sabotage them. The obstacle courses will include an easy, medium, and hard maze, though I had no clue how the streamer was going to sabotage viewers in these obstacle courses. But this algorithm is perfect! Being able to change the maze while people are inside of it is a nice sabotage without being too overpowered >:3 Thank you so much for creating this!
This aglgorithm is nice when the maze is small.
I tried to recreate it and use it on large maze (50x50).
If random is not on our side, the maze get a lot o horizontal lines.
My though on it:
1) generate a non random perfect maze like hilbert curve.
2) add a variable "touched" set to false on each cell, when a cell is modified by the generator, set it to true
3) try to avoid touched rewrite if unecessary: if there is 2 or more neibours cells untouched then choose to go to one of them
4) try to avoid turning around: when 1 or less neibours cell is untouched, target a untouched cell ar random and only go in a direction that go to it, keep that target until there is again 2 or more untouched neibours
Thank you for watching! I really like your idea of using a Hilbert curve as a starting point to get rid of the leftover horizontal paths. That is a very clever addition.
You can also add an "origin jump" (to a random location) in addition to an "origin shift" (to an adjacent location). To do an "origin jump" you pick a new random cell in the grid and recompute the direction of the arrows around that origin, the maze itself doesn't change. Then continue shifting like before from the new origin. The really cool part about the original origin shift method is that it's so computationally effective, but interspersing a few origin jumps can potentially increase the randomness.
Instead of generating an entirely new maze, your algorithm ingeniously optimized the path through an existing perfect maze structure. A subtle yet clever manipulation of the underlying architectur. Truly impressive work!
I have been developing a maze generation program for my A level project, and this algorithm looks really cool! I will be sure to implement this and cite your video. This is really cool
Hi, I'm a developer of a maze generation library Labyrinthian. Your algorithm has truly impressed me and I've even integrated it into my library. Unlike other graph-based algorithms like Kruskal or Wilson that generate a random spanning tree from scratch, Origin Shift operates on an existing spanning tree and dynamically modifies it.
In my implementation your algorithm can be used for any graph-based maze (delta, theta, sigma etc.). I start by selecting a cell (random by default) and perform a BFS from it to create the initial spanning tree (perfect maze). Then, I apply n iterations (n = 10 * mazeCellsCount by default, as per your suggestion in your video).
I've observed that in certain cases, especially with delta and larger mazes, Origin Shift may not fully traverse the graph which will lead to long empty corridors.
Despite this, I believe your algorithm has significant potential for enhancement or as a valuable secondary post-processing tool.
Could you create a heat map that lowers the probability that a node would be selected depending on how many times its been selected before? Then over time the untouched spots would get more attention.
@@preseasonedcookware1093 Yes, I modified the algorithm so that it stops when all cells have been visited. Then, I conducted 500 tests using a 50x50 orthogonal maze. In the default implementation, it took an average of 78,233 iterations (with a maximum of 204,425) to fully traverse the graph. However, with the heat map approach, it required only 8,134 iterations on average (with a maximum of 12,294).
Additionally, I performed some benchmarks. Origin Shift performs well for relatively small mazes and even outperforms some other maze generation algorithms. However, when there is more than approximately 200 cells Origin Shift algorithm becomes the slowest one, even using heat maps.
[3:57] "Here there are 25 nodes" -> shows a 7x7 grid with 49 nodes and 48 connections
Came here to post this, but I see you already have. Well done!
It's funny that exactly when I'm designing a game with a maze, this video pops up to give me some options for generation
be quiet, they are spying on you
@@geodebreaker if they're already spying, then i can share the information without giving anything extra away ☺
@@abraxas2658 fair enough
I just coded this and it takes like no time to make, that's really cool
It's convenient for the maze game I'm making, where I want each level to be a completely new maze, because I never have to reset the algorithm since I can always just run it using the last level's maze to get the new level
This is also convenient since the first run already pre-intialised into a mostly random maze, so future runs are less likely to have missing spots with fewer iterations (not that it matters for small mazes). With some tinkering, you could probably make it retain some entire zones from the previous run depending on the game.
Another cool aspect of this algorithm is you can move the origin anywhere you want to when you're done. Simply use the same algorithm but instead of moving the origin to a random neighbor you move it toward where you want it to be.
The best thing about this algorithm for me is that it can be implemented very efficiently in terms of memory use. Recursive methods can obviously use huge amounts of stack memory (although there are ways to use the heap), so for microcontrollers, this can restrict the maze size. This method can be implemented with a fixed amount of RAM, known at runtime! Nice work!
Hi, your algorithm is not just working great also your description of this algorithm is great. I have recreated your algorithm in Python and it works as expected. Appreciate it.
Initializing the maze with a less easy to traverse initial pattern might help. For example (for a maze where 0,0 is the bottom right node):
Make everything point right.
Override every column divisible by 2 to point down.
Override every row divisible by 3 to point right.
Override every column divisible by 4 to point down.
Override every row divisible by 6 to point down.
Override every column divisible by 8 to point down.
Override every row divisible by 12 to point down.
...
Make the bottom right node the origin.
This will make a nice "binary" tree with lots of dead ends. And it will leave only 3 straight paths that go all the way through the maze.
As a possible improvement, you could probably alternate between up and down for the powers of 2 (the columns), and alternate between right and left for the tripled powers of two (the rows), as that will then generate dead ends pointing in all directions, not just up and left.
no. 😐
@@Bagwah no
Yeah, using an actual maze generating algorithm before applying this procedure would be the better approach than just starting with something so simplistic and waiting for the random steps to eventually reach the entire thing.
What a simple and clever solution. Great insight about starting with a dead-simple seed maze and then just transforming it.
I love the dynamic changing of the maze. For the initial state, though, I'd use a minimum spanning tree algorithm such as a randomized Jarnik algorithm - with it, you could generate a maze with just one go through the nodes.
You can move the origin to any point in the maze if needed, by "reversing" all pointers between the two
this is really interesting and the maze that changes while being played sounds like a really cool concept
Before I opened this video I thought "hmm, I wonder if this would be useful for redstone mazes." Was not disappointed.
Now I'm inspired to get back into redstone logic, I would love to try and make my own implementation of this
Can't here after watching mattbatwings' video from yesterday and this is super impressive! Really nice work
It's topolgically perfect, and your modification does not change it. Quite genuines!
This is basically Aldous-Broder in reverse. If, like Aldous-Broder, you start with a disconnected graph and terminate once the graph is connected (equivalently, every vertex has been visited), you will have a uniform spanning tree. In fact, if you memorize one algorithm’s random walk and apply it to the other in reverse, the graphs are identical. This is most easily seen by giving Aldous-Broder similar arrows. When Origin Shift moves from vertex A to vertex B, it always changes A’s arrow to point at B. When Aldous-Broder moves from vertex B to vertex A, it only changes A’s arrow to point at B if this is the first encounter with A. This is a time reversal, Origin Shift choosing the newest move and Aldous-Broder choosing the oldest move.
Termination gets a little funky in this equivalence. Each algorithm likely revisits its starting point, whereas it only visits its termination point once. A reverse run never revisits its starting point, and likely keeps going after what would ordinarily be its termination condition. Origin Shift reversed into Aldous-Broder takes extra steps at the end to no effect. Aldous-Broder reversed into Origin Shift takes extra steps that keep modifying the graph! The first algorithm didn’t know ahead of time that its first moves would be redundant. This is benign with no effect on the distribution.
As you’ve found, the benefit of Origin Shift is that you can make incremental changes and terminate before a full randomization. Interesting find in all.
Interesting algorithm. Using the 2 conditions you mentioned there's also an alternative way that is quite similar to your approach: Starting with the grid where each node is connected to each of its neighbors. Now calculate a spanning tree (by using a random vertex at each point). Time complexity would be linear to the grid size (m x n).
Designing algorithms yourself is pretty fun, i remember feeling like a genius when i designed my own way of doing water physics
no. 😐
A cool fact I figured out about the origin shift algorithm: 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 is good isbecause 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.
the idea of the maze generating while being in it is cool! cool video
Computer Science student here, great work on the 'algorithm'! You've made quite an example of a maze generated using a digraph. I saw many others explain it splendidly in the comments so I won't bother, but I want you to know that you have a brilliant mind, great work!
First of all: excellent video, and very clever and simple algorithm, I'm writing this down.
Secondly: Playing with your website for a bit, the algorithm seems to have a pretty big flaw, though not one you can't overcome.
Because the direction to advance the origin is selected randomly, in larger grids the origin can move in just one area of the maze for a very long time.
This means that your number of iterations (height x width x 10) is not going to work if you scale up the maze size, meaning parts of it will remain unchanged.
A heat map can solve this, I think, though I couldn't tell you how to make that in Minecraft.
Alternatively, multiple smaller mazes can be generated and then linked together.
The linking of multiple mazes could cause loops, however... if you treat each maze chunk as a node, and run the algorithm again, you will generate a map of connections that will prevent this, keeping the large maze perfect.
> Alternatively, multiple smaller mazes can be generated and then linked together. The linking of multiple mazes could cause loops, however
You probably could come up with a hierarchical/recursive approach, so that you don't get any loops. (just define start/exit to be on any two distinct edges of the bounds)
not sure about how to do that in minecraft though.
@@Soraphis91 Yeah, I don't know about that, I didn't know this was a Minecraft channel, I'm a software engineer.
Woah, that's so neat. Not only some cool maths, but also the possible Minecraft implementations! I wonder if you could just have each cell be a separate redstone mechanism that can be just glued to the four neighboring cells and scale the entire maze indefinitely this way
this could be the most practical algorithm for games because with just like a few dozen random mazes as starting points you could minimally edit them with this and players would never notice the unchanged sections once in a while so you could get away with probably 1/4 of the steps
just implemented this algorithm in my tool in a video game, really greatful for this bro
As @teswa said, a perfect maze here is a rooted directed tree. The direction of each node is just upwards towards the root.
So, in such a tree, randomly select a node (except the root of the tree). Since it is not the root node, it would have a parent. Snip that edge (between the selected node and its parent) and take the selected node along with its entire subtree out. Add the existing root as a new direct child node of the selected node. The selected node is now the root.
If during the random selection, you only limit yourself to the nodes which are nearby in the grid, you get this algorithm in its entirety. Since you start with a rooted tree, and only move around subtrees, you are guaranteed a rooted tree at every step with no loops.
The shifting paths actually sounds fun to play
Came here from the bat's vid and just saying, glad you made it.
I really love your content and this maze generating algorithm fascinates me everytime i see , i just wanted to say thank you so much for sharing this amazing algorithm with the community , and i myself am implementing it in my maze generating game ( hope you're ok with me doing so, and if not lmk)
This is super neat! Love the suggestion of using it for a dynamic maze.
Congrats for finding this very elegant maze algorithm
Great video! One suggested clarification: I was wondering why the generated mazes had multiple entrances and exits and overall looked really weird. Then I realized I was looking at the visualization as the actual maze. The pointers aren't walls! The nodes are the square cells of the maze, and the actual maze is what's essentially the dual of the graph, where you turning all the nodes into cells and form connections between walls wherever there's a pointer between two nodes.
Yeah I also found that weird, it's generally not how people visualise mazes, but once you figure it out, it's a pretty cool way to generate a maze. It's something I worked on a month or two ago, and I sort of wish I thought of this approach xD
Perhaps if the arrows were drawn really thick, implying a path you can walk on, then it would be easier to consume. I was also surprised how, even knowing the nodes were the paths, that I kept reading them as walls.
Nice visuals and algorithm!
also you are doing a great job talking and explaining, no kidding
This is a cool algorithm. Makes me want to dust off my old n-D maze code and implement it.
I'm only seeing this today but as many have said, very cool creation. I have seen many formal definition of what this is and also many possible improvement/addition to it so it's really cool too.
This is a very interesting algorithm, thanks for sharing it 👍One thing though, at first I was confused about the 3rd step "remove the origins node pointer", at 2:04 this step is not visible because the new red pointer already overlaps the old blue pointer. And the rest of the animation moves too quickly to see it happening. Maybe let the anmation run a few steps into the algorithm at a slower pace, because then it'll also show some non-overlapping pointers. Other than that, cool video and great explanation
Constantly shifting maze!! Now that's an awesome idea!
I like the maze generating algorithm as it guarantees a correct maze. When additional checks are required, one can simply generate until the checks are satisfied. For example, a minimal distance to the exit, or a minimal difficulty score. This specific algorithm could be quite useful to generating 3D mazes for an Oscar cube. I've built one, a decade ago, but mine was very easy to solve, sadly.
Congrats on 1K!! it was either me or the next guy lol
That is great! And I can absolutely see how simple the redstone would be! Makes me wanna do it. I already wanted to have a maze somewhere, making it changeable is great!
I was making a cellular automata to do cave generation for a tile based game and I remember at one point I was generating massive sick looking mazes. Coolest bug ive ever had in game dev.
I love the concept you've developed with this. I especially like the idea of changing mazes. If I ever get time I might try implement something simpler is UE5. Thanks for sharing.
Nice work.
You should throw a mail to Jamis Buck, he wrote an entire book on maze generation.
I'm sure he'll be able to tell you if your approach is novel or not.
I've done extensive research on the topic myself and I can't say I've come across it yet. So looks good 👍
Nice. I really like this algorithm, because it is so simple and easy to understand why it produces perfect mazes. As of the name, the "origin" you mention, looks to a root of a tree.
What I do not like about perfect mazes or most algorithms in general, is that they produce a very uniform mazes. A generator that has some regions (of random size) have different character, would be more interesting. Isolated areas, long areas, loops, etc, would also be nice. (it throws simple maze solvers and they cannot solve it).
This idea that the maze changes while you in is cool, but since it's always a perfect maze you can't be trapped. x'D :)
Just so you know, I built a couple of dynamic mazes in a indie game called *Zeepkist*. One was generated via an edit of your code, the other has an actual implementation of the real-time algorithm, albeit too slow to make much impact of the gameplay. I might make a pre-programmed sequence just to make the dynamic maze more interesting.
That's clever! Using steps that don't change some important quality. Reminds me of stuff from calculus (or math in general) where you have invariants such as determinant of the linear operator matrix that does not depend on the basis and
The simplicity of the mutation step and the property that it remains solvable at all times makes me think of potential board game applications... Vs board game where you and your opponent take turns moving and mutating the maze, trying to make it better for yourself, while screwing your opponent over.
This is already used in a board game I once played where after each turn you could move a block to raise or lower the path to do just that. Unfortunately i couldn't tell you the name of the game.
You are so smart buddy nice work I will experiment with your algorithm to make it maybe better
This algorithm is so genius and yet so simple!
You can call it the "griever" algorithm
from the maze runner movie, where
the maze, is constantly changing
and the creature is called griever.
You can guarantee something changes every iteration by making sure the neighbouring node the origin moves to is one that does not connect directly to the origin. That way, every time you run the algorithm you get a wall being destroyed and a wall being built. That should make it a little more efficient.
Turns out that's not right. Tried doing it in my own C code and it didn't give the expected result. Making it so it can't move in the direction it just came from works though...
Following the boss fight idea... you could imagine your game character demanding a wall appears or disappears. Since you have immediate knowledge of pathing to the origin, it means you could move the origin without changing the maze to the spots on either side of the wall that is intended to be changed, and then change it. You have to think how the paths must change to impact the wall in question.
I love this. Implemented it in PICO-8 for potential use in a game. Maybe a "Wizard of Wor" sort of game, but the maze periodically changes?
Cool idea. I feel like every arrow here should point the other way if you're going to call that node the "origin". Since this is a tree, "root" would be a more standard name.
You can actually use this to generate a maze from scratch too, however it will take a random amount of time - up to infinite time. Start without any pointers, choose one node as the origin, and repeat the steps: Move origin to a random neighbouring node and create that pointer, and then remove the new origin's pointer (if it has one)
I am a bit late to the party. But I was pleasently suprised by your solution of this problem. Other already told you that this is a "Spanning Trees" Problem. I did a bit of researh into this topic as well and usually people want to find "all solutions" not "just" one. However i think you can still profit from these other algorithms if you want to. I think yours is similar to Matusi 1998 (An Algorithm for Finding All the Spanning Trees in Undirected Graphs) and I highly suggest to read Algorithms for generating all possible spanning trees of a simple
undirected connected graph: an extensive review if you want to learn more about this topic.
Nevertheless good work. Both in Algorithm and video! :)
The algo (or operation as some argued in other comments) is a clever solution fitting the constraints.
Still, there are 2 things that are annoying:
- depending on your RNG, the root could never move into a corner of the maze leaving them straight. Switching from "10 x cell count" to "the root must have been in every cell" could fixe that while remaining straightforward to implement (memory cell for each cell and a giant or gate).
- when dynamically adjusting the wall, the distance between 2 cells can change from 1 apart (single open wall between) to the entire length of the maze (the maze is a line and both tiles are the ends) in a single action. Not necessarily an issue but i can see a weak argument for "fairness". A version that cap changes in distance could avoid that but likely requires non-local knowledge.
I agree with the first point, though one of the constraints was needing to generate the maze in fixed time. One of the other comments mentioned a way to avoid entirely using a random walk during generation, which could address this issue.
1. Generate a maze
2. Generate another maze by origin walking the first maze
Really insightful video and very cool! I can see this being quite useful.
This is very cool! This algorithm could be applied to not just mazes but any connected directed acyclic graph to transform them while keeping the connected and acyclic properties intact. I'm curious if there is an equivalent algorithm in graph theory. You should definitely consider writing a paper about this, if not!
a couple people have mentioned about entrances and exits, failing to retain that the lines are paths and not walls. a moment in the video where some "walls" were faded in may help them :)
A perfect maze is just one of the spanning tree of the grid, should be even simpler to implement think, you just randomly grow a tree from the start node and pick any node that touch the border, possibly with significant depth from the starting node.
It's a nice approach, but I don't like the runtime complexity. There's an algorithm that works with coloring/flagging each column and basically generating an infinite maze row by row, and at any moment it's perfect.
Its operations are very similar to yours, but only in one row at a time.
This gives the maze linear generation time and constant, very low space complexity.
do you have the source of that. I'm interested to read it =)
very cool that you did this from first principles!
In theory you should be able to add loops to this pretty trivially. If the initial maze has loops, those are really just a number of extra paths.
I think the only process change would be in choosing the next node. If loops are present, the origin will occasionally have an outgoing path, when choosing a direction for the next origin, don't follow the outgoing path. Or if you do follow the outgoing path, don't do the add/remove step and just move.
Hello. It's almost perfect. My suggestion is to rename the "origin point" as "final destination point". Thank You.
Excellent work! Love this approach 🙌
Thanks for the easy explanation.
THAT is a very clever algorithm. Gonna implement it now.
Discovered a new channel on a video talking about an algorithm he created, already interesting
My man is doing redstone, which I love
And he’s also a GD player, the ultimate combo
Neat. You don't even have to reinitialize it to regenerate. That's cool as heck. My vote is to just make it after yourself, or maybe call it "Captain Luma's method". You should create a Wikipedia article on this too, bc that's honestly novel. 🤟
This feels like a more flexible version of how Berserk generated its mazes. Rather than connecting nodes, it had a 4x2 series of posts that would each have one wall coming from it in a random cardinal direction. Very fast, and makes a maze that can be navigated from and to any point.
This is really cool!
I've been making a GPU compute shader raytracer with openGL, and I thought it'd be fun to make it a backrooms game. I just downloaded a model off the internet and decimated it until it ran ingame at a solid 60fps, but I think I might implement this algorithm and procedurally generate a maze. As you play, the maze will shift around you, which I think will be really disorienting and weird.
this algorithm was fun and actually pretty simple to implement :0
Nice work mate, really incredible
You should have been given an award! That's crazy to invent a new algorithm, I'm really really impressed!
When I saw the simplicity of this algorithm, I was like: "YEAH CPT LUMA, YEAH SCIENCE"
dont you bring that filthy thing into this, this isnt knowledge, this is theory. something real!
Wonderful video. As far as I can tell it is indeed novel, which is amazing!
This was absolutely brilliant! 11/10 video, incredible work, I am blown away seriously 🎉. You should consider publishing this academically in a math journal, you might've broken new ground in this field. This video is going in my favorites folder!!
you could probably optimize the algorithm by restricting it from choosing the direction it just came from in the last "move". so if it makes a left, then it cant immediately follow-up with a right. if it then goes up, it can follow with a right now, but not a down. might be handy for larger mazes
Have you looked at Maze Craze for the Atari 2600s? 1978 on a system with only 128 bytes of RAM so might shed some light on ultra efficient algorithms.