CODEWITHSUNDEEP
javascriptalgorithmshortest-pathpath-findinga-star
Joe Morgan
Joe Morgan

Reputation: 441

Shortest path between 2 co-ordinates, through set of co-ordinates - Javascript

I need to write a JavaScript algorithm to find the shortest path between 2 co-ordinates. I have looked at using a few route finding algorithms, such as the A* algorithm.

The difference in my application however is that I know all of the co-ordinates that the path can take.

For example, in the image below, the green square would be the starting place co-ord, with the red square being the end place co-ord. The co-ord represented by every black square would be stored in an an array (or other data structure).

So I need the shortest path from the green square, to the red square, but it can only pass through a black square to get there. Would I still use the A* algorithm to implement this?

Grid

Upvotes: 2

Views: 815

Answers (1)

Martin Cup
Martin Cup

Reputation: 2582

Yes you can use A*. You would calculate the distance (number of moves) from every black coordinate to the red square. Then you got a graph structure from which square to which square you can move and every node in that graph has the distance stored to the red square. Then you apply the A* to that graph and get the shortest path.

EDIT

For A* you need a heuristic, that tells you which node is closer to the endpoint. Calculating the "air distance" between a black field and the red field gives you this heuristic for each field. Then you do A*, which is basically the Dijkstra-Algorithm with a heuristic. In your example the air distance between the green and the red field if the top left corner is (x = 0, y = 0), red is (14, 7) and green is (0, 1) then the air distance would be ABS(14 - 0) + ABS(7 - 1) = 20. So it is very easy to calculate from the coordinates.

Upvotes: 2

Related Questions