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 dest_station;
41 bool has_intermediate_dest =
false;
46 void SetDestination(
const Ship *v)
53 this->dest_station = INVALID_STATION;
61 this->has_intermediate_dest =
true;
63 this->intermediate_dest_region_patch = water_region_patch;
70 return *
static_cast<Tpf*
>(
this);
77 return this->PfDetectDestinationTile(n.segment_last_tile, n.segment_last_td);
82 if (this->has_intermediate_dest) {
99 const TileIndex destination_tile = this->has_intermediate_dest ? this->intermediate_dest_tile : this->dest_tile;
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 };
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.estimate = n.cost + d;
120 assert(n.estimate >= n.parent->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> water_region_corridor;
152 TrackFollower F(
Yapf().GetVehicle());
153 if (F.Follow(old_node.key.tile, old_node.key.td)) {
154 if (this->water_region_corridor.empty()
155 || std::find(this->water_region_corridor.begin(), this->water_region_corridor.end(),
157 Yapf().AddMultipleNodes(&old_node, F);
165 this->water_region_corridor.clear();
166 for (
const WaterRegionPatchDesc &path_entry : path) this->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->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());
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 += this->CurveCost(n.parent->GetTrackdir(), n.GetTrackdir());
391 if (speed_frac > 0) c +=
YAPF_TILE_LENGTH * (1 + tf->tiles_skipped) * speed_frac / (256 - speed_frac);
394 n.cost = n.parent->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) { this->max_search_nodes = max_nodes; }
437 return CYapfShip::CheckShipReverse(v, trackdir);
constexpr uint CountBits(T value)
Counts the number of set bits in a variable.
CYapfBaseT - A-star type path finder base class.
Cost Provider module of YAPF for ships.
Node::Key Key
key to hash tables.
bool PfCalcCost(Node &n, const TrackFollower *tf)
Called by YAPF to calculate the cost from the origin to the given node.
Types::NodeList::Titem Node
this will be our node type.
Tpf & Yapf()
to access inherited path finder
Types::Tpf Tpf
the pathfinder class (derived from THIS class).
Types::Tpf Tpf
the pathfinder class (derived from THIS class).
bool PfCalcEstimate(Node &n)
Called by YAPF to calculate cost estimate.
Types::NodeList::Titem Node
this will be our node type.
Tpf & Yapf()
To access inherited path finder.
bool PfDetectDestination(Node &n)
Called by YAPF to detect if node ends in the desired destination.
Node::Key Key
key to hash tables.
Node Follower module of YAPF for ships.
Types::NodeList::Titem Node
this will be our node type.
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,...
char TransportTypeChar() const
Return debug report character to identify the transportation type.
void PfFollowNode(Node &old_node)
Called by YAPF to move from the given node to the next tile.
static Trackdir GetRandomTrackdir(TrackdirBits trackdirs)
Returns a random trackdir out of a set of trackdirs.
Node::Key Key
key to hash tables.
static Trackdir CreateRandomPath(const Ship *v, ShipPathCache &path_cache, int path_length)
Creates a random path, avoids 90 degree turns.
Tpf & Yapf()
to access inherited path finder
Types::Tpf Tpf
the pathfinder class (derived from THIS class).
void RestrictSearch(const std::vector< WaterRegionPatchDesc > &path)
Restricts the search by creating corridor or water regions through which the ship is allowed to trave...
static bool CheckShipReverse(const Ship *v, Trackdir *trackdir)
Check whether a ship should reverse to reach its destination.
YAPF origin provider base class - used when origin is one tile / multiple trackdirs.
CYapfSegmentCostCacheNoneT - the formal only yapf cost cache provider that implements PfNodeCacheFetc...
YAPF template that uses Ttypes template argument to determine all YAPF components (base classes) from...
DiagDirection ReverseDiagDir(DiagDirection d)
Returns the reverse direction of the given DiagDirection.
DiagDirection
Enumeration for diagonal directions.
TrackStatus GetTileTrackStatus(TileIndex tile, TransportType mode, uint sub_mode, DiagDirection side)
Returns information about trackdirs and signal states.
static debug_inline uint TileY(TileIndex tile)
Get the Y component of a tile.
static debug_inline uint TileX(TileIndex tile)
Get the X component of a tile.
constexpr T abs(const T a)
Returns the absolute value of (scalar) variable.
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 const int YAPF_TILE_CORNER_LENGTH
Length (penalty) of a corner with YAPF.
static const int YAPF_TILE_LENGTH
Length (penalty) of one tile with YAPF.
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.
bool IsShipDestinationTile(TileIndex tile, StationID station)
Test if a tile is a docking tile for the given station.
WaterClass GetEffectiveWaterClass(TileIndex tile)
Determine the effective WaterClass for a ship travelling on a tile.
static Track ChooseShipTrack(Ship *v, TileIndex tile, TrackBits tracks)
Runs the pathfinder to choose a track to continue along.
VehicleType type
Type of vehicle.
Config struct of YAPF for ships.
CYapfSegmentCostCacheNoneT< Types > PfCache
Segment cost cache provider.
CYapfShip_TypesT< Tpf_, Ttrack_follower, Tnode_list > Types
Shortcut for this struct type.
CYapfFollowShipT< Types > PfFollow
Node follower.
CYapfBaseT< Types > PfBase
Pathfinder components (modules).
CYapfOriginTileT< Types > PfOrigin
Origin provider.
Ttrack_follower TrackFollower
Track follower helper class.
CYapfDestinationTileWaterT< Types > PfDestination
Destination/distance provider.
CYapfCostShipT< Types > PfCost
Cost provider.
DestinationID GetDestination() const
Gets the destination of this order.
bool IsType(OrderType type) const
Check whether this order is of the given type.
Information about a ship vehicle.
uint8_t ocean_speed_frac
Fraction of maximum speed for ocean tiles.
uint8_t canal_speed_frac
Fraction of maximum speed for canal/river tiles.
All ships have this type.
TrackBits state
The "track" the ship is following.
Trackdir GetVehicleTrackdir() const override
Returns the Trackdir on which the vehicle is currently located.
Direction direction
facing
Vehicle * first
NOSAVE: pointer to the first vehicle in the chain.
Order current_order
The current order (+ status, like: loading)
TileIndex tile
Current tile index.
TileIndex dest_tile
Heading for this tile.
Describes a single interconnected patch of water within a particular water region.
Trackdir RemoveFirstTrackdir(TrackdirBits *trackdirs)
Removes first Trackdir from TrackdirBits and returns it.
Track TrackdirToTrack(Trackdir trackdir)
Returns the Track that a given Trackdir represents.
DiagDirection VehicleExitDir(Direction direction, TrackBits track)
Determine the side in which the vehicle will leave the tile.
TrackdirBits TrackStatusToTrackdirBits(TrackStatus ts)
Returns the present-trackdir-information of a TrackStatus.
Trackdir NextTrackdir(Trackdir trackdir)
Maps a trackdir to the trackdir that you will end up on if you go straight ahead.
Trackdir ReverseTrackdir(Trackdir trackdir)
Maps a trackdir to the reverse trackdir.
bool IsValidTrackdir(Trackdir trackdir)
Checks if a Trackdir is valid for non-road vehicles.
Trackdir FindFirstTrackdir(TrackdirBits trackdirs)
Returns first Trackdir from TrackdirBits or INVALID_TRACKDIR.
TrackdirBits TrackdirCrossesTrackdirs(Trackdir trackdir)
Maps a trackdir to all trackdirs that make 90 deg turns with it.
TrackdirBits DiagdirReachesTrackdirs(DiagDirection diagdir)
Returns all trackdirs that can be reached when entering a tile from a given (diagonal) direction.
bool IsDiagonalTrackdir(Trackdir trackdir)
Checks if a given Trackdir is diagonal.
bool HasTrackdir(TrackdirBits trackdirs, Trackdir trackdir)
Checks whether a TrackdirBits has a given Trackdir.
TrackdirBits TrackdirToTrackdirBits(Trackdir trackdir)
Maps a Trackdir to the corresponding TrackdirBits value.
DiagDirection TrackdirToExitdir(Trackdir trackdir)
Maps a trackdir to the (4-way) direction the tile is exited when following that trackdir.
Trackdir
Enumeration for tracks and directions.
@ INVALID_TRACKDIR
Flag for an invalid trackdir.
TrackdirBits
Allow incrementing of Trackdir variables.
@ TRACKDIR_BIT_NONE
No track build.
@ INVALID_TRACKDIR_BIT
Flag for an invalid trackdirbit value.
Track
These are used to specify a single track.
@ INVALID_TRACK
Flag for an invalid track.
@ TRANSPORT_WATER
Transport over water.
bool HasVehicleOnPos(TileIndex tile, void *data, VehicleFromPosProc *proc)
Checks whether a vehicle is on a specific location.
@ VS_HIDDEN
Vehicle is not visible.
@ VEH_SHIP
Ship vehicle type.
bool IsDockingTile(Tile t)
Checks whether the tile is marked as a dockling tile.
WaterRegionDesc GetWaterRegionInfo(TileIndex tile)
Returns basic water region information for the provided tile.
WaterRegionPatchDesc GetWaterRegionPatchInfo(TileIndex tile)
Returns basic water region patch information for the provided tile.
TileIndex GetWaterRegionCenterTile(const WaterRegionDesc &water_region)
Returns the center tile of a particular water region.
Base includes/functions for YAPF.
Node tailored for ship pathfinding.
bool YapfShipCheckReverse(const Ship *v, Trackdir *trackdir)
Returns true if it is better to reverse the ship before leaving depot using YAPF.
Track YapfShipChooseTrack(const Ship *v, TileIndex tile, bool &path_found, ShipPathCache &path_cache)
Ship controller helper - path finder invoker.
std::vector< WaterRegionPatchDesc > YapfShipFindWaterRegionPath(const Ship *v, TileIndex start_tile, int max_returned_path_length)
Finds a path at the water region level.
Implementation of YAPF for water regions, which are used for finding intermediate ship destinations.