Go to the documentation of this file.
10 #include "../../stdafx.h"
13 #include "../../roadstop_base.h"
15 #include "../../safeguards.h"
18 template <
class Types>
22 typedef typename Types::Tpf
Tpf;
24 typedef typename Types::NodeList::Titem
Node;
25 typedef typename Node::Key
Key;
35 return *
static_cast<Tpf *
>(
this);
52 return Yapf().PfGetSettings().road_slope_penalty;
68 cost +=
Yapf().PfGetSettings().road_crossing_penalty;
76 cost +=
Yapf().PfGetSettings().road_stop_penalty;
86 cost +=
Yapf().PfGetSettings().road_stop_bay_occupied_penalty * (!rs->
IsFreeBay(0) + !rs->
IsFreeBay(1)) / 2;
102 inline void SetMaxCost(
int max_cost)
104 m_max_cost = max_cost;
114 int segment_cost = 0;
119 int parent_cost = (n.m_parent !=
nullptr) ? n.m_parent->m_cost : 0;
123 segment_cost +=
Yapf().OneTileCost(tile, trackdir);
127 if (
Yapf().PfDetectDestinationTile(tile, trackdir))
break;
131 if (m_max_cost > 0 && (parent_cost + segment_cost) > m_max_cost) {
143 if (!F.Follow(tile, trackdir))
break;
151 if (F.m_new_tile == n.m_key.m_tile && new_td == n.m_key.m_td)
return false;
155 tiles += F.m_tiles_skipped + 1;
158 segment_cost +=
Yapf().SlopeCost(tile, F.m_new_tile, trackdir);
163 int max_speed = F.GetSpeedLimit(&min_speed);
164 if (max_speed < max_veh_speed) segment_cost +=
YAPF_TILE_LENGTH * (max_veh_speed - max_speed) * (4 + F.m_tiles_skipped) / max_veh_speed;
165 if (min_speed > max_veh_speed) segment_cost +=
YAPF_TILE_LENGTH * (min_speed - max_veh_speed);
174 n.m_segment_last_tile = tile;
175 n.m_segment_last_td = trackdir;
178 n.m_cost = parent_cost + segment_cost;
184 template <
class Types>
188 typedef typename Types::Tpf
Tpf;
189 typedef typename Types::TrackFollower TrackFollower;
190 typedef typename Types::NodeList::Titem
Node;
191 typedef typename Node::Key
Key;
196 return *
static_cast<Tpf *
>(
this);
216 n.m_estimate = n.m_cost;
222 template <
class Types>
226 typedef typename Types::Tpf
Tpf;
227 typedef typename Types::TrackFollower TrackFollower;
228 typedef typename Types::NodeList::Titem
Node;
229 typedef typename Node::Key
Key;
234 StationID m_dest_station;
248 m_dest_station = INVALID_STATION;
254 const Station *GetDestinationStation()
const
263 return *
static_cast<Tpf *
>(
this);
270 return PfDetectDestinationTile(n.m_segment_last_tile, n.m_segment_last_td);
275 if (m_dest_station != INVALID_STATION) {
282 return tile == m_destTile &&
HasTrackdir(m_destTrackdirs, trackdir);
291 static const int dg_dir_to_x_offs[] = {-1, 0, 1, 0};
292 static const int dg_dir_to_y_offs[] = {0, 1, 0, -1};
294 n.m_estimate = n.m_cost;
300 int x1 = 2 *
TileX(tile) + dg_dir_to_x_offs[(int)exitdir];
301 int y1 = 2 *
TileY(tile) + dg_dir_to_y_offs[(int)exitdir];
302 int x2 = 2 *
TileX(m_destTile);
303 int y2 = 2 *
TileY(m_destTile);
304 int dx =
abs(x1 - x2);
305 int dy =
abs(y1 - y2);
306 int dmin = std::min(dx, dy);
307 int dxy =
abs(dx - dy);
309 n.m_estimate = n.m_cost + d;
310 assert(n.m_estimate >= n.m_parent->m_estimate);
317 template <
class Types>
321 typedef typename Types::Tpf
Tpf;
322 typedef typename Types::TrackFollower TrackFollower;
323 typedef typename Types::NodeList::Titem
Node;
324 typedef typename Node::Key
Key;
330 return *
static_cast<Tpf *
>(
this);
342 TrackFollower F(
Yapf().GetVehicle());
343 if (F.Follow(old_node.m_segment_last_tile, old_node.m_segment_last_td)) {
344 Yapf().AddMultipleNodes(&old_node, F);
357 return pf.ChooseRoadTrack(v, tile, enterdir, path_found, path_cache);
378 Yapf().SetOrigin(src_tile, src_trackdirs);
379 Yapf().SetDestination(v);
382 path_found =
Yapf().FindPath(v);
387 if (pNode !=
nullptr) {
389 for (
Node *n = pNode; n->m_parent !=
nullptr; n = n->m_parent) steps++;
393 while (pNode->m_parent !=
nullptr) {
396 path_cache.td.push_front(pNode->GetTrackdir());
397 path_cache.tile.push_front(pNode->GetTile());
399 pNode = pNode->m_parent;
402 Node &best_next_node = *pNode;
403 assert(best_next_node.GetTile() == tile);
404 next_trackdir = best_next_node.GetTrackdir();
406 if (path_found && !path_cache.empty() && tile == v->
dest_tile) {
407 path_cache.td.pop_back();
408 path_cache.tile.pop_back();
412 const Station *st =
Yapf().GetDestinationStation();
414 const RoadStop *stop = st->GetPrimaryRoadStop(v);
420 while (!path_cache.empty() && non_cached_area.
Contains(path_cache.tile.back())) {
421 path_cache.td.pop_back();
422 path_cache.tile.pop_back();
427 return next_trackdir;
433 return pf.DistanceToTile(v, tile);
439 if (dst_tile == v->
tile) {
447 Yapf().SetDestination(v);
450 uint dist = UINT_MAX;
453 if (!
Yapf().FindPath(v))
return dist;
456 if (pNode !=
nullptr) {
459 dist = pNode->GetCostEstimate();
483 return pf.FindNearestDepot(v, tile, td, max_distance);
497 Yapf().SetMaxCost(max_distance);
508 template <
class Tpf_,
class Tnode_list,
template <
class Types>
class Tdestination>
515 typedef Tnode_list NodeList;
520 typedef Tdestination<Types> PfDestination;
525 struct CYapfRoad1 :
CYapfT<CYapfRoad_TypesT<CYapfRoad1 , CRoadNodeListTrackDir, CYapfDestinationTileRoadT > > {};
526 struct CYapfRoad2 :
CYapfT<CYapfRoad_TypesT<CYapfRoad2 , CRoadNodeListExitDir , CYapfDestinationTileRoadT > > {};
528 struct CYapfRoadAnyDepot1 :
CYapfT<CYapfRoad_TypesT<CYapfRoadAnyDepot1, CRoadNodeListTrackDir, CYapfDestinationAnyDepotRoadT> > {};
529 struct CYapfRoadAnyDepot2 :
CYapfT<CYapfRoad_TypesT<CYapfRoadAnyDepot2, CRoadNodeListExitDir , CYapfDestinationAnyDepotRoadT> > {};
536 PfnChooseRoadTrack pfnChooseRoadTrack = &CYapfRoad2::stChooseRoadTrack;
540 pfnChooseRoadTrack = &CYapfRoad1::stChooseRoadTrack;
543 Trackdir td_ret = pfnChooseRoadTrack(v, tile, enterdir, path_found, path_cache);
558 PfnFindNearestDepot pfnFindNearestDepot = &CYapfRoadAnyDepot2::stFindNearestDepot;
562 pfnFindNearestDepot = &CYapfRoadAnyDepot1::stFindNearestDepot;
565 return pfnFindNearestDepot(v, tile, trackdir, max_distance);
Buses, trucks and trams belong to this class.
Tpf & Yapf()
to access inherited path finder
static DiagDirection GetRoadDepotDirection(TileIndex t)
Get the direction of the exit of a road depot.
uint32 TileIndex
The index/ID of a Tile.
Node::Key Key
key to hash tables
bool IsType(OrderType type) const
Check whether this order is of the given type.
static TileIndexDiff TileOffsByDiagDir(DiagDirection dir)
Convert a DiagDirection to a TileIndexDiff.
static bool IsBusStop(TileIndex t)
Is the station at t a bus stop?
Helper container to find a depot.
TrackdirBits
Enumeration of bitmasks for the TrackDirs.
bool PfCalcCost(Node &n, const TrackFollower *tf)
Called by YAPF to calculate the cost from the origin to the given node.
int GetOccupied() const
Get the amount of occupied space in this drive through stop.
TileIndex xy
Position on the map.
DestinationID GetDestination() const
Gets the destination of this order.
bool PfCalcEstimate(Node &n)
Called by YAPF to calculate cost estimate.
int OneTileCost(TileIndex tile, Trackdir trackdir)
return one tile cost
static bool IsRoadDepotTile(TileIndex t)
Return whether a tile is a road depot tile.
bool PfCalcEstimate(Node &n)
Called by YAPF to calculate cost estimate.
Types::TrackFollower TrackFollower
track follower helper
static T KillFirstBit(T value)
Clear the first bit in an integer.
FindDepotData YapfRoadVehicleFindNearestDepot(const RoadVehicle *v, int max_distance)
Used when user sends road vehicle to the nearest depot or if road vehicle needs servicing using YAPF.
static Trackdir DiagDirToDiagTrackdir(DiagDirection diagdir)
Maps a (4-way) direction to the diagonal trackdir that runs in that direction.
static RoadStopType GetRoadStopType(TileIndex t)
Get the road stop type of this tile.
static RoadStop * GetByTile(TileIndex tile, RoadStopType type)
Find a roadstop at given tile.
static bool IsDriveThroughStopTile(TileIndex t)
Is tile t a drive through road stop station?
static const uint TILE_SIZE
Tile size in world coordinates.
const Entry * GetEntry(DiagDirection dir) const
Get the drive through road stop entry struct for the given direction.
static uint TileY(TileIndex tile)
Get the Y component of a tile.
YAPF template that uses Ttypes template argument to determine all YAPF components (base classes) from...
RoadType roadtype
Roadtype of this vehicle.
static bool IsTruckStop(TileIndex t)
Is the station at t a truck stop?
@ MP_ROAD
A tile with road (or tram tracks)
static bool IsLevelCrossing(TileIndex t)
Return whether a tile is a level crossing.
Types::NodeList::Titem Node
this will be our node type
@ INVALID_TRACKDIR_BIT
Flag for an invalid trackdirbit value.
static uint TileX(TileIndex tile)
Get the X component of a tile.
TrackStatus GetTileTrackStatus(TileIndex tile, TransportType mode, uint sub_mode, DiagDirection side)
Returns information about trackdirs and signal states.
uint16 GetMaxSpeed() const
Get the maxmimum speed in km-ish/h a vehicle is allowed to reach on the way to the destination.
YAPF origin provider base class - used when origin is one tile / multiple trackdirs.
@ TRANSPORT_ROAD
Transport by road vehicle.
PathfinderSettings pf
settings for all pathfinders
TileIndex dest_tile
Heading for this tile.
Types::Tpf Tpf
pathfinder (derived from THIS class)
static const int YAPF_TILE_LENGTH
Length (penalty) of one tile with YAPF.
TileIndex tile
Current tile index.
static DiagDirection TrackdirToExitdir(Trackdir trackdir)
Maps a trackdir to the (4-way) direction the tile is exited when following that trackdir.
TileArea truck_station
Tile area the truck 'station' part covers.
Order current_order
The current order (+ status, like: loading)
static uint8 FindFirstBit2x64(const int value)
Finds the position of the first non-zero bit in an integer.
Represents the covered area of e.g.
GameSettings _settings_game
Game settings of a running game or the scenario editor.
static DiagDirection ReverseDiagDir(DiagDirection d)
Returns the reverse direction of the given DiagDirection.
TileArea bus_station
Tile area the bus 'station' part covers.
@ INVALID_TRACKDIR
Flag for an invalid trackdir.
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
DiagDirection
Enumeration for diagonal directions.
static const int YAPF_ROADVEH_PATH_CACHE_SEGMENTS
Maximum segments of road vehicle path cache.
static bool IsTileType(TileIndex tile, TileType type)
Checks if a tile is a given tiletype.
Types::NodeList::Titem Node
this will be our node type
static TileIndex CalcClosestStationTile(StationID station, TileIndex tile, StationType station_type)
Calculates the tile of given station that is closest to a given tile for this we assume the station i...
bool SetOriginFromVehiclePos(const RoadVehicle *v)
Return true if the valid origin (tile/trackdir) was set from the current vehicle position.
static TrackdirBits DiagdirReachesTrackdirs(DiagDirection diagdir)
Returns all trackdirs that can be reached when entering a tile from a given (diagonal) direction.
Tpf & Yapf()
to access inherited path finder
CYapfSegmentCostCacheNoneT - the formal only yapf cost cache provider that implements PfNodeCacheFetc...
static TrackdirBits GetTrackdirBitsForRoad(TileIndex tile, RoadTramType rtt)
Wrapper around GetTileTrackStatus() and TrackStatusToTrackdirBits(), as for single tram bits GetTileT...
@ TRACKDIR_BIT_NONE
No track build.
Types::NodeList::Titem Node
this will be our node type
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
bool PfDetectDestination(Node &n)
Called by YAPF to detect if node ends in the desired destination.
Types::NodeList::Titem Node
this will be our node type
static bool IsDriveThroughRoadStopContinuation(TileIndex rs, TileIndex next)
Checks whether the 'next' tile is still part of the road same drive through stop 'rs' in the same dir...
void PfFollowNode(Node &old_node)
Called by YAPF to move from the given node to the next tile.
bool disable_node_optimization
whether to use exit-dir instead of trackdir in node key
@ MP_STATION
A tile of a station.
static StationID GetStationIndex(TileIndex t)
Get StationID from a tile.
bool HasArticulatedPart() const
Check if an engine has an articulated part.
Tpf & Yapf()
to access inherited path finder
Node::Key Key
key to hash tables
static TrackdirBits TrackStatusToTrackdirBits(TrackStatus ts)
Returns the present-trackdir-information of a TrackStatus.
int GetLength() const
Get the length of this drive through stop.
int GetDisplayMaxSpeed() const
Gets the maximum speed in km-ish/h that can be sent into SetDParam for string processing.
static T abs(const T a)
Returns the absolute value of (scalar) variable.
Tpf & Yapf()
to access inherited path finder
static TrackdirBits TrackdirToTrackdirBits(Trackdir trackdir)
Maps a Trackdir to the corresponding TrackdirBits value.
FindDepotData FindNearestDepot(const RoadVehicle *v, TileIndex tile, Trackdir td, int max_distance)
Find the best depot for a road vehicle.
char TransportTypeChar() const
return debug report character to identify the transportation type
YAPFSettings yapf
pathfinder settings for the yet another pathfinder
static Station * GetIfValid(size_t index)
Returns station if the index is a valid index for this station type.
static const int YAPF_TILE_CORNER_LENGTH
Length (penalty) of a corner with YAPF.
bool IsFreeBay(uint nr) const
Checks whether the given bay is free in this road stop.
bool IsBus() const
Check whether a roadvehicle is a bus.
OrthogonalTileArea & Expand(int rad)
Expand a tile area by rad tiles in each direction, keeping within map bounds.
Trackdir
Enumeration for tracks and directions.
Node::Key Key
key to hash tables
CYapfBaseT - A-star type path finder base class.
static TileType GetTileType(TileIndex tile)
Get the tiletype of a given tile.
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
static const int YAPF_ROADVEH_PATH_CACHE_DESTINATION_LIMIT
Distance from destination road stops to not cache any further.
A Stop for a Road Vehicle.
static const uint MAX_MAP_SIZE
Maximal map size = 4096.
Trackdir YapfRoadVehicleChooseTrack(const RoadVehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool &path_found, RoadVehPathCache &path_cache)
Finds the best path for given road vehicle using YAPF.
static bool HasTrackdir(TrackdirBits trackdirs, Trackdir trackdir)
Checks whether a TrackdirBits has a given Trackdir.
Container for each entry point of a drive through road stop.
Node::Key Key
key to hash tables
RoadStop * GetNextRoadStop(const struct RoadVehicle *v) const
Get the next road stop accessible by this vehicle.
Track follower helper template class (can serve pathfinders and vehicle controllers).
Trackdir GetVehicleTrackdir() const
Returns the Trackdir on which the vehicle is currently located.
static bool IsDiagonalTrackdir(Trackdir trackdir)
Checks if a given Trackdir is diagonal.
bool Contains(TileIndex tile) const
Does this tile area contain a tile?
bool PfDetectDestination(Node &n)
Called by YAPF to detect if node ends in the desired destination.