12 #include "../../stdafx.h" 19 #include "../../viewport_func.h" 20 #include "../../newgrf_station.h" 22 #include "../../safeguards.h" 24 template <
typename Tpf>
void DumpState(Tpf &pf1, Tpf &pf2)
29 FILE *f1 = fopen(
"yapf1.txt",
"wt");
30 FILE *f2 = fopen(
"yapf2.txt",
"wt");
39 int _total_pf_time_us = 0;
41 template <
class Types>
45 typedef typename Types::Tpf
Tpf;
46 typedef typename Types::TrackFollower TrackFollower;
47 typedef typename Types::NodeList::Titem
Node;
53 return *
static_cast<Tpf *
>(
this);
98 m_res_fail_tile = tile;
104 m_res_fail_tile = tile;
123 }
else if (tile != m_res_fail_tile || td != m_res_fail_td) {
126 return (tile != m_res_dest || td != m_res_dest_td) && (tile != m_res_fail_tile || td !=
m_res_fail_td);
141 assert(node->m_parent != NULL);
144 if (node->m_parent->m_num_signals_passed >= 2)
return;
155 m_origin_tile = origin;
157 if (target != NULL) {
160 target->
okay =
false;
166 for (Node *node = m_res_node; node->m_parent != NULL; node = node->m_parent) {
174 m_res_fail_tile = fail_node == node ? stop_tile :
INVALID_TILE;
176 }
while (fail_node != node && (fail_node = fail_node->m_parent) != NULL);
182 if (target != NULL) target->
okay =
true;
184 if (
Yapf().CanUseGlobalCache(*m_res_node)) {
192 template <
class Types>
196 typedef typename Types::Tpf
Tpf;
197 typedef typename Types::TrackFollower TrackFollower;
198 typedef typename Types::NodeList::Titem
Node;
199 typedef typename Node::Key
Key;
205 return *
static_cast<Tpf *
>(
this);
216 TrackFollower F(
Yapf().GetVehicle());
217 if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir())) {
218 Yapf().AddMultipleNodes(&old_node, F);
240 if (max_penalty != 0) pf1.DisableCache(
true);
241 FindDepotData result1 = pf1.FindNearestDepotTwoWay(v, t1, td1, t2, td2, max_penalty, reverse_penalty);
243 if (_debug_desync_level >= 2) {
245 pf2.DisableCache(
true);
246 FindDepotData result2 = pf2.FindNearestDepotTwoWay(v, t1, td1, t2, td2, max_penalty, reverse_penalty);
248 DEBUG(desync, 2,
"CACHE ERROR: FindNearestDepotTwoWay() = [%s, %s]",
261 Yapf().SetOrigin(t1, td1, t2, td2, reverse_penalty,
true);
262 Yapf().SetDestination(v);
263 Yapf().SetMaxCost(max_penalty);
269 Node *n =
Yapf().GetBestNode();
273 while (pNode->m_parent != NULL) {
274 pNode = pNode->m_parent;
279 return FindDepotData(n->GetLastTile(), n->m_cost, pNode->m_cost != 0);
283 template <
class Types>
287 typedef typename Types::Tpf
Tpf;
288 typedef typename Types::TrackFollower TrackFollower;
289 typedef typename Types::NodeList::Titem
Node;
290 typedef typename Node::Key
Key;
296 return *
static_cast<Tpf *
>(
this);
307 TrackFollower F(
Yapf().GetVehicle(),
Yapf().GetCompatibleRailTypes());
308 if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir()) && F.MaskReservedTracks()) {
309 Yapf().AddMultipleNodes(&old_node, F);
324 if (_debug_desync_level < 2) {
325 result1 = pf1.FindNearestSafeTile(v, t1, td, override_railtype,
false);
327 bool result2 = pf1.FindNearestSafeTile(v, t1, td, override_railtype,
true);
329 pf2.DisableCache(
true);
330 result1 = pf2.FindNearestSafeTile(v, t1, td, override_railtype,
false);
331 if (result1 != result2) {
332 DEBUG(desync, 2,
"CACHE ERROR: FindSafeTile() = [%s, %s]", result2 ?
"T" :
"F", result1 ?
"T" :
"F");
340 bool FindNearestSafeTile(
const Train *v,
TileIndex t1,
Trackdir td,
bool override_railtype,
bool dont_reserve)
343 Yapf().SetOrigin(t1, td);
344 Yapf().SetDestination(v, override_railtype);
346 bool bFound =
Yapf().FindPath(v);
347 if (!bFound)
return false;
350 Node *pNode =
Yapf().GetBestNode();
355 while (pNode->m_parent != NULL) {
357 pNode = pNode->m_parent;
362 return dont_reserve || this->
TryReservePath(NULL, pNode->GetLastTile());
366 template <
class Types>
370 typedef typename Types::Tpf
Tpf;
371 typedef typename Types::TrackFollower TrackFollower;
372 typedef typename Types::NodeList::Titem
Node;
373 typedef typename Node::Key
Key;
379 return *
static_cast<Tpf *
>(
this);
390 TrackFollower F(
Yapf().GetVehicle());
391 if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir())) {
392 Yapf().AddMultipleNodes(&old_node, F);
408 if (_debug_desync_level < 2) {
409 result1 = pf1.ChooseRailTrack(v, tile, enterdir, tracks, path_found, reserve_track, target);
411 result1 = pf1.ChooseRailTrack(v, tile, enterdir, tracks, path_found,
false, NULL);
413 pf2.DisableCache(
true);
414 Trackdir result2 = pf2.ChooseRailTrack(v, tile, enterdir, tracks, path_found, reserve_track, target);
415 if (result1 != result2) {
416 DEBUG(desync, 2,
"CACHE ERROR: ChooseRailTrack() = [%d, %d]", result1, result2);
431 Yapf().SetDestination(v);
434 path_found =
Yapf().FindPath(v);
438 Node *pNode =
Yapf().GetBestNode();
446 while (pNode->m_parent != NULL) {
448 pNode = pNode->m_parent;
453 Node &best_next_node = *pPrev;
454 next_trackdir = best_next_node.GetTrackdir();
456 if (reserve_track && path_found) this->
TryReservePath(target, pNode->GetLastTile());
460 path_found |=
Yapf().m_stopped_on_first_two_way_signal;
461 return next_trackdir;
467 bool result1 = pf1.CheckReverseTrain(v, t1, td1, t2, td2, reverse_penalty);
469 if (_debug_desync_level >= 2) {
471 pf2.DisableCache(
true);
472 bool result2 = pf2.CheckReverseTrain(v, t1, td1, t2, td2, reverse_penalty);
473 if (result1 != result2) {
474 DEBUG(desync, 2,
"CACHE ERROR: CheckReverseTrain() = [%s, %s]", result1 ?
"T" :
"F", result2 ?
"T" :
"F");
486 Yapf().SetOrigin(t1, td1, t2, td2, reverse_penalty,
false);
487 Yapf().SetDestination(v);
490 bool bFound =
Yapf().FindPath(v);
492 if (!bFound)
return false;
496 Node *pNode =
Yapf().GetBestNode();
497 while (pNode->m_parent != NULL) {
498 pNode = pNode->m_parent;
502 Node &best_org_node = *pNode;
503 bool reversed = (best_org_node.m_cost != 0);
508 template <
class Tpf_,
class Ttrack_follower,
class Tnode_list,
template <
class Types>
class TdestinationT,
template <
class Types>
class TfollowT>
514 typedef Ttrack_follower TrackFollower;
515 typedef Tnode_list NodeList;
518 typedef TfollowT<Types> PfFollow;
520 typedef TdestinationT<Types> PfDestination;
525 struct CYapfRail1 :
CYapfT<CYapfRail_TypesT<CYapfRail1 , CFollowTrackRail , CRailNodeListTrackDir, CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {};
526 struct CYapfRail2 :
CYapfT<CYapfRail_TypesT<CYapfRail2 , CFollowTrackRailNo90, CRailNodeListTrackDir, CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {};
528 struct CYapfAnyDepotRail1 :
CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail1, CFollowTrackRail , CRailNodeListTrackDir, CYapfDestinationAnyDepotRailT , CYapfFollowAnyDepotRailT> > {};
529 struct CYapfAnyDepotRail2 :
CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail2, CFollowTrackRailNo90, CRailNodeListTrackDir, CYapfDestinationAnyDepotRailT , CYapfFollowAnyDepotRailT> > {};
531 struct CYapfAnySafeTileRail1 :
CYapfT<CYapfRail_TypesT<CYapfAnySafeTileRail1, CFollowTrackFreeRail , CRailNodeListTrackDir, CYapfDestinationAnySafeTileRailT , CYapfFollowAnySafeTileRailT> > {};
532 struct CYapfAnySafeTileRail2 :
CYapfT<CYapfRail_TypesT<CYapfAnySafeTileRail2, CFollowTrackFreeRailNo90, CRailNodeListTrackDir, CYapfDestinationAnySafeTileRailT , CYapfFollowAnySafeTileRailT> > {};
539 PfnChooseRailTrack pfnChooseRailTrack = &CYapfRail1::stChooseRailTrack;
543 pfnChooseRailTrack = &CYapfRail2::stChooseRailTrack;
546 Trackdir td_ret = pfnChooseRailTrack(v, tile, enterdir, tracks, path_found, reserve_track, target);
562 int reverse_penalty = 0;
594 PfnCheckReverseTrain pfnCheckReverseTrain = CYapfRail1::stCheckReverseTrain;
598 pfnCheckReverseTrain = &CYapfRail2::stCheckReverseTrain;
602 if (reverse_penalty == 0) reverse_penalty = 1;
604 bool reverse = pfnCheckReverseTrain(v, tile, td, tile_rev, td_rev, reverse_penalty);
618 PfnFindNearestDepotTwoWay pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail1::stFindNearestDepotTwoWay;
622 pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail2::stFindNearestDepotTwoWay;
631 PfnFindNearestSafeTile pfnFindNearestSafeTile = CYapfAnySafeTileRail1::stFindNearestSafeTile;
635 pfnFindNearestSafeTile = &CYapfAnySafeTileRail2::stFindNearestSafeTile;
638 return pfnFindNearestSafeTile(v, tile, td, override_railtype);
646 CSegmentCostCacheBase::NotifyTrackLayoutChange(tile, track);
CStrA m_out
the output string
void TriggerStationRandomisation(Station *st, TileIndex tile, StationRandomTrigger trigger, CargoID cargo_type)
Trigger station randomisation.
Determining the destination for rail vehicles.
GameSettings _settings_game
Game settings of a running game or the scenario editor.
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.
Trackdir m_res_dest_td
The reservation target trackdir.
int32 TileIndexDiff
An offset value between to tiles.
static Track TrackdirToTrack(Trackdir trackdir)
Returns the Track that a given Trackdir represents.
bool ReserveSingleTrack(TileIndex tile, Trackdir td)
Try to reserve a single track/platform.
Tpf & Yapf()
to access inherited pathfinder
bool reverse
True if reversing is necessary for the train to get to this depot.
Trackdir m_res_fail_td
The trackdir where the reservation failed.
void YapfNotifyTrackLayoutChange(TileIndex tile, Track track)
Use this function to notify YAPF that track layout (or signal configuration) has change.
Track
These are used to specify a single track.
Types::NodeList::Titem Node
this will be our node type
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
char TransportTypeChar() const
Return debug report character to identify the transportation type.
PathfinderSettings pf
settings for all pathfinders
void PfFollowNode(Node &old_node)
Called by YAPF to move from the given node to the next tile.
FindDepotData YapfTrainFindNearestDepot(const Train *v, int max_penalty)
Used when user sends train to the nearest depot or if train needs servicing using YAPF...
TileIndex m_origin_tile
Tile our reservation will originate from.
bool forbid_90_deg
forbid trains to make 90 deg turns
static void SetRailStationReservation(TileIndex t, bool b)
Set the reservation state of the rail station.
void FindSafePositionOnNode(Node *node)
Check the node for a possible reservation target.
Tpf & Yapf()
to access inherited path finder
Node * m_res_node
The reservation target node.
PBSTileInfo FollowTrainReservation(const Train *v, Vehicle **train_on_res)
Follow a train reservation to the last tile.
Node::Key Key
key to hash tables
static DiagDirection TrackdirToExitdir(Trackdir trackdir)
Maps a trackdir to the (4-way) direction the tile is exited when following that trackdir.
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 TryReserveRailTrack(TileIndex tile, Track t, bool trigger_stations)
Try to reserve a specific track on a tile.
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
static bool IsCompatibleTrainStationTile(TileIndex test_tile, TileIndex station_tile)
Check if a tile is a valid continuation to a railstation tile.
TrackBits
Bitfield corresponding to Track.
static int s_rail_change_counter
if any track changes, this counter is incremented - that will invalidate segment cost cache ...
bool TryReservePath(PBSTileInfo *target, TileIndex origin)
Try to reserve the path till the reservation target.
static TileIndexDiff TileOffsByDiagDir(DiagDirection dir)
Convert a DiagDirection to a TileIndexDiff.
CYapfBaseT - A-star type path finder base class.
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?
char TransportTypeChar() const
return debug report character to identify the transportation type
VehicleType
Available vehicle types.
Entry point for OpenTTD to YAPF's cache.
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.
Trigger platform when train reserves path.
TileIndex m_res_dest
The reservation target tile.
bool IsWaitingPositionFree(const Train *v, TileIndex tile, Trackdir trackdir, bool forbid_90deg)
Check if a safe position is free.
static const int YAPF_TILE_LENGTH
Length (penalty) of one tile with YAPF.
Trackdir
Enumeration for tracks and directions.
YAPF template that uses Ttypes template argument to determine all YAPF components (base classes) from...
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
TileIndex tile
Current tile index.
void MarkTileDirtyByTile(TileIndex tile, int bridge_level_offset, int tile_height_override)
Mark a tile given by its index dirty for repaint.
bool UnreserveSingleTrack(TileIndex tile, Trackdir td)
Unreserve a single track/platform.
bool okay
True if tile is a safe waiting position, false otherwise.
DiagDirection
Enumeration for diagonal directions.
Node::Key Key
key to hash tables
static DiagDirection GetTunnelBridgeDirection(TileIndex t)
Get the direction pointing to the other end.
static Trackdir ReverseTrackdir(Trackdir trackdir)
Maps a trackdir to the reverse trackdir.
TileIndex tile
Tile the path ends, INVALID_TILE if no valid path was found.
#define DEBUG(name, level,...)
Output a line of debugging information.
'Train' is either a loco or a wagon.
TileIndex tile
The tile of the depot.
This struct contains information about the end of a reserved path.
bool YapfTrainCheckReverse(const Train *v)
Returns true if it is better to reverse the train before leaving station using YAPF.
TileIndex m_res_fail_tile
The tile where the reservation failed.
void SetReservationTarget(Node *node, TileIndex tile, Trackdir td)
Set the target to where the reservation should be extended.
Bitflag for a wormhole (used for tunnels)
static TileIndex GetOtherTunnelBridgeEnd(TileIndex t)
Determines type of the wormhole and returns its other end.
CYapfSegmentCostCacheGlobalT - the yapf cost cache provider that adds the segment cost caching functi...
Tpf & Yapf()
to access inherited path finder
static TileIndex TileVirtXY(uint x, uint y)
Get a tile from the virtual XY-coordinate.
Flag for an invalid track.
Trackdir GetVehicleTrackdir() const
Get the tracks of the train vehicle.
T * Last()
Get the last vehicle in the chain.
uint32 TileIndex
The index/ID of a Tile.
uint DistanceManhattan(TileIndex t0, TileIndex t1)
Gets the Manhattan distance between the two given tiles.
Helper container to find a depot.
Base includes/functions for YAPF.
T * Data()
Return pointer to the first data item - non-const version.
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
static Track FindFirstTrack(TrackBits tracks)
Returns first Track from TrackBits or INVALID_TRACK.
Types::NodeList::Titem Node
this will be our node type
Trackdir trackdir
The reserved trackdir on the tile.
static const TileIndex INVALID_TILE
The very nice invalid tile marker.
Node::Key Key
key to hash tables
YAPF origin provider base class - used when there are two tile/trackdir origins.
Flag for an invalid trackdir.
size_t Size() const
Return number of items in the Blob.
Cost determination for rails.
void PfFollowNode(Node &old_node)
Called by YAPF to move from the given node to the next tile.
#define TILE_ADD(x, y)
Adds to tiles together.
bool ReserveRailStationPlatform(TileIndex &tile, DiagDirection dir)
Reserve a railway platform.
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.
char TransportTypeChar() const
return debug report character to identify the transportation type
Class that represents the dump-into-string target.
static const int YAPF_INFINITE_PENALTY
This penalty is the equivalent of "infinite", which means that paths that get this penalty will be ch...
Types::NodeList::Titem Node
this will be our node type
void UnreserveRailTrack(TileIndex tile, Track t)
Lift the reservation of a specific track on a tile.
Tpf & Yapf()
to access inherited path finder
Node tailored for rail pathfinding.