I decided to go with the name "Origin Shift" Algorithm. Thank you all for the great name suggestions!

@penguincute3564

9 күн бұрын

The fact that there might not be able to have an entrance and a exit.

@emiliaolfelt6370

9 күн бұрын

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

@k90v85

9 күн бұрын

​@@emiliaolfelt6370honestly it makes more sense practically aswell, as thats what you do in a maze

@BleachWizz

8 күн бұрын

oooh I came late TnT My suggestions would've been 2: technical name: random walk maze generator: Rwmag marketing name: the wandering painter algorithm.

@WMaster777

6 күн бұрын

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

@captainluma7991

Ай бұрын

Thanks for watching! I'm not too familiar with graph theory, so I will definitely look more into it.

@GameJam230

21 күн бұрын

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.

@birdbeakbeardneck3617

18 күн бұрын

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

@birdbeakbeardneck3617

18 күн бұрын

espetially the idea of an algorithm that keeps the perfectness of a maze

@henrycgs

15 күн бұрын

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!

@research417

8 күн бұрын

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.

@edouardgenetay5336

4 күн бұрын

have you the skill to analyse it theoretically? i could be fun to publish something =)

@RobinHouston

2 күн бұрын

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.

@research417

2 күн бұрын

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

@RobinHouston

2 күн бұрын

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

[3:57] "Here there are 25 nodes" -> shows a 7x7 grid with 49 nodes and 48 connections

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.

@Bagwah

8 күн бұрын

no. 😐

@GameJam230

8 күн бұрын

@@Bagwah .....what do you mean, "no"?

@user-ok8zj8xy6i

8 күн бұрын

​@@Bagwahyes 🦧

@Bagwah

7 күн бұрын

@@user-ok8zj8xy6i no.

@Bagwah

7 күн бұрын

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

@JDZeroZero

Ай бұрын

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

@captainluma7991

23 күн бұрын

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!

@efeloteishe4675

10 күн бұрын

​@@JDZeroZero me wanting to implement it in C++ while you want to do it in redstone 😂

@satibel

9 күн бұрын

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

@weshuiz1325

8 күн бұрын

I would go more with some sort of thing about A dynamic path find

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.

@captainluma7991

8 күн бұрын

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!

@timseguine2

5 күн бұрын

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.

@Pystro

4 күн бұрын

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

@timseguine2

4 күн бұрын

@@Pystro figures. Wanted to point out the invariant though, because it might not be obvious for everyone.

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

@Phoeboi

10 күн бұрын

we need someone to make a Minotaur boss with this

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!

@sheepcommander_

8 күн бұрын

thanks

@kaidatong1704

7 күн бұрын

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?"

@voliol8070

7 күн бұрын

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!

@kaidatong1704

7 күн бұрын

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

@voliol8070

3 күн бұрын

@@kaidatong1704 Nope! No Idea what that is ^^

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

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!

@Bundas102

8 күн бұрын

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

@captainluma7991

8 күн бұрын

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.

@shpralex

2 күн бұрын

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.

I love the dynamic changing of the maze. For the initial state, though, I'd use a minimum spanning tree algorithm such as a randomized Jarnik algorithm - with it, you could generate a maze with just one go through the nodes.

The nice thing too is that this will work in any dimension, or any type of grid. So elegant!

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.

@Bagwah

8 күн бұрын

no. 😐

@enirlo_origne

7 күн бұрын

@@Bagwah no

@SgtSupaman

3 күн бұрын

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.

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

@geodebreaker

8 күн бұрын

be quiet, they are spying on you

@abraxas2658

8 күн бұрын

@@geodebreaker if they're already spying, then i can share the information without giving anything extra away ☺

@geodebreaker

8 күн бұрын

@@abraxas2658 fair enough

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 ;)

@captainluma7991

13 күн бұрын

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!

@MrRyanroberson1

12 күн бұрын

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.

@rostcraft

9 күн бұрын

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

@mrtomithy

9 күн бұрын

@@MrRyanroberson1 thats an interesting way of thinking about it

@K0nomi

9 күн бұрын

would "increased entropy" be a good description of the output?

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.

@Soraphis91

7 күн бұрын

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

@MaxIzrin

7 күн бұрын

​@@Soraphis91 Yeah, I don't know about that, I didn't know this was a Minecraft channel, I'm a software engineer.

Woah, that's so neat. Not only some cool maths, but also the possible Minecraft implementations! I wonder if you could just have each cell be a separate redstone mechanism that can be just glued to the four neighboring cells and scale the entire maze indefinitely this way

Designing algorithms yourself is pretty fun, i remember feeling like a genius when i designed my own way of doing water physics

@Bagwah

8 күн бұрын

no. 😐

With this type of generation, you can easily pathfind, as the nodes always point towards the origin. Well done!

Interesting algorithm. Using the 2 conditions you mentioned there's also an alternative way that is quite similar to your approach: Starting with the grid where each node is connected to each of its neighbors. Now calculate a spanning tree (by using a random vertex at each point). Time complexity would be linear to the grid size (m x n).

Can't here after watching mattbatwings' video from yesterday and this is super impressive! Really nice work

Hi, your algorithm is not just working great also your description of this algorithm is great. I have recreated your algorithm in Python and it works as expected. Appreciate it.

The first step was genius! I have spent weeks and months thinking about how to match graph networks to mazes, but I never found a solution because I was always looking at cells with walls. Looking at the path makes things much easier. Thank you!

The 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!

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

@MrSonny6155

4 күн бұрын

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.

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!

I like the maze generating algorithm as it guarantees a correct maze. When additional checks are required, one can simply generate until the checks are satisfied. For example, a minimal distance to the exit, or a minimal difficulty score. This specific algorithm could be quite useful to generating 3D mazes for an Oscar cube. I've built one, a decade ago, but mine was very easy to solve, sadly.

This idea that the maze changes while you in is cool, but since it's always a perfect maze you can't be trapped. x'D :)

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

Before I opened this video I thought "hmm, I wonder if this would be useful for redstone mazes." Was not disappointed. Now I'm inspired to get back into redstone logic, I would love to try and make my own implementation of this

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.

@Faun471

8 күн бұрын

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

@JDoucette

7 күн бұрын

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.

It's topolgically perfect, and your modification does not change it. Quite genuines!

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.

Constantly shifting maze!! Now that's an awesome idea!

You can move the origin to any point in the maze if needed, by "reversing" all pointers between the two

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.

@edouardgenetay5336

4 күн бұрын

do you have the source of that. I'm interested to read it =)

You can call it the "griever" algorithm from the maze runner movie, where the maze, is constantly changing and the creature is called griever.

Nice work mate, really incredible

Crazy level of editing for just 833 views

@captainluma7991

12 күн бұрын

Thanks!

@fzerosoundfontcovers

9 күн бұрын

up to 3.5k only 3 days later 👀

@Jop_pop

3 күн бұрын

Finally now blew up 10 days later! (49k)

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!

Excellent work! Love this approach 🙌 Thanks for the easy explanation.

Damn that was surprisingly simple for the complex mazes it can make, impressive!

Nice visuals and algorithm! also you are doing a great job talking and explaining, no kidding

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.

Congrats for finding this very elegant maze algorithm

Great video ! You made me want to make a game in a Maze. Amazing Work !

What a simple and clever solution. Great insight about starting with a dead-simple seed maze and then just transforming it.

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.

Really insightful video and very cool! I can see this being quite useful.

I was making a cellular automata to do cave generation for a tile based game and I remember at one point I was generating massive sick looking mazes. Coolest bug ive ever had in game dev.

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?

@captainluma7991

21 күн бұрын

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!

a couple people have mentioned about entrances and exits, failing to retain that the lines are paths and not walls. a moment in the video where some "walls" were faded in may help them :)

That is great! And I can absolutely see how simple the redstone would be! Makes me wanna do it. I already wanted to have a maze somewhere, making it changeable is great!

very cool that you did this from first principles!

Hello. It's almost perfect. My suggestion is to rename the "origin point" as "final destination point". Thank You.

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.

@tigrisparvus2970

8 күн бұрын

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.

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.

Very ingenious! I'll try it in my games!

Your algorithm is really interesting. It does not scale with size since it does not have a linear complexity, but its shuffling property is really elegant and simple using basic tree properties. I really think you should publish it as a scientific paper. If you have a friend in academic who can formalize the maths and help you with the process, i think you should try it

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 👍

THAT is a very clever algorithm. Gonna implement it now.

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.

That's clever! Using steps that don't change some important quality. Reminds me of stuff from calculus (or math in general) where you have invariants such as determinant of the linear operator matrix that does not depend on the basis and

I'm only seeing this today but as many have said, very cool creation. I have seen many formal definition of what this is and also many possible improvement/addition to it so it's really cool too.

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

shadertoy has extremely small+fast maze-algorythms, but most of them assert an infinite plane, and a framed slice of it makes for a worse "maze!"

You can guarantee something changes every iteration by making sure the neighbouring node the origin moves to is one that does not connect directly to the origin. That way, every time you run the algorithm you get a wall being destroyed and a wall being built. That should make it a little more efficient.

@pcrig

3 күн бұрын

Turns out that's not right. Tried doing it in my own C code and it didn't give the expected result. Making it so it can't move in the direction it just came from works though...

This is very cool! This algorithm could be applied to not just mazes but any connected directed acyclic graph to transform them while keeping the connected and acyclic properties intact. I'm curious if there is an equivalent algorithm in graph theory. You should definitely consider writing a paper about this, if not!

Congrats on 1K!! it was either me or the next guy lol

Nice. I really like this algorithm, because it is so simple and easy to understand why it produces perfect mazes. As of the name, the "origin" you mention, looks to a root of a tree. What I do not like about perfect mazes or most algorithms in general, is that they produce a very uniform mazes. A generator that has some regions (of random size) have different character, would be more interesting. Isolated areas, long areas, loops, etc, would also be nice. (it throws simple maze solvers and they cannot solve it).

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

Damn that's a smart way to do a maze. Good job !

This would be a fun screensaver

This ties nicely into a dumb game I made when I was getting to know Godot 3D. Everything outside the FP view was regenerated, but it was just random. It would be nice to make such that, looking forward, it's always possible. Thanks for your work distilling this problem down.

Good thinking. Well done.

this is very cool stuff for hard mazes in video games

this algorithm was fun and actually pretty simple to implement :0

Simply Brilliant:)

Dangg imagine a Maze Runner game with shifting mazes using this algorithm

That's just beautiful!

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.

This algorithm is so genius and yet so simple!

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.

Interesting. Took me a moment to realize the arrows were the path, not the walls.

Very impressive!

Amazing idea ❤

When I saw the simplicity of this algorithm, I was like: "YEAH CPT LUMA, YEAH SCIENCE"

@atomictraveller

7 күн бұрын

dont you bring that filthy thing into this, this isnt knowledge, this is theory. something real!

Wonderful video. As far as I can tell it is indeed novel, which is amazing!

Clever. Well done.

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.

I am a bit late to the party. But I was pleasently suprised by your solution of this problem. Other already told you that this is a "Spanning Trees" Problem. I did a bit of researh into this topic as well and usually people want to find "all solutions" not "just" one. However i think you can still profit from these other algorithms if you want to. I think yours is similar to Matusi 1998 (An Algorithm for Finding All the Spanning Trees in Undirected Graphs) and I highly suggest to read Algorithms for generating all possible spanning trees of a simple undirected connected graph: an extensive review if you want to learn more about this topic. Nevertheless good work. Both in Algorithm and video! :)

The algo (or operation as some argued in other comments) is a clever solution fitting the constraints. Still, there are 2 things that are annoying: - depending on your RNG, the root could never move into a corner of the maze leaving them straight. Switching from "10 x cell count" to "the root must have been in every cell" could fixe that while remaining straightforward to implement (memory cell for each cell and a giant or gate). - when dynamically adjusting the wall, the distance between 2 cells can change from 1 apart (single open wall between) to the entire length of the maze (the maze is a line and both tiles are the ends) in a single action. Not necessarily an issue but i can see a weak argument for "fairness". A version that cap changes in distance could avoid that but likely requires non-local knowledge.

@ninthlyfe6838

8 күн бұрын

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.

@alpers.2123

4 күн бұрын

1. Generate a maze 2. Generate another maze by origin walking the first maze

Rly cool algo I"ll 100% use that for a future horror game

Following the boss fight idea... you could imagine your game character demanding a wall appears or disappears. Since you have immediate knowledge of pathing to the origin, it means you could move the origin without changing the maze to the spots on either side of the wall that is intended to be changed, and then change it. You have to think how the paths must change to impact the wall in question.

I once accidentally made a maze generator. I made conway's game of life in a shader and I played around with the rules and it ended up generating a maze. I could draw pixels and it would generate a maze around that.

This algorithm is more than just adequate -- with a slightly different stopping condition, you could prove that this algorithm is 'perfect': that is, the mazes it produces are unbiased, uniform random spanning trees. The modified stopping condition needed to make the algorithm 'perfect' isn't all that complex either: - When starting generation, mark all cells as 'dirty'. - Each time the origin changes, mark the new origin 'clean'. - Stop once there are no longer any cells marked 'dirty'. (This would mean adding a rs-latch per cell and global fan-in for a 'still dirty' signal; but the reset can be done with your existing 'pause' signal.)

@AJMansfield1

6 күн бұрын

With that 'all clean' stopping condition, that would make CaptainLuma's Origin Shift Algorithm in some sense 'equivalent' to Wilson's Algorithm -- in that they both ensure every cell connects to the maze via a uniformly-selected random walk. Wilson's Algorithm jumps the random walk to a new 'dirty' cell each time it reaches a 'clean' cell, as an optimization to lock in forward progress and not have to wait for the random walk to reach every node on its own -- but I'd bet for small mazes, the smaller big-O of Wilson's Algorithm probably loses to the practical speed benefits of the much simpler/faster redstone for CaptanLuma's Algorithm.

if you run it long enough, it just might create a spiral, which will be the longest chain of paths connected to the origin.

Simple and elegant.