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 different m_last_tiles 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 or closedNode, 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's FoundBestNode 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.

• The bug fix is important enough to be backported? (label: 'backport requested')
• This PR affects the save game format? (label 'savegame upgrade')
• This PR affects the GS/AI API? (label 'needs review: Script API')
  • ai_changelog.hpp, gs_changelog.hpp need updating.
  • The compatibility wrappers (compat_*.nut) need updating.
• This PR affects the NewGRF API? (label 'needs review: NewGRF')
  • newgrf_debug_data.h may need updating.
  • PR must be added to API tracker