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