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