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"
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?
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?
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.
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.
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!
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.
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.
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! :)
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.
Idk how original it really is, because it feels so simple and obvious there is a very high chance someone else has already come up with something similar, but if there is not, then fell free to call it “Luma's Algorithm” or “Luma's Maze Algorithm” . I certainly will call it that hahah
This is very similar to the Down Right generating method, where you randomly assign each node as pointing either down... or right. Aka a binary tree maze.
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.
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. 🤟
The idea of playing a maze that shifts around you in real-time is actually very interesting.. now can this also be made into a 3d matrix as well and manipulated similarly like that? 🤔
Not sure what happened with your visualization / script here (3:55). But you are highlighting 7x7 of green points you reffered to as "Nodes" earlier and claiming there are 25 of them x) Last time i checked, that would be 49 nodes, or a 5x5 representing the 25 nodes.
Isn't this a stupid maze? You just have to wait for the door in front of you to open up eventually, go to the outer Walls, and then face straight to the entrance.. Right? I mean the door in front of you will eventually open.. What I'm missing here?
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 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.)
Hi! This algorithm is really interesting, I implemented it in geometry dash as I want to use it in my next level. Is it okay? And how should I credit you?
Of course its okay! Credit is not necessary, but if you want you can put something like "algorithm by CaptainLuma" in the description. Thank you for watching!
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 :)
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 👍
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.
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.
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 maze algorithms. I like this one, but I think your definition on "when do you stop" may be overlooking an aspect of a complete maze. It has to be random as well. Your initial state is not random, so your algorithm is not complete until every node as been visited at least once. Any unvisited nodes would retain their non-random initial state. The larger the maze, the longer the algorithm has to run until it "looks" complete. That is hard to scale With mazes, performance starts to matter as they get larger. If you were doing something large, on the order of 10,000x10,000 grids, both memory and time are big factors. I'm pretty sure the mathematicians have already proven some algorithm as the "best", but I refuse to look it up. The most efficient I know uses as few as 6 bits per grid cell for its entire memory footprint and can be parallelized while still guaranteeing a perfect maze. I happened to be playing with chatGPT and Claude and walking them through implementations of it. It's an old algorithm, but it has some neat efficiency built into the implementation as a result. I was thinking about making a video on it, but your presentation style is a bajillion times better than anything I could ever do. I know you are on a bigger project, but if you ever come back to mazes some day, I'd be happy to share it with you.
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
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 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
Except, this is not a maze generation algorithm, its a maze modification algorithm. Given you must start with a perfect maze, you fail the criteria of generation. Very cool you came to this on your own, but, this is not new; It is called, among other things, wall shifting, and is a type of maze modification that has existed for awhile.
Beautiful algorithm unfortunately because the direction of moving the origin point is random in many cases this point moves several times e.g. left and right which slows down the operation of the algorithm. Did you find out about any way to improve it?
You should name it aMAZEing (get it because it’s like makes mazes and it’s a play on word because amazing sounds like it has the word maze in it when it does not but when you add in the word maze it is funny because it sounds like it does and this thing is about mazes and it’s cool/amazing)
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!
It is surely an interesting algorithm, but have you really considered the available alternatives? I found a survey where the Aldous-Broder algorithm is not quoted as the most competitive one. Also, is algorithm efficiency really an issue in your case? Any sane implementation of virtually any available algorithm would not, in most cases (such as games) have any trouble in generating some 1000x1000 maze in a fraction of a second. For use in computer games, such a maze would definitely pose a challenge to a human player. The selectable runtime of your algorithm is definitely an advantage for real-time systems, whatever is the reason that they might need mazes! Also, you do not need to use a random walk approach here. Instead, you can scan all cells in a predetermined order. So you can surely visit all cells in a bounded number of iterations.
Aldous-Broder is indeed very slow for large graphs and not guaranteed to terminate. A better algorithm for creating so called "uniform spanning trees" is Wilson's algorithm.
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!
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.
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.
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!
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.
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.
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)
@thedemr9736 Yeah I think there aren't any "entrances" or "exits," it's just a graph of the maze where the dots represent cells and not corners of walls. So imagine walking along the pointers rather than in the space between them.
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.
It's curious how im working for a similar project - a mod - that uses maze generation algorithms. For example, im trying to do a mockup of backrooms level 0 with randomly generated paths, using different maze generation algorithms to carve hallways, but I'm really struggling adapting maze patterns to both minecraft blocks and generation system (blocks are generated/ carved in chunks of 16x16 grids). & This kind of videos are most intresting to watch.
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.
I love the final part - this is captured by Euler's formula for graphs, V-E+F = 2. a "perfect maze" has V vertices, E edges, and 1 face (the walls of the maze and the exterior region), so V = E+1. We know there's only one face because a second face would require a circle (cycle) of edges, which would require one node to point to two other nodes, which breaks rule 1, or require all nodes in the cycle to point to other nodes in the cycle, making it impossible to reach the origin and breaking rule 2. Therefore, a perfect maze always has one more vertex than its number of edges! Or you can just realise every vertex has one edge except the origin in a perfect maze that works too. Just don't realise that after writing a larger proof for it in a youtube comment section 😂
Nooo, why am i only seeing his now😢. Until a month ago i had a project at uni to program an arduino that has a drawing arm(2 that can each turn 180° with a servo, and then a third servo for lifting/lowering a pen)(so 3 servos in total, giving the possibility to reach a 12x12 piece of paper.) We had to program some inverse kinematics to control the drawing, and program some primitives objects to draw(square, line, circle,...) and we also had to add creative aspect to the project. My group chose to create a random maze. For the mazegen algorithm we chose the recursive backtracker(i think that is the same as the one you used as an example, at least it looks like it) If i had seen this video earlier i would definately have tried using this algorithm.
Beautiful explanation. I love the application of using this for an ever shifting maze. This has so much story telling potential. For example, "Delicious in Dungeon" has a plot line about the dungeon constantly shifting and I'm sure many other stories. How frustrating is it to play the ever shifting maze?
Did you ever consider using a random spanning tree algorithm? It would give you a maze with the properties you want: no loops and no isolated areas. For the one I'm thinking of, the logic is extremely simple, but the runtime is random. While that may mean it's not as predictable as you want, I would still expect it to be much faster than MCMC.
This is GENIUS. My mind is blown... Also, my immediate question was, will every possible perfect maze eventually be generated? Turns out, the answer is yes: Lets say you want to transform a maze into another maze. You first walk the origin of the first maze to the origin O of the second maze. Since they have the same origin now, all that is left to do is point every node in the maze to the desired node. If every node points the correct way, you are done. Lets say there is a node A pointing to a node B when it should point to a different node C. There is exactly one way from C to O. You first walk that way from O backwards, reversing every arrow on the way but changing nothing else. You then walk from C directly to A. This makes C point to A and A point to nowhere. All that's left to do is going back from A to C and from there to O, again reversing every arrow but changing nothing else. So every arrow on the way from C to O got reversed twice (i.e. it points in the same direction as before), the arrow from A to B is gone and instead A points to C. You therefore changed nothing except the node that A points to. Now just repeat this for every node pointing to the wrong location and you are done.
I want to make a game since 2015, but i'm so noob i currently only do it with numerically (a set represent edge and another set represent the path) (and even this i had struggle to do it). It would be game where we move along the sides of polygons leaving a trace of a certain color, we can go back this will trace [[above/beside] / this will make another floor ] and when we have gone around the polygon respecting the rules*, this changes the color of the trace and saves it if it does not already exist. (*ex: no more than 2 round trips on the same segment/side)
@@captainluma7991 Constant runtime with no guarantee of a 'good' result is a little dubious. I could create an algorithm that randomly guesses lotto ticket numbers in constant time, and it would be very quick but certainly not guaranteed to be useful. I think your algorithm has potential to be useful, but might need some additional steps to increase the likelihood of a high entropy maze. Maybe adjusting the current node's probability of being landed on again could help. What sunofabeach9424 said is correct, relying too heavily on random walks could lead to portions of your maze being unmodified by the time you stop, particularly as you scale the size of the maze.
One of your grievances for Aldous/Broder was that it had a random runtime. Your algorithm also has a random runtime, does it not? You can stop at any point you'd like, but the sooner you stop, the less likely it is that the maze is any good. Does this scale for very large mazes where random walks could result in large areas being untouched?
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.
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
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
I was thinking, could that work with multiple origin points by giving the constraint that you have to be able to reach one origin from the other? I think that would be also parallelizable 🤔.
I like this video. The only thing is that I would prefer if the path would be thick and the walls thinner. 😅 At a quick glance it always felt reversed to me
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.
Another explanation, for step 3: 3. Repeat the following steps for as many iterations as you'd like: 3a. Move the red point to a random neighboring node. You can teleport of 1 case through a wall, or against an arrow. 3b. Add an arrow or change the arrow of your move, in order to follow You. 3c At arrival, destroy all bad arrows around You: replace them by a wall. I'm not sure: 2 iterations by image is not fair!
hmm i could use something like this for a escape or sandbox game add cool mechanics like crafting some beacon or etc which stops the maze for updating a cell Etc it would be fun maybe for future
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.
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.
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"
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?
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 ^^
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.
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.
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.
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!
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.
This is super neat! Love the suggestion of using it for a dynamic maze.
What a simple and clever solution. Great insight about starting with a dead-simple seed maze and then just transforming it.
just implemented this algorithm in my tool in a video game, really greatful for this bro
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.
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! :)
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 =)
Congrats on 1K!! it was either me or the next guy lol
Idk how original it really is, because it feels so simple and obvious there is a very high chance someone else has already come up with something similar, but if there is not, then fell free to call it “Luma's Algorithm” or “Luma's Maze Algorithm” . I certainly will call it that hahah
Nice visuals and algorithm!
also you are doing a great job talking and explaining, no kidding
This is very similar to the Down Right generating method, where you randomly assign each node as pointing either down... or right. Aka a binary tree maze.
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.
Excellent work! Love this approach 🙌
Thanks for the easy explanation.
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. 🤟
Simply Brilliant:)
Very ingenious! I'll try it in my games!
The idea of playing a maze that shifts around you in real-time is actually very interesting.. now can this also be made into a 3d matrix as well and manipulated similarly like that? 🤔
Not sure what happened with your visualization / script here (3:55).
But you are highlighting 7x7 of green points you reffered to as "Nodes" earlier and claiming there are 25 of them x)
Last time i checked, that would be 49 nodes, or a 5x5 representing the 25 nodes.
Won't this create maxes with multiple entrences/exits?
Does this generate all possible mazes, and if it does, will all of those be generated with equal probability? Can you prove?
As a Minecraft player I love this
This looks perfect for Minecraft ngl
Want to see if I can make it onto scratch
Simple and elegant.
Isn't this a stupid maze? You just have to wait for the door in front of you to open up eventually, go to the outer Walls, and then face straight to the entrance.. Right?
I mean the door in front of you will eventually open.. What I'm missing here?
i guess, but if you let it run for a while, and then stop it, you're able to generate a maze! thats why his algorithm is so good.
I feel like i have seen it before
Is this intended that the mase in the thumbnail has no solution for any of the entrances? ._.
UPD: Oh, I'm stupid. Lines represent paths, not walls.
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 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
[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!
Hi! This algorithm is really interesting, I implemented it in geometry dash as I want to use it in my next level. Is it okay? And how should I credit you?
Of course its okay! Credit is not necessary, but if you want you can put something like "algorithm by CaptainLuma" in the description. Thank you for watching!
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?
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 👍
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.
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.
Crazy level of editing for just 833 views
Thanks!
up to 3.5k only 3 days later 👀
Finally now blew up 10 days later! (49k)
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.
I love maze algorithms. I like this one, but I think your definition on "when do you stop" may be overlooking an aspect of a complete maze. It has to be random as well. Your initial state is not random, so your algorithm is not complete until every node as been visited at least once. Any unvisited nodes would retain their non-random initial state. The larger the maze, the longer the algorithm has to run until it "looks" complete. That is hard to scale
With mazes, performance starts to matter as they get larger. If you were doing something large, on the order of 10,000x10,000 grids, both memory and time are big factors. I'm pretty sure the mathematicians have already proven some algorithm as the "best", but I refuse to look it up.
The most efficient I know uses as few as 6 bits per grid cell for its entire memory footprint and can be parallelized while still guaranteeing a perfect maze. I happened to be playing with chatGPT and Claude and walking them through implementations of it. It's an old algorithm, but it has some neat efficiency built into the implementation as a result. I was thinking about making a video on it, but your presentation style is a bajillion times better than anything I could ever do.
I know you are on a bigger project, but if you ever come back to mazes some day, I'd be happy to share it with you.
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
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
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 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
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.
Designing algorithms yourself is pretty fun, i remember feeling like a genius when i designed my own way of doing water physics
no. 😐
Except, this is not a maze generation algorithm, its a maze modification algorithm. Given you must start with a perfect maze, you fail the criteria of generation.
Very cool you came to this on your own, but, this is not new; It is called, among other things, wall shifting, and is a type of maze modification that has existed for awhile.
Hello. It's almost perfect. My suggestion is to rename the "origin point" as "final destination point". Thank You.
Beautiful algorithm unfortunately because the direction of moving the origin point is random in many cases this point moves several times e.g. left and right which slows down the operation of the algorithm. Did you find out about any way to improve it?
You should name it aMAZEing (get it because it’s like makes mazes and it’s a play on word because amazing sounds like it has the word maze in it when it does not but when you add in the word maze it is funny because it sounds like it does and this thing is about mazes and it’s cool/amazing)
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!
Damn that was surprisingly simple for the complex mazes it can make, impressive!
It is surely an interesting algorithm, but have you really considered the available alternatives? I found a survey where the Aldous-Broder algorithm is not quoted as the most competitive one. Also, is algorithm efficiency really an issue in your case? Any sane implementation of virtually any available algorithm would not, in most cases (such as games) have any trouble in generating some 1000x1000 maze in a fraction of a second. For use in computer games, such a maze would definitely pose a challenge to a human player.
The selectable runtime of your algorithm is definitely an advantage for real-time systems, whatever is the reason that they might need mazes!
Also, you do not need to use a random walk approach here. Instead, you can scan all cells in a predetermined order. So you can surely visit all cells in a bounded number of iterations.
Aldous-Broder is indeed very slow for large graphs and not guaranteed to terminate. A better algorithm for creating so called "uniform spanning trees" is Wilson's algorithm.
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!
Can't here after watching mattbatwings' video from yesterday and this is super impressive! Really nice work
This would be a fun screensaver
This is fantastic! I wonder if it would work in 3d?
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.
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.
The nice thing too is that this will work in any dimension, or any type of grid. So elegant!
With this type of generation, you can easily pathfind, as the nodes always point towards the origin. Well done!
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!
This algorithm is so genius and yet so simple!
Interesting. Took me a moment to realize the arrows were the path, not the walls.
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.
But what is your definition of "perfect" maze? You keep repeating it while never mentioning what you mean.
1:00
@@Jop_pop oh! Thank you!
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.
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)
imagine somebody comes in later like "uhh this is schmeebly's algorithm from 1860" like, did bro make a youtube video about it? i dont think so...
no.
actually schmeebly's great great great great grandchild made a youtube video about it
I think a perfect maze should have only one enterance
for any perfect maze if you choose two random spots there will be exactly one path between them (i think)
Take the top left corner and the bottom right corner. Those are your entrances/exits
@@official-obama yes that is true, since the graph of a "perfect maze" is a tree, and any two nodes of a tree have a unique path between them.
@thedemr9736 Yeah I think there aren't any "entrances" or "exits," it's just a graph of the maze where the dots represent cells and not corners of walls. So imagine walking along the pointers rather than in the space between them.
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.
Wouldn't it be more optimal if it wasn't bruteforced? just evaluate each point and give it a random neighbour connection. NxM iterations, done
It's curious how im working for a similar project - a mod - that uses maze generation algorithms. For example, im trying to do a mockup of backrooms level 0 with randomly generated paths, using different maze generation algorithms to carve hallways, but I'm really struggling adapting maze patterns to both minecraft blocks and generation system (blocks are generated/ carved in chunks of 16x16 grids). & This kind of videos are most intresting to watch.
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.
I love the final part - this is captured by Euler's formula for graphs, V-E+F = 2. a "perfect maze" has V vertices, E edges, and 1 face (the walls of the maze and the exterior region), so V = E+1. We know there's only one face because a second face would require a circle (cycle) of edges, which would require one node to point to two other nodes, which breaks rule 1, or require all nodes in the cycle to point to other nodes in the cycle, making it impossible to reach the origin and breaking rule 2. Therefore, a perfect maze always has one more vertex than its number of edges!
Or you can just realise every vertex has one edge except the origin in a perfect maze that works too. Just don't realise that after writing a larger proof for it in a youtube comment section 😂
Nooo, why am i only seeing his now😢.
Until a month ago i had a project at uni to program an arduino that has a drawing arm(2 that can each turn 180° with a servo, and then a third servo for lifting/lowering a pen)(so 3 servos in total, giving the possibility to reach a 12x12 piece of paper.)
We had to program some inverse kinematics to control the drawing, and program some primitives objects to draw(square, line, circle,...) and we also had to add creative aspect to the project.
My group chose to create a random maze.
For the mazegen algorithm we chose the recursive backtracker(i think that is the same as the one you used as an example, at least it looks like it)
If i had seen this video earlier i would definately have tried using this algorithm.
Beautiful explanation. I love the application of using this for an ever shifting maze.
This has so much story telling potential. For example, "Delicious in Dungeon" has a plot line about the dungeon constantly shifting and I'm sure many other stories.
How frustrating is it to play the ever shifting maze?
Did you ever consider using a random spanning tree algorithm? It would give you a maze with the properties you want: no loops and no isolated areas. For the one I'm thinking of, the logic is extremely simple, but the runtime is random. While that may mean it's not as predictable as you want, I would still expect it to be much faster than MCMC.
This is GENIUS. My mind is blown...
Also, my immediate question was, will every possible perfect maze eventually be generated? Turns out, the answer is yes:
Lets say you want to transform a maze into another maze. You first walk the origin of the first maze to the origin O of the second maze. Since they have the same origin now, all that is left to do is point every node in the maze to the desired node. If every node points the correct way, you are done.
Lets say there is a node A pointing to a node B when it should point to a different node C. There is exactly one way from C to O. You first walk that way from O backwards, reversing every arrow on the way but changing nothing else. You then walk from C directly to A. This makes C point to A and A point to nowhere. All that's left to do is going back from A to C and from there to O, again reversing every arrow but changing nothing else. So every arrow on the way from C to O got reversed twice (i.e. it points in the same direction as before), the arrow from A to B is gone and instead A points to C. You therefore changed nothing except the node that A points to. Now just repeat this for every node pointing to the wrong location and you are done.
I want to make a game since 2015, but i'm so noob i currently only do it with numerically (a set represent edge and another set represent the path) (and even this i had struggle to do it).
It would be game where we move along the sides of polygons leaving a trace of a certain color, we can go back this will trace [[above/beside] / this will make another floor ] and when we have gone around the polygon respecting the rules*, this changes the color of the trace and saves it if it does not already exist.
(*ex: no more than 2 round trips on the same segment/side)
i made that algorithm in gd, and it was surprisingly easy, just extremely time consuming cus of build helper problems
the O(∞) worst case let's goooooooooo
the idea is cool but stick to some wave function collapse modification
It doesn't have infinite worst case runtime. The iteration count is set by the user. It will always be the same.
@@captainluma7991 I mean that with a bad enough random you might end up with algorithm cycling
@@captainluma7991 Constant runtime with no guarantee of a 'good' result is a little dubious. I could create an algorithm that randomly guesses lotto ticket numbers in constant time, and it would be very quick but certainly not guaranteed to be useful. I think your algorithm has potential to be useful, but might need some additional steps to increase the likelihood of a high entropy maze. Maybe adjusting the current node's probability of being landed on again could help. What sunofabeach9424 said is correct, relying too heavily on random walks could lead to portions of your maze being unmodified by the time you stop, particularly as you scale the size of the maze.
One of your grievances for Aldous/Broder was that it had a random runtime. Your algorithm also has a random runtime, does it not? You can stop at any point you'd like, but the sooner you stop, the less likely it is that the maze is any good. Does this scale for very large mazes where random walks could result in large areas being untouched?
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.
Please check the sibilance on the audio for your voice. I think a small cut in the higher frequencies or a de-esser would fix this.
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
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
You could change preview of the video with maze walls, instead of path graphs, IMO
I was thinking, could that work with multiple origin points by giving the constraint that you have to be able to reach one origin from the other?
I think that would be also parallelizable 🤔.
I like this video. The only thing is that I would prefer if the path would be thick and the walls thinner. 😅 At a quick glance it always felt reversed to me
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
Another explanation, for step 3:
3. Repeat the following steps for as many iterations as you'd like:
3a. Move the red point to a random neighboring node. You can teleport of 1 case through a wall, or against an arrow.
3b. Add an arrow or change the arrow of your move, in order to follow You.
3c At arrival, destroy all bad arrows around You: replace them by a wall.
I'm not sure: 2 iterations by image is not fair!
hmm i could use something like this for a escape or sandbox game add cool mechanics like crafting some beacon or etc which stops the maze for updating a cell Etc
it would be fun maybe for future
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.