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_>
55 this->key.Set(water_region_patch);
56 this->hash_next =
nullptr;
57 this->parent = parent;
62 inline void Set(
Node *parent,
const Key &key)
64 this->Set(parent, key.water_region_patch);
70 const int dx = this->key.water_region_patch.x - this->parent->key.water_region_patch.x;
71 const int dy = this->key.water_region_patch.y - this->parent->key.water_region_patch.y;
79 inline Node *GetHashNext() {
return this->hash_next; }
80 inline void SetHashNext(
Node *pNext) { this->hash_next = pNext; }
81 inline const Tkey_ &GetKey()
const {
return this->key; }
82 inline int GetCost() {
return this->cost; }
83 inline int GetCostEstimate() {
return this->estimate; }
84 inline bool operator<(
const Node &other)
const {
return this->estimate < other.estimate; }
88 template <
class Types>
92 typedef typename Types::Tpf
Tpf;
93 typedef typename Types::NodeList::Titem
Node;
94 typedef typename Node::Key
Key;
97 inline Tpf &Yapf() {
return *
static_cast<Tpf*
>(
this); }
100 std::vector<CYapfRegionPatchNodeKey> origin_keys;
105 if (water_region_patch.
label == INVALID_WATER_REGION_PATCH)
return;
106 if (!HasOrigin(water_region_patch)) this->origin_keys.push_back(
CYapfRegionPatchNodeKey{ water_region_patch });
111 return std::find(this->origin_keys.begin(), this->origin_keys.end(),
CYapfRegionPatchNodeKey{ water_region_patch }) != this->origin_keys.end();
114 void PfSetStartupNodes()
117 Node &node = Yapf().CreateNewNode();
118 node.Set(
nullptr, origin_key);
119 Yapf().AddStartupNode(node);
125 template <
class Types>
129 typedef typename Types::Tpf
Tpf;
130 typedef typename Types::NodeList::Titem
Node;
131 typedef typename Node::Key
Key;
139 this->dest.Set(water_region_patch);
143 Tpf &Yapf() {
return *
static_cast<Tpf*
>(
this); }
146 inline bool PfDetectDestination(
Node &n)
const
148 return n.key == this->dest;
151 inline bool PfCalcEstimate(
Node &n)
153 if (this->PfDetectDestination(n)) {
158 n.estimate = n.cost + ManhattanDistance(n.key, this->dest);
165 template <
class Types>
169 typedef typename Types::Tpf
Tpf;
170 typedef typename Types::TrackFollower TrackFollower;
171 typedef typename Types::NodeList::Titem
Node;
172 typedef typename Node::Key
Key;
175 inline Tpf &Yapf() {
return *
static_cast<Tpf*
>(
this); }
178 inline void PfFollowNode(
Node &old_node)
182 Node &node = Yapf().CreateNewNode();
183 node.Set(&old_node, water_region_patch);
184 Yapf().AddNewNode(node, TrackFollower{});
189 inline char TransportTypeChar()
const {
return '^'; }
191 static std::vector<WaterRegionPatchDesc> FindWaterRegionPath(
const Ship *v,
TileIndex start_tile,
int max_returned_path_length)
197 Tpf pf(std::min(
static_cast<int>(
Map::Size() * NODES_PER_REGION) / WATER_REGION_NUMBER_OF_TILES, MAX_NUMBER_OF_NODES));
198 pf.SetDestination(start_water_region_patch);
205 for (
const auto &tile : tile_area) {
216 std::vector<WaterRegionPatchDesc> path = { start_water_region_patch };
217 path.reserve(max_returned_path_length);
218 if (pf.HasOrigin(start_water_region_patch))
return path;
221 if (!pf.FindPath(v))
return {};
223 Node *node = pf.GetBestNode();
224 for (
int i = 0; i < max_returned_path_length - 1; ++i) {
225 if (node !=
nullptr) {
227 if (node !=
nullptr) path.push_back(node->key.water_region_patch);
231 assert(!path.empty());
237 template <
class Types>
241 typedef typename Types::Tpf
Tpf;
242 typedef typename Types::TrackFollower TrackFollower;
243 typedef typename Types::NodeList::Titem
Node;
244 typedef typename Node::Key
Key;
258 n.cost = n.parent->cost + ManhattanDistance(n.key, n.parent->key);
261 Node *grandparent = n.parent->parent;
262 if (grandparent !=
nullptr) {
278 template <
class Tpf_,
class Tnode_list>
284 typedef Tnode_list NodeList;
300 explicit CYapfRegionWater(
int max_nodes) { this->max_search_nodes = max_nodes; }
312 return CYapfRegionWater::FindWaterRegionPath(v, start_tile, max_returned_path_length);
Hash table based node list multi-container class.
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.
Node::Key Key
Key to hash tables.
Types::NodeList::Titem Node
This will be our node type.
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::NodeList::Titem Node
This will be our node type.
Types::Tpf Tpf
The pathfinder class (derived from THIS class).
YAPF node following for water region pathfinding.
Types::NodeList::Titem 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::Titem 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...
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.