CODEWITHSUNDEEP
c#algorithmperformancepath-finding
DividedByZero
DividedByZero

Reputation: 4391

If the A* algorithm explores more than one path, how do you choose the best one?

I have been working on a C# implementation of the A* pathfinding algorithm, and now that I have managed to get it to find a path from the starting point to the destination, I was wondering how I could choose the best path.

To clarify, if I make the program find a route from the square with a yellow border to the square with a green border (where dark grey squares cannot be crossed), the program will add all of the red squares to its 'closed' array.

enter image description here

As you can see, this isn't a direct route. How would I get the actual path from the closed array? By the way, I have disabled diagonal movement.

Upvotes: 0

Views: 246

Answers (1)

Pubby
Pubby

Reputation: 53097

It's been awhile since I've done A*, but if I recall correctly, you can trace backwards, starting from the end and following the path of least distance.

So if the numbers on this grid represent the distance to the yellow square, the shortest path could be found by starting at the green square (distance 12), and continually moving onto neighbors with the least distance until reaching the yellow square.

So you'd go 12 -> 11 -> 10 -> 9 ... -> 0

Upvotes: 4

Related Questions