Choosing proper heuristic for A* algorithm in subway network

69 Views Asked by At

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:

example situation

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.

0

There are 0 best solutions below