10 #include "../../stdafx.h" 11 #include "../../ship.h" 12 #include "../../industry.h" 13 #include "../../vehicle_func.h" 18 #include "../../safeguards.h" 20 template <
class Types>
24 typedef typename Types::Tpf
Tpf;
25 typedef typename Types::TrackFollower TrackFollower;
26 typedef typename Types::NodeList::Titem
Node;
27 typedef typename Node::Key
Key;
32 StationID m_destStation;
35 void SetDestination(
const Ship *v)
42 m_destStation = INVALID_STATION;
52 return *
static_cast<Tpf*
>(
this);
59 return PfDetectDestinationTile(n.m_segment_last_tile, n.m_segment_last_td);
64 if (m_destStation != INVALID_STATION) {
77 static const int dg_dir_to_x_offs[] = {-1, 0, 1, 0};
78 static const int dg_dir_to_y_offs[] = {0, 1, 0, -1};
80 n.m_estimate = n.m_cost;
86 int x1 = 2 *
TileX(tile) + dg_dir_to_x_offs[(int)exitdir];
87 int y1 = 2 *
TileY(tile) + dg_dir_to_y_offs[(int)exitdir];
88 int x2 = 2 *
TileX(m_destTile);
89 int y2 = 2 *
TileY(m_destTile);
90 int dx =
abs(x1 - x2);
91 int dy =
abs(y1 - y2);
92 int dmin =
min(dx, dy);
93 int dxy =
abs(dx - dy);
95 n.m_estimate = n.m_cost + d;
96 assert(n.m_estimate >= n.m_parent->m_estimate);
103 template <
class Types>
107 typedef typename Types::Tpf
Tpf;
108 typedef typename Types::TrackFollower TrackFollower;
109 typedef typename Types::NodeList::Titem
Node;
110 typedef typename Node::Key
Key;
116 return *
static_cast<Tpf *
>(
this);
127 TrackFollower F(
Yapf().GetVehicle());
128 if (F.Follow(old_node.m_key.m_tile, old_node.m_key.m_td)) {
129 Yapf().AddMultipleNodes(&old_node, F);
164 pf.SetOrigin(src_tile, trackdirs);
165 pf.SetDestination(v);
167 path_found = pf.FindPath(v);
171 Node *pNode = pf.GetBestNode();
172 if (pNode !=
nullptr) {
174 for (Node *n = pNode; n->m_parent !=
nullptr; n = n->m_parent) steps++;
179 Node *pPrevNode =
nullptr;
180 while (pNode->m_parent !=
nullptr) {
183 if (skip > 0) skip--;
185 path_cache.push_front(pNode->GetTrackdir());
188 pNode = pNode->m_parent;
191 Node &best_next_node = *pPrevNode;
192 assert(best_next_node.GetTile() == tile);
193 next_trackdir = best_next_node.GetTrackdir();
195 if (path_found && !path_cache.empty()) path_cache.pop_back();
197 return next_trackdir;
215 pf.SetDestination(v);
217 if (!pf.FindPath(v))
return false;
219 Node *pNode = pf.GetBestNode();
220 if (pNode ==
nullptr)
return false;
224 while (pNode->m_parent !=
nullptr) {
225 pNode = pNode->m_parent;
228 Trackdir best_trackdir = pNode->GetTrackdir();
229 assert(best_trackdir == td1 || best_trackdir == td2);
230 return best_trackdir == td2;
235 template <
class Types>
239 typedef typename Types::Tpf
Tpf;
240 typedef typename Types::TrackFollower TrackFollower;
241 typedef typename Types::NodeList::Titem
Node;
242 typedef typename Node::Key
Key;
248 return *
static_cast<Tpf *
>(
this);
259 return Yapf().PfGetSettings().ship_curve90_penalty;
262 return Yapf().PfGetSettings().ship_curve45_penalty;
269 uint *count = (uint *)data;
286 c += CurveCost(n.m_parent->GetTrackdir(), n.GetTrackdir());
301 if (speed_frac > 0) c +=
YAPF_TILE_LENGTH * (1 + tf->m_tiles_skipped) * speed_frac / (256 - speed_frac);
304 n.m_cost = n.m_parent->m_cost + c;
313 template <
class Tpf_,
class Ttrack_follower,
class Tnode_list>
336 struct CYapfShip1 :
CYapfT<CYapfShip_TypesT<CYapfShip1, CFollowTrackWater , CShipNodeListTrackDir> > {};
338 struct CYapfShip2 :
CYapfT<CYapfShip_TypesT<CYapfShip2, CFollowTrackWater , CShipNodeListExitDir > > {};
340 static inline bool RequireTrackdirKey()
362 Trackdir td_ret = pfnChooseShipTrack(v, tile, enterdir, tracks, path_found, path_cache);
373 PfnCheckReverseShip pfnCheckReverseShip = CYapfShip2::CheckShipReverse;
377 pfnCheckReverseShip = &CYapfShip1::CheckShipReverse;
380 bool reverse = pfnCheckReverseShip(v, tile, td, td_rev);
Information about a ship vehicle.
bool HasVehicleOnPos(TileIndex tile, void *data, VehicleFromPosProc *proc)
Checks whether a vehicle is on a specific location.
GameSettings _settings_game
Game settings of a running game or the scenario editor.
TrackdirBits
Enumeration of bitmasks for the TrackDirs.
Flag for an invalid track.
YAPF origin provider base class - used when origin is one tile / multiple trackdirs.
CYapfShip_TypesT< Tpf_, Ttrack_follower, Tnode_list > Types
Types - shortcut for this struct type.
Ttrack_follower TrackFollower
track follower helper class
byte ocean_speed_frac
Fraction of maximum speed for ocean tiles.
static Track TrackdirToTrack(Trackdir trackdir)
Returns the Track that a given Trackdir represents.
char TransportTypeChar() const
return debug report character to identify the transportation type
Trackdir
Enumeration for tracks and directions.
VehicleType
Available vehicle types.
TileIndex dest_tile
Heading for this tile.
CYapfSegmentCostCacheNoneT - the formal only yapf cost cache provider that implements PfNodeCacheFetc...
Tnode_list NodeList
node list type
bool PfCalcEstimate(Node &n)
Called by YAPF to calculate cost estimate.
static uint TileX(TileIndex tile)
Get the X component of a tile.
PathfinderSettings pf
settings for all pathfinders
static TileIndex TileAddByDiagDir(TileIndex tile, DiagDirection dir)
Adds a DiagDir to a tile.
Node::Key Key
key to hash tables
static Trackdir NextTrackdir(Trackdir trackdir)
Maps a trackdir to the trackdir that you will end up on if you go straight ahead. ...
static const int YAPF_SHIP_PATH_CACHE_LENGTH
Maximum length of ship path cache.
static TrackdirBits DiagdirReachesTrackdirs(DiagDirection diagdir)
Returns all trackdirs that can be reached when entering a tile from a given (diagonal) direction...
static DiagDirection TrackdirToExitdir(Trackdir trackdir)
Maps a trackdir to the (4-way) direction the tile is exited when following that trackdir.
Tpf & Yapf()
to access inherited path finder
bool PfDetectDestination(Node &n)
Called by YAPF to detect if node ends in the desired destination.
CYapfBaseT< Types > PfBase
pathfinder components (modules)
Types::NodeList::Titem Node
this will be our node type
Cost Provider module of YAPF for ships.
static bool IsValidTrackdir(Trackdir trackdir)
Checks if a Trackdir is valid for non-road vehicles.
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
CYapfBaseT - A-star type path finder base class.
Tpf & Yapf()
to access inherited path finder
bool disable_node_optimization
whether to use exit-dir instead of trackdir in node key
Config struct of YAPF for ships.
YAPFSettings yapf
pathfinder settings for the yet another pathfinder
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.
Node Follower module of YAPF for ships.
Types::NodeList::Titem Node
this will be our node type
Flag for an invalid trackdir.
static const int YAPF_TILE_LENGTH
Length (penalty) of one tile with YAPF.
YAPF template that uses Ttypes template argument to determine all YAPF components (base classes) from...
static bool IsDockingTile(TileIndex t)
Checks whether the tile is marked as a dockling tile.
Node::Key Key
key to hash tables
TrackBits
Bitfield corresponding to Track.
TileIndex tile
Current tile index.
uint32 ship_curve45_penalty
penalty for 45-deg curve for ships
static bool CheckShipReverse(const Ship *v, TileIndex tile, Trackdir td1, Trackdir td2)
Check whether a ship should reverse to reach its destination.
bool IsShipDestinationTile(TileIndex tile, StationID station)
Test if a tile is a docking tile for the given station.
static T min(const T a, const T b)
Returns the minimum of two values.
Tpf & Yapf()
to access inherited path finder
All ships have this 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...
static Trackdir ReverseTrackdir(Trackdir trackdir)
Maps a trackdir to the reverse trackdir.
TrackStatus GetTileTrackStatus(TileIndex tile, TransportType mode, uint sub_mode, DiagDirection side)
Returns information about trackdirs and signal states.
DestinationID GetDestination() const
Gets the destination of this order.
uint32 TileIndex
The index/ID of a Tile.
Base includes/functions for YAPF.
Track
These are used to specify a single track.
static uint TileY(TileIndex tile)
Get the Y component of a tile.
static T abs(const T a)
Returns the absolute value of (scalar) variable.
Types::NodeList::Titem Node
this will be our node type
static bool IsDiagonalTrackdir(Trackdir trackdir)
Checks if a given Trackdir is diagonal.
Trackdir GetVehicleTrackdir() const
Returns the Trackdir on which the vehicle is currently located.
VehicleType type
Type of vehicle.
static uint8 FindFirstBit2x64(const int value)
Finds the position of the first non-zero bit in an integer.
uint32 ship_curve90_penalty
penalty for 90-deg curve for ships
Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found, ShipPathCache &path_cache)
Ship controller helper - path finder invoker.
DiagDirection
Enumeration for diagonal directions.
static TrackdirBits TrackBitsToTrackdirBits(TrackBits bits)
Converts TrackBits to TrackdirBits while allowing both directions.
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
bool PfCalcCost(Node &n, const TrackFollower *tf)
Called by YAPF to calculate the cost from the origin to the given node.
Tpf_ Tpf
Tpf - pathfinder type.
static const int YAPF_TILE_CORNER_LENGTH
Length (penalty) of a corner with YAPF.
Flag for an invalid trackdirbit value.
WaterClass GetEffectiveWaterClass(TileIndex tile)
Determine the effective WaterClass for a ship travelling on a tile.
Node::Key Key
key to hash tables
static TrackdirBits TrackdirCrossesTrackdirs(Trackdir trackdir)
Maps a trackdir to all trackdirs that make 90 deg turns with it.
byte canal_speed_frac
Fraction of maximum speed for canal/river tiles.
static TrackdirBits TrackStatusToTrackdirBits(TrackStatus ts)
Returns the present-trackdir-information of a TrackStatus.
void PfFollowNode(Node &old_node)
Called by YAPF to move from the given node to the next tile.
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
Order current_order
The current order (+ status, like: loading)
bool YapfShipCheckReverse(const Ship *v)
Returns true if it is better to reverse the ship before leaving depot using YAPF. ...
Node tailored for ship pathfinding.
static Track ChooseShipTrack(Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks)
Runs the pathfinder to choose a track to continue along.