Go to the documentation of this file.
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)
27 FILE *f1 = fopen(
"yapf1.txt",
"wt");
28 FILE *f2 = fopen(
"yapf2.txt",
"wt");
29 assert(f1 !=
nullptr);
30 assert(f2 !=
nullptr);
37 template <
class Types>
41 typedef typename Types::Tpf
Tpf;
42 typedef typename Types::TrackFollower TrackFollower;
43 typedef typename Types::NodeList::Titem
Node;
49 return *
static_cast<Tpf *
>(
this);
137 assert(node->m_parent !=
nullptr);
140 if (node->m_parent->m_num_signals_passed >= 2)
return;
153 if (target !=
nullptr) {
156 target->
okay =
false;
162 for (
Node *node =
m_res_node; node->m_parent !=
nullptr; node = node->m_parent) {
172 }
while (fail_node != node && (fail_node = fail_node->m_parent) !=
nullptr);
178 if (target !=
nullptr) target->
okay =
true;
188 template <
class Types>
192 typedef typename Types::Tpf
Tpf;
193 typedef typename Types::TrackFollower TrackFollower;
194 typedef typename Types::NodeList::Titem
Node;
195 typedef typename Node::Key
Key;
201 return *
static_cast<Tpf *
>(
this);
212 TrackFollower F(
Yapf().GetVehicle());
213 if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir())) {
214 Yapf().AddMultipleNodes(&old_node, F);
236 if (max_penalty != 0) pf1.DisableCache(
true);
237 FindDepotData result1 = pf1.FindNearestDepotTwoWay(v, t1, td1, t2, td2, max_penalty, reverse_penalty);
239 if (_debug_desync_level >= 2) {
241 pf2.DisableCache(
true);
242 FindDepotData result2 = pf2.FindNearestDepotTwoWay(v, t1, td1, t2, td2, max_penalty, reverse_penalty);
244 DEBUG(desync, 2,
"CACHE ERROR: FindNearestDepotTwoWay() = [%s, %s]",
257 Yapf().SetOrigin(t1, td1, t2, td2, reverse_penalty,
true);
258 Yapf().SetDestination(v);
259 Yapf().SetMaxCost(max_penalty);
269 while (pNode->m_parent !=
nullptr) {
270 pNode = pNode->m_parent;
275 return FindDepotData(n->GetLastTile(), n->m_cost, pNode->m_cost != 0);
279 template <
class Types>
283 typedef typename Types::Tpf
Tpf;
284 typedef typename Types::TrackFollower TrackFollower;
285 typedef typename Types::NodeList::Titem
Node;
286 typedef typename Node::Key
Key;
292 return *
static_cast<Tpf *
>(
this);
303 TrackFollower F(
Yapf().GetVehicle(),
Yapf().GetCompatibleRailTypes());
304 if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir()) && F.MaskReservedTracks()) {
305 Yapf().AddMultipleNodes(&old_node, F);
320 if (_debug_desync_level < 2) {
321 result1 = pf1.FindNearestSafeTile(v, t1, td, override_railtype,
false);
323 bool result2 = pf1.FindNearestSafeTile(v, t1, td, override_railtype,
true);
325 pf2.DisableCache(
true);
326 result1 = pf2.FindNearestSafeTile(v, t1, td, override_railtype,
false);
327 if (result1 != result2) {
328 DEBUG(desync, 2,
"CACHE ERROR: FindSafeTile() = [%s, %s]", result2 ?
"T" :
"F", result1 ?
"T" :
"F");
336 bool FindNearestSafeTile(
const Train *v,
TileIndex t1,
Trackdir td,
bool override_railtype,
bool dont_reserve)
339 Yapf().SetOrigin(t1, td);
340 Yapf().SetDestination(v, override_railtype);
342 bool bFound =
Yapf().FindPath(v);
343 if (!bFound)
return false;
350 Node *pPrev =
nullptr;
351 while (pNode->m_parent !=
nullptr) {
353 pNode = pNode->m_parent;
358 return dont_reserve || this->
TryReservePath(
nullptr, pNode->GetLastTile());
362 template <
class Types>
366 typedef typename Types::Tpf
Tpf;
367 typedef typename Types::TrackFollower TrackFollower;
368 typedef typename Types::NodeList::Titem
Node;
369 typedef typename Node::Key
Key;
375 return *
static_cast<Tpf *
>(
this);
386 TrackFollower F(
Yapf().GetVehicle());
387 if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir())) {
388 Yapf().AddMultipleNodes(&old_node, F);
404 if (_debug_desync_level < 2) {
405 result1 = pf1.ChooseRailTrack(v, tile, enterdir, tracks, path_found, reserve_track, target);
407 result1 = pf1.ChooseRailTrack(v, tile, enterdir, tracks, path_found,
false,
nullptr);
409 pf2.DisableCache(
true);
410 Trackdir result2 = pf2.ChooseRailTrack(v, tile, enterdir, tracks, path_found, reserve_track, target);
411 if (result1 != result2) {
412 DEBUG(desync, 2,
"CACHE ERROR: ChooseRailTrack() = [%d, %d]", result1, result2);
427 Yapf().SetDestination(v);
430 path_found =
Yapf().FindPath(v);
435 if (pNode !=
nullptr) {
441 Node *pPrev =
nullptr;
442 while (pNode->m_parent !=
nullptr) {
444 pNode = pNode->m_parent;
449 Node &best_next_node = *pPrev;
450 next_trackdir = best_next_node.GetTrackdir();
452 if (reserve_track && path_found) this->
TryReservePath(target, pNode->GetLastTile());
456 path_found |=
Yapf().m_stopped_on_first_two_way_signal;
457 return next_trackdir;
463 bool result1 = pf1.CheckReverseTrain(v, t1, td1, t2, td2, reverse_penalty);
465 if (_debug_desync_level >= 2) {
467 pf2.DisableCache(
true);
468 bool result2 = pf2.CheckReverseTrain(v, t1, td1, t2, td2, reverse_penalty);
469 if (result1 != result2) {
470 DEBUG(desync, 2,
"CACHE ERROR: CheckReverseTrain() = [%s, %s]", result1 ?
"T" :
"F", result2 ?
"T" :
"F");
482 Yapf().SetOrigin(t1, td1, t2, td2, reverse_penalty,
false);
483 Yapf().SetDestination(v);
486 bool bFound =
Yapf().FindPath(v);
488 if (!bFound)
return false;
493 while (pNode->m_parent !=
nullptr) {
494 pNode = pNode->m_parent;
498 Node &best_org_node = *pNode;
499 bool reversed = (best_org_node.m_cost != 0);
504 template <
class Tpf_,
class Ttrack_follower,
class Tnode_list,
template <
class Types>
class TdestinationT,
template <
class Types>
class TfollowT>
510 typedef Ttrack_follower TrackFollower;
511 typedef Tnode_list NodeList;
514 typedef TfollowT<Types> PfFollow;
516 typedef TdestinationT<Types> PfDestination;
521 struct CYapfRail1 :
CYapfT<CYapfRail_TypesT<CYapfRail1 , CFollowTrackRail , CRailNodeListTrackDir, CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {};
522 struct CYapfRail2 :
CYapfT<CYapfRail_TypesT<CYapfRail2 , CFollowTrackRailNo90, CRailNodeListTrackDir, CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {};
524 struct CYapfAnyDepotRail1 :
CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail1, CFollowTrackRail , CRailNodeListTrackDir, CYapfDestinationAnyDepotRailT , CYapfFollowAnyDepotRailT> > {};
525 struct CYapfAnyDepotRail2 :
CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail2, CFollowTrackRailNo90, CRailNodeListTrackDir, CYapfDestinationAnyDepotRailT , CYapfFollowAnyDepotRailT> > {};
527 struct CYapfAnySafeTileRail1 :
CYapfT<CYapfRail_TypesT<CYapfAnySafeTileRail1, CFollowTrackFreeRail , CRailNodeListTrackDir, CYapfDestinationAnySafeTileRailT , CYapfFollowAnySafeTileRailT> > {};
528 struct CYapfAnySafeTileRail2 :
CYapfT<CYapfRail_TypesT<CYapfAnySafeTileRail2, CFollowTrackFreeRailNo90, CRailNodeListTrackDir, CYapfDestinationAnySafeTileRailT , CYapfFollowAnySafeTileRailT> > {};
535 PfnChooseRailTrack pfnChooseRailTrack = &CYapfRail1::stChooseRailTrack;
539 pfnChooseRailTrack = &CYapfRail2::stChooseRailTrack;
542 Trackdir td_ret = pfnChooseRailTrack(v, tile, enterdir, tracks, path_found, reserve_track, target);
558 int reverse_penalty = 0;
590 PfnCheckReverseTrain pfnCheckReverseTrain = CYapfRail1::stCheckReverseTrain;
594 pfnCheckReverseTrain = &CYapfRail2::stCheckReverseTrain;
598 if (reverse_penalty == 0) reverse_penalty = 1;
600 bool reverse = pfnCheckReverseTrain(v, tile, td, tile_rev, td_rev, reverse_penalty);
614 PfnFindNearestDepotTwoWay pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail1::stFindNearestDepotTwoWay;
618 pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail2::stFindNearestDepotTwoWay;
627 PfnFindNearestSafeTile pfnFindNearestSafeTile = CYapfAnySafeTileRail1::stFindNearestSafeTile;
631 pfnFindNearestSafeTile = &CYapfAnySafeTileRail2::stFindNearestSafeTile;
634 return pfnFindNearestSafeTile(v, tile, td, override_railtype);
642 CSegmentCostCacheBase::NotifyTrackLayoutChange(tile, track);
bool okay
True if tile is a safe waiting position, false otherwise.
@ TRACK_BIT_WORMHOLE
Bitflag for a wormhole (used for tunnels)
Trackdir m_res_dest_td
The reservation target trackdir.
uint32 TileIndex
The index/ID of a Tile.
#define TILE_ADD(x, y)
Adds to tiles together.
Types::NodeList::Titem Node
this will be our node type
static TileIndexDiff TileOffsByDiagDir(DiagDirection dir)
Convert a DiagDirection to a TileIndexDiff.
Tpf & Yapf()
to access inherited pathfinder
Tpf & Yapf()
to access inherited path finder
Helper container to find a depot.
bool forbid_90_deg
forbid trains to make 90 deg turns
bool ReserveRailStationPlatform(TileIndex &tile, DiagDirection dir)
Reserve a railway platform.
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
Node * m_res_node
The reservation target node.
void YapfNotifyTrackLayoutChange(TileIndex tile, Track track)
Use this function to notify YAPF that track layout (or signal configuration) has change.
bool reverse
True if reversing is necessary for the train to get to this depot.
static void SetRailStationReservation(TileIndex t, bool b)
Set the reservation state of the rail station.
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
PBSTileInfo FollowTrainReservation(const Train *v, Vehicle **train_on_res)
Follow a train reservation to the last tile.
void FindSafePositionOnNode(Node *node)
Check the node for a possible reservation target.
static bool IsCompatibleTrainStationTile(TileIndex test_tile, TileIndex station_tile)
Check if a tile is a valid continuation to a railstation tile.
YAPF template that uses Ttypes template argument to determine all YAPF components (base classes) from...
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
Trackdir GetVehicleTrackdir() const
Get the tracks of the train vehicle.
Trackdir m_res_fail_td
The trackdir where the reservation failed.
bool TryReserveRailTrack(TileIndex tile, Track t, bool trigger_stations)
Try to reserve a specific track on a tile.
Node::Key Key
key to hash tables
char TransportTypeChar() const
return debug report character to identify the transportation type
PathfinderSettings pf
settings for all pathfinders
uint DistanceManhattan(TileIndex t0, TileIndex t1)
Gets the Manhattan distance between the two given tiles.
void UnreserveRailTrack(TileIndex tile, Track t)
Lift the reservation of a specific track on a tile.
void TriggerStationRandomisation(Station *st, TileIndex tile, StationRandomTrigger trigger, CargoID cargo_type)
Trigger station randomisation.
bool IsWaitingPositionFree(const Train *v, TileIndex tile, Trackdir trackdir, bool forbid_90deg)
Check if a safe position is free.
YAPF origin provider base class - used when there are two tile/trackdir origins.
TileIndex m_origin_tile
Tile our reservation will originate from.
int32 TileIndexDiff
An offset value between to tiles.
static const int YAPF_TILE_LENGTH
Length (penalty) of one tile with YAPF.
TileIndex tile
Current tile index.
#define DEBUG(name, level,...)
Output a line of debugging information.
static DiagDirection TrackdirToExitdir(Trackdir trackdir)
Maps a trackdir to the (4-way) direction the tile is exited when following that trackdir.
size_t Size() const
Return number of items in the Blob.
This struct contains information about the end of a reserved path.
Node::Key Key
key to hash tables
Trackdir trackdir
The reserved trackdir on the tile.
CYapfSegmentCostCacheGlobalT - the yapf cost cache provider that adds the segment cost caching functi...
Class that represents the dump-into-string target.
GameSettings _settings_game
Game settings of a running game or the scenario editor.
'Train' is either a loco or a wagon.
bool UnreserveSingleTrack(TileIndex tile, Trackdir td)
Unreserve a single track/platform.
void SetReservationTarget(Node *node, TileIndex tile, Trackdir td)
Set the target to where the reservation should be extended.
bool TryReservePath(PBSTileInfo *target, TileIndex origin)
Try to reserve the path till the reservation target.
static bool HasStationReservation(TileIndex t)
Get the reservation state of the rail station.
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.
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
@ INVALID_TRACKDIR
Flag for an invalid trackdir.
DiagDirection
Enumeration for diagonal directions.
static bool IsRailStationTile(TileIndex t)
Is this tile a station tile and a rail station?
FindDepotData YapfTrainFindNearestDepot(const Train *v, int max_penalty)
Used when user sends train to the nearest depot or if train needs servicing using YAPF.
static DiagDirection GetTunnelBridgeDirection(TileIndex t)
Get the direction pointing to the other end.
char TransportTypeChar() const
Return debug report character to identify the transportation type.
static int s_rail_change_counter
if any track changes, this counter is incremented - that will invalidate segment cost cache
TileIndex m_res_fail_tile
The tile where the reservation failed.
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
Tpf & Yapf()
to access inherited path finder
TileIndex m_res_dest
The reservation target tile.
TileIndex tile
Tile the path ends, INVALID_TILE if no valid path was found.
Track YapfTrainChooseTrack(const Train *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found, bool reserve_track, PBSTileInfo *target)
Finds the best path for given train using YAPF.
void MarkTileDirtyByTile(TileIndex tile, int bridge_level_offset, int tile_height_override)
Mark a tile given by its index dirty for repaint.
void PfFollowNode(Node &old_node)
Called by YAPF to move from the given node to the next tile.
TileIndex tile
The tile of the depot.
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 Track FindFirstTrack(TrackBits tracks)
Returns first Track from TrackBits or INVALID_TRACK.
bool YapfTrainCheckReverse(const Train *v)
Returns true if it is better to reverse the train before leaving station using YAPF.
TrackBits
Bitfield corresponding to Track.
@ SRT_PATH_RESERVATION
Trigger platform when train reserves path.
static const TileIndex INVALID_TILE
The very nice invalid tile marker.
void PfFollowNode(Node &old_node)
Called by YAPF to move from the given node to the next tile.
Types::NodeList::Titem Node
this will be our node type
static TileIndex GetOtherTunnelBridgeEnd(TileIndex t)
Determines type of the wormhole and returns its other end.
static Trackdir ReverseTrackdir(Trackdir trackdir)
Maps a trackdir to the reverse trackdir.
CStrA m_out
the output string
Trackdir
Enumeration for tracks and directions.
CYapfBaseT - A-star type path finder base class.
Types::NodeList::Titem Node
this will be our node type
Track
These are used to specify a single track.
Node::Key Key
key to hash tables
T * Last()
Get the last vehicle in the chain.
T * Data()
Return pointer to the first data item - non-const version.
Tpf & Yapf()
to access inherited path finder
Types::NodeList::Titem Node
this will be our node type
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.
bool ReserveSingleTrack(TileIndex tile, Trackdir td)
Try to reserve a single track/platform.
static Track TrackdirToTrack(Trackdir trackdir)
Returns the Track that a given Trackdir represents.
static TileIndex TileVirtXY(uint x, uint y)
Get a tile from the virtual XY-coordinate.
@ INVALID_TRACK
Flag for an invalid track.