How about the red dot always being in a corner? This limits the world to a quarter of what it could be. Does that affect all algorhytms tha same? How would each perform if the location of the start ( red dot) were also random?
A more important factor would be the difference between searching in a closed maze vs a large open space with very few walls in which case many A* heuristics can vastly outperform the other algorithms.
@@BlameTaw I disgree, his DFS algorithm was getting an undue boost due to the fact that it is always starting in the SW corner which meant it was unable to search South and West first. Particularly think of if the starting dot was in the middle and the end was to the NE of it (such as the example given at 1:28)
The difference between Dijkstra and BFS is that Dijkstra can handle distances of different length. Since the distance between two adjacent cells is always 1 in your maze, these 2 will be basically the same every time.
I followed a path finding course 3 years ago, and we called that the cost to explore the node. In these mazes, there's only 1 solution, and each square has the same cost (1). There are some cases where there the shortest path isn't the cheaper path, and Djikstra as well as A* take both the distance and the cost. A good example of this scenario is google map's Directions API, where the cost is the estimated time to go from the point A to the point B.
In its most basic form, yes. The big thing with Dijkstra is that you can modify how it prioritizes the edges that it processes.. If you use Manhattan distance, it's gonna be a slower BFS that follows the same paths (since priority queues are slower than regular queues), but if you use something like Euclidian distance, Dijkstra will select slightly different paths. Especially for mazes like these though, they're not gonna be _that_ different. Not exactly the same, but pretty damn similar.
@@fotnite_ Djikstra’s + a heuristic is just A* is it not? Its not usually called Djikstra’s algorithm once you start using Manhattan or Euclidian distance, since at that point you’ve given it a heuristic and its now A*.
@@-Burb Not necessarily. A* requires that the heuristic be some representation of the cost to get to the goal, but that's not what I'm describing, which was using Euclidean distance from the start node. If I were using Euclidean distance from the goal node, then it would be A*.
A* is being heavily favored here due to how you generate mazes randomly. Your mazes are too "open" meaning that the correct way to the target is always a relatively straight line (notice how there are no zigzags or steep turns one after another, on the final paths). A* excels in these cases due to its usage of the Manhattan distance, and, while A* tends to indeed be the best algorithm, it performs poorly in scenarios where the best path requires you to first move away from the target. Other than that, nice video!
Plus it's the only one in the comparison for which you need to know the location of the target beforehand, the other three work fine w/o this info. Because those are searching algorithms meant to search through the whole graph (or at least a connected component). And if you consider the cost of switching branches like you have to physically backtrace your steps and go down on the other path (like in a real-life labirinth or for an automatic vacuumcleaner/lawnmower), suddenly DFS have a helluva big advantage.
A* doesn't necessarily use the Manhattan distance, you can use Euclidean or any other distance that guarantees not to under-estimate the distance remaining.
@@DaveLeCompte if the path is not a relatively straight forward one but constanly winding and rewinding, the Euclidean metric gives also false heuristic about the right path at the crossings.
@@DaveLeCompte yeah, but the main point was that due to the structure of the mazes, this kind of optimistic heuristics are heavily favoured which might not be .the case (or at least not this much) with more diverse maze structures.
When a maze has a single path from point A to point B, it's probably not worth comparing the lengths of the paths that the different algorithms discovered, since they will all discover the same path.
The maze have a single path from start to end. The point A and B are also generated randomly in the maze. So they search which route for each algorithm.
The fact that Dijkstra and BFS get similar result is really easy to understand, because they are basically equivalent in uniform graphs: - Dijkstra's principle is that nodes are added to the expanded monotonously with regard to distance. The search set is therefore always composed of nodes that have distance N or N+1 to the source. Nodes with distance N+2 will only be added to the search set when expanding an N+1 node, which will only happen one all N-distanced nodes have been expanded. - BFS will have the same property, because nodes are expanded from oldest to newest, and since every step only adds N+1-distanced nodes to the search set when expanding an N node, the search set will always be a queue containing N-distance nodes first, and then N+1-distance nodes only. In both cases, when the last N-distance node is expanded, they will have the same search set comprised of exclusively N+1-distanced nodes. They only differ in the ordering in which nodes at the same distance are explored, and their difference in performance is therefore bounded to the number of nodes that share the target's distance with the source. If we add a constraint for Dijkstra to pick the next expanded node deterministically, they will in fact have the exact same average performance.
"Hugging" the left or right wall is very human approach to mazes and for mazes with just one path between each two points this is quite similar to DFS search.
Nah, the moment you notice the maze has “islands”, the “hugging the wall” approach fails. I usually just look at random points until I find a string of points that connect both sides.
@@cezarcatalin1406 Even if it has islands, unless it is also donut shaped with one exit (but not both) on the inside, hugging the wall should still work. Hugging the wall will ensure that you visit every point along the edge on which your starting point lies exactly once, until you either reach the exit or are back where you started.
On another note, wallhugging becomes more useful when pathfiding in a situation where there are ranged attack entities and obstacles cast a "line of sight blocked" range to give them the illusion of height.
@@MrScarabus When you dont know were the exit is is called fog of war. And it is a bit different thing. Here algorithms "know" where exit is so you cannot compare it to "human don't know where exit is".
@@sexcommunist Nor DFS, BFS or Dijkstra know where the exit is. They just checks cell by cell looking for it. Only A* knows and guide itself straight to the exit. Mere humans usually like DSF - grab wall by one hand and follow it. But if you have GPS with exit coords - you are a king - that's how A* fells among other algorithms.
Thing is A* needs to know where the exit is. Also you could craft mazes designed to trap A* (although even with a trap I'm not entirely sure it would be worse than Dijkstra since those will basically always scan everything whatever happens).
If I remember right, of the algorithms, only A* already knows where the destination is. So it has an unfair advantage over the other three. A* doesn't belong in the same family as the other three. This is an apples and oranges comparison. You can see it by looking at how each of the trees grow as they search out the exit. A* is always roughly heading right for the exit. The other three don't, and this is something you can observer over multiple maps that are drawn.
> only A* already knows where the destination is. True. More generally, A* uses a heuristic function, and you can bake complete or partial knowledge about the solution and/or the search space into that heuristic function. What comparing A* to Dijkstra/BFS will tell you is something like "how useful is the extra information". Also (to whom it may concern) A* still performs work even if it already knows where the destination is. Anyone who has moved within a city and needs to go downtown from their new home knows where the destination is, but they don't know the optimal route from their new starting location; there's more to a route than simply knowing where the destination is.
in the type of maze he used, yes it's really good. however if it had a big upside down U shape in it's way, it would get stuck for a VERY long time trying to find it's way out of it. also it's completely fair to compare them to each other, they are all doing a set task (finding a path) and are all algorithms..... it's like trying to say that a horse carriage and a modern super car can't be compared. they most certainly can be as they are of the same category (travel). one is clearly more advanced then the other but that doesn't mean they can't be compared. in some instances it's okay to use the older forms of searching for a path. however in most cases, A* does it just fine if not better on avg and can be easily modified to adapt to anything else that might be needed. also why wouldn't you want to give your algorithm as much information as possible to complete it's task faster?
@@rocksfire4390 There are other algorithms that avoid filling large area such as the U shape you mentioned by following the surface of an obstacle until they are around it. Comand and Conquer used on of those algorithms, though it's quite a primitive variant. They work especially well for maps that aren't a dense maze with walls everywhere (as in the video), but have larger free areas. So they are very suitable for most computer games. An advantage is that they scale better with more tiles, so higher map 'resolution' is not much of a problem.
@Armin Reichert "A* does not "know" where the destination is, it only can estimate the distance to the target. " in order to estimate the distance, it NEEDS to know where the target location is, aka the destination. actually ALL pathfinding needs to know where the destination is......
Knowing the distance to the target tells you that the target lies on a particular circle. Three such circles have an unique intersection thus determining the target. Thus knowing the distance to the target at three points tells you where the target is.
It's not that it's "similar" to BFS. It's that Dijkstra where the cost is always 1 is exactly the same as BFS (perhaps modulo ties). Just like how A* where the heuristic is always 0 is exactly the same as Dijkstra. (And DFS is just useless.)
I could probably write a Dijkstra or A* pathfinder with BFS as an explicit failsafe, among others. You may never know if a malicious graph comes your way.
@@powerhouseofthecell9758 "failsafe" for what, though? A* will find *a* path, it just might not be the best one if the heuristic is bad. But BFS can't look at edge weights at all, so it also won't find the best path, so I don't see what you'd gain from that.
Dfs isn't useless, it's one of the best techniques for tree algorithms. You can easily use DFS to get the distances from the root and then use LCA. Yes, you can also use BFS, but DFS is easier to code in this situation.
@@deepdark8192 Indeed and it's also very close to what people do if they're needing to find their way when lost. Usually, we'll trace the left or right wall rather than expanding in the same direction, but the idea is analogous. It's worked for millennia even without the ability to keep track of large sets of data.
Another good comparison of Manhattan distance that people tend to understand is to compare it to what (I believe?) gave it its name -- think about walking through city blocks. The closest distance to some arbitrary place requires you to walk along a grid of streets, so you can't just find some short diagonal path, because you'd be walking through buildings.
I don't know how many times I've watched this video, but its a lot. Very useful to create code using the steps you provided and check the behavior of my pathfinding implementations compared to yours.
That was great, I'd love to see a similar comparison for cases where there are multiple valid paths, to see how such algorithms can be practically applied for searching quickest paths to destination for example
One application for Djikstra is more efficient is if you have multiple (N) goals. A* would need to search N times whereas Djikstra just needs to search once until all goals are found, then you can pick through the entrails to extract all N optimal paths. Just thought I'd share :)
Adding always 1 to the cost on the Dijkstra algorithm will indeed turn it into a BFS search algorithm. Instead, the cost should be the distance to the destination so that it preferably explores options that are closer to the end node.
I'd say that the random map generation algorithm actually favors that pathfinding algorithm. If say the end goal was near the start, but the right path was something like going really far away and then coming back I'm not sure that path would do it faster, so it depends on the general degree of connections your map gen makes.
To anyone learning this, just remember that the time it takes to find a path can vary depending on the scenario. Eg. an Astar algorithm where there is a right angle wall between the starting node and the end node, can have a higher runtime searching from there, than searching from the end point first, purely bc the end point would reach, and path around the wall earlier than the start Make sure to consider that if you plan to make or use Astar.
There is one thing that was overlooked with this test. The maze was generated and started from the same position, so all paths are essentially a tree branching from the start position so A star has for the most part a straight albeit bent path to its target, this setup heavily favors A star. had the start been in the bottom right and the end being at the top right while the maze is generated from the far left... i dont expect these results would be as good. Though that said, Astar probably isnt designed for mazes but general pathfinding with more open access points between locations. Also this maze isnt so much a normal maze, the paths are all fairly straightforward, real mazes could have you go to the far side and up and then back and move around the middle before going to the exit with many other possibilities all being dead ends. this map is simply generated from the corner and expands outward so there can be NO back paths when the maze is generated. That all said, its clear that Astar is far superior then a "dumb and blind" search that the others use. But Astar also needs to know where its target is. the others dont. Other differences... a human might not know where the exit is.
@Armin Reichert Thats right, the starting position of where the maze generation starts doesnt matter, but the starting position in the maze does matter because this is a flawed maze, if it wernt flawed i dont think it would matter.
@Armin Reichert depends if the branches connect to each other. but as the map is generated it spreads out and goes to the other side of the map, while the paths may not be a straight line, its essentially like having straight lines from the start to finish so its easier for A* to follow that path. If for instance the correct path was a 'straight line' but looped around the back side of the maze and then came back to the front, being "closer" to the exit wouldnt help and would in fact lead it to take other paths. For a simple visual you can think of it as starting a maze at the pointed end of a V and going to the end of either leg, its a straight path from start to finish. if the start was on the top of one leg and went to the other leg, being 'close' to the goal wouldnt help since it actually has to go away from the goal to get further down the correct path.
From what I’ve seen, dijkstra’s algorithm is most efficient when determining the shortest path between every point before the path finding needs to occur, so it’s really good for pathfinding in an unchanging area. I can’t find the video any more but I once saw someone use it to simulate a million particles moving to where the cursor is with no noticeable performance drop as they were simply moving in the direction that djkstra’s algorithm had pre-calculated to be most efficient. (If anyone can find the video I’d be very thankful) Overall though love the video!
That's called a flow field! It calculates the path to a target location from EVERY start location at once, so it's super useful when you have a bunch of entities that want to move to the same location
BFS and Djikstra are essentially the same when the costs/weights of all the edges are equal. Moving from one cell to another in this maze (graph) has the same cost (cost/weight of the edge) which is why their performance is almost equal in this comparison.
This was randomly recommended to me but I was needing it anyways, even though unconventionally. I think I can use the way A* works to visualize an economic circumstance. Whatever, nice vid, have a good one and thank you.
There is also a much simpler and faster algorithm which was used in early RTS games like Dune 2, Warcraft and Doom. It involved casting a ray into the direction of the goal, and if the ray hits an obstacle, they the algorithm either uses a right-hand side rule to go around it or shots a ray into random direction. It isn't guarantee to find the shortest path, but has constant memory usage and usually finds the path faster. You can also run it in parallel by shooting several rays. It also works when you have to navigate an actual drone without a pre-made map.
That's a combination of his mazes have no loops and his search order is top, right, bottom, left, which essentially produces a try up and right first heuristic. He needs to randomize start positions and use multiple systems for generating the mazes.
You omitted a random selection algorithm. It has the capacity to beat both DFS and BFS by avoiding their fixation with one direction. Also how do DFS and BFS if you rotate the start angle?
Astar performed great because this is a very generic maze with dead ends that are uniform distributed and never lead to false path. Would be interesting to watch case when the maze has several false passages lengthing from start to "almost end" but ends in dead ends.
All of these algorithms look at a node and find just the next node. Solving it in your head you can see the whole maze and recognize patterns like seeing a big stretch of empty space as a unit rather than a series of nodes. Also you're able to look from both ends.
At a glance you can tell when a branch is just dead space, by painting that area black it builds a wall of space that no longer needs to be considered. Of course that presumes that the map and red location are known. Can also walk backwards from the red dot in the same manner, assuming this is path finding, not dot finding.
The starting point location is a bit helping DFS. Because it prevents DFS running into a completely wrong direction. And the random mazes were leaning towards DFS also. 12 of the 20 mazes had the goal positioned roughly right of the starting point. The direction that DFS priorizes...
I love mazes!!! I am VERY good at it! The first maze you showed us, i tried to get the way (before the AI tryed it) i finished it in under five seconds :D
A and B could be very close to each other while the linking path could be extreme winded and long. So distance of A and B does not matter at all. Only if there is more than one linking path considering the distance should be taken into account.
your example would give vastly different results if the start point was in the center - DFS was only performed well because the arc was limited to 90 degrees.
The heuristic used in A* doesn't necessarily need to be the Manhattan distance. It works well with regular grid-placed nodes but in real life geometric scenarios the Euclidean distance would be the preferred choice.
There is another simple search algorithm not included. It is the Heuristic Search. On A*, we use both calculated distance from parent + heuristic distance to goal, in Heuristic Search, we only consider heuristic distance to goal.
A* is computationally more demanding per expanded node because of the heuristic calculation. That might be relevant for some, if not most search searches.
The cost of computing the heuristic is almost never relevant especially if you're implementing this in a modern computer. The running performance of all these algorithms will be bottlenecked by memory access/cache considerations, but for the most part the best way to make them run faster is to reach the endpoint in the smallest number of steps.
this was almost a good video. Showing the score in the end for the algorithms would have been useful to see how much better AStar is than the others... Adding some music while watching the mazes being finished. How to find the shortest path rather than just a path, if there are more than one path.
Imma take the high ground here and brag about my knowledge. This is one environment which may suit one algorithm more than others. The algorithm you use depends on the application and context of the problem. Still a great informative video 🙂 I don't mean to criticize, just like to seek attention and show off 😅
I think a* (and others path finding algo) are interesting to code once, it's a pretty good exercise. You can even add an hysteresis function to optimize it a bit more
Excellent video if you are criticised in any way, shape or form because you didn't include edge cases where the other algorithms would do better than A* or because it wasn't a conclusive, full proof as to why A* is generally better please do not be afraid to inform me.
almost all labyrinths have near to straight path solution, but in real maze you could go for example right on full width and then top on half height and then left on full width etc., or like a spiral or something more difficult, i suppose some of the algorithms could be better without heuristic.
flow field is effectively just a "baked" BFS where the BFS is performed at compile time and stored in memory, so that you can query any tile to know which direction to go in, and rather than starting from the Origin and searching for the goal, it starts at the goal and searches for the Origin. flow field doesn't work well for dynamic pathfinding, and then you need a custom algorithm like a recursive A* + flowfield impl where you might divide the entire tileset into groups of tiles as graph nodes, with tile groups that are connected having edges, you can then perform A* on the grouped tiles and then perform flowfield on the subtiles once you know which groups of tiles are relevant, this can massively reduce the amount of tiles you need to search. Regardless, flow field is only "better" than A* if you need to do pathfinding for many agents, or for an undefined starting position. ua-cam.com/video/Bspb9g9nTto/v-deo.html
Lord Monarch uses BFS or Dijkstra for pathfinding. In this game units must take the shortest path to their destination with least turning as unit can only move or turn on each tick.
DFS look like the method for humans to complete a labyrinth. "Always turn right (or left), if you meet a wall come back to the last intersection and take the 2nd on the right (or left)". The advantage is that there is no risk of making mistakes.
In grid, dijkstra IS bfs, because distance between every grid cell is 1. When you have distances though, dijkstra is going to find the optimal path and bfs is just going to find the path with the smallest number of road
The biggest problem with this comparison is that the maze is always build the same way which strongly favors the Astar algorithm. If you were to create a maze algorithm that builds the maze in quadrants but ensures that the route to the end zigzags through the entire maze, the Astar algorithm will possibly lose from dijkstra's algorithm. Or if the maze builds in a swirl, and the path to follow will become one, with the start at the edge or middle, and the end at the other location.
The testscase seem to be biased/flawed: 1)DFS/BFS going by in addition order/reversed profit from the cell being in a corner and the target being always to the right. The red dot should start in the center like a pacman ghost and the target(green) be somewhere around it. 2)In the first example DFS was shown to generate longer pathes than needed for open areas. So adding some bigger rooms inside the maze would demonstrate unneded long pathes. AFter all not just the time to generate/find but how optimized/short the path is weights into the quality of such an algorythm.
A few points to make... Dijkstra is equivalent to BFS here because the edges are not weighted, i.e. the cost of going from 1 cell to any adjacent cell is the same for all of the maze. The simulations are not statistically meaningful, and depend heavily on the position of the target node especially as far as DFS is concerned. DFS would have performed worse than BFS/Dijkstra if target nodes happened to be closer, or with a Y value bigger than an X value (as in, more over the source as opposed to more to the right of it).
At 3:04, A* should make a beeline toward the goal, it shouldn't be expanding a node in the opposite direction. Are you sure your A* implementation is correct?
There is a minor error in the A* Algorithm here. It does not have an optimal path when it first finds the target node, but only when a path with the target node in it is popped off the search stack. This is because there may be many paths that end up at the target, but you want to find the one with the lowest cost. Anyway, thanks for putting up these comparisons - very interesting.
@@SianaGearz Good point, but most real-life implementations of A* will have multiple ways of getting to a goal so it is important to understand the algorithm correctly.
When the heuristic is straight distance to the goal A* will always arrive at the goal from the optimal path. For there to be a better path, the current-furthest node on that path *must* be able to walk straight through walls and follow the heuristic's simplistic idea, otherwise A* would have followed that path. While this is a potential concern for some A* implementations, this error can only occur if the heuristic is capable of being worse than the real value remaining. This can happen if trying to optimise a road route for time, for example, if it misses a faster road option, because the optimal goal is time but the heuristic has to make assumptions about time from different values, distance and speed. If optimising for distance and using distance as your heuristic, the error is solved by the choice of heuristic.
Why do your mazes have only one path between each two points? The distance in your 20 trials has to be the same for each algorithm for that reason. You didn't show that while BFS, A* & Dijkstra all find the shortest path, the DSF doesn't and it's produced path can be very obscure. Also I wonder why you left the Greedy algorithm out, you could have swapped it for Dijkstra, since in your examples Dijkstra = BFS.
could you regenerate the tests with a colour gradient instead of orange so we can see which segments got checked when? It would increase the visual a lot in my point of view, especially when dijkstra or dfs are missing their goal by one field
The Dijkstra algorithm is made for distances of different length and in this simulation the distance between nodes is always 1. For pathfinding in this maze simulation A* is the best algorithm. For finding the shortest way through a network of streets, like navigation systems do, Dijkstra is the best and A* could not even handle this because A* requires a distance of 1 between nodes. So, this comparison is somehow senseless, because its done in an environment that do not fit for all candidates. It's a comparison of apples with pears, as we use to say in Germany.
I wonder how the algorithms would fare if you flipped all of those mazes on the upper left to lower right diagonal, and had the start in the top right cell. I get the impression that they were all designed for a "general case" of having the start in the lower left of a maze.
Is it possible to train these with generational learning? Would be really cool if they could learn to scan it without expanding and find the optimal path.
Serious note, what was the point of putting Dijkstra's in there? It is good for weighted searching (no negative weight cycle). Maze has no weights, so of course it's gonna be the same as bfs.
How about the red dot always being in a corner? This limits the world to a quarter of what it could be. Does that affect all algorhytms tha same? How would each perform if the location of the start ( red dot) were also random?
Yes all would be affected approximately the same. Variation in relative performance, if any, would be completely negligible.
A more important factor would be the difference between searching in a closed maze vs a large open space with very few walls in which case many A* heuristics can vastly outperform the other algorithms.
@@BlameTaw I disgree, his DFS algorithm was getting an undue boost due to the fact that it is always starting in the SW corner which meant it was unable to search South and West first. Particularly think of if the starting dot was in the middle and the end was to the NE of it (such as the example given at 1:28)
The mazes are quite simple anyways, and hence the distances are short. No wonder astar beats everything
@@RKelleyCook So you're saying that they should all be tested on their worst case scenario. Sounds good to me.
bogosearch: generate a list of coordinates and see if it works. If not repeat.
If you are infinitely lucky you can always find the answer in O(1) with Bogo.
ngl you made me laugh
yea baaby!!
No seriously someone make this a think
Alternatively: every step go in a random direction until you reach your destination
The difference between Dijkstra and BFS is that Dijkstra can handle distances of different length.
Since the distance between two adjacent cells is always 1 in your maze, these 2 will be basically the same every time.
I followed a path finding course 3 years ago, and we called that the cost to explore the node.
In these mazes, there's only 1 solution, and each square has the same cost (1).
There are some cases where there the shortest path isn't the cheaper path, and Djikstra as well as A* take both the distance and the cost.
A good example of this scenario is google map's Directions API, where the cost is the estimated time to go from the point A to the point B.
@@ulamgexe7442 yeah, if the maze would have swamp, then djikstra would make difference.
In its most basic form, yes. The big thing with Dijkstra is that you can modify how it prioritizes the edges that it processes.. If you use Manhattan distance, it's gonna be a slower BFS that follows the same paths (since priority queues are slower than regular queues), but if you use something like Euclidian distance, Dijkstra will select slightly different paths. Especially for mazes like these though, they're not gonna be _that_ different. Not exactly the same, but pretty damn similar.
@@fotnite_
Djikstra’s + a heuristic is just A* is it not? Its not usually called Djikstra’s algorithm once you start using Manhattan or Euclidian distance, since at that point you’ve given it a heuristic and its now A*.
@@-Burb Not necessarily. A* requires that the heuristic be some representation of the cost to get to the goal, but that's not what I'm describing, which was using Euclidean distance from the start node. If I were using Euclidean distance from the goal node, then it would be A*.
A* is being heavily favored here due to how you generate mazes randomly. Your mazes are too "open" meaning that the correct way to the target is always a relatively straight line (notice how there are no zigzags or steep turns one after another, on the final paths). A* excels in these cases due to its usage of the Manhattan distance, and, while A* tends to indeed be the best algorithm, it performs poorly in scenarios where the best path requires you to first move away from the target. Other than that, nice video!
Plus it's the only one in the comparison for which you need to know the location of the target beforehand, the other three work fine w/o this info. Because those are searching algorithms meant to search through the whole graph (or at least a connected component).
And if you consider the cost of switching branches like you have to physically backtrace your steps and go down on the other path (like in a real-life labirinth or for an automatic vacuumcleaner/lawnmower), suddenly DFS have a helluva big advantage.
A* doesn't necessarily use the Manhattan distance, you can use Euclidean or any other distance that guarantees not to under-estimate the distance remaining.
@@DaveLeCompte if the path is not a relatively straight forward one but constanly winding and rewinding, the Euclidean metric gives also false heuristic about the right path at the crossings.
@@jmiki89 It is an optimistic heuristic, which is "Admissible" to A* - but heuristics are, by definition, estimations.
@@DaveLeCompte yeah, but the main point was that due to the structure of the mazes, this kind of optimistic heuristics are heavily favoured which might not be .the case (or at least not this much) with more diverse maze structures.
When a maze has a single path from point A to point B, it's probably not worth comparing the lengths of the paths that the different algorithms discovered, since they will all discover the same path.
In this case the time required to be sorted is important (treat it as a fair test such that length of path is a control var.)
The maze have a single path from start to end. The point A and B are also generated randomly in the maze.
So they search which route for each algorithm.
The fact that Dijkstra and BFS get similar result is really easy to understand, because they are basically equivalent in uniform graphs:
- Dijkstra's principle is that nodes are added to the expanded monotonously with regard to distance. The search set is therefore always composed of nodes that have distance N or N+1 to the source. Nodes with distance N+2 will only be added to the search set when expanding an N+1 node, which will only happen one all N-distanced nodes have been expanded.
- BFS will have the same property, because nodes are expanded from oldest to newest, and since every step only adds N+1-distanced nodes to the search set when expanding an N node, the search set will always be a queue containing N-distance nodes first, and then N+1-distance nodes only.
In both cases, when the last N-distance node is expanded, they will have the same search set comprised of exclusively N+1-distanced nodes. They only differ in the ordering in which nodes at the same distance are explored, and their difference in performance is therefore bounded to the number of nodes that share the target's distance with the source. If we add a constraint for Dijkstra to pick the next expanded node deterministically, they will in fact have the exact same average performance.
"Hugging" the left or right wall is very human approach to mazes and for mazes with just one path between each two points this is quite similar to DFS search.
Nah, the moment you notice the maze has “islands”, the “hugging the wall” approach fails.
I usually just look at random points until I find a string of points that connect both sides.
@@cezarcatalin1406 how do you look at random points when you are in a maze
@@cezarcatalin1406 Even if it has islands, unless it is also donut shaped with one exit (but not both) on the inside, hugging the wall should still work. Hugging the wall will ensure that you visit every point along the edge on which your starting point lies exactly once, until you either reach the exit or are back where you started.
On another note, wallhugging becomes more useful when pathfiding in a situation where there are ranged attack entities and obstacles cast a "line of sight blocked" range to give them the illusion of height.
@@cezarcatalin1406 you can switch the side to hug, if you encounter a closed loop.
Humans search with DFS due to everything else being untenable to perform. Glad to hear that that's almost optimal in the long run!
Why do you think that "humans search with DFS"? A* is probably closest to human
@@sexcommunist Cause when you enter the maze you never know where the exit is (almost), but in A* you know where the exit is every time.
@@MrScarabus When you dont know were the exit is is called fog of war. And it is a bit different thing. Here algorithms "know" where exit is so you cannot compare it to "human don't know where exit is".
@@sexcommunist Nor DFS, BFS or Dijkstra know where the exit is. They just checks cell by cell looking for it. Only A* knows and guide itself straight to the exit. Mere humans usually like DSF - grab wall by one hand and follow it. But if you have GPS with exit coords - you are a king - that's how A* fells among other algorithms.
humans brain is able to comprehend 2 dimensional data unlike any modern machine so it can not be compared to a pathfinding algorithm.
Thing is A* needs to know where the exit is. Also you could craft mazes designed to trap A* (although even with a trap I'm not entirely sure it would be worse than Dijkstra since those will basically always scan everything whatever happens).
Exactly, I thought same. How can you know the distance without knowing where the target lies?
when a* correclty written - there is no chances for trap
If I remember right, of the algorithms, only A* already knows where the destination is. So it has an unfair advantage over the other three.
A* doesn't belong in the same family as the other three. This is an apples and oranges comparison.
You can see it by looking at how each of the trees grow as they search out the exit. A* is always roughly heading right for the exit. The other three don't, and this is something you can observer over multiple maps that are drawn.
> only A* already knows where the destination is.
True. More generally, A* uses a heuristic function, and you can bake complete or partial knowledge about the solution and/or the search space into that heuristic function.
What comparing A* to Dijkstra/BFS will tell you is something like "how useful is the extra information".
Also (to whom it may concern) A* still performs work even if it already knows where the destination is. Anyone who has moved within a city and needs to go downtown from their new home knows where the destination is, but they don't know the optimal route from their new starting location; there's more to a route than simply knowing where the destination is.
in the type of maze he used, yes it's really good. however if it had a big upside down U shape in it's way, it would get stuck for a VERY long time trying to find it's way out of it.
also it's completely fair to compare them to each other, they are all doing a set task (finding a path) and are all algorithms.....
it's like trying to say that a horse carriage and a modern super car can't be compared. they most certainly can be as they are of the same category (travel). one is clearly more advanced then the other but that doesn't mean they can't be compared.
in some instances it's okay to use the older forms of searching for a path. however in most cases, A* does it just fine if not better on avg and can be easily modified to adapt to anything else that might be needed.
also why wouldn't you want to give your algorithm as much information as possible to complete it's task faster?
@@rocksfire4390 There are other algorithms that avoid filling large area such as the U shape you mentioned by following the surface of an obstacle until they are around it. Comand and Conquer used on of those algorithms, though it's quite a primitive variant. They work especially well for maps that aren't a dense maze with walls everywhere (as in the video), but have larger free areas. So they are very suitable for most computer games. An advantage is that they scale better with more tiles, so higher map 'resolution' is not much of a problem.
@Armin Reichert
"A* does not "know" where the destination is, it only can estimate the distance to the target. "
in order to estimate the distance, it NEEDS to know where the target location is, aka the destination.
actually ALL pathfinding needs to know where the destination is......
Knowing the distance to the target tells you that the target lies on a particular circle. Three such circles have an unique intersection thus determining the target. Thus knowing the distance to the target at three points tells you where the target is.
It's not that it's "similar" to BFS. It's that Dijkstra where the cost is always 1 is exactly the same as BFS (perhaps modulo ties). Just like how A* where the heuristic is always 0 is exactly the same as Dijkstra. (And DFS is just useless.)
dfs isn't useless if you're playing chess. all minmax does is a dfs.
I could probably write a Dijkstra or A* pathfinder with BFS as an explicit failsafe, among others. You may never know if a malicious graph comes your way.
@@powerhouseofthecell9758 "failsafe" for what, though? A* will find *a* path, it just might not be the best one if the heuristic is bad. But BFS can't look at edge weights at all, so it also won't find the best path, so I don't see what you'd gain from that.
Dfs isn't useless, it's one of the best techniques for tree algorithms. You can easily use DFS to get the distances from the root and then use LCA. Yes, you can also use BFS, but DFS is easier to code in this situation.
@@deepdark8192 Indeed and it's also very close to what people do if they're needing to find their way when lost. Usually, we'll trace the left or right wall rather than expanding in the same direction, but the idea is analogous. It's worked for millennia even without the ability to keep track of large sets of data.
Another good comparison of Manhattan distance that people tend to understand is to compare it to what (I believe?) gave it its name -- think about walking through city blocks. The closest distance to some arbitrary place requires you to walk along a grid of streets, so you can't just find some short diagonal path, because you'd be walking through buildings.
Dijkstras is essentially a weighted BFS, but since each node has a weight of 1, they are identical algorithms in your implementation.
I don't know how many times I've watched this video, but its a lot. Very useful to create code using the steps you provided and check the behavior of my pathfinding implementations compared to yours.
That was great, I'd love to see a similar comparison for cases where there are multiple valid paths, to see how such algorithms can be practically applied for searching quickest paths to destination for example
One application for Djikstra is more efficient is if you have multiple (N) goals. A* would need to search N times whereas Djikstra just needs to search once until all goals are found, then you can pick through the entrails to extract all N optimal paths. Just thought I'd share :)
You could switch out the heuristic upon reaching the first goal and continue the expanding search from there.
A* doesn't need to rerun. You can have a composite decision-making heuristic that works for multiple targets individually.
@@superkingofdeathifyIt would have to rerun if the other targets are outside of the scanned range of cells.
Adding always 1 to the cost on the Dijkstra algorithm will indeed turn it into a BFS search algorithm. Instead, the cost should be the distance to the destination so that it preferably explores options that are closer to the end node.
isn't that just A*
I'd say that the random map generation algorithm actually favors that pathfinding algorithm. If say the end goal was near the start, but the right path was something like going really far away and then coming back I'm not sure that path would do it faster, so it depends on the general degree of connections your map gen makes.
I didn't read the title and I thought it was another bad apple video oh my god
Love clearly laid out comparisons like this.
To anyone learning this, just remember that the time it takes to find a path can vary depending on the scenario.
Eg. an Astar algorithm where there is a right angle wall between the starting node and the end node, can have a higher runtime searching from there, than searching from the end point first, purely bc the end point would reach, and path around the wall earlier than the start
Make sure to consider that if you plan to make or use Astar.
There is one thing that was overlooked with this test. The maze was generated and started from the same position, so all paths are essentially a tree branching from the start position so A star has for the most part a straight albeit bent path to its target, this setup heavily favors A star. had the start been in the bottom right and the end being at the top right while the maze is generated from the far left... i dont expect these results would be as good. Though that said, Astar probably isnt designed for mazes but general pathfinding with more open access points between locations. Also this maze isnt so much a normal maze, the paths are all fairly straightforward, real mazes could have you go to the far side and up and then back and move around the middle before going to the exit with many other possibilities all being dead ends. this map is simply generated from the corner and expands outward so there can be NO back paths when the maze is generated.
That all said, its clear that Astar is far superior then a "dumb and blind" search that the others use. But Astar also needs to know where its target is. the others dont.
Other differences... a human might not know where the exit is.
@Armin Reichert Thats right, the starting position of where the maze generation starts doesnt matter, but the starting position in the maze does matter because this is a flawed maze, if it wernt flawed i dont think it would matter.
@Armin Reichert depends if the branches connect to each other. but as the map is generated it spreads out and goes to the other side of the map, while the paths may not be a straight line, its essentially like having straight lines from the start to finish so its easier for A* to follow that path. If for instance the correct path was a 'straight line' but looped around the back side of the maze and then came back to the front, being "closer" to the exit wouldnt help and would in fact lead it to take other paths. For a simple visual you can think of it as starting a maze at the pointed end of a V and going to the end of either leg, its a straight path from start to finish. if the start was on the top of one leg and went to the other leg, being 'close' to the goal wouldnt help since it actually has to go away from the goal to get further down the correct path.
@Armin Reichert what is best
-first search ?
From what I’ve seen, dijkstra’s algorithm is most efficient when determining the shortest path between every point before the path finding needs to occur, so it’s really good for pathfinding in an unchanging area.
I can’t find the video any more but I once saw someone use it to simulate a million particles moving to where the cursor is with no noticeable performance drop as they were simply moving in the direction that djkstra’s algorithm had pre-calculated to be most efficient. (If anyone can find the video I’d be very thankful)
Overall though love the video!
That's called a flow field! It calculates the path to a target location from EVERY start location at once, so it's super useful when you have a bunch of entities that want to move to the same location
BFS and Djikstra are essentially the same when the costs/weights of all the edges are equal. Moving from one cell to another in this maze (graph) has the same cost (cost/weight of the edge) which is why their performance is almost equal in this comparison.
watching this video before and after my algorithms class was extremely satisfying. Good work.
This was randomly recommended to me but I was needing it anyways, even though unconventionally. I think I can use the way A* works to visualize an economic circumstance.
Whatever, nice vid, have a good one and thank you.
This was amazing, dfs performance was a surprise too
I am currently doing a course on AI, and you have no idea how useful this animation is!!
This channel has potential keep exploring topics you find interesting and share them with us in the same quality as this video
There is also a much simpler and faster algorithm which was used in early RTS games like Dune 2, Warcraft and Doom. It involved casting a ray into the direction of the goal, and if the ray hits an obstacle, they the algorithm either uses a right-hand side rule to go around it or shots a ray into random direction. It isn't guarantee to find the shortest path, but has constant memory usage and usually finds the path faster. You can also run it in parallel by shooting several rays. It also works when you have to navigate an actual drone without a pre-made map.
Flow field pathfinding?
Great video! Appreciate the visualization
Love how often dfs actually got first in the simulation... :) great video
That's a combination of his mazes have no loops and his search order is top, right, bottom, left, which essentially produces a try up and right first heuristic. He needs to randomize start positions and use multiple systems for generating the mazes.
@@GordonWrigley I know it's still funny
would be cool to see a version of this with more relevant modern algorithms like ANYA, Block A*, Sub-TL, Lazy Theta* w/ Optimizations, etc.
Only one small note:
Dijkstra is soumding somewhere between Deikstra and Daikstra
The grid in the first 3 minutes totally drives me nuts
Haha, yes me too, don't know why 😅
@@jojo_87_xy Probably because it's missing lines
You omitted a random selection algorithm. It has the capacity to beat both DFS and BFS by avoiding their fixation with one direction. Also how do DFS and BFS if you rotate the start angle?
Looking forward to that video on heuristics!
Love to see more videos like this!
I feel this favors DFS as the red dot is always on the left most side of the maze, meaning the green dot will almost always be to the right.
Astar performed great because this is a very generic maze with dead ends that are uniform distributed and never lead to false path.
Would be interesting to watch case when the maze has several false passages lengthing from start to "almost end" but ends in dead ends.
All of these algorithms look at a node and find just the next node. Solving it in your head you can see the whole maze and recognize patterns like seeing a big stretch of empty space as a unit rather than a series of nodes. Also you're able to look from both ends.
this guy just single handedly carrying me through uni
At a glance you can tell when a branch is just dead space, by painting that area black it builds a wall of space that no longer needs to be considered. Of course that presumes that the map and red location are known. Can also walk backwards from the red dot in the same manner, assuming this is path finding, not dot finding.
The starting point location is a bit helping DFS. Because it prevents DFS running into a completely wrong direction. And the random mazes were leaning towards DFS also. 12 of the 20 mazes had the goal positioned roughly right of the starting point. The direction that DFS priorizes...
great simple overview just what i've been looking for! :D
My favorite method still is picking a wall and following it
Epic video! Wish I found it sooner
I love mazes!!! I am VERY good at it! The first maze you showed us, i tried to get the way (before the AI tryed it) i finished it in under five seconds :D
What ai do you run on
there is a nerd for every field haha
@@30svich hahah thanks i see this as a compliment
@@Kai_On_Paws_4298 i'm sorry, Area 51 hasn't allowed me to express more on this subject
0:42 I was able to instantly solve the second maze!
A and B could be very close to each other while the linking path could be extreme winded and long. So distance of A and B does not matter at all. Only if there is more than one linking path considering the distance should be taken into account.
your example would give vastly different results if the start point was in the center - DFS was only performed well because the arc was limited to 90 degrees.
The heuristic used in A* doesn't necessarily need to be the Manhattan distance. It works well with regular grid-placed nodes but in real life geometric scenarios the Euclidean distance would be the preferred choice.
Nice vid love the graphics
Nicely done man, keep going
There is another simple search algorithm not included. It is the Heuristic Search. On A*, we use both calculated distance from parent + heuristic distance to goal, in Heuristic Search, we only consider heuristic distance to goal.
A* is computationally more demanding per expanded node because of the heuristic calculation. That might be relevant for some, if not most search searches.
If you have any plausible heuristic at all, it's essentially always worth it.
The cost of computing the heuristic is almost never relevant especially if you're implementing this in a modern computer. The running performance of all these algorithms will be bottlenecked by memory access/cache considerations, but for the most part the best way to make them run faster is to reach the endpoint in the smallest number of steps.
this was almost a good video. Showing the score in the end for the algorithms would have been useful to see how much better AStar is than the others... Adding some music while watching the mazes being finished. How to find the shortest path rather than just a path, if there are more than one path.
Love how some algorithms look like slime mold pathing.
Okay I still don’t get the difference between BFS and Dijkstras, I feel like they should be exactly the same, except Dijkstras has more computations?
Imma take the high ground here and brag about my knowledge. This is one environment which may suit one algorithm more than others. The algorithm you use depends on the application and context of the problem.
Still a great informative video 🙂 I don't mean to criticize, just like to seek attention and show off 😅
I think a* (and others path finding algo) are interesting to code once, it's a pretty good exercise. You can even add an hysteresis function to optimize it a bit more
how did you generate the mazes?
Excellent video if you are criticised in any way, shape or form because you didn't include edge cases where the other algorithms would do better than A* or because it wasn't a conclusive, full proof as to why A* is generally better please do not be afraid to inform me.
Your video was a quite useful for me, thanks! Subscribed. I will be plesured if you do some more content of this quality)
If yellow touching multiple orange, then: reduce search priority by orange number.
It’s 3 in the morning, I need to get ready for work in 2 hours, but yet here I am….
The two missing lines in the grid are making me unreasonably angry.
Try right hand rule through the maze where you put your hand on your right wall and walk where it reaches to
Bruh this was in my recommended
almost all labyrinths have near to straight path solution, but in real maze you could go for example right on full width and then top on half height and then left on full width etc., or like a spiral or something more difficult, i suppose some of the algorithms could be better without heuristic.
I heard that flow field is the current best pathfinding algorithms, to be implemented in future RTS games, replacing A star.
flow field is effectively just a "baked" BFS where the BFS is performed at compile time and stored in memory, so that you can query any tile to know which direction to go in, and rather than starting from the Origin and searching for the goal, it starts at the goal and searches for the Origin.
flow field doesn't work well for dynamic pathfinding, and then you need a custom algorithm like a recursive A* + flowfield impl where you might divide the entire tileset into groups of tiles as graph nodes, with tile groups that are connected having edges, you can then perform A* on the grouped tiles and then perform flowfield on the subtiles once you know which groups of tiles are relevant, this can massively reduce the amount of tiles you need to search.
Regardless, flow field is only "better" than A* if you need to do pathfinding for many agents, or for an undefined starting position. ua-cam.com/video/Bspb9g9nTto/v-deo.html
Lord Monarch uses BFS or Dijkstra for pathfinding. In this game units must take the shortest path to their destination with least turning as unit can only move or turn on each tick.
DFS look like the method for humans to complete a labyrinth. "Always turn right (or left), if you meet a wall come back to the last intersection and take the 2nd on the right (or left)". The advantage is that there is no risk of making mistakes.
Would have liked to see IDDFS
In grid, dijkstra IS bfs, because distance between every grid cell is 1. When you have distances though, dijkstra is going to find the optimal path and bfs is just going to find the path with the smallest number of road
The biggest problem with this comparison is that the maze is always build the same way which strongly favors the Astar algorithm. If you were to create a maze algorithm that builds the maze in quadrants but ensures that the route to the end zigzags through the entire maze, the Astar algorithm will possibly lose from dijkstra's algorithm. Or if the maze builds in a swirl, and the path to follow will become one, with the start at the edge or middle, and the end at the other location.
The testscase seem to be biased/flawed:
1)DFS/BFS going by in addition order/reversed profit from the cell being in a corner and the target being always to the right. The red dot should start in the center like a pacman ghost and the target(green) be somewhere around it.
2)In the first example DFS was shown to generate longer pathes than needed for open areas. So adding some bigger rooms inside the maze would demonstrate unneded long pathes. AFter all not just the time to generate/find but how optimized/short the path is weights into the quality of such an algorythm.
A few points to make...
Dijkstra is equivalent to BFS here because the edges are not weighted, i.e. the cost of going from 1 cell to any adjacent cell is the same for all of the maze.
The simulations are not statistically meaningful, and depend heavily on the position of the target node especially as far as DFS is concerned. DFS would have performed worse than BFS/Dijkstra if target nodes happened to be closer, or with a Y value bigger than an X value (as in, more over the source as opposed to more to the right of it).
could you do the same kind of video but for maze generators algorithms?
At 3:04, A* should make a beeline toward the goal, it shouldn't be expanding a node in the opposite direction. Are you sure your A* implementation is correct?
This was excellent. I would have loved more.
Here's something related
www.astrolog.org/labyrnth/algrithm.htm
Bro a star best one
There is a minor error in the A* Algorithm here. It does not have an optimal path when it first finds the target node, but only when a path with the target node in it is popped off the search stack. This is because there may be many paths that end up at the target, but you want to find the one with the lowest cost.
Anyway, thanks for putting up these comparisons - very interesting.
Mazes do not have circular, rejoining paths. There cannot be two different paths to a target.
@@SianaGearz Good point, but most real-life implementations of A* will have multiple ways of getting to a goal so it is important to understand the algorithm correctly.
When the heuristic is straight distance to the goal A* will always arrive at the goal from the optimal path. For there to be a better path, the current-furthest node on that path *must* be able to walk straight through walls and follow the heuristic's simplistic idea, otherwise A* would have followed that path.
While this is a potential concern for some A* implementations, this error can only occur if the heuristic is capable of being worse than the real value remaining. This can happen if trying to optimise a road route for time, for example, if it misses a faster road option, because the optimal goal is time but the heuristic has to make assumptions about time from different values, distance and speed.
If optimising for distance and using distance as your heuristic, the error is solved by the choice of heuristic.
Why do your mazes have only one path between each two points?
The distance in your 20 trials has to be the same for each algorithm for that reason.
You didn't show that while BFS, A* & Dijkstra all find the shortest path, the DSF doesn't and it's produced path can be very obscure.
Also I wonder why you left the Greedy algorithm out, you could have swapped it for Dijkstra, since in your examples Dijkstra = BFS.
Yeah, this is a serious limitation. I think he is show-cased what he learnt attending a path finding course.
DFS particularily shines in scenarios where the finish is towards the bottom right corner of the maze. Any other time and Astar beats it
You should do this with Jump point search as well. It works really well on mazes with straight corridors.
예전에 긱블에서 이거랑 유사한 거 다룬 영상 봤던 기억이 나네요.
This video reminds me that I've seen this similar method in UA-cam Geekble channel.
could you regenerate the tests with a colour gradient instead of orange so we can see which segments got checked when? It would increase the visual a lot in my point of view, especially when dijkstra or dfs are missing their goal by one field
DSF BSF and Dijkstra: randomly search
AStar: „Lets activate cheat code and find out how far away it is“
Nice! I think though that putting starting point in the corner of the maize is not ideal.
It's no wonder A* does the best -- it knows where the target is.
U : no.
To much information for my 3 braincells.
The maze searching animations could use some background music.
I'm not a coder, I don't know what I'm doing here. Watched till the end though 😄
The Dijkstra algorithm is made for distances of different length and in this simulation the distance between nodes is always 1.
For pathfinding in this maze simulation A* is the best algorithm. For finding the shortest way through a network of streets, like navigation systems do, Dijkstra is the best and A* could not even handle this because A* requires a distance of 1 between nodes. So, this comparison is somehow senseless, because its done in an environment that do not fit for all candidates. It's a comparison of apples with pears, as we use to say in Germany.
I wonder how the algorithms would fare if you flipped all of those mazes on the upper left to lower right diagonal, and had the start in the top right cell. I get the impression that they were all designed for a "general case" of having the start in the lower left of a maze.
Very cool video
Is it possible to train these with generational learning? Would be really cool if they could learn to scan it without expanding and find the optimal path.
Great video
Thank you
Serious note, what was the point of putting Dijkstra's in there? It is good for weighted searching (no negative weight cycle). Maze has no weights, so of course it's gonna be the same as bfs.