src/pathfinder/yapf/yapf_costrail.hpp

   1 /*
   2  * This file is part of OpenTTD.
   3  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
   4  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
   5  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
   6  */
   7
   8 /** @file yapf_costrail.hpp Cost determination for rails. */
   9
  10 #ifndef YAPF_COSTRAIL_HPP
  11 #define YAPF_COSTRAIL_HPP
  12
  13 #include "../../pbs.h"
  14
  15 template <class Types>
  16 class CYapfCostRailT : public CYapfCostBase {
  17 public:
  18         typedef typename Types::Tpf Tpf;              ///< the pathfinder class (derived from THIS class)
  19         typedef typename Types::TrackFollower TrackFollower;
  20         typedef typename Types::NodeList::Titem Node; ///< this will be our node type
  21         typedef typename Node::Key Key;               ///< key to hash tables
  22         typedef typename Node::CachedData CachedData;
  23
  24 protected:
  25
  26         /* Structure used inside PfCalcCost() to keep basic tile information. */
  27         struct TILE {
  28                 TileIndex   tile;
  29                 Trackdir    td;
  30                 TileType    tile_type;
  31                 RailType    rail_type;
  32
  33                 TILE()
  34                 {
  35                         tile = INVALID_TILE;
  36                         td = INVALID_TRACKDIR;
  37                         tile_type = MP_VOID;
  38                         rail_type = INVALID_RAILTYPE;
  39                 }
  40
  41                 TILE(TileIndex tile, Trackdir td)
  42                 {
  43                         this->tile = tile;
  44                         this->td = td;
  45                         this->tile_type = GetTileType(tile);
  46                         this->rail_type = GetTileRailType(tile);
  47                 }
  48         };
  49
  50 protected:
  51         /**
  52          * @note maximum cost doesn't work with caching enabled
  53          * @todo fix maximum cost failing with caching (e.g. FS#2900)
  54          */
  55         int           m_max_cost;
  56         CBlobT<int>   m_sig_look_ahead_costs;
  57         bool          m_disable_cache;
  58
  59 public:
  60         bool          m_stopped_on_first_two_way_signal;
  61 protected:
  62
  63         static const int s_max_segment_cost = 10000;
  64
  65         CYapfCostRailT() : m_max_cost(0), m_disable_cache(false), m_stopped_on_first_two_way_signal(false)
  66         {
  67                 /* pre-compute look-ahead penalties into array */
  68                 int p0 = Yapf().PfGetSettings().rail_look_ahead_signal_p0;
  69                 int p1 = Yapf().PfGetSettings().rail_look_ahead_signal_p1;
  70                 int p2 = Yapf().PfGetSettings().rail_look_ahead_signal_p2;
  71                 int *pen = m_sig_look_ahead_costs.GrowSizeNC(Yapf().PfGetSettings().rail_look_ahead_max_signals);
  72                 for (uint i = 0; i < Yapf().PfGetSettings().rail_look_ahead_max_signals; i++) {
  73                         pen[i] = p0 + i * (p1 + i * p2);
  74                 }
  75         }
  76
  77         /** to access inherited path finder */
  78         Tpf& Yapf()
  79         {
  80                 return *static_cast<Tpf *>(this);
  81         }
  82
  83 public:
  84         inline int SlopeCost(TileIndex tile, Trackdir td)
  85         {
  86                 CPerfStart perf_cost(Yapf().m_perf_slope_cost);
  87                 if (!stSlopeCost(tile, td)) return 0;
  88                 return Yapf().PfGetSettings().rail_slope_penalty;
  89         }
  90
  91         inline int CurveCost(Trackdir td1, Trackdir td2)
  92         {
  93                 assert(IsValidTrackdir(td1));
  94                 assert(IsValidTrackdir(td2));
  95                 int cost = 0;
  96                 if (TrackFollower::Allow90degTurns()
  97                                 && HasTrackdir(TrackdirCrossesTrackdirs(td1), td2)) {
  98                         /* 90-deg curve penalty */
  99                         cost += Yapf().PfGetSettings().rail_curve90_penalty;
 100                 } else if (td2 != NextTrackdir(td1)) {
 101                         /* 45-deg curve penalty */
 102                         cost += Yapf().PfGetSettings().rail_curve45_penalty;
 103                 }
 104                 return cost;
 105         }
 106
 107         inline int SwitchCost(TileIndex tile1, TileIndex tile2, DiagDirection exitdir)
 108         {
 109                 if (IsPlainRailTile(tile1) && IsPlainRailTile(tile2)) {
 110                         bool t1 = KillFirstBit(GetTrackBits(tile1) & DiagdirReachesTracks(ReverseDiagDir(exitdir))) != TRACK_BIT_NONE;
 111                         bool t2 = KillFirstBit(GetTrackBits(tile2) & DiagdirReachesTracks(exitdir)) != TRACK_BIT_NONE;
 112                         if (t1 && t2) return Yapf().PfGetSettings().rail_doubleslip_penalty;
 113                 }
 114                 return 0;
 115         }
 116
 117         /** Return one tile cost (base cost + level crossing penalty). */
 118         inline int OneTileCost(TileIndex &tile, Trackdir trackdir)
 119         {
 120                 int cost = 0;
 121                 /* set base cost */
 122                 if (IsDiagonalTrackdir(trackdir)) {
 123                         cost += YAPF_TILE_LENGTH;
 124                         switch (GetTileType(tile)) {
 125                                 case MP_ROAD:
 126                                         /* Increase the cost for level crossings */
 127                                         if (IsLevelCrossing(tile)) {
 128                                                 cost += Yapf().PfGetSettings().rail_crossing_penalty;
 129                                         }
 130                                         break;
 131
 132                                 default:
 133                                         break;
 134                         }
 135                 } else {
 136                         /* non-diagonal trackdir */
 137                         cost = YAPF_TILE_CORNER_LENGTH;
 138                 }
 139                 return cost;
 140         }
 141
 142         /** Check for a reserved station platform. */
 143         inline bool IsAnyStationTileReserved(TileIndex tile, Trackdir trackdir, int skipped)
 144         {
 145                 TileIndexDiff diff = TileOffsByDiagDir(TrackdirToExitdir(ReverseTrackdir(trackdir)));
 146                 for (; skipped >= 0; skipped--, tile += diff) {
 147                         if (HasStationReservation(tile)) return true;
 148                 }
 149                 return false;
 150         }
 151
 152         /** The cost for reserved tiles, including skipped ones. */
 153         inline int ReservationCost(Node &n, TileIndex tile, Trackdir trackdir, int skipped)
 154         {
 155                 if (n.m_num_signals_passed >= m_sig_look_ahead_costs.Size() / 2) return 0;
 156                 if (!IsPbsSignal(n.m_last_signal_type)) return 0;
 157
 158                 if (IsRailStationTile(tile) && IsAnyStationTileReserved(tile, trackdir, skipped)) {
 159                         return Yapf().PfGetSettings().rail_pbs_station_penalty * (skipped + 1);
 160                 } else if (TrackOverlapsTracks(GetReservedTrackbits(tile), TrackdirToTrack(trackdir))) {
 161                         int cost = Yapf().PfGetSettings().rail_pbs_cross_penalty;
 162                         if (!IsDiagonalTrackdir(trackdir)) cost = (cost * YAPF_TILE_CORNER_LENGTH) / YAPF_TILE_LENGTH;
 163                         return cost * (skipped + 1);
 164                 }
 165                 return 0;
 166         }
 167
 168         int SignalCost(Node &n, TileIndex tile, Trackdir trackdir)
 169         {
 170                 int cost = 0;
 171                 /* if there is one-way signal in the opposite direction, then it is not our way */
 172                 CPerfStart perf_cost(Yapf().m_perf_other_cost);
 173                 if (IsTileType(tile, MP_RAILWAY)) {
 174                         bool has_signal_against = HasSignalOnTrackdir(tile, ReverseTrackdir(trackdir));
 175                         bool has_signal_along = HasSignalOnTrackdir(tile, trackdir);
 176                         if (has_signal_against && !has_signal_along && IsOnewaySignal(tile, TrackdirToTrack(trackdir))) {
 177                                 /* one-way signal in opposite direction */
 178                                 n.m_segment->m_end_segment_reason |= ESRB_DEAD_END;
 179                         } else {
 180                                 if (has_signal_along) {
 181                                         SignalState sig_state = GetSignalStateByTrackdir(tile, trackdir);
 182                                         SignalType sig_type = GetSignalType(tile, TrackdirToTrack(trackdir));
 183
 184                                         n.m_last_signal_type = sig_type;
 185
 186                                         /* cache the look-ahead polynomial constant only if we didn't pass more signals than the look-ahead limit is */
 187                                         int look_ahead_cost = (n.m_num_signals_passed < m_sig_look_ahead_costs.Size()) ? m_sig_look_ahead_costs.Data()[n.m_num_signals_passed] : 0;
 188                                         if (sig_state != SIGNAL_STATE_RED) {
 189                                                 /* green signal */
 190                                                 n.flags_u.flags_s.m_last_signal_was_red = false;
 191                                                 /* negative look-ahead red-signal penalties would cause problems later, so use them as positive penalties for green signal */
 192                                                 if (look_ahead_cost < 0) {
 193                                                         /* add its negation to the cost */
 194                                                         cost -= look_ahead_cost;
 195                                                 }
 196                                         } else {
 197                                                 /* we have a red signal in our direction
 198                                                  * was it first signal which is two-way? */
 199                                                 if (!IsPbsSignal(sig_type) && Yapf().TreatFirstRedTwoWaySignalAsEOL() && n.flags_u.flags_s.m_choice_seen && has_signal_against && n.m_num_signals_passed == 0) {
 200                                                         /* yes, the first signal is two-way red signal => DEAD END. Prune this branch... */
 201                                                         Yapf().PruneIntermediateNodeBranch();
 202                                                         n.m_segment->m_end_segment_reason |= ESRB_DEAD_END;
 203                                                         Yapf().m_stopped_on_first_two_way_signal = true;
 204                                                         return -1;
 205                                                 }
 206                                                 n.m_last_red_signal_type = sig_type;
 207                                                 n.flags_u.flags_s.m_last_signal_was_red = true;
 208
 209                                                 /* look-ahead signal penalty */
 210                                                 if (!IsPbsSignal(sig_type) && look_ahead_cost > 0) {
 211                                                         /* add the look ahead penalty only if it is positive */
 212                                                         cost += look_ahead_cost;
 213                                                 }
 214
 215                                                 /* special signal penalties */
 216                                                 if (n.m_num_signals_passed == 0) {
 217                                                         switch (sig_type) {
 218                                                                 case SIGTYPE_COMBO:
 219                                                                 case SIGTYPE_EXIT:   cost += Yapf().PfGetSettings().rail_firstred_exit_penalty; break; // first signal is red pre-signal-exit
 220                                                                 case SIGTYPE_NORMAL:
 221                                                                 case SIGTYPE_ENTRY:  cost += Yapf().PfGetSettings().rail_firstred_penalty; break;
 222                                                                 default: break;
 223                                                         }
 224                                                 }
 225                                         }
 226
 227                                         n.m_num_signals_passed++;
 228                                         n.m_segment->m_last_signal_tile = tile;
 229                                         n.m_segment->m_last_signal_td = trackdir;
 230                                 }
 231
 232                                 if (has_signal_against && IsPbsSignal(GetSignalType(tile, TrackdirToTrack(trackdir)))) {
 233                                         cost += n.m_num_signals_passed < Yapf().PfGetSettings().rail_look_ahead_max_signals ? Yapf().PfGetSettings().rail_pbs_signal_back_penalty : 0;
 234                                 }
 235                         }
 236                 }
 237                 return cost;
 238         }
 239
 240         inline int PlatformLengthPenalty(int platform_length)
 241         {
 242                 int cost = 0;
 243                 const Train *v = Yapf().GetVehicle();
 244                 assert(v != nullptr);
 245                 assert(v->type == VEH_TRAIN);
 246                 assert(v->gcache.cached_total_length != 0);
 247                 int missing_platform_length = CeilDiv(v->gcache.cached_total_length, TILE_SIZE) - platform_length;
 248                 if (missing_platform_length < 0) {
 249                         /* apply penalty for longer platform than needed */
 250                         cost += Yapf().PfGetSettings().rail_longer_platform_penalty + Yapf().PfGetSettings().rail_longer_platform_per_tile_penalty * -missing_platform_length;
 251                 } else if (missing_platform_length > 0) {
 252                         /* apply penalty for shorter platform than needed */
 253                         cost += Yapf().PfGetSettings().rail_shorter_platform_penalty + Yapf().PfGetSettings().rail_shorter_platform_per_tile_penalty * missing_platform_length;
 254                 }
 255                 return cost;
 256         }
 257
 258 public:
 259         inline void SetMaxCost(int max_cost)
 260         {
 261                 m_max_cost = max_cost;
 262         }
 263
 264         /**
 265          * Called by YAPF to calculate the cost from the origin to the given node.
 266          *  Calculates only the cost of given node, adds it to the parent node cost
 267          *  and stores the result into Node::m_cost member
 268          */
 269         inline bool PfCalcCost(Node &n, const TrackFollower *tf)
 270         {
 271                 assert(!n.flags_u.flags_s.m_targed_seen);
 272                 assert(tf->m_new_tile == n.m_key.m_tile);
 273                 assert((HasTrackdir(tf->m_new_td_bits, n.m_key.m_td)));
 274
 275                 CPerfStart perf_cost(Yapf().m_perf_cost);
 276
 277                 /* Does the node have some parent node? */
 278                 bool has_parent = (n.m_parent != nullptr);
 279
 280                 /* Do we already have a cached segment? */
 281                 CachedData &segment = *n.m_segment;
 282                 bool is_cached_segment = (segment.m_cost >= 0);
 283
 284                 int parent_cost = has_parent ? n.m_parent->m_cost : 0;
 285
 286                 /* Each node cost contains 2 or 3 main components:
 287                  *  1. Transition cost - cost of the move from previous node (tile):
 288                  *    - curve cost (or zero for straight move)
 289                  *  2. Tile cost:
 290                  *    - base tile cost
 291                  *      - YAPF_TILE_LENGTH for diagonal tiles
 292                  *      - YAPF_TILE_CORNER_LENGTH for non-diagonal tiles
 293                  *    - tile penalties
 294                  *      - tile slope penalty (upward slopes)
 295                  *      - red signal penalty
 296                  *      - level crossing penalty
 297                  *      - speed-limit penalty (bridges)
 298                  *      - station platform penalty
 299                  *      - penalty for reversing in the depot
 300                  *      - etc.
 301                  *  3. Extra cost (applies to the last node only)
 302                  *    - last red signal penalty
 303                  *    - penalty for too long or too short platform on the destination station
 304                  */
 305                 int transition_cost = 0;
 306                 int extra_cost = 0;
 307
 308                 /* Segment: one or more tiles connected by contiguous tracks of the same type.
 309                  * Each segment cost includes 'Tile cost' for all its tiles (including the first
 310                  * and last), and the 'Transition cost' between its tiles. The first transition
 311                  * cost of segment entry (move from the 'parent' node) is not included!
 312                  */
 313                 int segment_entry_cost = 0;
 314                 int segment_cost = 0;
 315
 316                 const Train *v = Yapf().GetVehicle();
 317
 318                 /* start at n.m_key.m_tile / n.m_key.m_td and walk to the end of segment */
 319                 TILE cur(n.m_key.m_tile, n.m_key.m_td);
 320
 321                 /* the previous tile will be needed for transition cost calculations */
 322                 TILE prev = !has_parent ? TILE() : TILE(n.m_parent->GetLastTile(), n.m_parent->GetLastTrackdir());
 323
 324                 EndSegmentReasonBits end_segment_reason = ESRB_NONE;
 325
 326                 TrackFollower tf_local(v, Yapf().GetCompatibleRailTypes(), &Yapf().m_perf_ts_cost);
 327
 328                 if (!has_parent) {
 329                         /* We will jump to the middle of the cost calculator assuming that segment cache is not used. */
 330                         assert(!is_cached_segment);
 331                         /* Skip the first transition cost calculation. */
 332                         goto no_entry_cost;
 333                 }
 334
 335                 for (;;) {
 336                         /* Transition cost (cost of the move from previous tile) */
 337                         transition_cost = Yapf().CurveCost(prev.td, cur.td);
 338                         transition_cost += Yapf().SwitchCost(prev.tile, cur.tile, TrackdirToExitdir(prev.td));
 339
 340                         /* First transition cost counts against segment entry cost, other transitions
 341                          * inside segment will come to segment cost (and will be cached) */
 342                         if (segment_cost == 0) {
 343                                 /* We just entered the loop. First transition cost goes to segment entry cost)*/
 344                                 segment_entry_cost = transition_cost;
 345                                 transition_cost = 0;
 346
 347                                 /* It is the right time now to look if we can reuse the cached segment cost. */
 348                                 if (is_cached_segment) {
 349                                         /* Yes, we already know the segment cost. */
 350                                         segment_cost = segment.m_cost;
 351                                         /* We know also the reason why the segment ends. */
 352                                         end_segment_reason = segment.m_end_segment_reason;
 353                                         /* We will need also some information about the last signal (if it was red). */
 354                                         if (segment.m_last_signal_tile != INVALID_TILE) {
 355                                                 assert(HasSignalOnTrackdir(segment.m_last_signal_tile, segment.m_last_signal_td));
 356                                                 SignalState sig_state = GetSignalStateByTrackdir(segment.m_last_signal_tile, segment.m_last_signal_td);
 357                                                 bool is_red = (sig_state == SIGNAL_STATE_RED);
 358                                                 n.flags_u.flags_s.m_last_signal_was_red = is_red;
 359                                                 if (is_red) {
 360                                                         n.m_last_red_signal_type = GetSignalType(segment.m_last_signal_tile, TrackdirToTrack(segment.m_last_signal_td));
 361                                                 }
 362                                         }
 363                                         /* No further calculation needed. */
 364                                         cur = TILE(n.GetLastTile(), n.GetLastTrackdir());
 365                                         break;
 366                                 }
 367                         } else {
 368                                 /* Other than first transition cost count as the regular segment cost. */
 369                                 segment_cost += transition_cost;
 370                         }
 371
 372 no_entry_cost: // jump here at the beginning if the node has no parent (it is the first node)
 373
 374                         /* All other tile costs will be calculated here. */
 375                         segment_cost += Yapf().OneTileCost(cur.tile, cur.td);
 376
 377                         /* If we skipped some tunnel/bridge/station tiles, add their base cost */
 378                         segment_cost += YAPF_TILE_LENGTH * tf->m_tiles_skipped;
 379
 380                         /* Slope cost. */
 381                         segment_cost += Yapf().SlopeCost(cur.tile, cur.td);
 382
 383                         /* Signal cost (routine can modify segment data). */
 384                         segment_cost += Yapf().SignalCost(n, cur.tile, cur.td);
 385
 386                         /* Reserved tiles. */
 387                         segment_cost += Yapf().ReservationCost(n, cur.tile, cur.td, tf->m_tiles_skipped);
 388
 389                         end_segment_reason = segment.m_end_segment_reason;
 390
 391                         /* Tests for 'potential target' reasons to close the segment. */
 392                         if (cur.tile == prev.tile) {
 393                                 /* Penalty for reversing in a depot. */
 394                                 assert(IsRailDepot(cur.tile));
 395                                 segment_cost += Yapf().PfGetSettings().rail_depot_reverse_penalty;
 396
 397                         } else if (IsRailDepotTile(cur.tile)) {
 398                                 /* We will end in this pass (depot is possible target) */
 399                                 end_segment_reason |= ESRB_DEPOT;
 400
 401                         } else if (cur.tile_type == MP_STATION && IsRailWaypoint(cur.tile)) {
 402                                 if (v->current_order.IsType(OT_GOTO_WAYPOINT) &&
 403                                                 GetStationIndex(cur.tile) == v->current_order.GetDestination() &&
 404                                                 !Waypoint::Get(v->current_order.GetDestination())->IsSingleTile()) {
 405                                         /* This waypoint is our destination; maybe this isn't an unreserved
 406                                          * one, so check that and if so see that as the last signal being
 407                                          * red. This way waypoints near stations should work better. */
 408                                         CFollowTrackRail ft(v);
 409                                         TileIndex t = cur.tile;
 410                                         Trackdir td = cur.td;
 411                                         /* Arbitrary maximum tiles to follow to avoid infinite loops. */
 412                                         uint max_tiles = 20;
 413                                         while (ft.Follow(t, td)) {
 414                                                 assert(t != ft.m_new_tile);
 415                                                 t = ft.m_new_tile;
 416                                                 if (t == cur.tile || --max_tiles == 0) {
 417                                                         /* We looped back on ourself or found another loop, bail out. */
 418                                                         td = INVALID_TRACKDIR;
 419                                                         break;
 420                                                 }
 421                                                 if (KillFirstBit(ft.m_new_td_bits) != TRACKDIR_BIT_NONE) {
 422                                                         /* We encountered a junction; it's going to be too complex to
 423                                                          * handle this perfectly, so just bail out. There is no simple
 424                                                          * free path, so try the other possibilities. */
 425                                                         td = INVALID_TRACKDIR;
 426                                                         break;
 427                                                 }
 428                                                 td = RemoveFirstTrackdir(&ft.m_new_td_bits);
 429                                                 /* If this is a safe waiting position we're done searching for it */
 430                                                 if (IsSafeWaitingPosition(v, t, td, true, _settings_game.pf.forbid_90_deg)) break;
 431                                         }
 432
 433                                         /* In the case this platform is (possibly) occupied we add penalty so the
 434                                          * other platforms of this waypoint are evaluated as well, i.e. we assume
 435                                          * that there is a red signal in the waypoint when it's occupied. */
 436                                         if (td == INVALID_TRACKDIR ||
 437                                                         !IsSafeWaitingPosition(v, t, td, true, _settings_game.pf.forbid_90_deg) ||
 438                                                         !IsWaitingPositionFree(v, t, td, _settings_game.pf.forbid_90_deg)) {
 439                                                 extra_cost += Yapf().PfGetSettings().rail_lastred_penalty;
 440                                         }
 441                                 }
 442                                 /* Waypoint is also a good reason to finish. */
 443                                 end_segment_reason |= ESRB_WAYPOINT;
 444
 445                         } else if (tf->m_is_station) {
 446                                 /* Station penalties. */
 447                                 uint platform_length = tf->m_tiles_skipped + 1;
 448                                 /* We don't know yet if the station is our target or not. Act like
 449                                  * if it is pass-through station (not our destination). */
 450                                 segment_cost += Yapf().PfGetSettings().rail_station_penalty * platform_length;
 451                                 /* We will end in this pass (station is possible target) */
 452                                 end_segment_reason |= ESRB_STATION;
 453
 454                         } else if (TrackFollower::DoTrackMasking() && cur.tile_type == MP_RAILWAY) {
 455                                 /* Searching for a safe tile? */
 456                                 if (HasSignalOnTrackdir(cur.tile, cur.td) && !IsPbsSignal(GetSignalType(cur.tile, TrackdirToTrack(cur.td)))) {
 457                                         end_segment_reason |= ESRB_SAFE_TILE;
 458                                 }
 459                         }
 460
 461                         /* Apply min/max speed penalties only when inside the look-ahead radius. Otherwise
 462                          * it would cause desync in MP. */
 463                         if (n.m_num_signals_passed < m_sig_look_ahead_costs.Size())
 464                         {
 465                                 int min_speed = 0;
 466                                 int max_speed = tf->GetSpeedLimit(&min_speed);
 467                                 int max_veh_speed = v->GetDisplayMaxSpeed();
 468                                 if (max_speed < max_veh_speed) {
 469                                         extra_cost += YAPF_TILE_LENGTH * (max_veh_speed - max_speed) * (4 + tf->m_tiles_skipped) / max_veh_speed;
 470                                 }
 471                                 if (min_speed > max_veh_speed) {
 472                                         extra_cost += YAPF_TILE_LENGTH * (min_speed - max_veh_speed);
 473                                 }
 474                         }
 475
 476                         /* Finish if we already exceeded the maximum path cost (i.e. when
 477                          * searching for the nearest depot). */
 478                         if (m_max_cost > 0 && (parent_cost + segment_entry_cost + segment_cost) > m_max_cost) {
 479                                 end_segment_reason |= ESRB_PATH_TOO_LONG;
 480                         }
 481
 482                         /* Move to the next tile/trackdir. */
 483                         tf = &tf_local;
 484                         tf_local.Init(v, Yapf().GetCompatibleRailTypes(), &Yapf().m_perf_ts_cost);
 485
 486                         if (!tf_local.Follow(cur.tile, cur.td)) {
 487                                 assert(tf_local.m_err != TrackFollower::EC_NONE);
 488                                 /* Can't move to the next tile (EOL?). */
 489                                 if (tf_local.m_err == TrackFollower::EC_RAIL_ROAD_TYPE) {
 490                                         end_segment_reason |= ESRB_RAIL_TYPE;
 491                                 } else {
 492                                         end_segment_reason |= ESRB_DEAD_END;
 493                                 }
 494
 495                                 if (TrackFollower::DoTrackMasking() && !HasOnewaySignalBlockingTrackdir(cur.tile, cur.td)) {
 496                                         end_segment_reason |= ESRB_SAFE_TILE;
 497                                 }
 498                                 break;
 499                         }
 500
 501                         /* Check if the next tile is not a choice. */
 502                         if (KillFirstBit(tf_local.m_new_td_bits) != TRACKDIR_BIT_NONE) {
 503                                 /* More than one segment will follow. Close this one. */
 504                                 end_segment_reason |= ESRB_CHOICE_FOLLOWS;
 505                                 break;
 506                         }
 507
 508                         /* Gather the next tile/trackdir/tile_type/rail_type. */
 509                         TILE next(tf_local.m_new_tile, (Trackdir)FindFirstBit2x64(tf_local.m_new_td_bits));
 510
 511                         if (TrackFollower::DoTrackMasking() && IsTileType(next.tile, MP_RAILWAY)) {
 512                                 if (HasSignalOnTrackdir(next.tile, next.td) && IsPbsSignal(GetSignalType(next.tile, TrackdirToTrack(next.td)))) {
 513                                         /* Possible safe tile. */
 514                                         end_segment_reason |= ESRB_SAFE_TILE;
 515                                 } else if (HasSignalOnTrackdir(next.tile, ReverseTrackdir(next.td)) && GetSignalType(next.tile, TrackdirToTrack(next.td)) == SIGTYPE_PBS_ONEWAY) {
 516                                         /* Possible safe tile, but not so good as it's the back of a signal... */
 517                                         end_segment_reason |= ESRB_SAFE_TILE | ESRB_DEAD_END;
 518                                         extra_cost += Yapf().PfGetSettings().rail_lastred_exit_penalty;
 519                                 }
 520                         }
 521
 522                         /* Check the next tile for the rail type. */
 523                         if (next.rail_type != cur.rail_type) {
 524                                 /* Segment must consist from the same rail_type tiles. */
 525                                 end_segment_reason |= ESRB_RAIL_TYPE;
 526                                 break;
 527                         }
 528
 529                         /* Avoid infinite looping. */
 530                         if (next.tile == n.m_key.m_tile && next.td == n.m_key.m_td) {
 531                                 end_segment_reason |= ESRB_INFINITE_LOOP;
 532                                 break;
 533                         }
 534
 535                         if (segment_cost > s_max_segment_cost) {
 536                                 /* Potentially in the infinite loop (or only very long segment?). We should
 537                                  * not force it to finish prematurely unless we are on a regular tile. */
 538                                 if (IsTileType(tf->m_new_tile, MP_RAILWAY)) {
 539                                         end_segment_reason |= ESRB_SEGMENT_TOO_LONG;
 540                                         break;
 541                                 }
 542                         }
 543
 544                         /* Any other reason bit set? */
 545                         if (end_segment_reason != ESRB_NONE) {
 546                                 break;
 547                         }
 548
 549                         /* For the next loop set new prev and cur tile info. */
 550                         prev = cur;
 551                         cur = next;
 552
 553                 } // for (;;)
 554
 555                 /* Don't consider path any further it if exceeded max_cost. */
 556                 if (end_segment_reason & ESRB_PATH_TOO_LONG) return false;
 557
 558                 bool target_seen = false;
 559                 if ((end_segment_reason & ESRB_POSSIBLE_TARGET) != ESRB_NONE) {
 560                         /* Depot, station or waypoint. */
 561                         if (Yapf().PfDetectDestination(cur.tile, cur.td)) {
 562                                 /* Destination found. */
 563                                 target_seen = true;
 564                         }
 565                 }
 566
 567                 /* Update the segment if needed. */
 568                 if (!is_cached_segment) {
 569                         /* Write back the segment information so it can be reused the next time. */
 570                         segment.m_cost = segment_cost;
 571                         segment.m_end_segment_reason = end_segment_reason & ESRB_CACHED_MASK;
 572                         /* Save end of segment back to the node. */
 573                         n.SetLastTileTrackdir(cur.tile, cur.td);
 574                 }
 575
 576                 /* Do we have an excuse why not to continue pathfinding in this direction? */
 577                 if (!target_seen && (end_segment_reason & ESRB_ABORT_PF_MASK) != ESRB_NONE) {
 578                         /* Reason to not continue. Stop this PF branch. */
 579                         return false;
 580                 }
 581
 582                 /* Special costs for the case we have reached our target. */
 583                 if (target_seen) {
 584                         n.flags_u.flags_s.m_targed_seen = true;
 585                         /* Last-red and last-red-exit penalties. */
 586                         if (n.flags_u.flags_s.m_last_signal_was_red) {
 587                                 if (n.m_last_red_signal_type == SIGTYPE_EXIT) {
 588                                         /* last signal was red pre-signal-exit */
 589                                         extra_cost += Yapf().PfGetSettings().rail_lastred_exit_penalty;
 590                                 } else if (!IsPbsSignal(n.m_last_red_signal_type)) {
 591                                         /* Last signal was red, but not exit or path signal. */
 592                                         extra_cost += Yapf().PfGetSettings().rail_lastred_penalty;
 593                                 }
 594                         }
 595
 596                         /* Station platform-length penalty. */
 597                         if ((end_segment_reason & ESRB_STATION) != ESRB_NONE) {
 598                                 const BaseStation *st = BaseStation::GetByTile(n.GetLastTile());
 599                                 assert(st != nullptr);
 600                                 uint platform_length = st->GetPlatformLength(n.GetLastTile(), ReverseDiagDir(TrackdirToExitdir(n.GetLastTrackdir())));
 601                                 /* Reduce the extra cost caused by passing-station penalty (each station receives it in the segment cost). */
 602                                 extra_cost -= Yapf().PfGetSettings().rail_station_penalty * platform_length;
 603                                 /* Add penalty for the inappropriate platform length. */
 604                                 extra_cost += PlatformLengthPenalty(platform_length);
 605                         }
 606                 }
 607
 608                 /* total node cost */
 609                 n.m_cost = parent_cost + segment_entry_cost + segment_cost + extra_cost;
 610
 611                 return true;
 612         }
 613
 614         inline bool CanUseGlobalCache(Node &n) const
 615         {
 616                 return !m_disable_cache
 617                         && (n.m_parent != nullptr)
 618                         && (n.m_parent->m_num_signals_passed >= m_sig_look_ahead_costs.Size());
 619         }
 620
 621         inline void ConnectNodeToCachedData(Node &n, CachedData &ci)
 622         {
 623                 n.m_segment = &ci;
 624                 if (n.m_segment->m_cost < 0) {
 625                         n.m_segment->m_last_tile = n.m_key.m_tile;
 626                         n.m_segment->m_last_td = n.m_key.m_td;
 627                 }
 628         }
 629
 630         void DisableCache(bool disable)
 631         {
 632                 m_disable_cache = disable;
 633         }
 634 };
 635
 636 #endif /* YAPF_COSTRAIL_HPP */