Comparison of different pathfinding algorithms on real maps. Every method has been adjusted to have the same duration so you can evaluate the space of search but not the time spend for each algoritm. In A* algorithms the following heuristics have been used to estimate the cost: - Euclidean distance (sqrt((y2-y1)^2 +: (x2-x1)^2) It is the rect line distance between two points. Probably the heuristic most useful in this video using the algorithm in real maps. - Chebysev distance (max(y2 - y1, x2 - x1)): It measures distance between two points as the maximum difference over any of their axis values. - Manhattan distance (abs(y2-y1)+abs(x2-x1)): It is a metric in which the distance between two points is the sum of the absolute differences of their Cartesian coordinates. On real maps this heuristics is not admisible for A* algorithm since the value that it takes can be higher than the actual cost to the destiny of a node. This implies it is not guaranteed that the finded path is the shortest path. Tools used for visualization: Python with OSMnx Blender API Da Vinci Resolve Chapters: 00:00 Madrid Dijkstra 00:27 Madrid A* Euclidean 00:49 Madrid A* Chebyshev 01:10 Madrid A* Manhattan 01:30 Los Angeles Dijkstra 01:56 Los Angeles A* Euclidean 02:18 Los Angeles A* Chebyshev 02:39 Los Angeles A* Manhattan 03:00 Tokyo Dijkstra 03:27 Tokyo A* Euclidean 03:49 Tokyo A* Chebyshev 04:10 Tokyo A* Manhattan #openstreetmap #pathfinding #dijkstra #astar #python #blender #heuristics #map #osm #osmnx