10#ifndef YAPF_COSTRAIL_HPP
11#define YAPF_COSTRAIL_HPP
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;
50 bool disable_cache =
false;
51 std::vector<int> sig_look_ahead_costs = {};
52 bool treat_first_red_two_way_signal_as_eol =
false;
55 bool stopped_on_first_two_way_signal =
false;
58 static constexpr int MAX_SEGMENT_COST = 10000;
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));
76 return *
static_cast<Tpf *
>(
this);
86 this->treat_first_red_two_way_signal_as_eol = enabled;
95 return Yapf().PfGetSettings().rail_firstred_twoway_eol && this->treat_first_red_two_way_signal_as_eol;
101 return Yapf().PfGetSettings().rail_slope_penalty;
109 if (TrackFollower::Allow90degTurns()
112 cost +=
Yapf().PfGetSettings().rail_curve90_penalty;
115 cost +=
Yapf().PfGetSettings().rail_curve45_penalty;
125 if (t1 && t2)
return Yapf().PfGetSettings().rail_doubleslip_penalty;
146 cost +=
Yapf().PfGetSettings().rail_crossing_penalty;
170 for (; distance >= 0; distance--, tile += diff) {
186 if (n.num_signals_passed >= this->sig_look_ahead_costs.size() / 2)
return 0;
190 return Yapf().PfGetSettings().rail_pbs_station_penalty * (skipped + 1);
192 int cost =
Yapf().PfGetSettings().rail_pbs_cross_penalty;
194 return cost * (skipped + 1);
210 if (has_signal_along) {
214 n.last_signal_type = sig_type;
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;
220 n.flags_u.flags_s.last_signal_was_red =
false;
222 if (look_ahead_cost < 0) {
224 cost -= look_ahead_cost;
231 Yapf().PruneIntermediateNodeBranch(&n);
233 Yapf().stopped_on_first_two_way_signal =
true;
236 n.last_red_signal_type = sig_type;
237 n.flags_u.flags_s.last_signal_was_red =
true;
240 if (!
IsPbsSignal(sig_type) && look_ahead_cost > 0) {
242 cost += look_ahead_cost;
246 if (n.num_signals_passed == 0) {
257 n.num_signals_passed++;
258 n.segment->last_signal_tile = tile;
259 n.segment->last_signal_td = trackdir;
263 cost += n.num_signals_passed <
Yapf().PfGetSettings().rail_look_ahead_max_signals ?
Yapf().PfGetSettings().rail_pbs_signal_back_penalty : 0;
270 inline int PlatformLengthPenalty(
int platform_length)
274 assert(v !=
nullptr);
278 if (missing_platform_length < 0) {
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) {
283 cost +=
Yapf().PfGetSettings().rail_shorter_platform_penalty +
Yapf().PfGetSettings().rail_shorter_platform_per_tile_penalty * missing_platform_length;
289 inline void SetMaxCost(
int max_cost)
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));
302 bool has_parent = (n.parent !=
nullptr);
305 CachedData &segment = *n.segment;
306 bool is_cached_segment = (segment.cost >= 0);
308 int parent_cost = has_parent ? n.parent->cost : 0;
329 int transition_cost = 0;
337 int segment_entry_cost = 0;
338 int segment_cost = 0;
343 TILE cur(n.key.tile, n.key.td);
346 TILE prev = !has_parent ?
TILE() :
TILE(n.parent->GetLastTile(), n.parent->GetLastTrackdir());
350 TrackFollower follower_local{v,
Yapf().GetCompatibleRailTypes()};
354 assert(!is_cached_segment);
361 transition_cost =
Yapf().CurveCost(prev.td, cur.td);
366 if (segment_cost == 0) {
368 segment_entry_cost = transition_cost;
371 if (is_cached_segment) {
373 segment_cost = segment.cost;
375 end_segment_reason = segment.end_segment_reason;
381 n.flags_u.flags_s.last_signal_was_red = is_red;
387 cur =
TILE(n.GetLastTile(), n.GetLastTrackdir());
392 segment_cost += transition_cost;
398 segment_cost +=
Yapf().OneTileCost(cur.tile, cur.td);
404 segment_cost +=
Yapf().SlopeCost(cur.tile, cur.td);
407 segment_cost +=
Yapf().SignalCost(n, cur.tile, cur.td);
410 segment_cost +=
Yapf().ReservationCost(n, cur.tile, cur.td, follower->tiles_skipped);
412 end_segment_reason = segment.end_segment_reason;
415 if (cur.tile == prev.tile) {
418 segment_cost +=
Yapf().PfGetSettings().rail_depot_reverse_penalty;
431 CFollowTrackRail ft(v);
436 while (ft.
Follow(t, td)) {
439 if (t == cur.tile || --max_tiles == 0) {
462 extra_cost +=
Yapf().PfGetSettings().rail_lastred_penalty;
468 }
else if (follower->is_station) {
470 uint platform_length = follower->tiles_skipped + 1;
473 segment_cost +=
Yapf().PfGetSettings().rail_station_penalty * platform_length;
477 }
else if (TrackFollower::DoTrackMasking() && cur.tile_type ==
TileType::Railway) {
486 if (n.num_signals_passed < this->sig_look_ahead_costs.size())
489 int max_speed = follower->GetSpeedLimit(&min_speed);
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;
494 if (min_speed > max_veh_speed) {
501 if (this->max_cost > 0 && (parent_cost + segment_entry_cost + segment_cost) > this->max_cost) {
506 follower = &follower_local;
507 follower_local.Init(v,
Yapf().GetCompatibleRailTypes());
509 if (!follower_local.Follow(cur.tile, cur.td)) {
510 assert(follower_local.err != TrackFollower::ErrorCode::None);
512 if (follower_local.err == TrackFollower::ErrorCode::RailRoadType) {
525 if (follower_local.new_td_bits.Count() > 1) {
532 TILE next(follower_local.new_tile, follower_local.new_td_bits.GetNthSetBit(0).value());
541 extra_cost +=
Yapf().PfGetSettings().rail_lastred_exit_penalty;
546 if (next.rail_type != cur.rail_type) {
553 if (next.tile == n.key.tile && next.td == n.key.td) {
558 if (segment_cost > MAX_SEGMENT_COST) {
568 if (end_segment_reason.
Any()) {
581 bool target_seen =
false;
584 if (
Yapf().PfDetectDestination(cur.tile, cur.td)) {
591 if (!is_cached_segment) {
593 segment.cost = segment_cost;
596 n.SetLastTileTrackdir(cur.tile, cur.td);
607 n.flags_u.flags_s.target_seen =
true;
609 if (n.flags_u.flags_s.last_signal_was_red) {
612 extra_cost +=
Yapf().PfGetSettings().rail_lastred_exit_penalty;
615 extra_cost +=
Yapf().PfGetSettings().rail_lastred_penalty;
622 assert(st !=
nullptr);
625 extra_cost -=
Yapf().PfGetSettings().rail_station_penalty * platform_length;
627 extra_cost += PlatformLengthPenalty(platform_length);
632 n.cost = parent_cost + segment_entry_cost + segment_cost + extra_cost;
637 inline bool CanUseGlobalCache(Node &n)
const
639 return !this->disable_cache
640 && (n.parent !=
nullptr)
641 && (n.parent->num_signals_passed >= this->sig_look_ahead_costs.size());
644 inline void ConnectNodeToCachedData(
Node &n, CachedData &ci)
647 if (n.segment->cost < 0) {
648 n.segment->last_tile = n.key.tile;
649 n.segment->last_td = n.key.td;
653 void DisableCache(
bool disable)
655 this->disable_cache = disable;
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.
int32_t TileIndexDiff
An offset value between two tiles.
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.
bool IsWaitingPositionFree(const Train *v, TileIndex tile, Trackdir trackdir, bool forbid_90deg)
Check if a safe position is free.
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.
RailType GetTileRailType(Tile tile)
Return the rail type of tile, or INVALID_RAILTYPE if this is no rail tile.
bool HasOnewaySignalBlockingTrackdir(Tile tile, Trackdir td)
Is a one-way signal blocking the trackdir?
bool HasSignalOnTrackdir(Tile tile, Trackdir trackdir)
Checks for the presence of signals along the given trackdir on the given rail tile.
static bool IsRailDepot(Tile t)
Is this rail tile a rail depot?
TrackBits GetTrackBits(Tile tile)
Gets the track bits of the given tile.
static bool IsPlainRailTile(Tile t)
Checks whether the tile is a rail tile or rail tile with signals.
bool IsPbsSignal(SignalType s)
Checks whether the given signal is a path based signal.
bool IsOnewaySignal(Tile t, Track track)
Is the signal at the given track on a tile a one way signal?
SignalType GetSignalType(Tile t, Track track)
Get the signal type for a track on a tile.
SignalState GetSignalStateByTrackdir(Tile tile, Trackdir trackdir)
Gets the state of the signal along the given trackdir.
static bool IsRailDepotTile(Tile t)
Is this tile rail tile and a rail depot?
RailType
Enumeration for all possible railtypes.
@ INVALID_RAILTYPE
Flag for invalid railtype.
bool IsLevelCrossing(Tile t)
Return whether a tile is a level crossing.
GameSettings _settings_game
Game settings of a running game or the scenario editor.
SignalType
Type of signal, i.e.
@ Entry
presignal block entry.
@ PathOneWay
no-entry path signal.
@ Combo
presignal inter-block.
@ Exit
presignal block exit.
SignalState
These are states in which a signal can be.
@ 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.
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.
DestinationID GetDestination() const
Gets the destination of this order.
bool IsType(OrderType type) const
Check whether this order is of the given type.
static Waypoint * Get(auto index)
'Train' is either a loco or a wagon.
int GetDisplayMaxSpeed() const override
Gets the maximum speed in km-ish/h that can be sent into string parameters for string processing.
Order current_order
The current order (+ status, like: loading).
static bool IsTileType(Tile tile, TileType type)
Checks if a tile is a given tiletype.
static TileType GetTileType(Tile tile)
Get the tiletype of a given tile.
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.
constexpr TileIndex INVALID_TILE
The very nice invalid tile marker.
static constexpr uint TILE_SIZE
Tile size in world coordinates.
TileType
The different types of tiles.
@ Station
A tile of a station or airport.
@ Railway
A tile with railway.
@ Void
Invisible tiles at the SW and SE border.
@ Road
A tile with road and/or tram tracks.
Track TrackdirToTrack(Trackdir trackdir)
Returns the Track that a given Trackdir represents.
bool TrackOverlapsTracks(TrackBits tracks, Track track)
Check if a given track is contained within or overlaps some other tracks.
Trackdir NextTrackdir(Trackdir trackdir)
Maps a trackdir to the trackdir that you will end up on if you go straight ahead.
Trackdir ReverseTrackdir(Trackdir trackdir)
Maps a trackdir to the reverse trackdir.
bool IsValidTrackdir(Trackdir trackdir)
Checks if a Trackdir is valid for non-road vehicles.
TrackdirBits TrackdirCrossesTrackdirs(Trackdir trackdir)
Maps a trackdir to all trackdirs that make 90 deg turns with it.
Trackdir RemoveFirstTrackdir(TrackdirBits &trackdirs)
Removes first Trackdir from TrackdirBits and returns it.
bool IsDiagonalTrackdir(Trackdir trackdir)
Checks if a given Trackdir is diagonal.
TrackBits DiagdirReachesTracks(DiagDirection diagdir)
Returns all tracks that can be reached when entering a tile from a given (diagonal) direction.
DiagDirection TrackdirToExitdir(Trackdir trackdir)
Maps a trackdir to the (4-way) direction the tile is exited when following that trackdir.
Trackdir
Enumeration for tracks and directions.
@ Invalid
Flag for an invalid trackdir.
@ Train
Train vehicle type.
Handling of cost determination.
static constexpr EndSegmentReasons ESRF_ABORT_PF_MASK
Reasons to abort pathfinding in this direction.
static constexpr EndSegmentReasons ESRF_CACHED_MASK
What reasons can be stored back into cached segment.
EnumBitSet< EndSegmentReason, uint16_t > EndSegmentReasons
Bitset of EndSegmentReason elements.
@ SegmentTooLong
the segment is too long (possible infinite loop)
@ ChoiceFollows
the next tile contains a choice (the track splits to more than one segments)
@ Waypoint
waypoint encountered (could be a target next time)
@ Station
station encountered (could be a target next time)
@ RailType
the next tile has a different rail type than our tiles
@ InfiniteLoop
infinite loop detected
@ Depot
stop in the depot (could be a target next time)
@ SafeTile
safe waiting position found (could be a target)
@ PathTooLong
the path is too long (searching for the nearest depot in the given radius)
static constexpr EndSegmentReasons ESRF_POSSIBLE_TARGET
What reasons mean that the target can be found and needs to be detected.