12 #include "../../stdafx.h" 15 #include "../../roadstop_base.h" 17 #include "../../safeguards.h" 20 template <
class Types>
24 typedef typename Types::Tpf
Tpf;
26 typedef typename Types::NodeList::Titem
Node;
27 typedef typename Node::Key
Key;
37 return *
static_cast<Tpf *
>(
this);
54 return Yapf().PfGetSettings().road_slope_penalty;
70 cost +=
Yapf().PfGetSettings().road_crossing_penalty;
78 cost +=
Yapf().PfGetSettings().road_stop_penalty;
88 cost +=
Yapf().PfGetSettings().road_stop_bay_occupied_penalty * (!rs->
IsFreeBay(0) + !rs->
IsFreeBay(1)) / 2;
104 inline void SetMaxCost(
int max_cost)
106 m_max_cost = max_cost;
116 int segment_cost = 0;
121 int parent_cost = (n.m_parent != NULL) ? n.m_parent->m_cost : 0;
125 segment_cost +=
Yapf().OneTileCost(tile, trackdir);
129 if (
Yapf().PfDetectDestinationTile(tile, trackdir))
break;
133 if (m_max_cost > 0 && (parent_cost + segment_cost) > m_max_cost) {
144 TrackFollower F(
Yapf().GetVehicle());
145 if (!F.Follow(tile, trackdir))
break;
153 if (F.m_new_tile == n.m_key.m_tile && new_td == n.m_key.m_td)
return false;
157 tiles += F.m_tiles_skipped + 1;
160 segment_cost +=
Yapf().SlopeCost(tile, F.m_new_tile, trackdir);
165 int max_speed = F.GetSpeedLimit(&min_speed);
166 if (max_speed < max_veh_speed) segment_cost += 1 * (max_veh_speed - max_speed);
167 if (min_speed > max_veh_speed) segment_cost += 10 * (min_speed - max_veh_speed);
176 n.m_segment_last_tile = tile;
177 n.m_segment_last_td = trackdir;
180 n.m_cost = parent_cost + segment_cost;
186 template <
class Types>
190 typedef typename Types::Tpf
Tpf;
192 typedef typename Types::NodeList::Titem
Node;
193 typedef typename Node::Key
Key;
198 return *
static_cast<Tpf *
>(
this);
218 n.m_estimate = n.m_cost;
224 template <
class Types>
228 typedef typename Types::Tpf
Tpf;
230 typedef typename Types::NodeList::Titem
Node;
231 typedef typename Node::Key
Key;
236 StationID m_dest_station;
250 m_dest_station = INVALID_STATION;
260 return *
static_cast<Tpf *
>(
this);
267 return PfDetectDestinationTile(n.m_segment_last_tile, n.m_segment_last_td);
272 if (m_dest_station != INVALID_STATION) {
279 return tile == m_destTile &&
HasTrackdir(m_destTrackdirs, trackdir);
288 static const int dg_dir_to_x_offs[] = {-1, 0, 1, 0};
289 static const int dg_dir_to_y_offs[] = {0, 1, 0, -1};
290 if (PfDetectDestination(n)) {
291 n.m_estimate = n.m_cost;
297 int x1 = 2 *
TileX(tile) + dg_dir_to_x_offs[(int)exitdir];
298 int y1 = 2 *
TileY(tile) + dg_dir_to_y_offs[(int)exitdir];
299 int x2 = 2 *
TileX(m_destTile);
300 int y2 = 2 *
TileY(m_destTile);
301 int dx =
abs(x1 - x2);
302 int dy =
abs(y1 - y2);
303 int dmin =
min(dx, dy);
304 int dxy =
abs(dx - dy);
306 n.m_estimate = n.m_cost + d;
307 assert(n.m_estimate >= n.m_parent->m_estimate);
314 template <
class Types>
318 typedef typename Types::Tpf
Tpf;
320 typedef typename Types::NodeList::Titem
Node;
321 typedef typename Node::Key
Key;
327 return *
static_cast<Tpf *
>(
this);
339 TrackFollower F(
Yapf().GetVehicle());
340 if (F.Follow(old_node.m_segment_last_tile, old_node.m_segment_last_td)) {
341 Yapf().AddMultipleNodes(&old_node, F);
354 return pf.ChooseRoadTrack(v, tile, enterdir, path_found);
375 Yapf().SetOrigin(src_tile, src_trackdirs);
376 Yapf().SetDestination(v);
379 path_found =
Yapf().FindPath(v);
383 Node *pNode =
Yapf().GetBestNode();
387 while (pNode->m_parent != NULL) {
388 pNode = pNode->m_parent;
391 Node &best_next_node = *pNode;
392 assert(best_next_node.GetTile() == tile);
393 next_trackdir = best_next_node.GetTrackdir();
395 return next_trackdir;
401 return pf.DistanceToTile(v, tile);
407 if (dst_tile == v->
tile) {
412 if (!SetOriginFromVehiclePos(v))
return UINT_MAX;
415 Yapf().SetDestination(v);
418 uint dist = UINT_MAX;
421 if (!
Yapf().FindPath(v))
return dist;
423 Node *pNode =
Yapf().GetBestNode();
427 dist = pNode->GetCostEstimate();
451 return pf.FindNearestDepot(v, tile, td, max_distance);
465 Yapf().SetMaxCost(max_distance);
471 Node *n =
Yapf().GetBestNode();
476 template <
class Tpf_,
class Tnode_list,
template <
class Types>
class Tdestination>
483 typedef Tnode_list NodeList;
488 typedef Tdestination<Types> PfDestination;
493 struct CYapfRoad1 :
CYapfT<CYapfRoad_TypesT<CYapfRoad1 , CRoadNodeListTrackDir, CYapfDestinationTileRoadT > > {};
494 struct CYapfRoad2 :
CYapfT<CYapfRoad_TypesT<CYapfRoad2 , CRoadNodeListExitDir , CYapfDestinationTileRoadT > > {};
496 struct CYapfRoadAnyDepot1 :
CYapfT<CYapfRoad_TypesT<CYapfRoadAnyDepot1, CRoadNodeListTrackDir, CYapfDestinationAnyDepotRoadT> > {};
497 struct CYapfRoadAnyDepot2 :
CYapfT<CYapfRoad_TypesT<CYapfRoadAnyDepot2, CRoadNodeListExitDir , CYapfDestinationAnyDepotRoadT> > {};
504 PfnChooseRoadTrack pfnChooseRoadTrack = &CYapfRoad2::stChooseRoadTrack;
508 pfnChooseRoadTrack = &CYapfRoad1::stChooseRoadTrack;
511 Trackdir td_ret = pfnChooseRoadTrack(v, tile, enterdir, path_found);
525 PfnFindNearestDepot pfnFindNearestDepot = &CYapfRoadAnyDepot2::stFindNearestDepot;
529 pfnFindNearestDepot = &CYapfRoadAnyDepot1::stFindNearestDepot;
532 return pfnFindNearestDepot(v, tile, trackdir, max_distance);
static TileType GetTileType(TileIndex tile)
Get the tiletype of a given tile.
GameSettings _settings_game
Game settings of a running game or the scenario editor.
bool SetOriginFromVehiclePos(const RoadVehicle *v)
Return true if the valid origin (tile/trackdir) was set from the current vehicle position.
YAPF origin provider base class - used when origin is one tile / multiple trackdirs.
Node::Key Key
key to hash tables
Node::Key Key
key to hash tables
bool PfCalcEstimate(Node &n)
Called by YAPF to calculate cost estimate.
static RoadStopType GetRoadStopType(TileIndex t)
Get the road stop type of this tile.
int GetLength() const
Get the length of this drive through stop.
int OneTileCost(TileIndex tile, Trackdir trackdir)
return one tile cost
Flag for an invalid trackdirbit value.
A tile with road (or tram tracks)
int GetDisplayMaxSpeed() const
Gets the maximum speed in km-ish/h that can be sent into SetDParam for string processing.
int GetOccupied() const
Get the amount of occupied space in this drive through stop.
Tpf & Yapf()
to access inherited path finder
TileIndex dest_tile
Heading for this tile.
CYapfSegmentCostCacheNoneT - the formal only yapf cost cache provider that implements PfNodeCacheFetc...
bool PfCalcCost(Node &n, const TrackFollower *tf)
Called by YAPF to calculate the cost from the origin to the given node.
static uint TileX(TileIndex tile)
Get the X component of a tile.
PathfinderSettings pf
settings for all pathfinders
Types::NodeList::Titem Node
this will be our node type
Types::NodeList::Titem Node
this will be our node type
static DiagDirection GetRoadDepotDirection(TileIndex t)
Get the direction of the exit of a road depot.
FindDepotData FindNearestDepot(const RoadVehicle *v, TileIndex tile, Trackdir td, int max_distance)
Find the best depot for a road vehicle.
static TrackdirBits DiagdirReachesTrackdirs(DiagDirection diagdir)
Returns all trackdirs that can be reached when entering a tile from a given (diagonal) direction...
static bool IsLevelCrossing(TileIndex t)
Return whether a tile is a level crossing.
void PfFollowNode(Node &old_node)
Called by YAPF to move from the given node to the next tile.
static bool IsDriveThroughStopTile(TileIndex t)
Is tile t a drive through road stop station?
static DiagDirection TrackdirToExitdir(Trackdir trackdir)
Maps a trackdir to the (4-way) direction the tile is exited when following that trackdir.
Node::Key Key
key to hash tables
static const uint TILE_SIZE
Tile size in world coordinates.
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...
Buses, trucks and trams belong to this class.
char TransportTypeChar() const
return debug report character to identify the transportation type
static TileIndexDiff TileOffsByDiagDir(DiagDirection dir)
Convert a DiagDirection to a TileIndexDiff.
static bool IsTileType(TileIndex tile, TileType type)
Checks if a tile is a given tiletype.
CYapfBaseT - A-star type path finder base class.
bool disable_node_optimization
whether to use exit-dir instead of trackdir in node key
YAPFSettings yapf
pathfinder settings for the yet another pathfinder
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
VehicleType
Available vehicle types.
static bool IsTruckStop(TileIndex t)
Is the station at t a truck stop?
static TrackdirBits TrackdirToTrackdirBits(Trackdir trackdir)
Maps a Trackdir to the corresponding TrackdirBits value.
bool IsType(OrderType type) const
Check whether this order is of the given type.
static DiagDirection ReverseDiagDir(DiagDirection d)
Returns the reverse direction of the given DiagDirection.
static bool HasTrackdir(TrackdirBits trackdirs, Trackdir trackdir)
Checks whether a TrackdirBits has a given Trackdir.
Trackdir GetVehicleTrackdir() const
Returns the Trackdir on which the vehicle is currently located.
Types::Tpf Tpf
pathfinder (derived from THIS class)
static const int YAPF_TILE_LENGTH
Length (penalty) of one tile with YAPF.
static bool IsRoadDepotTile(TileIndex t)
Return whether a tile is a road depot tile.
Trackdir
Enumeration for tracks and directions.
YAPF template that uses Ttypes template argument to determine all YAPF components (base classes) from...
bool PfDetectDestination(Node &n)
Called by YAPF to detect if node ends in the desired destination.
TileIndex tile
Current tile index.
bool HasArticulatedPart() const
Check if an engine has an articulated part.
static Trackdir DiagDirToDiagTrackdir(DiagDirection diagdir)
Maps a (4-way) direction to the diagonal trackdir that runs in that direction.
Trackdir YapfRoadVehicleChooseTrack(const RoadVehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool &path_found)
Finds the best path for given road vehicle using YAPF.
bool IsFreeBay(uint nr) const
Checks whether the given bay is free in this road stop.
DiagDirection
Enumeration for diagonal directions.
static T min(const T a, const T b)
Returns the minimum of two values.
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
Track follower helper template class (can serve pathfinders and vehicle controllers).
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...
TrackStatus GetTileTrackStatus(TileIndex tile, TransportType mode, uint sub_mode, DiagDirection side)
Returns information about trackdirs and signal states.
Container for each entry point of a drive through road stop.
static StationID GetStationIndex(TileIndex t)
Get StationID from a tile.
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
static T KillFirstBit(T value)
Clear the first bit in an integer.
bool IsBus() const
Check whether a roadvehicle is a bus.
Node tailored for road pathfinding.
Types::NodeList::Titem Node
this will be our node type
DestinationID GetDestination() const
Gets the destination of this order.
Tpf & Yapf()
to access inherited path finder
uint32 TileIndex
The index/ID of a Tile.
Helper container to find a depot.
Base includes/functions for YAPF.
static uint TileY(TileIndex tile)
Get the Y component of a tile.
bool PfDetectDestination(Node &n)
Called by YAPF to detect if node ends in the desired destination.
static T abs(const T a)
Returns the absolute value of (scalar) variable.
static bool IsDiagonalTrackdir(Trackdir trackdir)
Checks if a given Trackdir is diagonal.
static uint8 FindFirstBit2x64(const int value)
Finds the position of the first non-zero bit in an integer.
Transport by road vehicle.
const Entry * GetEntry(DiagDirection dir) const
Get the drive through road stop entry struct for the given direction.
TrackdirBits
Enumeration of bitmasks for the TrackDirs.
Types::NodeList::Titem Node
this will be our node type
A Stop for a Road Vehicle.
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...
Tpf & Yapf()
to access inherited path finder
static const uint MAX_MAP_SIZE
Maximal map size = 4096.
Node::Key Key
key to hash tables
Flag for an invalid trackdir.
Tpf & Yapf()
to access inherited path finder
static const int YAPF_TILE_CORNER_LENGTH
Length (penalty) of a corner with YAPF.
Types::TrackFollower TrackFollower
track follower helper
static bool IsBusStop(TileIndex t)
Is the station at t a bus stop?
static TrackdirBits TrackStatusToTrackdirBits(TrackStatus ts)
Returns the present-trackdir-information of a TrackStatus.
Order current_order
The current order (+ status, like: loading)
static RoadStop * GetByTile(TileIndex tile, RoadStopType type)
Find a roadstop at given tile.
bool PfCalcEstimate(Node &n)
Called by YAPF to calculate cost estimate.