10 #include "../../stdafx.h"
11 #include "../../ship.h"
15 #include "../water_regions.h"
17 #include "../../safeguards.h"
19 constexpr
int DIRECT_NEIGHBOR_COST = 100;
20 constexpr
int NODES_PER_REGION = 4;
21 constexpr
int MAX_NUMBER_OF_NODES = 65536;
29 this->water_region_patch = water_region_patch;
33 inline bool operator==(
const CYapfRegionPatchNodeKey &other)
const {
return this->CalcHash() == other.CalcHash(); }
38 return (
std::abs(a.water_region_patch.
x - b.water_region_patch.
x) +
std::abs(a.water_region_patch.
y - b.water_region_patch.
y)) * DIRECT_NEIGHBOR_COST;
42 template <
class Tkey_>
49 this->key.Set(water_region_patch);
50 this->hash_next =
nullptr;
51 this->parent = parent;
56 inline void Set(
Node *parent,
const Key &key)
58 this->Set(parent, key.water_region_patch);
64 const int dx = this->key.water_region_patch.x - this->parent->key.water_region_patch.x;
65 const int dy = this->key.water_region_patch.y - this->parent->key.water_region_patch.y;
75 template <
class Types>
79 typedef typename Types::Tpf
Tpf;
80 typedef typename Types::NodeList::Item
Node;
81 typedef typename Node::Key
Key;
84 inline Tpf &Yapf() {
return *
static_cast<Tpf*
>(
this); }
87 std::vector<CYapfRegionPatchNodeKey> origin_keys;
92 if (water_region_patch.
label == INVALID_WATER_REGION_PATCH)
return;
98 return std::find(this->origin_keys.begin(), this->origin_keys.end(),
CYapfRegionPatchNodeKey{ water_region_patch }) != this->origin_keys.end();
101 void PfSetStartupNodes()
104 Node &node = Yapf().CreateNewNode();
105 node.Set(
nullptr, origin_key);
106 Yapf().AddStartupNode(node);
112 template <
class Types>
116 typedef typename Types::Tpf
Tpf;
117 typedef typename Types::NodeList::Item
Node;
118 typedef typename Node::Key
Key;
126 this->dest.Set(water_region_patch);
130 Tpf &Yapf() {
return *
static_cast<Tpf*
>(
this); }
133 inline bool PfDetectDestination(
Node &n)
const
135 return n.key == this->dest;
138 inline bool PfCalcEstimate(
Node &n)
140 if (this->PfDetectDestination(n)) {
145 n.estimate = n.cost + ManhattanDistance(n.key, this->dest);
152 template <
class Types>
156 typedef typename Types::Tpf
Tpf;
157 typedef typename Types::TrackFollower TrackFollower;
158 typedef typename Types::NodeList::Item
Node;
159 typedef typename Node::Key
Key;
162 inline Tpf &Yapf() {
return *
static_cast<Tpf*
>(
this); }
165 inline void PfFollowNode(
Node &old_node)
169 Node &node = Yapf().CreateNewNode();
170 node.Set(&old_node, water_region_patch);
171 Yapf().AddNewNode(node, TrackFollower{});
176 inline char TransportTypeChar()
const {
return '^'; }
178 static std::vector<WaterRegionPatchDesc> FindWaterRegionPath(
const Ship *v,
TileIndex start_tile,
int max_returned_path_length)
184 Tpf pf(std::min(
static_cast<int>(
Map::Size() * NODES_PER_REGION) / WATER_REGION_NUMBER_OF_TILES, MAX_NUMBER_OF_NODES));
185 pf.SetDestination(start_water_region_patch);
192 for (
const auto &tile : tile_area) {
203 std::vector<WaterRegionPatchDesc> path = { start_water_region_patch };
204 path.reserve(max_returned_path_length);
205 if (pf.HasOrigin(start_water_region_patch))
return path;
208 if (!pf.FindPath(v))
return {};
210 Node *node = pf.GetBestNode();
211 for (
int i = 0; i < max_returned_path_length - 1; ++i) {
212 if (node !=
nullptr) {
214 if (node !=
nullptr) path.push_back(node->key.water_region_patch);
218 assert(!path.empty());
224 template <
class Types>
228 typedef typename Types::Tpf
Tpf;
229 typedef typename Types::TrackFollower TrackFollower;
230 typedef typename Types::NodeList::Item
Node;
231 typedef typename Node::Key
Key;
245 n.cost = n.parent->cost + ManhattanDistance(n.key, n.parent->key);
248 Node *grandparent = n.parent->parent;
249 if (grandparent !=
nullptr) {
265 template <
class Tpf_,
class Tnode_list>
287 explicit CYapfRegionWater(
int max_nodes) { this->max_search_nodes = max_nodes; }
299 return CYapfRegionWater::FindWaterRegionPath(v, start_tile, max_returned_path_length);
CYapfBaseT - A-star type path finder base class.
Cost Provider of YAPF for water regions.
Types::Tpf Tpf
The pathfinder class (derived from THIS class).
Tpf & Yapf()
To access inherited path finder.
Types::NodeList::Item Node
This will be our node type.
Node::Key Key
Key to hash tables.
bool PfCalcCost(Node &n, const TrackFollower *)
Called by YAPF to calculate the cost from the origin to the given node.
YAPF destination provider for water regions.
Node::Key Key
Key to hash tables.
Types::Tpf Tpf
The pathfinder class (derived from THIS class).
Types::NodeList::Item Node
This will be our node type.
YAPF node following for water region pathfinding.
Types::NodeList::Item Node
This will be our node type.
Types::Tpf Tpf
The pathfinder class (derived from THIS class).
Node::Key Key
Key to hash tables.
YAPF origin for water regions.
Types::NodeList::Item Node
This will be our node type.
Node::Key Key
Key to hash tables.
Types::Tpf Tpf
The pathfinder class (derived from THIS class).
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.
DiagDirDiff DiagDirDifference(DiagDirection d0, DiagDirection d1)
Calculate the difference between two DiagDirection values.
DiagDirection
Enumeration for diagonal directions.
@ DIAGDIR_NE
Northeast, upper right on your monitor.
@ INVALID_DIAGDIR
Flag for an invalid DiagDirection.
DiagDirDiff
Enumeration for the difference between to DiagDirection.
@ DIAGDIRDIFF_90RIGHT
90 degrees right
@ DIAGDIRDIFF_90LEFT
90 degrees left
constexpr T abs(const T a)
Returns the absolute value of (scalar) variable.
bool IsShipDestinationTile(TileIndex tile, StationID station)
Test if a tile is a docking tile for the given station.
Base class for all station-ish types.
virtual void GetTileArea(TileArea *ta, StationType type) const =0
Get the tile area for a given station type.
Track follower helper template class (can serve pathfinders and vehicle controllers).
Yapf Node for water regions.
Yapf Node Key that represents a single patch of interconnected water within a water region.
Config struct of YAPF for route planning.
CYapfRegion_TypesT< Tpf_, Tnode_list > Types
Shortcut for this struct type.
DummyFollower TrackFollower
Track follower helper class.
CYapfDestinationRegionT< Types > PfDestination
Destination/distance provider.
CYapfBaseT< Types > PfBase
Pathfinder components (modules).
CYapfSegmentCostCacheNoneT< Types > PfCache
Segment cost cache provider.
CYapfFollowRegionT< Types > PfFollow
Node follower.
CYapfOriginRegionT< Types > PfOrigin
Origin provider.
CYapfCostRegionT< Types > PfCost
Cost provider.
static debug_inline uint Size()
Get the size of the map.
DestinationID GetDestination() const
Gets the destination of this order.
bool IsType(OrderType type) const
Check whether this order is of the given type.
Represents the covered area of e.g.
static Titem * Get(size_t index)
Returns Titem with given index.
All ships have this type.
Order current_order
The current order (+ status, like: loading)
TileIndex dest_tile
Heading for this tile.
Describes a single interconnected patch of water within a particular water region.
TWaterRegionPatchLabel label
Unique label identifying the patch within the region.
int y
The Y coordinate of the water region, i.e. Y=2 is the 3rd water region along the Y-axis.
int x
The X coordinate of the water region, i.e. X=2 is the 3rd water region along the X-axis.
bool IsDockingTile(Tile t)
Checks whether the tile is marked as a dockling tile.
WaterRegionPatchDesc GetWaterRegionPatchInfo(TileIndex tile)
Returns basic water region patch information for the provided tile.
void VisitWaterRegionPatchNeighbors(const WaterRegionPatchDesc &water_region_patch, TVisitWaterRegionPatchCallBack &callback)
Calls the provided callback function on all accessible water region patches in each cardinal directio...
int CalculateWaterRegionPatchHash(const WaterRegionPatchDesc &water_region_patch)
Calculates a number that uniquely identifies the provided water region patch.
Base includes/functions for YAPF.
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.