daihovey
daihovey

Reputation: 3575

Finding shortest distance / route on map

map with points

In Actionscript, I'm trying to work out the best way to create the shortest route between two point on the map above. I have all the distances.

Algorithms like A* I dont think are relevant as it is near impossible to work out the heuristic distance.

I thought I could create a big array of all the nodes with the distances to any connected nodes and just iterate through until Ive found the the shortest distance, but this I know is very inefficient.

Upvotes: 0

Views: 539

Answers (2)

Philippe
Philippe

Reputation: 446

I think you are looking for this algorithm: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Upvotes: 3

lettucemode
lettucemode

Reputation: 445

A* is extremely relevant to this problem - it's an excellent pathfinding algorithm. Are you really unable to find the heuristic distances between each point (that is, do you not have positional information for each point)?

You could give Dijkstra's algorithm a try, but if you don't have a heuristic then a brute force solution is the only thing you can do.

Upvotes: 1

Related Questions