10 #ifndef YAPF_COSTRAIL_HPP
11 #define YAPF_COSTRAIL_HPP
14 #include "../../pbs.h"
15 #include "../follow_track.hpp"
16 #include "../pathfinder_type.h"
20 template <
class Types>
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;
50 std::vector<int> sig_look_ahead_costs;
53 bool stopped_on_first_two_way_signal;
56 static constexpr
int MAX_SEGMENT_COST = 10000;
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));
74 return *
static_cast<Tpf *
>(
this);
81 return Yapf().PfGetSettings().rail_slope_penalty;
89 if (TrackFollower::Allow90degTurns()
92 cost +=
Yapf().PfGetSettings().rail_curve90_penalty;
95 cost +=
Yapf().PfGetSettings().rail_curve45_penalty;
105 if (t1 && t2)
return Yapf().PfGetSettings().rail_doubleslip_penalty;
121 cost +=
Yapf().PfGetSettings().rail_crossing_penalty;
139 for (; skipped >= 0; skipped--, tile += diff) {
148 if (n.num_signals_passed >= this->sig_look_ahead_costs.size() / 2)
return 0;
149 if (!IsPbsSignal(n.last_signal_type))
return 0;
152 return Yapf().PfGetSettings().rail_pbs_station_penalty * (skipped + 1);
154 int cost =
Yapf().PfGetSettings().rail_pbs_cross_penalty;
156 return cost * (skipped + 1);
170 n.segment->end_segment_reason |= ESRB_DEAD_END;
172 if (has_signal_along) {
176 n.last_signal_type = sig_type;
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;
182 n.flags_u.flags_s.last_signal_was_red =
false;
184 if (look_ahead_cost < 0) {
186 cost -= look_ahead_cost;
191 if (!IsPbsSignal(sig_type) &&
Yapf().TreatFirstRedTwoWaySignalAsEOL() && n.flags_u.flags_s.choice_seen && has_signal_against && n.num_signals_passed == 0) {
193 Yapf().PruneIntermediateNodeBranch(&n);
194 n.segment->end_segment_reason |= ESRB_DEAD_END;
195 Yapf().stopped_on_first_two_way_signal =
true;
198 n.last_red_signal_type = sig_type;
199 n.flags_u.flags_s.last_signal_was_red =
true;
202 if (!IsPbsSignal(sig_type) && look_ahead_cost > 0) {
204 cost += look_ahead_cost;
208 if (n.num_signals_passed == 0) {
211 case SIGTYPE_EXIT: cost +=
Yapf().PfGetSettings().rail_firstred_exit_penalty;
break;
219 n.num_signals_passed++;
220 n.segment->last_signal_tile = tile;
221 n.segment->last_signal_td = trackdir;
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;
232 inline int PlatformLengthPenalty(
int platform_length)
236 assert(v !=
nullptr);
240 if (missing_platform_length < 0) {
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) {
245 cost +=
Yapf().PfGetSettings().rail_shorter_platform_penalty +
Yapf().PfGetSettings().rail_shorter_platform_per_tile_penalty * missing_platform_length;
251 inline void SetMaxCost(
int max_cost)
263 assert(!n.flags_u.flags_s.target_seen);
264 assert(tf->new_tile == n.key.tile);
268 bool has_parent = (n.parent !=
nullptr);
271 CachedData &segment = *n.segment;
272 bool is_cached_segment = (segment.cost >= 0);
274 int parent_cost = has_parent ? n.parent->cost : 0;
295 int transition_cost = 0;
303 int segment_entry_cost = 0;
304 int segment_cost = 0;
309 TILE cur(n.key.tile, n.key.td);
312 TILE prev = !has_parent ?
TILE() :
TILE(n.parent->GetLastTile(), n.parent->GetLastTrackdir());
314 EndSegmentReasonBits end_segment_reason = ESRB_NONE;
316 TrackFollower tf_local(v,
Yapf().GetCompatibleRailTypes());
320 assert(!is_cached_segment);
327 transition_cost =
Yapf().CurveCost(prev.td, cur.td);
332 if (segment_cost == 0) {
334 segment_entry_cost = transition_cost;
338 if (is_cached_segment) {
340 segment_cost = segment.cost;
342 end_segment_reason = segment.end_segment_reason;
348 n.flags_u.flags_s.last_signal_was_red = is_red;
350 n.last_red_signal_type = GetSignalType(segment.last_signal_tile,
TrackdirToTrack(segment.last_signal_td));
354 cur =
TILE(n.GetLastTile(), n.GetLastTrackdir());
359 segment_cost += transition_cost;
365 segment_cost +=
Yapf().OneTileCost(cur.tile, cur.td);
371 segment_cost +=
Yapf().SlopeCost(cur.tile, cur.td);
374 segment_cost +=
Yapf().SignalCost(n, cur.tile, cur.td);
377 segment_cost +=
Yapf().ReservationCost(n, cur.tile, cur.td, tf->tiles_skipped);
379 end_segment_reason = segment.end_segment_reason;
382 if (cur.tile == prev.tile) {
385 segment_cost +=
Yapf().PfGetSettings().rail_depot_reverse_penalty;
389 end_segment_reason |= ESRB_DEPOT;
403 while (ft.
Follow(t, td)) {
406 if (t == cur.tile || --max_tiles == 0) {
429 extra_cost +=
Yapf().PfGetSettings().rail_lastred_penalty;
433 end_segment_reason |= ESRB_WAYPOINT;
435 }
else if (tf->is_station) {
437 uint platform_length = tf->tiles_skipped + 1;
440 segment_cost +=
Yapf().PfGetSettings().rail_station_penalty * platform_length;
442 end_segment_reason |= ESRB_STATION;
444 }
else if (TrackFollower::DoTrackMasking() && cur.tile_type ==
MP_RAILWAY) {
447 end_segment_reason |= ESRB_SAFE_TILE;
453 if (n.num_signals_passed < this->sig_look_ahead_costs.size())
456 int max_speed = tf->GetSpeedLimit(&min_speed);
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;
461 if (min_speed > max_veh_speed) {
468 if (this->max_cost > 0 && (parent_cost + segment_entry_cost + segment_cost) > this->
max_cost) {
469 end_segment_reason |= ESRB_PATH_TOO_LONG;
474 tf_local.Init(v,
Yapf().GetCompatibleRailTypes());
476 if (!tf_local.Follow(cur.tile, cur.td)) {
477 assert(tf_local.err != TrackFollower::EC_NONE);
479 if (tf_local.err == TrackFollower::EC_RAIL_ROAD_TYPE) {
480 end_segment_reason |= ESRB_RAIL_TYPE;
482 end_segment_reason |= ESRB_DEAD_END;
486 end_segment_reason |= ESRB_SAFE_TILE;
494 end_segment_reason |= ESRB_CHOICE_FOLLOWS;
504 end_segment_reason |= ESRB_SAFE_TILE;
507 end_segment_reason |= ESRB_SAFE_TILE | ESRB_DEAD_END;
508 extra_cost +=
Yapf().PfGetSettings().rail_lastred_exit_penalty;
513 if (next.rail_type != cur.rail_type) {
515 end_segment_reason |= ESRB_RAIL_TYPE;
520 if (next.tile == n.key.tile && next.td == n.key.td) {
521 end_segment_reason |= ESRB_INFINITE_LOOP;
525 if (segment_cost > MAX_SEGMENT_COST) {
529 end_segment_reason |= ESRB_SEGMENT_TOO_LONG;
535 if (end_segment_reason != ESRB_NONE) {
546 if (end_segment_reason & ESRB_PATH_TOO_LONG)
return false;
548 bool target_seen =
false;
549 if ((end_segment_reason & ESRB_POSSIBLE_TARGET) != ESRB_NONE) {
551 if (
Yapf().PfDetectDestination(cur.tile, cur.td)) {
558 if (!is_cached_segment) {
560 segment.cost = segment_cost;
561 segment.end_segment_reason = end_segment_reason & ESRB_CACHED_MASK;
563 n.SetLastTileTrackdir(cur.tile, cur.td);
567 if (!target_seen && (end_segment_reason & ESRB_ABORT_PF_MASK) != ESRB_NONE) {
574 n.flags_u.flags_s.target_seen =
true;
576 if (n.flags_u.flags_s.last_signal_was_red) {
579 extra_cost +=
Yapf().PfGetSettings().rail_lastred_exit_penalty;
580 }
else if (!IsPbsSignal(n.last_red_signal_type)) {
582 extra_cost +=
Yapf().PfGetSettings().rail_lastred_penalty;
587 if ((end_segment_reason & ESRB_STATION) != ESRB_NONE) {
589 assert(st !=
nullptr);
592 extra_cost -=
Yapf().PfGetSettings().rail_station_penalty * platform_length;
594 extra_cost += PlatformLengthPenalty(platform_length);
599 n.cost = parent_cost + segment_entry_cost + segment_cost + extra_cost;
604 inline bool CanUseGlobalCache(
Node &n)
const
606 return !this->disable_cache
607 && (n.parent !=
nullptr)
608 && (n.parent->num_signals_passed >= this->sig_look_ahead_costs.size());
611 inline void ConnectNodeToCachedData(
Node &n, CachedData &ci)
614 if (n.segment->cost < 0) {
615 n.segment->last_tile = n.key.tile;
616 n.segment->last_td = n.key.td;
620 void DisableCache(
bool disable)
622 this->disable_cache = disable;
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.
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.
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? A one-way signal on the trackdir against will block,...
bool HasSignalOnTrackdir(Tile tile, Trackdir trackdir)
Checks for the presence of signals along the given trackdir on the given rail tile.
TrackBits GetTrackBits(Tile tile)
Gets the track bits of the given tile.
static debug_inline bool IsRailDepotTile(Tile t)
Is this tile rail tile and a rail depot?
bool IsOnewaySignal(Tile t, Track track)
One-way signals can't be passed the 'wrong' way.
static debug_inline bool IsRailDepot(Tile t)
Is this rail tile a rail depot?
static debug_inline bool IsPlainRailTile(Tile t)
Checks whether the tile is a rail tile or rail tile with signals.
SignalState GetSignalStateByTrackdir(Tile tile, Trackdir trackdir)
Gets the state of the signal along the given trackdir.
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.
@ SIGTYPE_PBS_ONEWAY
no-entry signal
@ SIGTYPE_ENTRY
presignal block entry
@ SIGTYPE_COMBO
presignal inter-block
@ SIGTYPE_EXIT
presignal block exit
@ SIGTYPE_BLOCK
block signal
SignalState
These are states in which a signal can be.
@ SIGNAL_STATE_RED
The signal is red.
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.
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.
uint16_t GetMaxSpeed() const
Get the maxmimum 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.
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.
int GetDisplayMaxSpeed() const override
Gets the maximum speed in km-ish/h that can be sent into SetDParam for string processing.
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.
static debug_inline bool IsTileType(Tile tile, TileType type)
Checks if a tile is a given tiletype.
static const uint TILE_SIZE
Tile size in world coordinates.
constexpr TileIndex INVALID_TILE
The very nice invalid tile marker.
TileType
The different types of tiles.
@ MP_ROAD
A tile with road (or tram tracks)
@ MP_STATION
A tile of a station.
@ MP_VOID
Invisible tiles at the SW and SE border.
Trackdir RemoveFirstTrackdir(TrackdirBits *trackdirs)
Removes first Trackdir from TrackdirBits and returns it.
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.
bool IsDiagonalTrackdir(Trackdir trackdir)
Checks if a given Trackdir is diagonal.
bool HasTrackdir(TrackdirBits trackdirs, Trackdir trackdir)
Checks whether a TrackdirBits has a given Trackdir.
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.
@ TRACK_BIT_NONE
No track.
Trackdir
Enumeration for tracks and directions.
@ INVALID_TRACKDIR
Flag for an invalid trackdir.
@ TRACKDIR_BIT_NONE
No track build.
@ VEH_TRAIN
Train vehicle type.
Handling of cost determination.