10 #ifndef YAPF_COSTRAIL_HPP 11 #define YAPF_COSTRAIL_HPP 13 #include "../../pbs.h" 15 template <
class Types>
18 typedef typename Types::Tpf
Tpf;
19 typedef typename Types::TrackFollower TrackFollower;
20 typedef typename Types::NodeList::Titem
Node;
21 typedef typename Node::Key
Key;
22 typedef typename Node::CachedData CachedData;
60 bool m_stopped_on_first_two_way_signal;
63 static const int s_max_segment_cost = 10000;
65 CYapfCostRailT() : m_max_cost(0), m_disable_cache(false), m_stopped_on_first_two_way_signal(false)
68 int p0 =
Yapf().PfGetSettings().rail_look_ahead_signal_p0;
69 int p1 =
Yapf().PfGetSettings().rail_look_ahead_signal_p1;
70 int p2 =
Yapf().PfGetSettings().rail_look_ahead_signal_p2;
71 int *pen = m_sig_look_ahead_costs.
GrowSizeNC(
Yapf().PfGetSettings().rail_look_ahead_max_signals);
72 for (uint i = 0; i <
Yapf().PfGetSettings().rail_look_ahead_max_signals; i++) {
73 pen[i] = p0 + i * (p1 + i * p2);
80 return *
static_cast<Tpf *
>(
this);
88 return Yapf().PfGetSettings().rail_slope_penalty;
96 if (TrackFollower::Allow90degTurns()
99 cost +=
Yapf().PfGetSettings().rail_curve90_penalty;
102 cost +=
Yapf().PfGetSettings().rail_curve45_penalty;
112 if (t1 && t2)
return Yapf().PfGetSettings().rail_doubleslip_penalty;
128 cost +=
Yapf().PfGetSettings().rail_crossing_penalty;
146 for (; skipped >= 0; skipped--, tile += diff) {
155 if (n.m_num_signals_passed >= m_sig_look_ahead_costs.
Size() / 2)
return 0;
156 if (!IsPbsSignal(n.m_last_signal_type))
return 0;
159 return Yapf().PfGetSettings().rail_pbs_station_penalty * (skipped + 1);
161 int cost =
Yapf().PfGetSettings().rail_pbs_cross_penalty;
163 return cost * (skipped + 1);
178 n.m_segment->m_end_segment_reason |= ESRB_DEAD_END;
180 if (has_signal_along) {
184 n.m_last_signal_type = sig_type;
187 int look_ahead_cost = (n.m_num_signals_passed < m_sig_look_ahead_costs.
Size()) ? m_sig_look_ahead_costs.
Data()[n.m_num_signals_passed] : 0;
190 n.flags_u.flags_s.m_last_signal_was_red =
false;
192 if (look_ahead_cost < 0) {
194 cost -= look_ahead_cost;
199 if (!IsPbsSignal(sig_type) &&
Yapf().TreatFirstRedTwoWaySignalAsEOL() && n.flags_u.flags_s.m_choice_seen && has_signal_against && n.m_num_signals_passed == 0) {
201 Yapf().PruneIntermediateNodeBranch();
202 n.m_segment->m_end_segment_reason |= ESRB_DEAD_END;
203 Yapf().m_stopped_on_first_two_way_signal =
true;
206 n.m_last_red_signal_type = sig_type;
207 n.flags_u.flags_s.m_last_signal_was_red =
true;
210 if (!IsPbsSignal(sig_type) && look_ahead_cost > 0) {
212 cost += look_ahead_cost;
216 if (n.m_num_signals_passed == 0) {
219 case SIGTYPE_EXIT: cost +=
Yapf().PfGetSettings().rail_firstred_exit_penalty;
break;
227 n.m_num_signals_passed++;
228 n.m_segment->m_last_signal_tile = tile;
229 n.m_segment->m_last_signal_td = trackdir;
232 if (has_signal_against && IsPbsSignal(GetSignalType(tile,
TrackdirToTrack(trackdir)))) {
233 cost += n.m_num_signals_passed <
Yapf().PfGetSettings().rail_look_ahead_max_signals ?
Yapf().PfGetSettings().rail_pbs_signal_back_penalty : 0;
240 inline int PlatformLengthPenalty(
int platform_length)
244 assert(v !=
nullptr);
248 if (missing_platform_length < 0) {
250 cost +=
Yapf().PfGetSettings().rail_longer_platform_penalty +
Yapf().PfGetSettings().rail_longer_platform_per_tile_penalty * -missing_platform_length;
251 }
else if (missing_platform_length > 0) {
253 cost +=
Yapf().PfGetSettings().rail_shorter_platform_penalty +
Yapf().PfGetSettings().rail_shorter_platform_per_tile_penalty * missing_platform_length;
259 inline void SetMaxCost(
int max_cost)
261 m_max_cost = max_cost;
271 assert(!n.flags_u.flags_s.m_targed_seen);
272 assert(tf->m_new_tile == n.m_key.m_tile);
273 assert((
HasTrackdir(tf->m_new_td_bits, n.m_key.m_td)));
278 bool has_parent = (n.m_parent !=
nullptr);
281 CachedData &segment = *n.m_segment;
282 bool is_cached_segment = (segment.m_cost >= 0);
284 int parent_cost = has_parent ? n.m_parent->m_cost : 0;
305 int transition_cost = 0;
313 int segment_entry_cost = 0;
314 int segment_cost = 0;
319 TILE cur(n.m_key.m_tile, n.m_key.m_td);
322 TILE prev = !has_parent ?
TILE() : TILE(n.m_parent->GetLastTile(), n.m_parent->GetLastTrackdir());
324 EndSegmentReasonBits end_segment_reason = ESRB_NONE;
326 TrackFollower tf_local(v,
Yapf().GetCompatibleRailTypes(), &
Yapf().m_perf_ts_cost);
330 assert(!is_cached_segment);
337 transition_cost =
Yapf().CurveCost(prev.td, cur.td);
342 if (segment_cost == 0) {
344 segment_entry_cost = transition_cost;
348 if (is_cached_segment) {
350 segment_cost = segment.m_cost;
352 end_segment_reason = segment.m_end_segment_reason;
358 n.flags_u.flags_s.m_last_signal_was_red = is_red;
360 n.m_last_red_signal_type = GetSignalType(segment.m_last_signal_tile,
TrackdirToTrack(segment.m_last_signal_td));
364 cur = TILE(n.GetLastTile(), n.GetLastTrackdir());
369 segment_cost += transition_cost;
375 segment_cost +=
Yapf().OneTileCost(cur.tile, cur.td);
381 segment_cost +=
Yapf().SlopeCost(cur.tile, cur.td);
384 segment_cost +=
Yapf().SignalCost(n, cur.tile, cur.td);
387 segment_cost +=
Yapf().ReservationCost(n, cur.tile, cur.td, tf->m_tiles_skipped);
389 end_segment_reason = segment.m_end_segment_reason;
392 if (cur.tile == prev.tile) {
395 segment_cost +=
Yapf().PfGetSettings().rail_depot_reverse_penalty;
399 end_segment_reason |= ESRB_DEPOT;
413 while (ft.
Follow(t, td)) {
416 if (t == cur.tile || --max_tiles == 0) {
439 extra_cost +=
Yapf().PfGetSettings().rail_lastred_penalty;
443 end_segment_reason |= ESRB_WAYPOINT;
445 }
else if (tf->m_is_station) {
447 uint platform_length = tf->m_tiles_skipped + 1;
450 segment_cost +=
Yapf().PfGetSettings().rail_station_penalty * platform_length;
452 end_segment_reason |= ESRB_STATION;
454 }
else if (TrackFollower::DoTrackMasking() && cur.tile_type ==
MP_RAILWAY) {
457 end_segment_reason |= ESRB_SAFE_TILE;
463 if (n.m_num_signals_passed < m_sig_look_ahead_costs.
Size())
466 int max_speed = tf->GetSpeedLimit(&min_speed);
468 if (max_speed < max_veh_speed) {
469 extra_cost +=
YAPF_TILE_LENGTH * (max_veh_speed - max_speed) * (4 + tf->m_tiles_skipped) / max_veh_speed;
471 if (min_speed > max_veh_speed) {
478 if (m_max_cost > 0 && (parent_cost + segment_entry_cost + segment_cost) >
m_max_cost) {
479 end_segment_reason |= ESRB_PATH_TOO_LONG;
484 tf_local.Init(v,
Yapf().GetCompatibleRailTypes(), &
Yapf().m_perf_ts_cost);
486 if (!tf_local.Follow(cur.tile, cur.td)) {
487 assert(tf_local.m_err != TrackFollower::EC_NONE);
489 if (tf_local.m_err == TrackFollower::EC_RAIL_ROAD_TYPE) {
490 end_segment_reason |= ESRB_RAIL_TYPE;
492 end_segment_reason |= ESRB_DEAD_END;
496 end_segment_reason |= ESRB_SAFE_TILE;
504 end_segment_reason |= ESRB_CHOICE_FOLLOWS;
514 end_segment_reason |= ESRB_SAFE_TILE;
517 end_segment_reason |= ESRB_SAFE_TILE | ESRB_DEAD_END;
518 extra_cost +=
Yapf().PfGetSettings().rail_lastred_exit_penalty;
523 if (next.rail_type != cur.rail_type) {
525 end_segment_reason |= ESRB_RAIL_TYPE;
530 if (next.tile == n.m_key.m_tile && next.td == n.m_key.m_td) {
531 end_segment_reason |= ESRB_INFINITE_LOOP;
535 if (segment_cost > s_max_segment_cost) {
539 end_segment_reason |= ESRB_SEGMENT_TOO_LONG;
545 if (end_segment_reason != ESRB_NONE) {
556 if (end_segment_reason & ESRB_PATH_TOO_LONG)
return false;
558 bool target_seen =
false;
559 if ((end_segment_reason & ESRB_POSSIBLE_TARGET) != ESRB_NONE) {
561 if (
Yapf().PfDetectDestination(cur.tile, cur.td)) {
568 if (!is_cached_segment) {
570 segment.m_cost = segment_cost;
571 segment.m_end_segment_reason = end_segment_reason & ESRB_CACHED_MASK;
573 n.SetLastTileTrackdir(cur.tile, cur.td);
577 if (!target_seen && (end_segment_reason & ESRB_ABORT_PF_MASK) != ESRB_NONE) {
584 n.flags_u.flags_s.m_targed_seen =
true;
586 if (n.flags_u.flags_s.m_last_signal_was_red) {
589 extra_cost +=
Yapf().PfGetSettings().rail_lastred_exit_penalty;
590 }
else if (!IsPbsSignal(n.m_last_red_signal_type)) {
592 extra_cost +=
Yapf().PfGetSettings().rail_lastred_penalty;
597 if ((end_segment_reason & ESRB_STATION) != ESRB_NONE) {
599 assert(st !=
nullptr);
602 extra_cost -=
Yapf().PfGetSettings().rail_station_penalty * platform_length;
604 extra_cost += PlatformLengthPenalty(platform_length);
609 n.m_cost = parent_cost + segment_entry_cost + segment_cost + extra_cost;
614 inline bool CanUseGlobalCache(Node &n)
const 616 return !m_disable_cache
617 && (n.m_parent !=
nullptr)
618 && (n.m_parent->m_num_signals_passed >= m_sig_look_ahead_costs.
Size());
621 inline void ConnectNodeToCachedData(Node &n, CachedData &ci)
624 if (n.m_segment->m_cost < 0) {
625 n.m_segment->m_last_tile = n.m_key.m_tile;
626 n.m_segment->m_last_td = n.m_key.m_td;
630 void DisableCache(
bool disable)
632 m_disable_cache = disable;
bool PfCalcCost(Node &n, const TrackFollower *tf)
Called by YAPF to calculate the cost from the origin to the given node.
static TileType GetTileType(TileIndex tile)
Get the tiletype of a given tile.
static bool HasSignalOnTrackdir(TileIndex tile, Trackdir trackdir)
Checks for the presence of signals along the given trackdir on the given rail tile.
GameSettings _settings_game
Game settings of a running game or the scenario editor.
virtual uint GetPlatformLength(TileIndex tile) const =0
Obtain the length of a platform.
bool Follow(TileIndex old_tile, Trackdir old_td)
main follower routine.
SignalType
Type of signal, i.e.
TrackdirBits m_new_td_bits
the new set of available trackdirs
int32 TileIndexDiff
An offset value between to tiles.
static Track TrackdirToTrack(Trackdir trackdir)
Returns the Track that a given Trackdir represents.
TileType
The different types of tiles.
Trackdir
Enumeration for tracks and directions.
A tile with road (or tram tracks)
Flag for invalid railtype.
SignalState
These are states in which a signal can be.
static bool IsOnewaySignal(TileIndex t, Track track)
One-way signals can't be passed the 'wrong' way.
PathfinderSettings pf
settings for all pathfinders
Types::NodeList::Titem Node
this will be our node type
static Trackdir NextTrackdir(Trackdir trackdir)
Maps a trackdir to the trackdir that you will end up on if you go straight ahead. ...
int GetDisplayMaxSpeed() const
Gets the maximum speed in km-ish/h that can be sent into SetDParam for string processing.
bool forbid_90_deg
forbid trains to make 90 deg turns
Tpf & Yapf()
to access inherited path finder
static bool IsLevelCrossing(TileIndex t)
Return whether a tile is a level crossing.
static DiagDirection TrackdirToExitdir(Trackdir trackdir)
Maps a trackdir to the (4-way) direction the tile is exited when following that trackdir.
static const uint TILE_SIZE
Tile size in world coordinates.
int ReservationCost(Node &n, TileIndex tile, Trackdir trackdir, int skipped)
The cost for reserved tiles, including skipped ones.
static bool TrackOverlapsTracks(TrackBits tracks, Track track)
Check if a given track is contained within or overlaps some other tracks.
Base implementation for cost accounting.
static TileIndexDiff TileOffsByDiagDir(DiagDirection dir)
Convert a DiagDirection to a TileIndexDiff.
static bool IsValidTrackdir(Trackdir trackdir)
Checks if a Trackdir is valid for non-road vehicles.
static bool IsTileType(TileIndex tile, TileType type)
Checks if a tile is a given tiletype.
T * GrowSizeNC(size_t num_items)
Grow number of data items in Blob by given number - doesn't construct items.
static bool HasStationReservation(TileIndex t)
Get the reservation state of the rail station.
static bool IsRailStationTile(TileIndex t)
Is this tile a station tile and a rail station?
bool IsType(OrderType type) const
Check whether this order is of the given type.
static DiagDirection ReverseDiagDir(DiagDirection d)
Returns the reverse direction of the given DiagDirection.
static bool HasTrackdir(TrackdirBits trackdirs, Trackdir trackdir)
Checks whether a TrackdirBits has a given Trackdir.
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.
bool IsWaitingPositionFree(const Train *v, TileIndex tile, Trackdir trackdir, bool forbid_90deg)
Check if a safe position is free.
Flag for an invalid trackdir.
static Trackdir RemoveFirstTrackdir(TrackdirBits *trackdirs)
Removes first Trackdir from TrackdirBits and returns it.
static uint CeilDiv(uint a, uint b)
Computes ceil(a / b) for non-negative a and b.
static const int YAPF_TILE_LENGTH
Length (penalty) of one tile with YAPF.
static bool stSlopeCost(TileIndex tile, Trackdir td)
Does the given track direction on the given tile yield an uphill penalty?
Node::Key Key
key to hash tables
static bool IsPlainRailTile(TileIndex t)
Checks whether the tile is a rail tile or rail tile with signals.
Track follower helper template class (can serve pathfinders and vehicle controllers).
static Trackdir ReverseTrackdir(Trackdir trackdir)
Maps a trackdir to the reverse trackdir.
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
static TrackBits DiagdirReachesTracks(DiagDirection diagdir)
Returns all tracks that can be reached when entering a tile from a given (diagonal) direction...
'Train' is either a loco or a wagon.
static TrackBits GetTrackBits(TileIndex tile)
Gets the track bits of the given tile.
static BaseStation * GetByTile(TileIndex tile)
Get the base station belonging to a specific tile.
RailType GetTileRailType(TileIndex tile)
Return the rail type of tile, or INVALID_RAILTYPE if this is no rail tile.
static StationID GetStationIndex(TileIndex t)
Get StationID from a tile.
static T KillFirstBit(T value)
Clear the first bit in an integer.
RailType
Enumeration for all possible railtypes.
static bool IsRailDepot(TileIndex t)
Is this rail tile a rail depot?
DestinationID GetDestination() const
Gets the destination of this order.
static bool IsRailDepotTile(TileIndex t)
Is this tile rail tile and a rail depot?
Invisible tiles at the SW and SE border.
uint32 TileIndex
The index/ID of a Tile.
TrackBits GetReservedTrackbits(TileIndex t)
Get the reserved trackbits for any tile, regardless of type.
TileIndex m_new_tile
the new tile (the vehicle has entered)
T * Data()
Return pointer to the first data item - non-const version.
uint16 cached_total_length
Length of the whole vehicle (valid only for the first engine).
static bool IsDiagonalTrackdir(Trackdir trackdir)
Checks if a given Trackdir is diagonal.
VehicleType type
Type of vehicle.
static uint8 FindFirstBit2x64(const int value)
Finds the position of the first non-zero bit in an integer.
static bool IsRailWaypoint(TileIndex t)
Is this station tile a rail waypoint?
DiagDirection
Enumeration for diagonal directions.
static const TileIndex INVALID_TILE
The very nice invalid tile marker.
int OneTileCost(TileIndex &tile, Trackdir trackdir)
Return one tile cost (base cost + level crossing penalty).
size_t Size() const
Return number of items in the Blob.
static const int YAPF_TILE_CORNER_LENGTH
Length (penalty) of a corner with YAPF.
static bool HasOnewaySignalBlockingTrackdir(TileIndex tile, Trackdir td)
Is a one-way signal blocking the trackdir? A one-way signal on the trackdir against will block...
static SignalState GetSignalStateByTrackdir(TileIndex tile, Trackdir trackdir)
Gets the state of the signal along the given trackdir.
static Waypoint * Get(size_t index)
Gets station with given index.
static TrackdirBits TrackdirCrossesTrackdirs(Trackdir trackdir)
Maps a trackdir to all trackdirs that make 90 deg turns with it.
Base class for all station-ish types.
Order current_order
The current order (+ status, like: loading)
bool IsAnyStationTileReserved(TileIndex tile, Trackdir trackdir, int skipped)
Check for a reserved station platform.
GroundVehicleCache gcache
Cache of often calculated values.