10 #include "../../stdafx.h"
11 #include "../../ship.h"
12 #include "../../vehicle_func.h"
17 #include "../water_regions.h"
19 #include "../../safeguards.h"
21 constexpr
int NUMBER_OR_WATER_REGIONS_LOOKAHEAD = 4;
22 constexpr
int MAX_SHIP_PF_NODES = (NUMBER_OR_WATER_REGIONS_LOOKAHEAD + 1) * WATER_REGION_NUMBER_OF_TILES * 4;
24 constexpr
int SHIP_LOST_PATH_LENGTH = 8;
26 template <
class Types>
30 typedef typename Types::Tpf
Tpf;
31 typedef typename Types::TrackFollower TrackFollower;
32 typedef typename Types::NodeList::Item
Node;
33 typedef typename Node::Key
Key;
38 StationID dest_station;
40 bool has_intermediate_dest =
false;
45 void SetDestination(
const Ship *v)
52 this->dest_station = INVALID_STATION;
60 this->has_intermediate_dest =
true;
62 this->intermediate_dest_region_patch = water_region_patch;
69 return *
static_cast<Tpf*
>(
this);
76 return this->PfDetectDestinationTile(n.segment_last_tile, n.segment_last_td);
81 if (this->has_intermediate_dest) {
98 const TileIndex destination_tile = this->has_intermediate_dest ? this->intermediate_dest_tile : this->dest_tile;
100 static const int dg_dir_to_x_offs[] = { -1, 0, 1, 0 };
101 static const int dg_dir_to_y_offs[] = { 0, 1, 0, -1 };
109 int x1 = 2 *
TileX(tile) + dg_dir_to_x_offs[(int)exitdir];
110 int y1 = 2 *
TileY(tile) + dg_dir_to_y_offs[(int)exitdir];
111 int x2 = 2 *
TileX(destination_tile);
112 int y2 = 2 *
TileY(destination_tile);
113 int dx =
abs(x1 - x2);
114 int dy =
abs(y1 - y2);
115 int dmin = std::min(dx, dy);
116 int dxy =
abs(dx - dy);
118 n.estimate = n.cost + d;
119 assert(n.estimate >= n.parent->estimate);
125 template <
class Types>
129 typedef typename Types::Tpf
Tpf;
130 typedef typename Types::TrackFollower TrackFollower;
131 typedef typename Types::NodeList::Item
Node;
132 typedef typename Node::Key
Key;
138 return *
static_cast<Tpf*
>(
this);
141 std::vector<WaterRegionDesc> water_region_corridor;
151 TrackFollower F(
Yapf().GetVehicle());
152 if (F.Follow(old_node.key.tile, old_node.key.td)) {
153 if (this->water_region_corridor.empty()
154 || std::find(this->water_region_corridor.begin(), this->water_region_corridor.end(),
156 Yapf().AddMultipleNodes(&old_node, F);
164 this->water_region_corridor.clear();
165 for (
const WaterRegionPatchDesc &path_entry : path) this->water_region_corridor.push_back(path_entry);
185 TrackFollower follower(v);
186 if (follower.Follow(tile, dir)) {
199 for (
int i = 0; i < path_length; ++i) {
202 path_cache.push_back(tile_dir.second);
208 std::reverse(std::begin(path_cache), std::end(path_cache));
210 const Trackdir result = path_cache.back().trackdir;
211 path_cache.pop_back();
216 bool &path_found, ShipPathCache &path_cache,
Trackdir &best_origin_dir)
218 const std::vector<WaterRegionPatchDesc> high_level_path =
YapfShipFindWaterRegionPath(v, tile, NUMBER_OR_WATER_REGIONS_LOOKAHEAD + 1);
219 if (high_level_path.empty()) {
228 for (
int attempt = 0; attempt < 2; ++attempt) {
229 Tpf pf(MAX_SHIP_PF_NODES);
232 pf.SetOrigin(v->
tile, forward_dirs | reverse_dirs);
233 pf.SetDestination(v);
234 const bool is_intermediate_destination =
static_cast<int>(high_level_path.size()) >= NUMBER_OR_WATER_REGIONS_LOOKAHEAD + 1;
235 if (is_intermediate_destination) pf.SetIntermediateDestination(high_level_path.back());
239 if (attempt > 0) pf.RestrictSearch(high_level_path);
242 path_found = pf.FindPath(v);
243 Node *node = pf.GetBestNode();
244 if (attempt == 0 && !path_found)
continue;
247 if (!path_found)
return CreateRandomPath(v, path_cache, SHIP_LOST_PATH_LENGTH);
255 while (node->parent) {
258 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();
259 const bool add_full_path = !is_intermediate_destination && node_water_patch != end_water_patch;
263 if (add_full_path || !node_water_patch_on_high_level_path || node_water_patch == start_water_patch) {
264 path_cache.push_back(node->GetTrackdir());
270 assert(node->GetTile() == v->
tile);
273 best_origin_dir = node->GetTrackdir();
284 const Trackdir result = path_cache.back().trackdir;
285 path_cache.pop_back();
288 if (start_water_patch == end_water_patch) path_cache.clear();
305 bool path_found =
false;
306 ShipPathCache dummy_cache;
309 if (trackdir ==
nullptr) {
314 (void)ChooseShipTrack(v, v->
tile, forward_dirs, reverse_dirs, path_found, dummy_cache, best_origin_dir);
315 return path_found && best_origin_dir == reverse_dir;
320 (void)ChooseShipTrack(v, v->
tile,
TRACKDIR_BIT_NONE, reverse_dirs, path_found, dummy_cache, best_origin_dir);
328 template <
class Types>
332 typedef typename Types::Tpf
Tpf;
333 typedef typename Types::TrackFollower TrackFollower;
334 typedef typename Types::NodeList::Item
Node;
335 typedef typename Node::Key
Key;
340 return *
static_cast<Tpf*
>(
this);
351 return Yapf().PfGetSettings().ship_curve90_penalty;
354 return Yapf().PfGetSettings().ship_curve45_penalty;
361 uint *count = (uint*)data;
378 c += this->CurveCost(n.parent->GetTrackdir(), n.GetTrackdir());
393 if (speed_frac > 0) c +=
YAPF_TILE_LENGTH * (1 + tf->tiles_skipped) * speed_frac / (256 - speed_frac);
396 n.cost = n.parent->cost + c;
405 template <
class Tpf_,
class Ttrack_follower,
class Tnode_list>
423 struct CYapfShip :
CYapfT<CYapfShip_TypesT<CYapfShip, CFollowTrackWater, CShipNodeListExitDir > >
425 explicit CYapfShip(
int max_nodes) { this->max_search_nodes = max_nodes; }
439 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::Item 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::Item 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.
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::NodeList::Item Node
this will be our node type.
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...
Hash table based node list multi-container class.
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.