This may be obvious but still fun fact: each endpoint is the same taxicab distance away from the origin so essentially you’re just using an expanding circular radar scanning up a tree
From the video is not noticeable but Dijkstra is not something we are doing in real life, we are more likely to make A*, because Dijkstra is a greedy algorithm and it would spread in all directions, and I doubt a person could track more than 2-3 paths at once
@@MoldovaStandsWithUkraine I mean yeah, obv I’m not an AI /lh. I can understand and respect that an algorithm is different than me, I was just joking that on the surface my strategy is similar
That would be depth first traversal, dijsktra's algorithm uses a modified breadth first traversal method. Depth first would go down a certain path until reaching a dead end, after which it would backtrack and continue with the next path. Which is similar to the left/right hand rule. Breadth first traversal goes down every possible branch at once, like this one.
It's not following the color back. Each time an "end" expands the path, the new segment marks which neighbor came to it. Backtracking is just a matter of going back through these previous neighbors until you get to the start. In the event a board has loops and there's maybe weights for going down certain paths, you can also store how much the current neighbor cost to get to and how much it costs to go to the next neighbor. Compare the values and keep the cheapest. Coloring the paths as they expand is likely just cosmetic in this case (incrementing an RGB or HSL value is pretty trivial).
Think of it as following a series of numbers. All squares start off as either 'start', 'end', 'wall' or 'empty'. From the 'start' square all adjacent 'empty' squares are labeled as '1'. From there it checks every empty square next to '1', and puts a '2' in them. It then checks all empty squares next to '2', and puts a 3 in them, aso. If there are two possible options for a square, then it becomes 1 higher than the lower of the two (so if one adjacent square is 16 and the other is 20, then the empty square becomes 17). Eventually it gets to the square marked 'end'. From 'end', it selects the non-'empty' square with the lowest number in it, changes that to 'path'. From that 'path' square it then finds the adjacent non-empty square with the lowest number next to it. That one is changed to path, and the process is repeated until it gets back to the start. That selection of squares labeled 'path' is the shortest route.
Breadth first search is used to find the exit. Dijkstra's method is later used to find the shortest path. Though by the coloring of the process I can only guess it calculates the shortest path to any intersection while doing the BFS which is in essence Dijkstra's algorithm and it's only fair it may be confusing. The two algorithms have different objectives.
Although this would find the most efficient path in any given maze, it would require a lot of computational power for all of those wasted routes and probably there’s a more efficient system out there that does the same thing
@@zecuse note that A* requires a useful underlying metric field. On an arbitrary graph with no such known structure it cannot be used properly, reducing to Dijkstra's, and I am doubtful that a better algorithm exists in such a case.
The nice part is that it doesn't use those wasted routes for longer than the maze length is. For example if the correct path is 100 squares long, then the different paths it is checking will be at most 100 squares long. Compare that to left or right-hand paths that can exceed 100 squares in length due to dead-ends. It also allows for lots of multi-threading as each separate path it is following can have its own run-time instead of needing to be confined to the single left or right-hand path. Even left or right-hand path maze-solving can only be double-threaded, where one thread follows the left-hand path, and the other the right-hand path.
no, A* is better for this. it only looks into Paths that get it closer to the Destination/exit. at 0:13 A* it would not branch to the left for example.
@@unitrader403 But you miss the point of this method. It goes down all branches it comes across. So it literally goes down the correct path from the very beginning. The only way you could get more effective is if it moved faster.
@@lewismackay9533 A* is faster because you can only place one square/pixel per loop of the algorithm. Dijkstra unnecesarily goes into paths wich go away from the exit and therefore waste time/cycles placing pixels that go away from the exit, A* will ignore these but otherwise behave the same.
oh, and this explaination is based on how it is visualized here. i am aware that both actually dont work with a grid internally but rather on a network of nodes.
@@unitrader403 In any case A* would be faster than Dijkstra’s First Dijkstra’s algorithm is a greedy algorithm So it just exhaustively searches the path Secondly A* would not continue searching paths that leads the pivot further from the target as it happens in Dijkstra’s algorithm Hence, it will save iterations to explore the right paths However, A* need a good heuristic function (an approximation value that tells how close the node is to the target) On a plain it is very easy because we use coordinates But on an abstract network it needs more implication
If I had to guess based on the fact that the color is a gradient throughout a single edge and that this maze is laid out on a discrete (x, y) grid, each cell of the grid could be given the value 1 and the weight of the edge could be simply the sum of the number of cells on the edge, i.e. the length of that portion of the maze. That being said, I would think a more efficient way of doing it could be to weight all the edges the same because we're not so concerned with the shortest path itself but rather the correct one and once it finds the end it the search halts. I'm just thinking aloud though, I'm still just a beginner. But now that I'm thinking about it, is this technically Dijkstra's algorithm? I think the one guy might be right and this is just a breadthfirst search, since it's searching all possible paths in parallel 🤷♂️
@@_Mute_ Every time the algorithm encounters a new cell, it checks if adding that cell will give the next shortest path from the beginning. Not necessary the shortest weight edge available
with dislocated blocks when or whatever it was called i forgor. basically maze with blocks, unreachable to hand/left hand rule edit: Its called disjointed mazes
u can do better algorithm. first what you need to know is position of start and the end, and if u ll fall to the wall from start and between your hit of the wall and between start is no finish that means ur not supposed to go there... somethin like this A = start C = Finish and B = hit to the wall If there is no C between B and A then you shouldnt go even in this place where u have a lot of ways that u know u ll not go there
So the longer the continuous line , the darker the colour gets right? It looks like it’s just brute force - send a line down every path and see which one makes it
In a maze environmentally is nothing than Brute Force. A Breadth-First Search would do the same. Also, Dijkstra’s algorithm is a greedy algorithm, so brute forcing is the method for it.
Distance from the entrance. Remembering that is needed to find the way back once you've found the exit, and also guarantees the path you find is the shortest one.
This may be obvious but still fun fact: each endpoint is the same taxicab distance away from the origin so essentially you’re just using an expanding circular radar scanning up a tree
what flag is in your name ?
Wrong
Wow, good work. Never knew that this witcher character is so good in mazes.
This is my favorite method irl. Just go down every possible path until you find the one that works
From the video is not noticeable but Dijkstra is not something we are doing in real life, we are more likely to make A*, because Dijkstra is a greedy algorithm and it would spread in all directions, and I doubt a person could track more than 2-3 paths at once
@@MoldovaStandsWithUkraine I mean yeah, obv I’m not an AI /lh. I can understand and respect that an algorithm is different than me, I was just joking that on the surface my strategy is similar
That would be depth first traversal, dijsktra's algorithm uses a modified breadth first traversal method.
Depth first would go down a certain path until reaching a dead end, after which it would backtrack and continue with the next path. Which is similar to the left/right hand rule.
Breadth first traversal goes down every possible branch at once, like this one.
So it looks like it branches out until it reaches the end, the. It follows the lightest color back. Did I get it?
It's not following the color back. Each time an "end" expands the path, the new segment marks which neighbor came to it. Backtracking is just a matter of going back through these previous neighbors until you get to the start. In the event a board has loops and there's maybe weights for going down certain paths, you can also store how much the current neighbor cost to get to and how much it costs to go to the next neighbor. Compare the values and keep the cheapest. Coloring the paths as they expand is likely just cosmetic in this case (incrementing an RGB or HSL value is pretty trivial).
Think of it as following a series of numbers. All squares start off as either 'start', 'end', 'wall' or 'empty'. From the 'start' square all adjacent 'empty' squares are labeled as '1'. From there it checks every empty square next to '1', and puts a '2' in them. It then checks all empty squares next to '2', and puts a 3 in them, aso. If there are two possible options for a square, then it becomes 1 higher than the lower of the two (so if one adjacent square is 16 and the other is 20, then the empty square becomes 17).
Eventually it gets to the square marked 'end'. From 'end', it selects the non-'empty' square with the lowest number in it, changes that to 'path'. From that 'path' square it then finds the adjacent non-empty square with the lowest number next to it. That one is changed to path, and the process is repeated until it gets back to the start. That selection of squares labeled 'path' is the shortest route.
This algorythm is better than hand one because it explores whole maze once in the worst scenario.
Wait this is just breadth first search
Look more carefully
@@dented42 what am i looking for?
they're definitely very similar
Djikstra’s algorithm works only slightly differently from bfs. It’s more different on an actual graph where edges have different weights I think.
Breadth first search is used to find the exit. Dijkstra's method is later used to find the shortest path. Though by the coloring of the process I can only guess it calculates the shortest path to any intersection while doing the BFS which is in essence Dijkstra's algorithm and it's only fair it may be confusing. The two algorithms have different objectives.
ahh the favorite algorithm of network engineers
Although this would find the most efficient path in any given maze, it would require a lot of computational power for all of those wasted routes and probably there’s a more efficient system out there that does the same thing
A* (a-star) attempts to do just that by using a heuristic to predict which current known routes would get you closer to the goal.
@@zecuse note that A* requires a useful underlying metric field. On an arbitrary graph with no such known structure it cannot be used properly, reducing to Dijkstra's, and I am doubtful that a better algorithm exists in such a case.
The nice part is that it doesn't use those wasted routes for longer than the maze length is. For example if the correct path is 100 squares long, then the different paths it is checking will be at most 100 squares long. Compare that to left or right-hand paths that can exceed 100 squares in length due to dead-ends. It also allows for lots of multi-threading as each separate path it is following can have its own run-time instead of needing to be confined to the single left or right-hand path. Even left or right-hand path maze-solving can only be double-threaded, where one thread follows the left-hand path, and the other the right-hand path.
I'm quite positive I understood this.
I’m watching this instead of sleeping
This is the most effective method since it essentially goes down the correct path from the start.
no, A* is better for this. it only looks into Paths that get it closer to the Destination/exit. at 0:13 A* it would not branch to the left for example.
@@unitrader403 But you miss the point of this method. It goes down all branches it comes across. So it literally goes down the correct path from the very beginning. The only way you could get more effective is if it moved faster.
@@lewismackay9533 A* is faster because you can only place one square/pixel per loop of the algorithm. Dijkstra unnecesarily goes into paths wich go away from the exit and therefore waste time/cycles placing pixels that go away from the exit, A* will ignore these but otherwise behave the same.
oh, and this explaination is based on how it is visualized here. i am aware that both actually dont work with a grid internally but rather on a network of nodes.
@@unitrader403
In any case A* would be faster than Dijkstra’s
First
Dijkstra’s algorithm is a greedy algorithm
So it just exhaustively searches the path
Secondly
A* would not continue searching paths that leads the pivot further from the target as it happens in Dijkstra’s algorithm
Hence, it will save iterations to explore the right paths
However, A* need a good heuristic function (an approximation value that tells how close the node is to the target)
On a plain it is very easy because we use coordinates
But on an abstract network it needs more implication
you are amazing, I am using this method to but I wasnt knowing the name lol.
It looks vaguely like a sunset.
how are edges weighed here?
If I had to guess based on the fact that the color is a gradient throughout a single edge and that this maze is laid out on a discrete (x, y) grid, each cell of the grid could be given the value 1 and the weight of the edge could be simply the sum of the number of cells on the edge, i.e. the length of that portion of the maze.
That being said, I would think a more efficient way of doing it could be to weight all the edges the same because we're not so concerned with the shortest path itself but rather the correct one and once it finds the end it the search halts. I'm just thinking aloud though, I'm still just a beginner.
But now that I'm thinking about it, is this technically Dijkstra's algorithm? I think the one guy might be right and this is just a breadthfirst search, since it's searching all possible paths in parallel 🤷♂️
@@_Mute_ the algorithm uses breadth first to find the exit, and then dsiktra's to find the shortest path
@@olixx1213 Ah I see. So at every intersection it will proceed to the cell with the lowest weight which is just distance away from the start, yes?
@@_Mute_ Every time the algorithm encounters a new cell, it checks if adding that cell will give the next shortest path from the beginning. Not necessary the shortest weight edge available
with dislocated blocks when
or whatever it was called i forgor.
basically maze with blocks, unreachable to hand/left hand rule
edit: Its called disjointed mazes
Look closer at 0:25 ...
It's not a disjointed maze, every area is reachable. The algorithm solved it without having to test every branch.
@@southernflatland Nono, im asking a video about an AI solving disjointed mazes when
Grand Theft Auto algorithm
Bisexual algorithm
The algorithm loves ‘em all!
hell to the yeah
Lol
u can do better algorithm. first what you need to know is position of start and the end, and if u ll fall to the wall from start and between your hit of the wall and between start is no finish that means ur not supposed to go there... somethin like this A = start C = Finish and B = hit to the wall If there is no C between B and A then you shouldnt go even in this place where u have a lot of ways that u know u ll not go there
cause non of those ways would lead to finish
So the longer the continuous line , the darker the colour gets right?
It looks like it’s just brute force - send a line down every path and see which one makes it
In a maze environmentally is nothing than Brute Force. A Breadth-First Search would do the same.
Also, Dijkstra’s algorithm is a greedy algorithm, so brute forcing is the method for it.
Is it any less brute force than right-hand rule? That’s just “I’m going to run along this whole wall really fast”
bisexual maze solving
Best way to solve a maze is to solve it backwards. I solved in 30 seconds
What does the color change indicate?
Distance from the entrance. Remembering that is needed to find the way back once you've found the exit, and also guarantees the path you find is the shortest one.
Each time the tracker divides, it changes its colour, so that it can backtrack its way by following the different colours
222 s
amazing. anyone has djikstra's contact info?
You'll need a ouija board