Pathfinding algorithms visualized [OC]

Pathfinding algorithms visualized [OC]

Great visualization! It's worth noting that depth first won't always be the fastest and can be very bad if it follows the wrong path.

Absolutely. It also doesn’t return the shortest path. DFS should not be your path finding algorithm haha

So I think what we want now is a video with several panels of DFS run against different paths, to show the variability.

Play with my algorithms here.

Recorded my screen and exported with Premiere Pro.

You can play with your own algorithm, thank you very much!

This gives me an interesting idea: take a map like this and set the "start" in the center. Then run each algorithm for every valid goal on the outside edge of the map. Then you could create a heatmap of the states that get expanded by each algorithm at each step

Dijkstra doesn't check every possible branch. That would be breadth first search. Dijkstra chooses which branch to check next based on how long it is from the start point. So if the optimal path is 30 steps long, all paths of 29 steps will have to be checked by Dijkstra before the optimal path is found.

On the other hand, A* is an optimized version of Dijkstra because it calculates which path to check next with a heuristic. What this means is that it partially takes into account how long it is from the start point (Dijkstra) but adds its guesstimated distance to the end point. That's why you see all the paths on the bottom right of the blob being checked before paths that are much closer to the start at the upper left.

TLDR: Dijkstra chooses paths based on distance from start. A* choose paths based on distance from start + guesstimated distance to end.

A path finding algorithm is basically what it says on the tin: an algorithm to find a path.

Think of the units in a game like Starcraft. You tell them where to move by telling them where you want them to end up. The game then has to figure out how to get the units from point A to point B without making them look completely gormless. You would use a path finding algorithm to calculate their path through the map.

On the right side, you have a depth first search and a breadth first search. They're essentially the same thing but in two different directions. Go in one direction until you can't anymore or you find the end, then go in the other direction until you can go in the original again. For example in a breadth first search, you go sideways until you can't. Then you go up/down until you can go sideways again. This was off, my b.

Depth first picks one path and traverses it until it can't go anymore or it finds the end. Check the "depth" of a path.

Breadth first finds all steps from the current spot, sees if it's the end and it it's not, checks all the steps from those steps.

Djikstra and A*, the ones on the left are also similar. Basically you know the distance between the start point and the end point, and you choose the path from the current point that looks like the shortest path until you can't go any more or you find the end. Basically if the absolute distance from the current point is 5 down and 3 left, you'd choose a path that would make that distance shorter. Probably down or to the left.

The visualization is showing how each is algorithm is traversing the maze. The blue represents the paths they are trying. When an algorithm finds the route, it's done and highlights the path in green.

Since the path is mostly vertical from the starting point, it does give you a skewed view of the efficiency of the depth first search. If the path were horizontal or diagonal, it would give a different result.

Everyday I realize how much I don't belong in this sub.

Can anyone give me an ELI5 of what a pathfind algorithm is and what the 4 are doing?

Is A* similar to an optimized version of Dijkstra? I never realized that Dijkstra would check every possible branch until it found the end.

Well, it depends on the application. Mazes are just graphs. I can definitely think of use cases where finding a path quickly is more important than finding the fastest path. For example, I have 1 million mazes that I need to determine whether they have a solution or not (e.g. you have a social network and you want to determine whether two users are connected at all). Depending on the expected layout of the graphs/mazes dfs could be the most performant option.

Computer Science student here. Time isn't a major factor with mazes like this because because computers are really fast. The best or optimal path is the path that has the lowest cost.

With problems that do take a while people user smarter searching algorithms. These "Smart" Searching algorithms like A* pick where to go next by minimizing the distance they've travelled (correlated to time) and the distance they think they'll have to travel to find the solution. But still the best solution is the one with the shortest path, they just find it faster by picking their next move better.