CODEWITHSUNDEEP
algorithmpseudocodepath-finding
Stack452378
Stack452378

Reputation: 11

Trouble understanding A* pathfinding algorithm pseudocode on wikipedia

The pseudocode for the A* algortihm on wikipedia semms to not be right, but i somebody smarter than me probably made it, so i doubt that is true. Im having trouble understanding how:

 if tentative_gScore < gScore[neighbor]

can ever be true. I'll try to prove it here (also, current starts with being the start node, because it is the only thing in openSet at first):

tentative_gScore = distance(start, current) + distance(current, neighbor)

Because current is start, distance(start, current) is 0. therefore tentative_gScore is just:

tentative_gScore = distance(current, neighbor)

and if we replace current with start, and compare the two gScore's:

tentative_gScore = distance(start, neighbor)
gScore[neighbor] = distance(start neighbor)

I'm really having trouble seeing what i am misunderstanding, or is the pseudocode just wrong? afterall it is from wikipedia, and everyone can edit there.

Upvotes: 1

Views: 62

Answers (1)

btilly
btilly

Reputation: 46399

The answer is that gScore[neighbor] is the best distance recorded so far to neighbor. But we have not yet recorded the possibility of passing through current. And so we may discover an improvement.

This is dramatically demonstrated at the start when gScore is given a default value of Infinity. That records the fact that we have NO routes to anything except start. And makes it really easy to find improvements!

The one important guarantee that the algorithm depends on is that, by the time that we actually make a node current, we have discovered the best possible route to it. But until that point we can continue to improve distances.

Upvotes: 2

Related Questions