Motivation / Problem

The pathfinder sometimes makes weird decisions when encountering a two-way red signal (with yapf.rail_firstred_twoway_eol on). Most recently spotted in this game: prune_bug.zip

This problem has also been reported in #6637

Description

The core of the issue is that when the pathfinder encounters a two-way red signal, it starts pruning the branch leading to the best intermediate node. However, this does not work in two cases:

1. the branches corresponding to the best intermediate node and the two-way red node are completely unrelated, in which case the pathfinder simply prunes the wrong branch
2. the intermediate node branch is a subset of the two-way red node branch and there is a node whose segment ends due to ESRB_CHOICE_FOLLOWS between those two nodes, in which case no pruning should be done

The 1. case is self-explanatory. For the 2. case, you can take a look at the attached savegame. The pathfinder:

• discovers the two-way red signal node, prunes (there was no intermediate node, so nothing happens)
• discovers the depot, sets it as the intermediate node
• discovers the choice leading from the depot, its distance to the target is worse than the intermediate, so nothing happens
• discovers the two-way red signal once again, prunes the depot node (intermediate node is now nullptr)

The PR solves these issues by first checking whether the intermediate node lays on the path between the two-way signal node and the preceding "choice follows" node and only prunes if that is the case.

Limitations

No known limitations.

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