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