Exploring Pathfinding Algorithms Using a Real Map of Amsterdam

A* (A Star) pathfinding algorithm visualized on the city streets of Amsterdam, comparing the shortest and fastest path.

As I continue my exploration of the A* Pathfinding algorithm, I wanted to share the difference between finding the shortest path and the fastest path, which are often not the same. By using the max allowed speed of a certain street we can calculate the minimal duration it would take to use that street.

Using the A* Star path finding algorithm to find the fastest path instead of the shortest path. By taking in to account the max allowed speed of certain street and their length, we can calculate the minimal duration of using this particular edge. To calculate the heuristic for a node, the current speed (total distance / total duration) is applied to the heuristic distance (regardless of how we measure the distance). This will make sure that not only the edge with the lowest duration will be chosen next but also the path with the lowest duration to get to that point will be favoured.

I also take into account the allowed driving direction, this is why it might look like the animation is lagging sometimes. What actually happens during these moments is that it found another street connecting an already visited intersection but at a lower cost (or in this case, through a faster path) because of that it adds all the connecting streets again to the open list and recalculates all their edges with the new lower cost and less duration.

Thanks to Martin Raifer and his Overpass Turbo tool which I used for the initial data where intersections of streets represented as nodes and streets as edges

[eliasforamitti]

A beautiful visualization!!!

But if I understand your heuristic for the fastest path correctly, than it is not admissible, I think (i.e. A* will not necessarily find the fastest path if it terminates at the first valid path)

Imagine a triangle with straight edges as a minimal example, where the direct connection from source (S) to target (T) is of course the shortest but has a medium speed limit, while the path S->A->T is of course longer, and S->A has an even lower speed limit than S->T, but A->T makes up for it, such that S->A->T is overall the fastest route.

S --- T
\ /
A

Distance(S, T) = 60
Distance(S, A) = 12
Distance(A, T) = 60
SpeedLimit(S, T) = 10
SpeedLimit(S, A) = 6
SpeedLimit(A, T) = 60

So A* will first generate A and T, with your definition of cost (c) and heuristic (h) the evaluation function (f) for those paths yields:
f(S->T) = c(S->T) + h(T) = (60/10) + 0 = 6
f(S->A) = c(S->A) + h(A) = (12/6) + (60/2) = 32
(where the current speed of 6 from S to A is assumed to continue for the remaining A->T)
Since f(S->T)<f(S->A), A* will expand S->T next and then terminate, since T is the target. Even though c(S->A->T) = (12/6) + (60/60) = 3 is actually the cheapest path.

To ensure admissibility you would need to find some guaranteed upper bound for the speed and use that in the heuristic (e.g. use the overall max speed limit in the whole graph, or maybe you could find a more clever approach to find bounds in certain subgraphs), but using the previous speed is not admissible, since later speeds might be dramatically different.

[krns]

the firsr long street higlighted at 0:04 i used to take that almost everyday... i miss this city

[bytes]

can you share the file, or drop a tutorial of how to make this, or where did you learn yourself?
i am good in python, totally unfamiliar with blender. i badly want to make this simulation. but seems like no one has ever made any tutorial or documentation on this

[behnamrahdari]

Nice visualization. 👌Would be nice to see shortest path and the fastest path compete side by side.