OpenTTD Source
1.11.0-beta2
|
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 int _total_pf_time_us = 0;
39 template <
class Types>
43 typedef typename Types::Tpf
Tpf;
44 typedef typename Types::TrackFollower TrackFollower;
45 typedef typename Types::NodeList::Titem
Node;
51 return *
static_cast<Tpf *
>(
this);
139 assert(node->m_parent !=
nullptr);
142 if (node->m_parent->m_num_signals_passed >= 2)
return;
155 if (target !=
nullptr) {
158 target->
okay =
false;
164 for (
Node *node =
m_res_node; node->m_parent !=
nullptr; node = node->m_parent) {
174 }
while (fail_node != node && (fail_node = fail_node->m_parent) !=
nullptr);
180 if (target !=
nullptr) target->
okay =
true;
190 template <
class Types>
194 typedef typename Types::Tpf
Tpf;
195 typedef typename Types::TrackFollower TrackFollower;
196 typedef typename Types::NodeList::Titem
Node;
197 typedef typename Node::Key
Key;
203 return *
static_cast<Tpf *
>(
this);
214 TrackFollower F(
Yapf().GetVehicle());
215 if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir())) {
216 Yapf().AddMultipleNodes(&old_node, F);
238 if (max_penalty != 0) pf1.DisableCache(
true);
239 FindDepotData result1 = pf1.FindNearestDepotTwoWay(v, t1, td1, t2, td2, max_penalty, reverse_penalty);
241 if (_debug_desync_level >= 2) {
243 pf2.DisableCache(
true);
244 FindDepotData result2 = pf2.FindNearestDepotTwoWay(v, t1, td1, t2, td2, max_penalty, reverse_penalty);
246 DEBUG(desync, 2,
"CACHE ERROR: FindNearestDepotTwoWay() = [%s, %s]",
259 Yapf().SetOrigin(t1, td1, t2, td2, reverse_penalty,
true);
260 Yapf().SetDestination(v);
261 Yapf().SetMaxCost(max_penalty);
271 while (pNode->m_parent !=
nullptr) {
272 pNode = pNode->m_parent;
277 return FindDepotData(n->GetLastTile(), n->m_cost, pNode->m_cost != 0);
281 template <
class Types>
285 typedef typename Types::Tpf
Tpf;
286 typedef typename Types::TrackFollower TrackFollower;
287 typedef typename Types::NodeList::Titem
Node;
288 typedef typename Node::Key
Key;
294 return *
static_cast<Tpf *
>(
this);
305 TrackFollower F(
Yapf().GetVehicle(),
Yapf().GetCompatibleRailTypes());
306 if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir()) && F.MaskReservedTracks()) {
307 Yapf().AddMultipleNodes(&old_node, F);
322 if (_debug_desync_level < 2) {
323 result1 = pf1.FindNearestSafeTile(v, t1, td, override_railtype,
false);
325 bool result2 = pf1.FindNearestSafeTile(v, t1, td, override_railtype,
true);
327 pf2.DisableCache(
true);
328 result1 = pf2.FindNearestSafeTile(v, t1, td, override_railtype,
false);
329 if (result1 != result2) {
330 DEBUG(desync, 2,
"CACHE ERROR: FindSafeTile() = [%s, %s]", result2 ?
"T" :
"F", result1 ?
"T" :
"F");
338 bool FindNearestSafeTile(
const Train *v,
TileIndex t1,
Trackdir td,
bool override_railtype,
bool dont_reserve)
341 Yapf().SetOrigin(t1, td);
342 Yapf().SetDestination(v, override_railtype);
344 bool bFound =
Yapf().FindPath(v);
345 if (!bFound)
return false;
352 Node *pPrev =
nullptr;
353 while (pNode->m_parent !=
nullptr) {
355 pNode = pNode->m_parent;
360 return dont_reserve || this->
TryReservePath(
nullptr, pNode->GetLastTile());
364 template <
class Types>
368 typedef typename Types::Tpf
Tpf;
369 typedef typename Types::TrackFollower TrackFollower;
370 typedef typename Types::NodeList::Titem
Node;
371 typedef typename Node::Key
Key;
377 return *
static_cast<Tpf *
>(
this);
388 TrackFollower F(
Yapf().GetVehicle());
389 if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir())) {
390 Yapf().AddMultipleNodes(&old_node, F);
406 if (_debug_desync_level < 2) {
407 result1 = pf1.ChooseRailTrack(v, tile, enterdir, tracks, path_found, reserve_track, target);
409 result1 = pf1.ChooseRailTrack(v, tile, enterdir, tracks, path_found,
false,
nullptr);
411 pf2.DisableCache(
true);
412 Trackdir result2 = pf2.ChooseRailTrack(v, tile, enterdir, tracks, path_found, reserve_track, target);
413 if (result1 != result2) {
414 DEBUG(desync, 2,
"CACHE ERROR: ChooseRailTrack() = [%d, %d]", result1, result2);
429 Yapf().SetDestination(v);
432 path_found =
Yapf().FindPath(v);
437 if (pNode !=
nullptr) {
443 Node *pPrev =
nullptr;
444 while (pNode->m_parent !=
nullptr) {
446 pNode = pNode->m_parent;
451 Node &best_next_node = *pPrev;
452 next_trackdir = best_next_node.GetTrackdir();
454 if (reserve_track && path_found) this->
TryReservePath(target, pNode->GetLastTile());
458 path_found |=
Yapf().m_stopped_on_first_two_way_signal;
459 return next_trackdir;
465 bool result1 = pf1.CheckReverseTrain(v, t1, td1, t2, td2, reverse_penalty);
467 if (_debug_desync_level >= 2) {
469 pf2.DisableCache(
true);
470 bool result2 = pf2.CheckReverseTrain(v, t1, td1, t2, td2, reverse_penalty);
471 if (result1 != result2) {
472 DEBUG(desync, 2,
"CACHE ERROR: CheckReverseTrain() = [%s, %s]", result1 ?
"T" :
"F", result2 ?
"T" :
"F");
484 Yapf().SetOrigin(t1, td1, t2, td2, reverse_penalty,
false);
485 Yapf().SetDestination(v);
488 bool bFound =
Yapf().FindPath(v);
490 if (!bFound)
return false;
495 while (pNode->m_parent !=
nullptr) {
496 pNode = pNode->m_parent;
500 Node &best_org_node = *pNode;
501 bool reversed = (best_org_node.m_cost != 0);
506 template <
class Tpf_,
class Ttrack_follower,
class Tnode_list,
template <
class Types>
class TdestinationT,
template <
class Types>
class TfollowT>
512 typedef Ttrack_follower TrackFollower;
513 typedef Tnode_list NodeList;
516 typedef TfollowT<Types> PfFollow;
518 typedef TdestinationT<Types> PfDestination;
523 struct CYapfRail1 :
CYapfT<CYapfRail_TypesT<CYapfRail1 , CFollowTrackRail , CRailNodeListTrackDir, CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {};
524 struct CYapfRail2 :
CYapfT<CYapfRail_TypesT<CYapfRail2 , CFollowTrackRailNo90, CRailNodeListTrackDir, CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {};
526 struct CYapfAnyDepotRail1 :
CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail1, CFollowTrackRail , CRailNodeListTrackDir, CYapfDestinationAnyDepotRailT , CYapfFollowAnyDepotRailT> > {};
527 struct CYapfAnyDepotRail2 :
CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail2, CFollowTrackRailNo90, CRailNodeListTrackDir, CYapfDestinationAnyDepotRailT , CYapfFollowAnyDepotRailT> > {};
529 struct CYapfAnySafeTileRail1 :
CYapfT<CYapfRail_TypesT<CYapfAnySafeTileRail1, CFollowTrackFreeRail , CRailNodeListTrackDir, CYapfDestinationAnySafeTileRailT , CYapfFollowAnySafeTileRailT> > {};
530 struct CYapfAnySafeTileRail2 :
CYapfT<CYapfRail_TypesT<CYapfAnySafeTileRail2, CFollowTrackFreeRailNo90, CRailNodeListTrackDir, CYapfDestinationAnySafeTileRailT , CYapfFollowAnySafeTileRailT> > {};
537 PfnChooseRailTrack pfnChooseRailTrack = &CYapfRail1::stChooseRailTrack;
541 pfnChooseRailTrack = &CYapfRail2::stChooseRailTrack;
544 Trackdir td_ret = pfnChooseRailTrack(v, tile, enterdir, tracks, path_found, reserve_track, target);
560 int reverse_penalty = 0;
592 PfnCheckReverseTrain pfnCheckReverseTrain = CYapfRail1::stCheckReverseTrain;
596 pfnCheckReverseTrain = &CYapfRail2::stCheckReverseTrain;
600 if (reverse_penalty == 0) reverse_penalty = 1;
602 bool reverse = pfnCheckReverseTrain(v, tile, td, tile_rev, td_rev, reverse_penalty);
616 PfnFindNearestDepotTwoWay pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail1::stFindNearestDepotTwoWay;
620 pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail2::stFindNearestDepotTwoWay;
629 PfnFindNearestSafeTile pfnFindNearestSafeTile = CYapfAnySafeTileRail1::stFindNearestSafeTile;
633 pfnFindNearestSafeTile = &CYapfAnySafeTileRail2::stFindNearestSafeTile;
636 return pfnFindNearestSafeTile(v, tile, td, override_railtype);
644 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.