OpenTTD Source
20240917-master-g9ab0a47812
|
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;
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 !=
nullptr) ? 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) {
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 +=
YAPF_TILE_LENGTH * (max_veh_speed - max_speed) * (4 + F.m_tiles_skipped) / max_veh_speed;
167 if (min_speed > max_veh_speed) segment_cost +=
YAPF_TILE_LENGTH * (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;
191 typedef typename Types::TrackFollower TrackFollower;
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;
229 typedef typename Types::TrackFollower TrackFollower;
230 typedef typename Types::NodeList::Titem
Node;
231 typedef typename Node::Key
Key;
236 StationID m_dest_station;
245 m_station_type = v->
IsBus() ? STATION_BUS : STATION_TRUCK;
251 m_station_type = STATION_ROADWAYPOINT;
256 m_dest_station = INVALID_STATION;
262 const Station *GetDestinationStation()
const
271 return *
static_cast<Tpf *
>(
this);
278 return PfDetectDestinationTile(n.m_segment_last_tile, n.m_segment_last_td);
283 if (m_dest_station != INVALID_STATION) {
290 return tile == m_destTile &&
HasTrackdir(m_destTrackdirs, trackdir);
299 static const int dg_dir_to_x_offs[] = {-1, 0, 1, 0};
300 static const int dg_dir_to_y_offs[] = {0, 1, 0, -1};
302 n.m_estimate = n.m_cost;
308 int x1 = 2 *
TileX(tile) + dg_dir_to_x_offs[(int)exitdir];
309 int y1 = 2 *
TileY(tile) + dg_dir_to_y_offs[(int)exitdir];
310 int x2 = 2 *
TileX(m_destTile);
311 int y2 = 2 *
TileY(m_destTile);
312 int dx =
abs(x1 - x2);
313 int dy =
abs(y1 - y2);
314 int dmin = std::min(dx, dy);
315 int dxy =
abs(dx - dy);
317 n.m_estimate = n.m_cost + d;
318 assert(n.m_estimate >= n.m_parent->m_estimate);
325 template <
class Types>
329 typedef typename Types::Tpf
Tpf;
330 typedef typename Types::TrackFollower TrackFollower;
331 typedef typename Types::NodeList::Titem
Node;
332 typedef typename Node::Key
Key;
338 return *
static_cast<Tpf *
>(
this);
350 TrackFollower F(
Yapf().GetVehicle());
351 if (F.Follow(old_node.m_segment_last_tile, old_node.m_segment_last_td)) {
352 Yapf().AddMultipleNodes(&old_node, F);
365 return pf.ChooseRoadTrack(v, tile, enterdir, path_found, path_cache);
386 Yapf().SetOrigin(src_tile, src_trackdirs);
387 Yapf().SetDestination(v);
390 path_found =
Yapf().FindPath(v);
395 if (pNode !=
nullptr) {
397 for (
Node *n = pNode; n->m_parent !=
nullptr; n = n->m_parent) steps++;
401 while (pNode->m_parent !=
nullptr) {
404 path_cache.td.push_front(pNode->GetTrackdir());
405 path_cache.tile.push_front(pNode->GetTile());
407 pNode = pNode->m_parent;
410 Node &best_next_node = *pNode;
411 assert(best_next_node.GetTile() == tile);
412 next_trackdir = best_next_node.GetTrackdir();
414 if (path_found && !path_cache.empty() && tile == v->
dest_tile) {
415 path_cache.td.pop_back();
416 path_cache.tile.pop_back();
420 const Station *st =
Yapf().GetDestinationStation();
422 const RoadStop *stop = st->GetPrimaryRoadStop(v);
428 while (!path_cache.empty() && non_cached_area.
Contains(path_cache.tile.back())) {
429 path_cache.td.pop_back();
430 path_cache.tile.pop_back();
435 return next_trackdir;
441 if (dst_tile == v->
tile) {
449 Yapf().SetDestination(v);
452 uint dist = UINT_MAX;
455 if (!
Yapf().FindPath(v))
return dist;
458 if (pNode !=
nullptr) {
461 dist = pNode->GetCostEstimate();
485 return pf.FindNearestDepot(v, tile, td, max_distance);
499 Yapf().SetMaxCost(max_distance);
510 template <
class Tpf_,
class Tnode_list,
template <
class Types>
class Tdestination>
517 typedef Tnode_list NodeList;
522 typedef Tdestination<Types> PfDestination;
527 struct CYapfRoad1 :
CYapfT<CYapfRoad_TypesT<CYapfRoad1 , CRoadNodeListTrackDir, CYapfDestinationTileRoadT > > {};
528 struct CYapfRoad2 :
CYapfT<CYapfRoad_TypesT<CYapfRoad2 , CRoadNodeListExitDir , CYapfDestinationTileRoadT > > {};
530 struct CYapfRoadAnyDepot1 :
CYapfT<CYapfRoad_TypesT<CYapfRoadAnyDepot1, CRoadNodeListTrackDir, CYapfDestinationAnyDepotRoadT> > {};
531 struct CYapfRoadAnyDepot2 :
CYapfT<CYapfRoad_TypesT<CYapfRoadAnyDepot2, CRoadNodeListExitDir , CYapfDestinationAnyDepotRoadT> > {};
538 PfnChooseRoadTrack pfnChooseRoadTrack = &CYapfRoad2::stChooseRoadTrack;
542 pfnChooseRoadTrack = &CYapfRoad1::stChooseRoadTrack;
545 Trackdir td_ret = pfnChooseRoadTrack(v, tile, enterdir, path_found, path_cache);
560 PfnFindNearestDepot pfnFindNearestDepot = &CYapfRoadAnyDepot2::stFindNearestDepot;
564 pfnFindNearestDepot = &CYapfRoadAnyDepot1::stFindNearestDepot;
567 return pfnFindNearestDepot(v, tile, trackdir, max_distance);
Buses, trucks and trams belong to this class.
static debug_inline uint TileY(TileIndex tile)
Get the Y component of a tile.
Tpf & Yapf()
to access inherited path finder
Node::Key Key
key to hash tables
bool IsType(OrderType type) const
Check whether this order is of the given type.
bool PfCalcCost(Node &n, const TrackFollower *)
Called by YAPF to calculate the cost from the origin to the given node.
Helper container to find a depot.
TrackdirBits TrackStatusToTrackdirBits(TrackStatus ts)
Returns the present-trackdir-information of a TrackStatus.
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.
DiagDirection TrackdirToExitdir(Trackdir trackdir)
Maps a trackdir to the (4-way) direction the tile is exited when following that trackdir.
bool PfCalcEstimate(Node &n)
Called by YAPF to calculate cost estimate.
TrackdirBits TrackdirToTrackdirBits(Trackdir trackdir)
Maps a Trackdir to the corresponding TrackdirBits value.
int OneTileCost(TileIndex tile, Trackdir trackdir)
return one tile cost
bool PfCalcEstimate(Node &n)
Called by YAPF to calculate cost estimate.
Types::TrackFollower TrackFollower
track follower helper
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 RoadStop * GetByTile(TileIndex tile, RoadStopType type)
Find a roadstop at given tile.
static const uint TILE_SIZE
Tile size in world coordinates.
DiagDirection
Enumeration for diagonal directions.
bool IsLevelCrossing(Tile t)
Return whether a tile is a level crossing.
const Entry * GetEntry(DiagDirection dir) const
Get the drive through road stop entry struct for the given direction.
YAPF template that uses Ttypes template argument to determine all YAPF components (base classes) from...
RoadType roadtype
NOSAVE: Roadtype of this vehicle.
int GetSlopePixelZ(int x, int y, bool ground_vehicle)
Return world Z coordinate of a given point of a tile.
@ MP_ROAD
A tile with road (or tram tracks)
constexpr T KillFirstBit(T value)
Clear the first bit in an integer.
Types::NodeList::Titem Node
this will be our node type
StationType
Station types.
TrackStatus GetTileTrackStatus(TileIndex tile, TransportType mode, uint sub_mode, DiagDirection side)
Returns information about trackdirs and signal states.
@ TRANSPORT_ROAD
Transport by road vehicle.
static debug_inline TileType GetTileType(Tile tile)
Get the tiletype of a given tile.
YAPF origin provider base class - used when origin is one tile / multiple trackdirs.
DiagDirection GetRoadDepotDirection(Tile t)
Get the direction of the exit of a road depot.
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.
int GetDisplayMaxSpeed() const override
Gets the maximum speed in km-ish/h that can be sent into SetDParam for string processing.
@ TRACKDIR_BIT_NONE
No track build.
TileArea truck_station
Tile area the truck 'station' part covers.
DiagDirection ReverseDiagDir(DiagDirection d)
Returns the reverse direction of the given DiagDirection.
Order current_order
The current order (+ status, like: loading)
Represents the covered area of e.g.
TrackdirBits DiagdirReachesTrackdirs(DiagDirection diagdir)
Returns all trackdirs that can be reached when entering a tile from a given (diagonal) direction.
GameSettings _settings_game
Game settings of a running game or the scenario editor.
TileArea bus_station
Tile area the bus 'station' part covers.
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
static const int YAPF_ROADVEH_PATH_CACHE_SEGMENTS
Maximum segments of road vehicle path cache.
Trackdir GetVehicleTrackdir() const override
Returns the Trackdir on which the vehicle is currently located.
StationType GetStationType(Tile t)
Get the station type of this tile.
Types::NodeList::Titem Node
this will be our node type
bool SetOriginFromVehiclePos(const RoadVehicle *v)
Return true if the valid origin (tile/trackdir) was set from the current vehicle position.
TileIndexDiff TileOffsByDiagDir(DiagDirection dir)
Convert a DiagDirection to a TileIndexDiff.
bool IsRoadWaypoint(Tile t)
Is the station at t a road waypoint?
Tpf & Yapf()
to access inherited path finder
CYapfSegmentCostCacheNoneT - the formal only yapf cost cache provider that implements PfNodeCacheFetc...
Types::NodeList::Titem Node
this will be our node type
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
TrackdirBits GetTrackdirBitsForRoad(TileIndex tile, RoadTramType rtt)
Wrapper around GetTileTrackStatus() and TrackStatusToTrackdirBits(), as for single tram bits GetTileT...
bool PfDetectDestination(Node &n)
Called by YAPF to detect if node ends in the desired destination.
Trackdir
Enumeration for tracks and directions.
Types::NodeList::Titem Node
this will be our node type
constexpr T abs(const T a)
Returns the absolute value of (scalar) variable.
StationID GetStationIndex(Tile t)
Get StationID from a tile.
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...
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.
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
int GetLength() const
Get the length of this drive through stop.
StrongType::Typedef< uint32_t, struct TileIndexTag, StrongType::Compare, StrongType::Integer, StrongType::Compatible< int32_t >, StrongType::Compatible< int64_t > > TileIndex
The index/ID of a Tile.
bool IsDiagonalTrackdir(Trackdir trackdir)
Checks if a given Trackdir is diagonal.
uint16_t GetMaxSpeed() const
Get the maxmimum speed in km-ish/h a vehicle is allowed to reach on the way to the destination.
Tpf & Yapf()
to access inherited path finder
RoadStopType GetRoadStopType(Tile t)
Get the road stop type of this tile.
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.
Node::Key Key
key to hash tables
CYapfBaseT - A-star type path finder base class.
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
static debug_inline bool IsTileType(Tile tile, TileType type)
Checks if a tile is a given tiletype.
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.
TrackdirBits
Allow incrementing of Trackdir variables.
static debug_inline uint TileX(TileIndex tile)
Get the X component of a tile.
static const uint MAX_MAP_SIZE
Maximal map size = 4096.
bool HasTrackdir(TrackdirBits trackdirs, Trackdir trackdir)
Checks whether a TrackdirBits has a given Trackdir.
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.
Container for each entry point of a drive through road stop.
Trackdir DiagDirToDiagTrackdir(DiagDirection diagdir)
Maps a (4-way) direction to the diagonal trackdir that runs in that direction.
@ INVALID_TRACKDIR
Flag for an invalid trackdir.
Node::Key Key
key to hash tables
@ INVALID_TRACKDIR_BIT
Flag for an invalid trackdirbit value.
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).
bool IsDriveThroughStopTile(Tile t)
Is tile t a drive through road stop station or waypoint?
bool Contains(TileIndex tile) const
Does this tile area contain a tile?
static debug_inline bool IsRoadDepotTile(Tile t)
Return whether a tile is a road depot tile.
bool PfDetectDestination(Node &n)
Called by YAPF to detect if node ends in the desired destination.
constexpr uint8_t FindFirstBit(T x)
Search the first set bit in a value.