Currently I am developing pathfinding module for subway network. I have question about admissible heuristic.
Prerequisites:
Graph is weighted. You can move only on edges (tunnels between stations in real life)
Map have size 3000 x 2500 pixels. I have nodes and available edges with their weight (in seconds) – adjacency list.
Nodes contains this attributes:
- id – unique identifier
- name – subway station name
- x – X position on map
- y – Y position on map
- lineId – line id
So right now I`m using Euclidean distance, but it seems like not a good option, because it gives wrong results for stations that is near each other, but on different lines.
For example:
Stations A and B is near each other and Euclidian distance gives us value of 200.
But the actual path weight is 1600. Because we can move only by available edges.
Finally, I tried to use ALT preprocessing and it gives close results.
But I think that my heuristic function is wrong for such case at all.
I tried to use ALT preprocessing and it gives close results.
Expecting to find proper heuristic function for my project.