Fix: Do not send vehicles towards incomplete PF nodes #9280
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Motivation / Problem
When a path cannot be found, the pathfinder attempts to send the vehicle as close to its destination as possible. However, it is possible to set up a situation where the pathfinder ends up sending the vehicle away from the destination.
Here's a savegame which demonstrates this issue: overwrite_bug.zip. If you start the vehicle, it chooses the track going away from its destination. If you remove the waypoint or the signal after it, the train chooses the correct track.
Description
When the pathfinder is exploring a new graph node, it requests a fresh node from the underlying
NodeList
which can either produce a completely new node or reuse the last node (if that node was never added to the open list or was not marked as the destination).It is possible to set up a situation where the
NodeList
reuses a node that's currently marked as the best intermediate node (m_pBestIntermediateNode
). If the best node is then never updated, it will end up with whatever random data the next round of the pathfinder fills it with, which might be completely unrelated to the actual best node.The attached savegame works by exploiting very long track segments (
ESRB_SEGMENT_TOO_LONG
). In particular, the are two ways of getting to the waypoint (key:m_tile=3055 m_td=TRACKDIR_X_NE
) that end up having differentm_last_tile
s of their segments. When the pathfinder gets to the waypoint for the second time, it creates a new node, it sees that its last tile is closer to the destination and sets it as the best intermediate node. Then it finds out that the key is already present in the closed list and the new node is never added to the open list (and thus finalized).The fix to this issue is simple: the best intermediate node is only updated once we're sure that the construction of the node is finalized (i.e. it is inserted into the open list).
Limitations
A case could be made for changing the best intermediate node to the
openNode
orclosedNode
, but the content of the open/closed node couldn't be changed to match the newly created node (in particular the distance to the destination would be wrong). This is very unlikely to matter, but I'm open to suggestions.Another possibility is to use
ItemList
'sFoundBestNode
to ensure the node isn't reused, but that seems like a misuse of that function.Checklist for review
Some things are not automated, and forgotten often. This list is a reminder for the reviewers.