Node with lower cost in closed set is removed without being re-added to open set

[Lunarsong]

astar.c lines 188-192.

if ( idx_c >= 0 && cost < closed[ idx_c ].g )
{
    // remove neighbor from CLOSED
    if ( numClosed ) closed[ idx_c ] = closed[ numClosed-1 ];
    numClosed--;
}

Should add idx_c = -1;

if ( idx_c >= 0 && cost < closed[ idx_c ].g )
{
    // remove neighbor from CLOSED
    if ( numClosed ) closed[ idx_c ] = closed[ numClosed-1 ];
    numClosed--;
    **idx_c = -1;**
}

[stolk]

Thank you,

This bug got transcribed from the source material: the pseudo code from: http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html

It looks like the pseudo code is missing the 're-adding.' So I will have to incorporate your fix. Just to be sure, I will fire off an email to the author of the pseudo code.

Thanks again,

Bram

[Lunarsong]

Hi Bram,

The wording on Amit's page are the same for a node that is in open list and closed list yet you are handling them different :)

Generally speaking, I am not entirely sure if it needs re-adding to open list if state is identical as any new nodes added from that would be the same anyway so as long as the node points to the shorter path it should be fine and the node's evaluation would have been the same.

[stolk]

Never mind, after re-reading the pseudo code, it turns out that I introduced this error in my implementation. It's not in the pseudo source, but was in my implementation. Thank you for fixing it. This should make GPGOAP behave better in situations with non admissible heuristics.

[stolk]

Thanks Lunarsong! You are quite right.