OpenTTD Source
20240917-master-g9ab0a47812
|
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 "../water_regions.h"
20 #include "../../safeguards.h"
22 constexpr
int NUMBER_OR_WATER_REGIONS_LOOKAHEAD = 4;
23 constexpr
int MAX_SHIP_PF_NODES = (NUMBER_OR_WATER_REGIONS_LOOKAHEAD + 1) * WATER_REGION_NUMBER_OF_TILES * 4;
25 constexpr
int SHIP_LOST_PATH_LENGTH = 8;
27 template <
class Types>
31 typedef typename Types::Tpf
Tpf;
32 typedef typename Types::TrackFollower TrackFollower;
33 typedef typename Types::NodeList::Titem
Node;
34 typedef typename Node::Key
Key;
39 StationID m_destStation;
41 bool m_has_intermediate_dest =
false;
46 void SetDestination(
const Ship *v)
53 m_destStation = INVALID_STATION;
61 m_has_intermediate_dest =
true;
63 m_intermediate_dest_region_patch = water_region_patch;
70 return *
static_cast<Tpf*
>(
this);
77 return PfDetectDestinationTile(n.m_segment_last_tile, n.m_segment_last_td);
82 if (m_has_intermediate_dest) {
99 const TileIndex destination_tile = m_has_intermediate_dest ? m_intermediate_dest_tile : m_destTile;
101 static const int dg_dir_to_x_offs[] = { -1, 0, 1, 0 };
102 static const int dg_dir_to_y_offs[] = { 0, 1, 0, -1 };
104 n.m_estimate = n.m_cost;
110 int x1 = 2 *
TileX(tile) + dg_dir_to_x_offs[(int)exitdir];
111 int y1 = 2 *
TileY(tile) + dg_dir_to_y_offs[(int)exitdir];
112 int x2 = 2 *
TileX(destination_tile);
113 int y2 = 2 *
TileY(destination_tile);
114 int dx =
abs(x1 - x2);
115 int dy =
abs(y1 - y2);
116 int dmin = std::min(dx, dy);
117 int dxy =
abs(dx - dy);
119 n.m_estimate = n.m_cost + d;
120 assert(n.m_estimate >= n.m_parent->m_estimate);
126 template <
class Types>
130 typedef typename Types::Tpf
Tpf;
131 typedef typename Types::TrackFollower TrackFollower;
132 typedef typename Types::NodeList::Titem
Node;
133 typedef typename Node::Key
Key;
139 return *
static_cast<Tpf*
>(
this);
142 std::vector<WaterRegionDesc> m_water_region_corridor;
152 TrackFollower F(
Yapf().GetVehicle());
153 if (F.Follow(old_node.m_key.m_tile, old_node.m_key.m_td)) {
154 if (m_water_region_corridor.empty()
155 || std::find(m_water_region_corridor.begin(), m_water_region_corridor.end(),
157 Yapf().AddMultipleNodes(&old_node, F);
165 m_water_region_corridor.clear();
166 for (
const WaterRegionPatchDesc &path_entry : path) m_water_region_corridor.push_back(path_entry);
186 TrackFollower follower(v);
187 if (follower.Follow(tile, dir)) {
200 for (
int i = 0; i < path_length; ++i) {
203 path_cache.push_back(tile_dir.second);
208 const Trackdir result = path_cache.front();
209 path_cache.pop_front();
214 bool &path_found, ShipPathCache &path_cache,
Trackdir &best_origin_dir)
216 const std::vector<WaterRegionPatchDesc> high_level_path =
YapfShipFindWaterRegionPath(v, tile, NUMBER_OR_WATER_REGIONS_LOOKAHEAD + 1);
217 if (high_level_path.empty()) {
226 for (
int attempt = 0; attempt < 2; ++attempt) {
227 Tpf pf(MAX_SHIP_PF_NODES);
230 pf.SetOrigin(v->
tile, forward_dirs | reverse_dirs);
231 pf.SetDestination(v);
232 const bool is_intermediate_destination =
static_cast<int>(high_level_path.size()) >= NUMBER_OR_WATER_REGIONS_LOOKAHEAD + 1;
233 if (is_intermediate_destination) pf.SetIntermediateDestination(high_level_path.back());
237 if (attempt > 0) pf.RestrictSearch(high_level_path);
240 path_found = pf.FindPath(v);
241 Node *node = pf.GetBestNode();
242 if (attempt == 0 && !path_found)
continue;
245 if (!path_found)
return CreateRandomPath(v, path_cache, SHIP_LOST_PATH_LENGTH);
253 while (node->m_parent) {
256 const bool node_water_patch_on_high_level_path = std::find(high_level_path.begin(), high_level_path.end(), node_water_patch) != high_level_path.end();
257 const bool add_full_path = !is_intermediate_destination && node_water_patch != end_water_patch;
261 if (add_full_path || !node_water_patch_on_high_level_path || node_water_patch == start_water_patch) {
262 path_cache.push_front(node->GetTrackdir());
266 node = node->m_parent;
268 assert(node->GetTile() == v->
tile);
271 best_origin_dir = node->GetTrackdir();
282 const Trackdir result = path_cache.front();
283 path_cache.pop_front();
286 if (start_water_patch == end_water_patch) path_cache.clear();
303 bool path_found =
false;
304 ShipPathCache dummy_cache;
307 if (trackdir ==
nullptr) {
312 (void)ChooseShipTrack(v, v->
tile, forward_dirs, reverse_dirs, path_found, dummy_cache, best_origin_dir);
313 return path_found && best_origin_dir == reverse_dir;
318 (void)ChooseShipTrack(v, v->
tile,
TRACKDIR_BIT_NONE, reverse_dirs, path_found, dummy_cache, best_origin_dir);
326 template <
class Types>
330 typedef typename Types::Tpf
Tpf;
331 typedef typename Types::TrackFollower TrackFollower;
332 typedef typename Types::NodeList::Titem
Node;
333 typedef typename Node::Key
Key;
338 return *
static_cast<Tpf*
>(
this);
349 return Yapf().PfGetSettings().ship_curve90_penalty;
352 return Yapf().PfGetSettings().ship_curve45_penalty;
359 uint *count = (uint*)data;
376 c += CurveCost(n.m_parent->GetTrackdir(), n.GetTrackdir());
391 if (speed_frac > 0) c +=
YAPF_TILE_LENGTH * (1 + tf->m_tiles_skipped) * speed_frac / (256 - speed_frac);
394 n.m_cost = n.m_parent->m_cost + c;
403 template <
class Tpf_,
class Ttrack_follower,
class Tnode_list>
409 typedef Tnode_list NodeList;
421 struct CYapfShip :
CYapfT<CYapfShip_TypesT<CYapfShip, CFollowTrackWater, CShipNodeListExitDir > >
423 explicit CYapfShip(
int max_nodes) { m_max_search_nodes = max_nodes; }
437 return CYapfShip::CheckShipReverse(v, trackdir);
static debug_inline uint TileY(TileIndex tile)
Get the Y component of a tile.
bool IsType(OrderType type) const
Check whether this order is of the given type.
Config struct of YAPF for ships.
TrackdirBits TrackStatusToTrackdirBits(TrackStatus ts)
Returns the present-trackdir-information of a TrackStatus.
bool HasVehicleOnPos(TileIndex tile, void *data, VehicleFromPosProc *proc)
Checks whether a vehicle is on a specific location.
Describes a single interconnected patch of water within a particular water region.
Trackdir GetVehicleTrackdir() const override
Returns the Trackdir on which the vehicle is currently located.
bool PfCalcEstimate(Node &n)
Called by YAPF to calculate cost estimate.
@ TRANSPORT_WATER
Transport over water.
DestinationID GetDestination() const
Gets the destination of this order.
Track TrackdirToTrack(Trackdir trackdir)
Returns the Track that a given Trackdir represents.
DiagDirection TrackdirToExitdir(Trackdir trackdir)
Maps a trackdir to the (4-way) direction the tile is exited when following that trackdir.
TrackdirBits TrackdirToTrackdirBits(Trackdir trackdir)
Maps a Trackdir to the corresponding TrackdirBits value.
Node::Key Key
key to hash tables.
bool YapfShipCheckReverse(const Ship *v, Trackdir *trackdir)
Returns true if it is better to reverse the ship before leaving depot using YAPF.
CYapfFollowShipT< Types > PfFollow
Node follower.
Trackdir FindFirstTrackdir(TrackdirBits trackdirs)
Returns first Trackdir from TrackdirBits or INVALID_TRACKDIR.
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.
DiagDirection
Enumeration for diagonal directions.
TileIndex GetWaterRegionCenterTile(const WaterRegionDesc &water_region)
Returns the center tile of a particular water region.
YAPF template that uses Ttypes template argument to determine all YAPF components (base classes) from...
Trackdir NextTrackdir(Trackdir trackdir)
Maps a trackdir to the trackdir that you will end up on if you go straight ahead.
Types::NodeList::Titem Node
this will be our node type.
uint8_t canal_speed_frac
Fraction of maximum speed for canal/river tiles.
void RestrictSearch(const std::vector< WaterRegionPatchDesc > &path)
Restricts the search by creating corridor or water regions through which the ship is allowed to trave...
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).
WaterRegionPatchDesc GetWaterRegionPatchInfo(TileIndex tile)
Returns basic water region patch information for the provided tile.
@ VS_HIDDEN
Vehicle is not visible.
Tpf & Yapf()
To access inherited path finder.
WaterRegionDesc GetWaterRegionInfo(TileIndex tile)
Returns basic water region information for the provided tile.
TileIndex dest_tile
Heading for this tile.
CYapfCostShipT< Types > PfCost
Cost provider.
Types::Tpf Tpf
the pathfinder class (derived from THIS class).
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.
@ TRACKDIR_BIT_NONE
No track build.
DiagDirection ReverseDiagDir(DiagDirection d)
Returns the reverse direction of the given DiagDirection.
Order current_order
The current order (+ status, like: loading)
@ VEH_SHIP
Ship vehicle type.
Node::Key Key
key to hash tables.
static Track ChooseShipTrack(Ship *v, TileIndex tile, TrackBits tracks)
Runs the pathfinder to choose a track to continue along.
Trackdir ReverseTrackdir(Trackdir trackdir)
Maps a trackdir to the reverse trackdir.
TrackdirBits DiagdirReachesTrackdirs(DiagDirection diagdir)
Returns all trackdirs that can be reached when entering a tile from a given (diagonal) direction.
Node::Key Key
key to hash tables.
DiagDirection VehicleExitDir(Direction direction, TrackBits track)
Determine the side in which the vehicle will leave the tile.
Trackdir RemoveFirstTrackdir(TrackdirBits *trackdirs)
Removes first Trackdir from TrackdirBits and returns it.
uint8_t ocean_speed_frac
Fraction of maximum speed for ocean tiles.
CYapfShip_TypesT< Tpf_, Ttrack_follower, Tnode_list > Types
Shortcut for this struct type.
constexpr uint CountBits(T value)
Counts the number of set bits in a variable.
Direction direction
facing
CYapfBaseT< Types > PfBase
Pathfinder components (modules).
CYapfSegmentCostCacheNoneT - the formal only yapf cost cache provider that implements PfNodeCacheFetc...
All ships have this type.
Track
These are used to specify a single track.
Tpf & Yapf()
to access inherited path finder
Trackdir
Enumeration for tracks and directions.
bool IsDockingTile(Tile t)
Checks whether the tile is marked as a dockling tile.
Track YapfShipChooseTrack(const Ship *v, TileIndex tile, bool &path_found, ShipPathCache &path_cache)
Ship controller helper - path finder invoker.
constexpr T abs(const T a)
Returns the absolute value of (scalar) variable.
Types::NodeList::Titem Node
this will be our node type.
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...
Node Follower module of YAPF for ships.
TrackBits state
The "track" the ship is following.
CYapfSegmentCostCacheNoneT< Types > PfCache
Segment cost cache provider.
Information about a ship vehicle.
static bool CheckShipReverse(const Ship *v, Trackdir *trackdir)
Check whether a ship should reverse to reach its destination.
CYapfOriginTileT< Types > PfOrigin
Origin provider.
bool PfCalcCost(Node &n, const TrackFollower *tf)
Called by YAPF to calculate the cost from the origin to the given node.
bool IsDiagonalTrackdir(Trackdir trackdir)
Checks if a given Trackdir is diagonal.
static std::pair< TileIndex, Trackdir > GetRandomFollowUpTileTrackdir(const Ship *v, TileIndex tile, Trackdir dir)
Returns a random tile/trackdir that can be reached from the current tile/trackdir,...
uint32_t RandomRange(uint32_t limit, const std::source_location location=std::source_location::current())
Pick a random number between 0 and limit - 1, inclusive.
static Trackdir CreateRandomPath(const Ship *v, ShipPathCache &path_cache, int path_length)
Creates a random path, avoids 90 degree turns.
Cost Provider module of YAPF for ships.
std::vector< WaterRegionPatchDesc > YapfShipFindWaterRegionPath(const Ship *v, TileIndex start_tile, int max_returned_path_length)
Finds a path at the water region level.
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.
CYapfBaseT - A-star type path finder base class.
Types::Tpf Tpf
the pathfinder class (derived from THIS class).
TrackdirBits TrackdirCrossesTrackdirs(Trackdir trackdir)
Maps a trackdir to all trackdirs that make 90 deg turns with it.
VehicleType type
Type of vehicle.
TrackdirBits
Allow incrementing of Trackdir variables.
static debug_inline uint TileX(TileIndex tile)
Get the X component of a tile.
CYapfDestinationTileWaterT< Types > PfDestination
Destination/distance provider.
bool HasTrackdir(TrackdirBits trackdirs, Trackdir trackdir)
Checks whether a TrackdirBits has a given Trackdir.
bool IsValidTrackdir(Trackdir trackdir)
Checks if a Trackdir is valid for non-road vehicles.
@ INVALID_TRACK
Flag for an invalid track.
Types::NodeList::Titem Node
this will be our node type.
@ INVALID_TRACKDIR
Flag for an invalid trackdir.
Vehicle * first
NOSAVE: pointer to the first vehicle in the chain.
static Trackdir GetRandomTrackdir(TrackdirBits trackdirs)
Returns a random trackdir out of a set of trackdirs.
@ INVALID_TRACKDIR_BIT
Flag for an invalid trackdirbit value.
char TransportTypeChar() const
Return debug report character to identify the transportation type.