A Comparison of Pathfinding Algorithms

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?

bogosearch: generate a list of coordinates and see if it works. If not repeat.

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

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!

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.

Humans search with DFS due to everything else being untenable to perform. Glad to hear that that's almost optimal in the long run!

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

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

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.

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.

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.

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

Nicely done man, keep going

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

Love clearly laid out comparisons like this.

watching this video before and after my algorithms class was extremely satisfying. Good work.

Dijkstras is essentially a weighted BFS, but since each node has a weight of 1, they are identical algorithms in your implementation.

This channel has potential keep exploring topics you find interesting and share them with us in the same quality as this video