OpenTTD Source
1.11.0-beta2
|
Go to the documentation of this file.
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 = std::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);
static Track ChooseShipTrack(Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks)
Runs the pathfinder to choose a track to continue along.
uint32 TileIndex
The index/ID of a Tile.
Tnode_list NodeList
node list type
bool IsType(OrderType type) const
Check whether this order is of the given type.
TrackdirBits
Enumeration of bitmasks for the TrackDirs.
Config struct of YAPF for ships.
bool HasVehicleOnPos(TileIndex tile, void *data, VehicleFromPosProc *proc)
Checks whether a vehicle is on a specific location.
byte canal_speed_frac
Fraction of maximum speed for canal/river tiles.
bool PfCalcEstimate(Node &n)
Called by YAPF to calculate cost estimate.
DestinationID GetDestination() const
Gets the destination of this order.
Node::Key Key
key to hash tables
Tpf_ Tpf
Tpf - pathfinder type.
static const int YAPF_SHIP_PATH_CACHE_LENGTH
Maximum length of ship path cache.
bool PfDetectDestination(Node &n)
Called by YAPF to detect if node ends in the desired destination.
WaterClass GetEffectiveWaterClass(TileIndex tile)
Determine the effective WaterClass for a ship travelling on a tile.
Ttrack_follower TrackFollower
track follower helper class
uint32 ship_curve45_penalty
penalty for 45-deg curve for ships
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...
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.
static bool CheckShipReverse(const Ship *v, TileIndex tile, Trackdir td1, Trackdir td2)
Check whether a ship should reverse to reach its destination.
Tpf & Yapf()
to access inherited path finder
TrackStatus GetTileTrackStatus(TileIndex tile, TransportType mode, uint sub_mode, DiagDirection side)
Returns information about trackdirs and signal states.
YAPF origin provider base class - used when origin is one tile / multiple trackdirs.
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
PathfinderSettings pf
settings for all pathfinders
@ VS_HIDDEN
Vehicle is not visible.
Tpf & Yapf()
to access inherited path finder
TileIndex dest_tile
Heading for this tile.
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
static TrackdirBits TrackBitsToTrackdirBits(TrackBits bits)
Converts TrackBits to TrackdirBits while allowing both directions.
void PfFollowNode(Node &old_node)
Called by YAPF to move from the given node to the next tile.
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.
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.
Node::Key Key
key to hash tables
GameSettings _settings_game
Game settings of a running game or the scenario editor.
static TrackdirBits TrackdirCrossesTrackdirs(Trackdir trackdir)
Maps a trackdir to all trackdirs that make 90 deg turns with it.
Node::Key Key
key to hash tables
static DiagDirection ReverseDiagDir(DiagDirection d)
Returns the reverse direction of the given DiagDirection.
static TileIndex TileAddByDiagDir(TileIndex tile, DiagDirection dir)
Adds a DiagDir to a tile.
@ INVALID_TRACKDIR
Flag for an invalid trackdir.
DiagDirection
Enumeration for diagonal directions.
CYapfShip_TypesT< Tpf_, Ttrack_follower, Tnode_list > Types
Types - shortcut for this struct 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...
Trackdir GetVehicleTrackdir() const
Returns the Trackdir on which the vehicle is currently located.
CYapfBaseT< Types > PfBase
pathfinder components (modules)
static TrackdirBits DiagdirReachesTrackdirs(DiagDirection diagdir)
Returns all trackdirs that can be reached when entering a tile from a given (diagonal) direction.
CYapfSegmentCostCacheNoneT - the formal only yapf cost cache provider that implements PfNodeCacheFetc...
@ TRACKDIR_BIT_NONE
No track build.
All ships have this type.
Tpf & Yapf()
to access inherited path finder
Types::NodeList::Titem Node
this will be our node type
Node Follower module of YAPF for ships.
@ TRANSPORT_WATER
Transport over water.
bool disable_node_optimization
whether to use exit-dir instead of trackdir in node key
Information about a ship vehicle.
static TrackdirBits TrackStatusToTrackdirBits(TrackStatus ts)
Returns the present-trackdir-information of a TrackStatus.
bool PfCalcCost(Node &n, const TrackFollower *tf)
Called by YAPF to calculate the cost from the origin to the given node.
static T abs(const T a)
Returns the absolute value of (scalar) variable.
TrackBits
Bitfield corresponding to Track.
static bool IsDockingTile(TileIndex t)
Checks whether the tile is marked as a dockling tile.
static TrackdirBits TrackdirToTrackdirBits(Trackdir trackdir)
Maps a Trackdir to the corresponding TrackdirBits value.
Cost Provider module of YAPF for ships.
YAPFSettings yapf
pathfinder settings for the yet another pathfinder
static const int YAPF_TILE_CORNER_LENGTH
Length (penalty) of a corner with YAPF.
bool IsShipDestinationTile(TileIndex tile, StationID station)
Test if a tile is a docking tile for the given station.
static Trackdir ReverseTrackdir(Trackdir trackdir)
Maps a trackdir to the reverse trackdir.
Trackdir
Enumeration for tracks and directions.
static Trackdir NextTrackdir(Trackdir trackdir)
Maps a trackdir to the trackdir that you will end up on if you go straight ahead.
CYapfBaseT - A-star type path finder base class.
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
VehicleType type
Type of vehicle.
Track
These are used to specify a single track.
static bool HasTrackdir(TrackdirBits trackdirs, Trackdir trackdir)
Checks whether a TrackdirBits has a given Trackdir.
@ VEH_SHIP
Ship vehicle type.
Types::NodeList::Titem Node
this will be our node type
static bool IsValidTrackdir(Trackdir trackdir)
Checks if a Trackdir is valid for non-road vehicles.
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.
char TransportTypeChar() const
return debug report character to identify the transportation type
static Track TrackdirToTrack(Trackdir trackdir)
Returns the Track that a given Trackdir represents.
static bool IsDiagonalTrackdir(Trackdir trackdir)
Checks if a given Trackdir is diagonal.
byte ocean_speed_frac
Fraction of maximum speed for ocean tiles.
bool YapfShipCheckReverse(const Ship *v)
Returns true if it is better to reverse the ship before leaving depot using YAPF.
@ INVALID_TRACK
Flag for an invalid track.