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