True. I think what this would be most useful for is quickly reducing the worst-case search space for a directed DFS like A*. I'd have to see how the performance compares; this seems like iterations of a 3x3 kernel over a matrix, known to be fast and parallelizable. I'd wager this only gives performance gains on extremely large mazes with lots of loop-backs; A* tends to be very efficient out-of-the-box.
@@mikechurvis9995 as we saw in the video, it can be very linear and slow in the end if we have a long dead end. maybe we could use some kind of hybrid approach where both the search and the dead-end elimination are done in parallel, so we aren’t forced to wait for those. btw, if we have unlimited parallelism isn’t dijkstra’s algorithm as fast as A*? but maybe it’s harder to parallelize than the dead-end elimination? maybe another alternative would be to simply limit the number of iterations before switching to A*, either by a fixed number based on the size of the maze or by a limit on the minimum number of dead ends
I think it would fully preserve them with nothing extra. If you wanted to get the shortest path you could breadth first search after getting all the working paths, and then whichever path reaches first, you can trim the rest.
Multiple good paths? Was exactly what I wondered. Since only dead ends are removed, right up till they hit a 3-4 junction, the multiple paths would be preserved. Then the A-B travel would have to chose from the multiple paths but this is not implemented. Since the multiple paths are all valid, itmwould still travel from A to B just fine, but there is no mechanism to determine the best of multiple paths, nor choosemthe best path... I do like this algorithm because it doesnt need to be recursive, it could even be done sequentially instead of simultaneously as seen in the video. That means it can be done with an incredibly simple, and reliable, tiny bit of code.
Since this algorithm just trims off the dead ends, and working paths are the only ones which are ultimately not dead ends, they would all be preserved.
@@brandonallen2301 22²22222²22222221111111222222222222222²2222222222222²²22²2222²²222222222222222222²2²²222222222222222222222222222222222²²222ww area WW2 ww was a ass wàwww ass wwwww a áwwwww see ãwàw was wwwwwwwwwwww ass wáw saw2222222222222²²²²222222222222222222222²2222222222222222222222⅔wwwww we wwwwww3w3 wew was wewa33aw www we 3w3 was awa
This algorithm can be implemented as a celular automaton. 4 states: endpoint, path, deadend, black. Neighbor: von neumann Rule: path with one or zero neighboring path and not near to any endpoints becomes a deadend.
@@Pystro I want to preserve the looks of the maze, though. Strictly speaking, only two states are necessary, which can be expressed with B/S234V in Golly's notation
@@Vextrove I was going to say the same thing. It's how I solved mazes as a 10 year old. Color in the dead ends until you reach a T intersection that hasn't been colored in. Of course, as a human you can periodically look to see if the solution has become clear before you finish coloring it all in. It actually made mazes too easy and uninteresting.
@@obscurereference6298 "but it knows when to stop and not interfere with the correct route which we would not know how to do." We can recognize any dead space by looking around it. Any space that's not the entrance or exit is a dead end if it doesn't have at least two open spaces next to it. Watch carefully and see which spaces it blocks off every time.
@@wizardbrandon3544 The missile knows where it is at all times. It knows this because it knows where it isn't. By subtracting where it is from where it isn't, or where it isn't from where it is (whichever is greater), it obtains a difference, or deviation. The guidance subsystem uses deviations to generate corrective commands to drive the missile from a position where it is to a position where it isn't, and arriving at a position where it wasn't, it now is. Consequently, the position where it is, is now the position that it wasn't, and it follows that the position that it was, is now the position that it isn't. In the event that the position that it is in is not the position that it wasn't, the system has acquired a variation, the variation being the difference between where the missile is, and where it wasn't. If variation is considered to be a significant factor, it too may be corrected by the GEA. However, the missile must also know where it was. The missile guidance computer scenario works as follows. Because a variation has modified some of the information the missile has obtained, it is not sure just where it is. However, it is sure where it isn't, within reason, and it knows where it was. It now subtracts where it should be from where it wasn't, or vice-versa, and by differentiating this from the algebraic sum of where it shouldn't be, and where it was, it is able to obtain the deviation and its variation, which is called error.
Congrats to this creative approach! It is specialized for dense mazes of limited, rectangular size on a regular, square grid. I think you can use this algorithm for multi-path mazes with some small modifications: a) Find and store all branches b) While filling dead-ends, stop at the first branch. In the remaining maze you could choose the shortest path (avoiding loops). Cost-wise, you still have square complexity of the initial dead-end scan.
This is the hardest maze I've ever tried to solve, usually I solve mazes with just my eyes but damn this maze confuses my eyes like an optical illusion.
Omg the designer of this maze is so evil. The fact that the very first path has a 50/50 chance of leading you on the most elaborate dead end the world has ever seen is insane 😂 Even solving from the end first, there’s a huge elaborate dead end not too far from the end either 😅
That is very cool! What optimizing is done on the pass-handling? I assume it runs through pr row or column unless run on a parallel processing architecture? Once there is no more dead ends on a row there will not ever be until the row above or below have been changed so it can be skipped.
It looks like once you find the initial set of dead ends, you only have to check if the cells around the current dead ends are now dead ends. I.e., each step involves trimming off the dead end, finding the single adjacent cell that was open, and marking that as a new dead end. No need to scan the entire maze once you've done the first scan. Just track where the dead ends are.
This is funny. Back in college in 1980, I was on a programming team competing with a bunch of teams in the midwest. Four programmers, Four problems, Four hours, and ForTran. One of the problems was to find a path through a maze like this. Everyone at the contest knew mazes were solved via recursion but ForTran IV doesn't support it. The students tackling the problem were all trying to implement their own form of recursion. After the contest was over and nobody solved that one, I took a look at it and slapped my forehead. I saw this fill-in algorithm immediately. Could have coded it in 10 minutes. Ah, well, we came in fourth behind 3 teams of grad students, so we didn't feel too bad.
this is how I solve the mazes that would be a part of the kids menus at restaurants lol Use one color to figure out the correct path, and every dead end I find gets filled in with a different color (usually red and green like in the video lol)
Limitation of this algorithm is, that the computer needs the "full picture" to apply the algorithm. It's not like a "mouse" which has only a subjective view and needs to optimize its algorithm from "inside" of the maze.
3 mandalorians are stuck in a maze. 2 of them are arguing with each other. “This is the way” “No, this is the way” they keep saying to each other. Then the third flies up and out of the maze with his jetpack. “No that’s the way” the second says to the first
If you cannot see the top-down layout of the maze, you are back to guessing or “always turning left”. This algorithm could be useful after the first run to make the next pnes more effective.
That’s pretty similar to how I solve puzzles irl. Is it considered efficient? I think I use a combination of this method, the trick about the right most path (when applicable), and segmenting the puzzle so large swaths of it can be ignored all at once, but for a computer that might technically be less efficient.
This is how I used to solve mazes. I'd take a pencil and carefully black out all the dead ends. It was much more satisfying that way. Yeaah I was a weird kid.
could you have an algorithm that checks for forks and dead ends, then do something like filling the path between dead ends and the closest fork, then start over and repeat?
@@drjvoices no I mean if the white was walls then it wouldn’t make sense because some black parts make islands which wouldn’t make sense if it was a path
This is how I pictured it going from the title. My question is that once all of the dead ends are detected, does the program scan the entire maze again for new dead ends or did it map the dead end points and then start making decisions for only those points of interest. The first would be a shorter code but more steps. The longer code should be less steps.
From the first 20 seconds of the video, it looks like the algorithm tries to find all the dead ends first, then parses back from them until it reaches a white square that is bordered by 2+ white squares.
I get that this is illustrative, but every branch choice should be held in a tree and the branch elided when a dead end is reached, no need to backtrace. Also scanning the maze for dead ends is not a benefit as you must still walk the maze to get the connectivity so you might as well walk the maze and discover the dead ends as you go and pop back to the branching point.
Seems slow, but I guess the upside is that it can be done in parallel, so no matter how large the maze is, you can always just throw more threads at it.
Sounds possible, but there would be a lot of overhead due to synchronization issues. If a dead end branches out to two dead ends, then those two dead ends would meet up and only one of the threads are going to continue from that point. I think OpenMP's tasks implementation would be great for such a problem, but I am unsure if you would actually see any speedup when using huge numbers of threads.
@@ifroad33 Yeah, I think thinking of the maze as a matrix and using a gpu would be better in this case. Basically, you would: 1) Create a matrix with 0 for walls, 1 for paths and 2 for the starting and ending cell. 2) Then, you would add the surrounding values (paths) for a new (temporary) matrix, not adding the original value of the cell in question. 3) Once you do this, substract 1 for each value. 4) Multiply the matrix with the original one. Any value that's 0 is now a wall, any other value is a path. 5) Finally, set every cell that's not 0 to 1, and the starting and ending cells to 2, and compare the new matrix to the old one . If they are the same, end the task. If not, repeat from step 2 This was a fun problem! If you read this, please tell me if you find any improvements/flaws with my process. Anyway, have a nice day! Edit: I've found a problem -> The starting and ending cells shouldn't be 2. Instead, we should make their values = 1 after each iteration, before returning the matrix
@@lombas3185 The only thing with the algorithm I can see is wrong is step 3) where you want to perform matrix multiplication. I know what you are referring to, because you are trying to multiply each separate value from the temporary matrix, with the values in the original matrix. But matrix multiplication refers to another operation which works a bit differently. The only thing I can come up with as an optimization (which you might already be aware of) is the ability to combine some of the steps without any synchronization barriers between. For example, if you can guarantee that every thread that works on specific areas of the maze in step 4) will be working on the same areas in step 5) you would not need to wait for all the threads to finish step 4) before going on to step 5). The same goes for every step in the algorithm I think, except going from step 5) back to step 2) because you would have to store the current iteration's temporary matrix into the original matrix so that you count the new paths and walls from the walls that are generated from the first iteration. Some very interesting topics that can be observed from this problem is how to properly schedule your GPU to perform this task optimally. By distributing the work to too many threads, the algorithm might perform worse due to how the GPU delegates different tasks to different blocks. Every place where threads have to wait for eachother (referred to as barriers) requires synchronization between threads, and GPUs offer quick communications between threads that are in the same block, which makes it possible to efficiently make use of barriers. But if threads appear in different blocks, the barriers must rely on global memory which may cause the program to run slower due to latency. I am currently taking a master course in low level parallel programming(Sweden, Uppsala University), and using GPUs for parallelization is a very relevant subject in that course. Once I've finished my assignments, and have some spare time over I will absolutely sit down and try to implement your algorithm and see if I can get it to work and maybe come up with some more optimizations that can be done. I am far from a professional in this field, but I am very interested in it since I am a real nerd haha. Let me know if you thought of something that I missed, or if you think I am wrong about something. Thanks for the nice comment! Have a great day.
@@ifroad33 Hi! Wow, I didn't expect a follow-up to be honest, but I really enjoyed your insight, and I'd love to see it implemented when you've got the time. I'm just getting started with GPUs and have barely started getting my hands dirty, so my knowledge was only from theory. With that said, I thought of a way to implement this with bitwise operations (I'm implementing it in python without the gpu operations for the moment), so only boolean matrixes would be necessary and the performance way better. I'm not going to explain everything again, but here's how an iteration would look like, just in case you prefer it i=index : int r=row size : int 1=path 0=wall An outer wall of 0s should be added to speed up the logic and avoid out of bounds exceptions Initial matrix = λ 1=Staring and ending cells 0=Every cell but the starting and ending ones Starting and ending cells-Matrix = Φ A = Left cell (A[i] = λ[i-1]) B = Top cell (B[i] = λ[i-r]) C = Right cell (C[i] = λ[i+1]) D = Bottom cell (D[i] = λ[i+r]) More-than-two-paths-next-to-cell - Matrix = Ω = A(B+C+D)+B(C+D)+CD Resulting Matrix = Π = λ AND Ω OR Φ If Π λ : -> Iterate again(λ=Π) Else return λ
When I fed this into my HAL 2000 computer he said it was a star system in, GN-z11, a high-redshift galaxy found in the constellation Ursa Major. He has plotted a course but I can't get anyone to go with me.
It's interesting that if you take the correct course there's only 8 points where you could make a wrong turn. I thought it would be more for some reason.
I believe this works as a concurrent algorithm, and may be faster in many cases, the same way that Bitonic Sort can also be faster in many cases despite being a less efficient algorithm all in all.
@@piisfun for sure no doubt in that. But.. using two algorithms to "efficiently solve the maze" is kinda not that impressive. Also larger the maze is, more cycles this algorithm would use to "make the maze easier" for other algorithm. Its just waste of calculation cycles in my opinion. Definitely one of the coolest to watch tho. I would like to be proven wrong by comparing calculation cycles between a well known maze solving algorithm vs This + well known maze solving algorithm. (In few different sized mazes) Comparison as in "which method setup accesses(read & write) to the maze cells more than the other in total"
You could totally make this algorithm that way. bool closed = true; while (closed) { closed = false; for(int y = 0; y < num_rows; y++) { for (int x = 0; x < num_columns; x++) { if (maze[y][x].sides() == 3) { maze[y][x].close(); closed = true; }}} Note this would be horribly inefficient, but if you just want to solve small mazes and/or just want get something working that you can check other algorithms against, this wouldn't be too bad.
Flood fill tools used in paint apps work much the same way, only they don't worry if it's a dead end, they just look for identical adjacent squares and fill them in with the selected color. All this is doing is adding a little extra code that visually shows the pruning of the dead ends. Flood fill tools don't care if it's a maze or a space with objects in it or a large open space, they just fill it in until they can't find any more spaces to fill.
It marks all the dead ends, and then moves backwards until it reaches an intersection, where it blocks off that direction in the intersection. By doing this, it prevents the path from going towards the dead end. If a dead end leads to an intersection which had a direction blocked off, that just means the intersection leads to two dead ends, so it continues. What remains is the path. This also works if there are multiple paths.
The algorithm does a pass of all the pixels/blocks in the maze, and it searches for white pixels with 3 adjacent black pixels. When it finds them, it colors the white pixels red. After the initial pass, it goes to every red pixel, turns is black, then checks the neighboring pixels to find a white pixel. It checks to see if that white pixel is adjacent to 3 black pixels, and if it is, it turns that white pixel red. It repeats this until there are no more red pixels.
@@michaelweiske702 ... how does the computer know what the red colour is if it is colourblind and can only see two binary colours; black and white? Do you need a special computer? 🤔
@@wizrom3046 computers are not color blind. Every pixel does not have 1 value, they have 3: R, G, and B. These values vary between 0 and 1 to create every possible hue. 'White' is defined as when the values equal . 'Black' is defined as . 'Red' is defined as . Therefore, if a computer wants to find a 'red' pixel, it just needs to find pixels that have a value of . Edit: some more color examples from this system include: Green: Blue: Yellow: Orange: Violet:
Наука![Maze solving with wall follower algorithm [right-hand rule]](http://i.ytimg.com/vi/vF6gO86RKp4/mqdefault.jpg)
![Maze solving with wall follower algorithm [right-hand rule]](/img/tr.png)
This won't filter out any wrong paths that loop back on themselves though. It will only work an mazes that have a tree-structure.
precisely what I was thinking
True. I think what this would be most useful for is quickly reducing the worst-case search space for a directed DFS like A*. I'd have to see how the performance compares; this seems like iterations of a 3x3 kernel over a matrix, known to be fast and parallelizable. I'd wager this only gives performance gains on extremely large mazes with lots of loop-backs; A* tends to be very efficient out-of-the-box.
@@mikechurvis9995 as we saw in the video, it can be very linear and slow in the end if we have a long dead end. maybe we could use some kind of hybrid approach where both the search and the dead-end elimination are done in parallel, so we aren’t forced to wait for those.
btw, if we have unlimited parallelism isn’t dijkstra’s algorithm as fast as A*? but maybe it’s harder to parallelize than the dead-end elimination?
maybe another alternative would be to simply limit the number of iterations before switching to A*, either by a fixed number based on the size of the maze or by a limit on the minimum number of dead ends
It only claims to BE a dead-end filler 🙂
True but it's a very simple algorithm, and the additions necessary to detect and fill dead-end-loops would be simple too.
Wonder what it would look like with multiple working paths.
I think it would fully preserve them with nothing extra. If you wanted to get the shortest path you could breadth first search after getting all the working paths, and then whichever path reaches first, you can trim the rest.
Multiple good paths? Was exactly what I wondered. Since only dead ends are removed, right up till they hit a 3-4 junction, the multiple paths would be preserved.
Then the A-B travel would have to chose from the multiple paths but this is not implemented.
Since the multiple paths are all valid, itmwould still travel from A to B just fine, but there is no mechanism to determine the best of multiple paths, nor choosemthe best path...
I do like this algorithm because it doesnt need to be recursive, it could even be done sequentially instead of simultaneously as seen in the video. That means it can be done with an incredibly simple, and reliable, tiny bit of code.
Since this algorithm just trims off the dead ends, and working paths are the only ones which are ultimately not dead ends, they would all be preserved.
@@brandonallen2301 You can still do that without trimming the dead ends, though.
@@brandonallen2301 22²22222²22222221111111222222222222222²2222222222222²²22²2222²²222222222222222222²2²²222222222222222222222222222222222²²222ww area WW2 ww was a ass wàwww ass wwwww a áwwwww see ãwàw was wwwwwwwwwwww ass wáw saw2222222222222²²²²222222222222222222222²2222222222222222222222⅔wwwww we wwwwww3w3 wew was wewa33aw www we 3w3 was awa
This algorithm can be implemented as a celular automaton.
4 states: endpoint, path, deadend, black.
Neighbor: von neumann
Rule: path with one or zero neighboring path and not near to any endpoints becomes a deadend.
Or just use a 2x2 square of path for the endpoints and you can simplify it down a bit more.
@@Pystro I want to preserve the looks of the maze, though. Strictly speaking, only two states are necessary, which can be expressed with B/S234V in Golly's notation
All algorithms can be implemented as a cellular automation
If there are multiple paths this algorithm would break.
2 rules are necessary :
-if the cell is black, it stays black
-if a cell is adjacent to 3 black cells, the cell become black
So basically, going left at the start instead of straight is a single move that would cost everything
What maze do you start from the bottom right in? English is read left to read top to down, mazes are designed following that rule.
@@drakebalzer2098 they're referring to the perspective when you enter the maze from the top left
@@drakebalzer2098 you don't solve mazes from the end?
And a right-hand turn towards the end would take you on another journey the wrong way.
Started off interesting but the plot kinda slowed down towards the end of the second act.
I don't care if this is not the most efficient or not this is by far the most satisfying
I must admit this is an algorithm I haven't seen before, and I've seen a lot of algorithms about mazes.
It's one I came up with as a child
@@Vextrove I was going to say the same thing. It's how I solved mazes as a 10 year old. Color in the dead ends until you reach a T intersection that hasn't been colored in. Of course, as a human you can periodically look to see if the solution has become clear before you finish coloring it all in. It actually made mazes too easy and uninteresting.
@@oldguydoesstuff120 Yeah. I did it to bide my time during boring parts of my life
I never thought about it, but filling in dead-ends, even if only partially, is a much more consistent way of solving mazes than just trial and error.
I always did it with a pencil myself lol.
but it knows when to stop and not interfere with the correct route which we would not know how to do.
@@obscurereference6298 Well we can start by filling our way from the simple ends to the bigger ones. We just can't do it as quickly as the AI can.
@@obscurereference6298 No, the algorithm stops at intersections!
@@obscurereference6298 "but it knows when to stop and not interfere with the correct route which we would not know how to do."
We can recognize any dead space by looking around it. Any space that's not the entrance or exit is a dead end if it doesn't have at least two open spaces next to it. Watch carefully and see which spaces it blocks off every time.
Those are massive offshoots, this is one evil maze.
1:18 = Awesome, they FINALLY fixed the soda machine. Time for some Sprite.
The definition of knowing where to go by knowing where not to go. Neat algorithm though.
the missile knows where it is becuase it knows where it isnt
@@wizardbrandon3544 The missile knows where it is at all times. It knows this because it knows where it isn't. By subtracting where it is from where it isn't, or where it isn't from where it is (whichever is greater), it obtains a difference, or deviation. The guidance subsystem uses deviations to generate corrective commands to drive the missile from a position where it is to a position where it isn't, and arriving at a position where it wasn't, it now is. Consequently, the position where it is, is now the position that it wasn't, and it follows that the position that it was, is now the position that it isn't.
In the event that the position that it is in is not the position that it wasn't, the system has acquired a variation, the variation being the difference between where the missile is, and where it wasn't. If variation is considered to be a significant factor, it too may be corrected by the GEA. However, the missile must also know where it was.
The missile guidance computer scenario works as follows. Because a variation has modified some of the information the missile has obtained, it is not sure just where it is. However, it is sure where it isn't, within reason, and it knows where it was. It now subtracts where it should be from where it wasn't, or vice-versa, and by differentiating this from the algebraic sum of where it shouldn't be, and where it was, it is able to obtain the deviation and its variation, which is called error.
Congrats to this creative approach! It is specialized for dense mazes of limited, rectangular size on a regular, square grid.
I think you can use this algorithm for multi-path mazes with some small modifications: a) Find and store all branches b) While filling dead-ends, stop at the first branch.
In the remaining maze you could choose the shortest path (avoiding loops). Cost-wise, you still have square complexity of the initial dead-end scan.
I was kind of expecting a jump scare scream at the end lol
This is the hardest maze I've ever tried to solve, usually I solve mazes with just my eyes but damn this maze confuses my eyes like an optical illusion.
If Jack Torrence had access to this technology, Danny would be a goner...
Having visibility of the whole maze to find the ends is quite the luxury of course.
Omg the designer of this maze is so evil. The fact that the very first path has a 50/50 chance of leading you on the most elaborate dead end the world has ever seen is insane 😂 Even solving from the end first, there’s a huge elaborate dead end not too far from the end either 😅
its a random generated maze most likely where only one path leads to the end.
I bet there's a talking worm at the beginning who will be all too happy to send you the wrong way because you phrased your question wrong.
This doesn't make the Jerma teacher noise. B-tier algorithm.
also helps when making mazes as to check if they have multiple solutions :]
That is very cool!
What optimizing is done on the pass-handling? I assume it runs through pr row or column unless run on a parallel processing architecture?
Once there is no more dead ends on a row there will not ever be until the row above or below have been changed so it can be skipped.
It looks like once you find the initial set of dead ends, you only have to check if the cells around the current dead ends are now dead ends. I.e., each step involves trimming off the dead end, finding the single adjacent cell that was open, and marking that as a new dead end. No need to scan the entire maze once you've done the first scan. Just track where the dead ends are.
Is this visual ASMR that people have been telling me about..? I never understood slime or carvings... but this: this is art.
This is funny. Back in college in 1980, I was on a programming team competing with a bunch of teams in the midwest. Four programmers, Four problems, Four hours, and ForTran. One of the problems was to find a path through a maze like this. Everyone at the contest knew mazes were solved via recursion but ForTran IV doesn't support it. The students tackling the problem were all trying to implement their own form of recursion. After the contest was over and nobody solved that one, I took a look at it and slapped my forehead. I saw this fill-in algorithm immediately. Could have coded it in 10 minutes. Ah, well, we came in fourth behind 3 teams of grad students, so we didn't feel too bad.
I've seen mazes filled with gas in a simulation as the dead ends would back pressure and solve the maze
The algorithm was cool, but I did not expect the maze to fall apart like that
this is how I solve the mazes that would be a part of the kids menus at restaurants lol
Use one color to figure out the correct path, and every dead end I find gets filled in with a different color (usually red and green like in the video lol)
Sometimes I'll buy a variety puzzle magazine and I'll work out the mazes this way. It's very relaxing!
This is amazing. Thanks for sharing!
this is way better then dfs, thanks
Limitation of this algorithm is, that the computer needs the "full picture" to apply the algorithm. It's not like a "mouse" which has only a subjective view and needs to optimize its algorithm from "inside" of the maze.
Solving a model, not a problem
3 mandalorians are stuck in a maze. 2 of them are arguing with each other. “This is the way” “No, this is the way” they keep saying to each other. Then the third flies up and out of the maze with his jetpack. “No that’s the way” the second says to the first
It's like a Castlevania map is getting erased.
When you can’t solve the cereal box maze
Weirdly I thought there was going to be a jumpscare at the end
AAAAAAAAAAAAAAAAAAAARHG!!!!!!
This video made me anxious as fuck.
simple explanation: you cut off paths to a dead end. Up to when there are 2 or more branches that would be a choice.
Imagine doing this maze and being on that one long dead end
If you cannot see the top-down layout of the maze, you are back to guessing or “always turning left”. This algorithm could be useful after the first run to make the next pnes more effective.
That’s pretty similar to how I solve puzzles irl. Is it considered efficient? I think I use a combination of this method, the trick about the right most path (when applicable), and segmenting the puzzle so large swaths of it can be ignored all at once, but for a computer that might technically be less efficient.
answer me this immediatly, goddess of mazes: how do you come up with these magic maze solving tricks?
Great work
This is how I used to solve mazes. I'd take a pencil and carefully black out all the dead ends. It was much more satisfying that way.
Yeaah I was a weird kid.
You are still weird.
I'm sorry to tell you this, but you are actually a robot with this algorithm implemented to your AI.
Clever, not weird.
But the best kind of weird kid, we would've had a lot of fun as weird kids with mazes together haha
That was beautiful
I get that this was slowed down for animation purposes, so how does it compare to the depth first search algorithm?
Hey Vsauce, Micheal here. How in the he-
Btw I am programmer. This is easy to make but challenging to come up with.
The missle knows where it is.. by knowing where it isn't
could you have an algorithm that checks for forks and dead ends, then do something like filling the path between dead ends and the closest fork, then start over and repeat?
In O() notation what’s the runtime complexity given and nxn maze?
who else thought that the white stuff were walls?
No that wouldn’t make sense considering the layout
@@DreadEnder some people think diffrent
@@drjvoices no I mean if the white was walls then it wouldn’t make sense because some black parts make islands which wouldn’t make sense if it was a path
@@DreadEnder I'm talking at in first glance
@@gideon_kang1 alright
It turned into a Castlevania map
This is how I pictured it going from the title. My question is that once all of the dead ends are detected, does the program scan the entire maze again for new dead ends or did it map the dead end points and then start making decisions for only those points of interest. The first would be a shorter code but more steps. The longer code should be less steps.
From the first 20 seconds of the video, it looks like the algorithm tries to find all the dead ends first, then parses back from them until it reaches a white square that is bordered by 2+ white squares.
I guess the question is how it compares to A* and JPS
Is there a 4k HD version of this?
I get that this is illustrative, but every branch choice should be held in a tree and the branch elided when a dead end is reached, no need to backtrace. Also scanning the maze for dead ends is not a benefit as you must still walk the maze to get the connectivity so you might as well walk the maze and discover the dead ends as you go and pop back to the branching point.
I can't look at maze videos on the internet without thinking that there's gonna be a screamer popping up 😬
Could you make it so each of the dead ends fill in a different color
Inside my head I was going..."wonka, wonka, wonka, wonka"
Is it faster than always taking right turns?
i love coding and i love algorythms; this makes me want to make one of my own. i wonder if there's a faster approach?
one problem with this approach is that it struggles with loops. so that would be a nice challenge to try to solve
A* is a million times better
Seems slow, but I guess the upside is that it can be done in parallel, so no matter how large the maze is, you can always just throw more threads at it.
Sounds possible, but there would be a lot of overhead due to synchronization issues. If a dead end branches out to two dead ends, then those two dead ends would meet up and only one of the threads are going to continue from that point. I think OpenMP's tasks implementation would be great for such a problem, but I am unsure if you would actually see any speedup when using huge numbers of threads.
Vastly easier for an organic brain as well.
@@ifroad33 Yeah, I think thinking of the maze as a matrix and using a gpu would be better in this case.
Basically, you would:
1) Create a matrix with 0 for walls, 1 for paths and 2 for the starting and ending cell.
2) Then, you would add the surrounding values (paths) for a new (temporary) matrix, not adding the original value of the cell in question.
3) Once you do this, substract 1 for each value.
4) Multiply the matrix with the original one. Any value that's 0 is now a wall, any other value is a path.
5) Finally, set every cell that's not 0 to 1, and the starting and ending cells to 2, and compare the new matrix to the old one . If they are the same, end the task. If not, repeat from step 2
This was a fun problem! If you read this, please tell me if you find any improvements/flaws with my process.
Anyway, have a nice day!
Edit: I've found a problem -> The starting and ending cells shouldn't be 2. Instead, we should make their values = 1 after each iteration, before returning the matrix
@@lombas3185
The only thing with the algorithm I can see is wrong is step 3) where you want to perform matrix multiplication. I know what you are referring to, because you are trying to multiply each separate value from the temporary matrix, with the values in the original matrix. But matrix multiplication refers to another operation which works a bit differently.
The only thing I can come up with as an optimization (which you might already be aware of) is the ability to combine some of the steps without any synchronization barriers between. For example, if you can guarantee that every thread that works on specific areas of the maze in step 4) will be working on the same areas in step 5) you would not need to wait for all the threads to finish step 4) before going on to step 5). The same goes for every step in the algorithm I think, except going from step 5) back to step 2) because you would have to store the current iteration's temporary matrix into the original matrix so that you count the new paths and walls from the walls that are generated from the first iteration.
Some very interesting topics that can be observed from this problem is how to properly schedule your GPU to perform this task optimally. By distributing the work to too many threads, the algorithm might perform worse due to how the GPU delegates different tasks to different blocks. Every place where threads have to wait for eachother (referred to as barriers) requires synchronization between threads, and GPUs offer quick communications between threads that are in the same block, which makes it possible to efficiently make use of barriers. But if threads appear in different blocks, the barriers must rely on global memory which may cause the program to run slower due to latency.
I am currently taking a master course in low level parallel programming(Sweden, Uppsala University), and using GPUs for parallelization is a very relevant subject in that course. Once I've finished my assignments, and have some spare time over I will absolutely sit down and try to implement your algorithm and see if I can get it to work and maybe come up with some more optimizations that can be done. I am far from a professional in this field, but I am very interested in it since I am a real nerd haha.
Let me know if you thought of something that I missed, or if you think I am wrong about something. Thanks for the nice comment! Have a great day.
@@ifroad33 Hi! Wow, I didn't expect a follow-up to be honest, but I really enjoyed your insight, and I'd love to see it implemented when you've got the time. I'm just getting started with GPUs and have barely started getting my hands dirty, so my knowledge was only from theory.
With that said, I thought of a way to implement this with bitwise operations (I'm implementing it in python without the gpu operations for the moment), so only boolean matrixes would be necessary and the performance way better. I'm not going to explain everything again, but here's how an iteration would look like, just in case you prefer it
i=index : int
r=row size : int
1=path
0=wall
An outer wall of 0s should be added to speed up the logic and avoid out of bounds exceptions
Initial matrix = λ
1=Staring and ending cells
0=Every cell but the starting and ending ones
Starting and ending cells-Matrix = Φ
A = Left cell (A[i] = λ[i-1])
B = Top cell (B[i] = λ[i-r])
C = Right cell (C[i] = λ[i+1])
D = Bottom cell (D[i] = λ[i+r])
More-than-two-paths-next-to-cell - Matrix = Ω = A(B+C+D)+B(C+D)+CD
Resulting Matrix = Π = λ AND Ω OR Φ
If Π λ :
-> Iterate again(λ=Π)
Else return λ
bro, one left turn at the begining and your like fucked for a good day if it was a real maze
You gotta trick those "left hand wall rule" smartasses.
But points lost for not tricking the right hand rule guys too...
@@wizrom3046 But the second longest path is on the right hand wall
@@kalahatze hahaha youre right of course! 👍
0:05 1:18 keep clicking these 2 timestamps one at a time
Beautiful! 😀
if you took the first left 💀
Oh Jesus, you would of been stuck in that maze for life if it was real
When I fed this into my HAL 2000 computer he said it was a star system in, GN-z11, a high-redshift galaxy found in the constellation Ursa Major. He has plotted a course but I can't get anyone to go with me.
When double tapping on phone (to go backwards or forwards), you can see original maze
It’s really interesting to think that no space in a maze matters except for the one path from start to finish.
it's like doing every possible wrong until you make it right. Sounds like edison...
The very first turn of this maze goes to the furthest dead end. Just mean.
I remember doing this exact same thing on mazes when I was, like, 6
It's isn't to hard too escape this maze but you should always remember the paths
It's interesting that if you take the correct course there's only 8 points where you could make a wrong turn. I thought it would be more for some reason.
Crazy how I solved it in less than a minute.
Not efficient but very cool to watch!
I believe this works as a concurrent algorithm, and may be faster in many cases, the same way that Bitonic Sort can also be faster in many cases despite being a less efficient algorithm all in all.
@@XerosOfficial i doubt. This algorithm "requires" to collapse almost every single cell to decide where to go.
@@piisfun for sure no doubt in that. But.. using two algorithms to "efficiently solve the maze" is kinda not that impressive. Also larger the maze is, more cycles this algorithm would use to "make the maze easier" for other algorithm. Its just waste of calculation cycles in my opinion. Definitely one of the coolest to watch tho.
I would like to be proven wrong by comparing calculation cycles between a well known maze solving algorithm vs This + well known maze solving algorithm. (In few different sized mazes)
Comparison as in "which method setup accesses(read & write) to the maze cells more than the other in total"
Awesome!
what language do you use?
C++, you can view the GitHub page
So amazing...
wow amazing!
that's a-maze-ing
Dang that’s cool :D
Can you get it to play minesweeper yet?
Is this a new windows 95 screensaver?
Amazing.
this project is a very simple concept with a difficult implementation
if (sides == 3) close
You could totally make this algorithm that way.
bool closed = true;
while (closed) {
closed = false;
for(int y = 0; y < num_rows; y++) {
for (int x = 0; x < num_columns; x++) {
if (maze[y][x].sides() == 3) {
maze[y][x].close();
closed = true;
}}}
Note this would be horribly inefficient, but if you just want to solve small mazes and/or just want get something working that you can check other algorithms against, this wouldn't be too bad.
This was nice
Oddly satisfying but could look better if it started pathing as it backed deadends
NEAT. I've only ever used A-star.
Which you should, this is most likely much slower than A*
@@empireempire3545 Thank you, that answers my next question: Should we run this first on maps to exclude tiles BEFORE doing path finding 🙂
Flood fill tools used in paint apps work much the same way, only they don't worry if it's a dead end, they just look for identical adjacent squares and fill them in with the selected color. All this is doing is adding a little extra code that visually shows the pruning of the dead ends. Flood fill tools don't care if it's a maze or a space with objects in it or a large open space, they just fill it in until they can't find any more spaces to fill.
Holly sht. For you know, i throught that would be screamer in the end of the video
Is it mandatory to use algorithms to find the exit? I found it in 6 seconds without using algorithms
I like the stupidity of this question
Is this how we terraform mars
This is an easy maze. Just always go right and down. You'll get there asap
Literally the first step going right is wrong
@@Uuugggg but the down is correct XD
My brain when playing pacman but 1000x faster and in realtine
I need further explanation
It marks all the dead ends, and then moves backwards until it reaches an intersection, where it blocks off that direction in the intersection. By doing this, it prevents the path from going towards the dead end. If a dead end leads to an intersection which had a direction blocked off, that just means the intersection leads to two dead ends, so it continues. What remains is the path. This also works if there are multiple paths.
snek
The algorithm does a pass of all the pixels/blocks in the maze, and it searches for white pixels with 3 adjacent black pixels. When it finds them, it colors the white pixels red. After the initial pass, it goes to every red pixel, turns is black, then checks the neighboring pixels to find a white pixel. It checks to see if that white pixel is adjacent to 3 black pixels, and if it is, it turns that white pixel red. It repeats this until there are no more red pixels.
@@michaelweiske702 ... how does the computer know what the red colour is if it is colourblind and can only see two binary colours; black and white?
Do you need a special computer? 🤔
@@wizrom3046 computers are not color blind. Every pixel does not have 1 value, they have 3: R, G, and B. These values vary between 0 and 1 to create every possible hue. 'White' is defined as when the values equal . 'Black' is defined as . 'Red' is defined as . Therefore, if a computer wants to find a 'red' pixel, it just needs to find pixels that have a value of .
Edit: some more color examples from this system include:
Green:
Blue:
Yellow:
Orange:
Violet:
WOw I would have given up a long time ago.
I used to do this with pencil :)
So humans never need to think for themselves ever again.
why did this make me feel sad?
me tricking the algorithm by making some dead ends double thick
0:35 There are now only 2 dead ends. Why isn't the algorithm speeding up?