10 #include "../../stdafx.h"
17 #include "../../viewport_func.h"
18 #include "../../newgrf_station.h"
20 #include "../../safeguards.h"
22 template <
typename Tpf>
void DumpState(Tpf &pf1, Tpf &pf2)
29 assert(f1.has_value());
30 assert(f2.has_value());
31 fwrite(dmp1.
m_out.c_str(), 1, dmp1.
m_out.size(), *f1);
32 fwrite(dmp2.
m_out.c_str(), 1, dmp2.
m_out.size(), *f2);
35 template <
class Types>
39 typedef typename Types::Tpf
Tpf;
40 typedef typename Types::TrackFollower TrackFollower;
41 typedef typename Types::NodeList::Titem
Node;
47 return *
static_cast<Tpf *
>(
this);
63 this->res_dest_tile = tile;
64 this->res_dest_td = td;
95 this->res_fail_tile = tile;
96 this->res_fail_td = td;
101 this->res_fail_tile = tile;
102 this->res_fail_td = td;
108 this->signals_set_to_red.emplace_back(tile, rev_td);
114 return tile != this->res_dest_tile || td != this->
res_dest_td;
127 }
else if (tile != this->res_fail_tile || td != this->res_fail_td) {
130 return (tile != this->res_dest_tile || td != this->res_dest_td) && (tile != this->res_fail_tile || td != this->
res_fail_td);
137 this->res_dest_node = node;
138 this->res_dest_tile = tile;
139 this->res_dest_td = td;
145 assert(node->parent !=
nullptr);
148 if (node->parent->num_signals_passed >= 2)
return;
151 this->res_dest_node = node;
159 this->origin_tile = origin;
161 if (target !=
nullptr) {
164 target->
okay =
false;
170 this->signals_set_to_red.clear();
171 for (
Node *node = this->res_dest_node; node->parent !=
nullptr; node = node->parent) {
179 this->res_fail_tile = fail_node == node ? stop_tile :
INVALID_TILE;
181 }
while (fail_node != node && (fail_node = fail_node->parent) !=
nullptr);
184 for (
auto [sig_tile, td] : this->signals_set_to_red) {
192 if (target !=
nullptr) target->
okay =
true;
194 if (
Yapf().CanUseGlobalCache(*this->res_dest_node)) {
202 template <
class Types>
206 typedef typename Types::Tpf
Tpf;
207 typedef typename Types::TrackFollower TrackFollower;
208 typedef typename Types::NodeList::Titem
Node;
209 typedef typename Node::Key
Key;
215 return *
static_cast<Tpf *
>(
this);
226 TrackFollower F(
Yapf().GetVehicle());
227 if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir())) {
228 Yapf().AddMultipleNodes(&old_node, F);
250 if (max_penalty != 0) pf1.DisableCache(
true);
251 FindDepotData result1 = pf1.FindNearestDepotTwoWay(v, t1, td1, t2, td2, max_penalty, reverse_penalty);
253 if (_debug_desync_level >= 2) {
255 pf2.DisableCache(
true);
256 FindDepotData result2 = pf2.FindNearestDepotTwoWay(v, t1, td1, t2, td2, max_penalty, reverse_penalty);
258 Debug(desync, 2,
"warning: FindNearestDepotTwoWay cache mismatch: {} vs {}",
271 Yapf().SetOrigin(t1, td1, t2, td2, reverse_penalty,
true);
272 Yapf().SetDestination(v);
273 Yapf().SetMaxCost(max_penalty);
283 while (pNode->parent !=
nullptr) {
284 pNode = pNode->parent;
289 return FindDepotData(n->GetLastTile(), n->cost, pNode->cost != 0);
293 template <
class Types>
297 typedef typename Types::Tpf
Tpf;
298 typedef typename Types::TrackFollower TrackFollower;
299 typedef typename Types::NodeList::Titem
Node;
300 typedef typename Node::Key
Key;
306 return *
static_cast<Tpf *
>(
this);
317 TrackFollower F(
Yapf().GetVehicle(),
Yapf().GetCompatibleRailTypes());
318 if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir()) && F.MaskReservedTracks()) {
319 Yapf().AddMultipleNodes(&old_node, F);
334 if (_debug_desync_level < 2) {
335 result1 = pf1.FindNearestSafeTile(v, t1, td, override_railtype,
false);
337 bool result2 = pf1.FindNearestSafeTile(v, t1, td, override_railtype,
true);
339 pf2.DisableCache(
true);
340 result1 = pf2.FindNearestSafeTile(v, t1, td, override_railtype,
false);
341 if (result1 != result2) {
342 Debug(desync, 2,
"warning: FindSafeTile cache mismatch: {} vs {}", result2 ?
"T" :
"F", result1 ?
"T" :
"F");
350 bool FindNearestSafeTile(
const Train *v,
TileIndex t1,
Trackdir td,
bool override_railtype,
bool dont_reserve)
353 Yapf().SetOrigin(t1, td);
354 Yapf().SetDestination(v, override_railtype);
356 if (!
Yapf().FindPath(v))
return false;
363 Node *pPrev =
nullptr;
364 while (pNode->parent !=
nullptr) {
366 pNode = pNode->parent;
371 return dont_reserve || this->
TryReservePath(
nullptr, pNode->GetLastTile());
375 template <
class Types>
379 typedef typename Types::Tpf
Tpf;
380 typedef typename Types::TrackFollower TrackFollower;
381 typedef typename Types::NodeList::Titem
Node;
382 typedef typename Node::Key
Key;
388 return *
static_cast<Tpf *
>(
this);
399 TrackFollower F(
Yapf().GetVehicle());
400 if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir())) {
401 Yapf().AddMultipleNodes(&old_node, F);
417 if (_debug_desync_level < 2) {
418 result1 = pf1.ChooseRailTrack(v, tile, enterdir, tracks, path_found, reserve_track, target, dest);
420 result1 = pf1.ChooseRailTrack(v, tile, enterdir, tracks, path_found,
false,
nullptr,
nullptr);
422 pf2.DisableCache(
true);
423 Trackdir result2 = pf2.ChooseRailTrack(v, tile, enterdir, tracks, path_found, reserve_track, target, dest);
424 if (result1 != result2) {
425 Debug(desync, 2,
"warning: ChooseRailTrack cache mismatch: {} vs {}", result1, result2);
441 Yapf().SetDestination(v);
444 path_found =
Yapf().FindPath(v);
449 if (pNode !=
nullptr) {
455 Node *pPrev =
nullptr;
456 while (pNode->parent !=
nullptr) {
458 pNode = pNode->parent;
468 Node &best_next_node = *pPrev;
469 next_trackdir = best_next_node.GetTrackdir();
471 if (reserve_track && path_found) {
472 if (dest !=
nullptr) *dest =
Yapf().GetBestNode()->GetLastTile();
478 path_found |=
Yapf().stopped_on_first_two_way_signal;
479 return next_trackdir;
485 bool result1 = pf1.CheckReverseTrain(v, t1, td1, t2, td2, reverse_penalty);
487 if (_debug_desync_level >= 2) {
489 pf2.DisableCache(
true);
490 bool result2 = pf2.CheckReverseTrain(v, t1, td1, t2, td2, reverse_penalty);
491 if (result1 != result2) {
492 Debug(desync, 2,
"warning: CheckReverseTrain cache mismatch: {} vs {}", result1 ?
"T" :
"F", result2 ?
"T" :
"F");
504 Yapf().SetOrigin(t1, td1, t2, td2, reverse_penalty,
false);
505 Yapf().SetDestination(v);
508 if (!
Yapf().FindPath(v))
return false;
513 while (pNode->parent !=
nullptr) {
514 pNode = pNode->parent;
518 bool reversed = (pNode->cost != 0);
523 template <
class Tpf_,
class Ttrack_follower,
class Tnode_list,
template <
class Types>
class TdestinationT,
template <
class Types>
class TfollowT>
529 typedef Ttrack_follower TrackFollower;
530 typedef Tnode_list NodeList;
533 typedef TfollowT<Types> PfFollow;
535 typedef TdestinationT<Types> PfDestination;
540 struct CYapfRail1 :
CYapfT<CYapfRail_TypesT<CYapfRail1 , CFollowTrackRail , CRailNodeListTrackDir, CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {};
541 struct CYapfRail2 :
CYapfT<CYapfRail_TypesT<CYapfRail2 , CFollowTrackRailNo90, CRailNodeListTrackDir, CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {};
543 struct CYapfAnyDepotRail1 :
CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail1, CFollowTrackRail , CRailNodeListTrackDir, CYapfDestinationAnyDepotRailT , CYapfFollowAnyDepotRailT> > {};
544 struct CYapfAnyDepotRail2 :
CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail2, CFollowTrackRailNo90, CRailNodeListTrackDir, CYapfDestinationAnyDepotRailT , CYapfFollowAnyDepotRailT> > {};
546 struct CYapfAnySafeTileRail1 :
CYapfT<CYapfRail_TypesT<CYapfAnySafeTileRail1, CFollowTrackFreeRail , CRailNodeListTrackDir, CYapfDestinationAnySafeTileRailT , CYapfFollowAnySafeTileRailT> > {};
547 struct CYapfAnySafeTileRail2 :
CYapfT<CYapfRail_TypesT<CYapfAnySafeTileRail2, CFollowTrackFreeRailNo90, CRailNodeListTrackDir, CYapfDestinationAnySafeTileRailT , CYapfFollowAnySafeTileRailT> > {};
553 ? CYapfRail2::stChooseRailTrack(v, tile, enterdir, tracks, path_found, reserve_track, target, dest)
554 : CYapfRail1::stChooseRailTrack(v, tile, enterdir, tracks, path_found, reserve_track, target, dest);
571 int reverse_penalty = 0;
603 if (reverse_penalty == 0) reverse_penalty = 1;
606 ? CYapfRail2::stCheckReverseTrain(v, tile, td, tile_rev, td_rev, reverse_penalty)
607 : CYapfRail1::stCheckReverseTrain(v, tile, td, tile_rev, td_rev, reverse_penalty);
628 ? CYapfAnySafeTileRail2::stFindNearestSafeTile(v, tile, td, override_railtype)
629 : CYapfAnySafeTileRail1::stFindNearestSafeTile(v, tile, td, override_railtype);
637 CSegmentCostCacheBase::NotifyTrackLayoutChange(tile, track);
CYapfBaseT - A-star type path finder base class.
Types::NodeList::Titem Node
this will be our node type
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
Tpf & Yapf()
to access inherited path finder
void PfFollowNode(Node &old_node)
Called by YAPF to move from the given node to the next tile.
char TransportTypeChar() const
return debug report character to identify the transportation type
Node::Key Key
key to hash tables
Tpf & Yapf()
to access inherited path finder
char TransportTypeChar() const
Return debug report character to identify the transportation type.
Node::Key Key
key to hash tables
Types::NodeList::Titem Node
this will be our node type
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
void PfFollowNode(Node &old_node)
Called by YAPF to move from the given node to the next tile.
Node::Key Key
key to hash tables
char TransportTypeChar() const
return debug report character to identify the transportation type
Tpf & Yapf()
to access inherited path finder
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
Types::NodeList::Titem Node
this will be our node type
void PfFollowNode(Node &old_node)
Called by YAPF to move from the given node to the next tile.
YAPF origin provider base class - used when there are two tile/trackdir origins.
void SetReservationTarget(Node *node, TileIndex tile, Trackdir td)
Set the target to where the reservation should be extended.
TileIndex res_fail_tile
The tile where the reservation failed.
bool UnreserveSingleTrack(TileIndex tile, Trackdir td)
Unreserve a single track/platform.
bool ReserveRailStationPlatform(TileIndex &tile, DiagDirection dir)
Reserve a railway platform.
bool ReserveSingleTrack(TileIndex tile, Trackdir td)
Try to reserve a single track/platform.
std::vector< std::pair< TileIndex, Trackdir > > signals_set_to_red
List of signals turned red during a path reservation.
Trackdir res_fail_td
The trackdir where the reservation failed.
Node * res_dest_node
The reservation target node.
TileIndex origin_tile
Tile our reservation will originate from.
TileIndex res_dest_tile
The reservation target tile.
bool TryReservePath(PBSTileInfo *target, TileIndex origin)
Try to reserve the path till the reservation target.
Types::NodeList::Titem Node
this will be our node type
void FindSafePositionOnNode(Node *node)
Check the node for a possible reservation target.
Trackdir res_dest_td
The reservation target trackdir.
Tpf & Yapf()
to access inherited pathfinder
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
CYapfSegmentCostCacheGlobalT - the yapf cost cache provider that adds the segment cost caching functi...
YAPF template that uses Ttypes template argument to determine all YAPF components (base classes) from...
static std::optional< FileHandle > Open(const std::string &filename, const std::string &mode)
Open an RAII file handle if possible.
#define Debug(category, level, format_string,...)
Ouptut a line of debugging information.
DiagDirection
Enumeration for diagonal directions.
void MarkTileDirtyByTile(TileIndex tile, int bridge_level_offset, int tile_height_override)
Mark a tile given by its index dirty for repaint.
uint DistanceManhattan(TileIndex t0, TileIndex t1)
Gets the Manhattan distance between the two given tiles.
constexpr TileIndex TileAdd(TileIndex tile, TileIndexDiff offset)
Adds a given offset to a tile.
TileIndexDiff TileOffsByDiagDir(DiagDirection dir)
Convert a DiagDirection to a TileIndexDiff.
static debug_inline TileIndex TileVirtXY(uint x, uint y)
Get a tile from the virtual XY-coordinate.
int32_t TileIndexDiff
An offset value between two tiles.
void TriggerStationRandomisation(Station *st, TileIndex trigger_tile, StationRandomTrigger trigger, CargoID cargo_type)
Trigger station randomisation.
@ SRT_PATH_RESERVATION
Trigger platform when train reserves path.
static const int YAPF_INFINITE_PENALTY
This penalty is the equivalent of "infinite", which means that paths that get this penalty will be ch...
static const int YAPF_TILE_LENGTH
Length (penalty) of one tile with YAPF.
PBSTileInfo FollowTrainReservation(const Train *v, Vehicle **train_on_res)
Follow a train reservation to the last tile.
bool TryReserveRailTrack(TileIndex tile, Track t, bool trigger_stations)
Try to reserve a specific track on a tile.
bool IsWaitingPositionFree(const Train *v, TileIndex tile, Trackdir trackdir, bool forbid_90deg)
Check if a safe position is free.
void UnreserveRailTrack(TileIndex tile, Track t)
Lift the reservation of a specific track on a tile.
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.
void SetSignalStateByTrackdir(Tile tile, Trackdir trackdir, SignalState state)
Sets the state of the signal along the given trackdir.
bool HasPbsSignalOnTrackdir(Tile tile, Trackdir td)
Is a pbs signal present along the trackdir?
SignalState GetSignalStateByTrackdir(Tile tile, Trackdir trackdir)
Gets the state of the signal along the given trackdir.
GameSettings _settings_game
Game settings of a running game or the scenario editor.
@ SIGNAL_STATE_RED
The signal is red.
@ SIGNAL_STATE_GREEN
The signal is green.
bool IsCompatibleTrainStationTile(Tile test_tile, Tile station_tile)
Check if a tile is a valid continuation to a railstation tile.
bool IsRailStationTile(Tile t)
Is this tile a station tile and a rail station?
void SetRailStationReservation(Tile t, bool b)
Set the reservation state of the rail station.
bool HasStationReservation(Tile t)
Get the reservation state of the rail station.
static int s_rail_change_counter
if any track changes, this counter is incremented - that will invalidate segment cost cache
Class that represents the dump-into-string target.
std::string m_out
the output string
Helper container to find a depot.
bool reverse
True if reversing is necessary for the train to get to this depot.
TileIndex tile
The tile of the depot.
PathfinderSettings pf
settings for all pathfinders
This struct contains information about the end of a reserved path.
Trackdir trackdir
The reserved trackdir on the tile.
TileIndex tile
Tile the path ends, INVALID_TILE if no valid path was found.
bool okay
True if tile is a safe waiting position, false otherwise.
bool forbid_90_deg
forbid trains to make 90 deg turns
T * Last()
Get the last vehicle in the chain.
'Train' is either a loco or a wagon.
Trackdir GetVehicleTrackdir() const override
Get the tracks of the train vehicle.
int32_t y_pos
y coordinate.
int32_t x_pos
x coordinate.
TileIndex tile
Current tile index.
constexpr TileIndex INVALID_TILE
The very nice invalid tile marker.
Track TrackdirToTrack(Trackdir trackdir)
Returns the Track that a given Trackdir represents.
Trackdir ReverseTrackdir(Trackdir trackdir)
Maps a trackdir to the reverse trackdir.
Track FindFirstTrack(TrackBits tracks)
Returns first Track from TrackBits or INVALID_TRACK.
DiagDirection TrackdirToExitdir(Trackdir trackdir)
Maps a trackdir to the (4-way) direction the tile is exited when following that trackdir.
TrackBits
Allow incrementing of Track variables.
@ TRACK_BIT_WORMHOLE
Bitflag for a wormhole (used for tunnels)
Trackdir
Enumeration for tracks and directions.
@ INVALID_TRACKDIR
Flag for an invalid trackdir.
Track
These are used to specify a single track.
@ INVALID_TRACK
Flag for an invalid track.
DiagDirection GetTunnelBridgeDirection(Tile t)
Get the direction pointing to the other end.
TileIndex GetOtherTunnelBridgeEnd(Tile t)
Determines type of the wormhole and returns its other end.
Base includes/functions for YAPF.
Entry point for OpenTTD to YAPF's cache.
Cost determination for rails.
Determining the destination for rail vehicles.
Node tailored for rail pathfinding.
void YapfNotifyTrackLayoutChange(TileIndex tile, Track track)
Use this function to notify YAPF that track layout (or signal configuration) has change.
bool YapfTrainFindNearestSafeTile(const Train *v, TileIndex tile, Trackdir td, bool override_railtype)
Try to extend the reserved path of a train to the nearest safe tile using YAPF.
Track YapfTrainChooseTrack(const Train *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found, bool reserve_track, PBSTileInfo *target, TileIndex *dest)
Finds the best path for given train using YAPF.
FindDepotData YapfTrainFindNearestDepot(const Train *v, int max_penalty)
Used when user sends train to the nearest depot or if train needs servicing using YAPF.
bool YapfTrainCheckReverse(const Train *v)
Returns true if it is better to reverse the train before leaving station using YAPF.