OpenTTD Source  20241108-master-g80f628063a
yapf_ship_regions.cpp
Go to the documentation of this file.
1 /*
2  * This file is part of OpenTTD.
3  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
4  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
5  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
6  */
7 
10 #include "../../stdafx.h"
11 #include "../../ship.h"
12 
13 #include "yapf.hpp"
14 #include "yapf_ship_regions.h"
15 #include "../water_regions.h"
16 
17 #include "../../safeguards.h"
18 
19 constexpr int DIRECT_NEIGHBOR_COST = 100;
20 constexpr int NODES_PER_REGION = 4;
21 constexpr int MAX_NUMBER_OF_NODES = 65536;
22 
25  WaterRegionPatchDesc water_region_patch;
26 
27  inline void Set(const WaterRegionPatchDesc &water_region_patch)
28  {
29  this->water_region_patch = water_region_patch;
30  }
31 
32  inline int CalcHash() const { return CalculateWaterRegionPatchHash(this->water_region_patch); }
33  inline bool operator==(const CYapfRegionPatchNodeKey &other) const { return this->CalcHash() == other.CalcHash(); }
34 };
35 
36 inline uint ManhattanDistance(const CYapfRegionPatchNodeKey &a, const CYapfRegionPatchNodeKey &b)
37 {
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;
39 }
40 
42 template <class Tkey_>
44  typedef Tkey_ Key;
46 
47  Tkey_ key;
48  Node *hash_next;
49  Node *parent;
50  int cost;
51  int estimate;
52 
53  inline void Set(Node *parent, const WaterRegionPatchDesc &water_region_patch)
54  {
55  this->key.Set(water_region_patch);
56  this->hash_next = nullptr;
57  this->parent = parent;
58  this->cost = 0;
59  this->estimate = 0;
60  }
61 
62  inline void Set(Node *parent, const Key &key)
63  {
64  this->Set(parent, key.water_region_patch);
65  }
66 
67  DiagDirection GetDiagDirFromParent() const
68  {
69  if (!this->parent) return INVALID_DIAGDIR;
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;
72  if (dx > 0 && dy == 0) return DIAGDIR_SW;
73  if (dx < 0 && dy == 0) return DIAGDIR_NE;
74  if (dx == 0 && dy > 0) return DIAGDIR_SE;
75  if (dx == 0 && dy < 0) return DIAGDIR_NW;
76  return INVALID_DIAGDIR;
77  }
78 
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; }
85 };
86 
88 template <class Types>
90 {
91 public:
92  typedef typename Types::Tpf Tpf;
93  typedef typename Types::NodeList::Titem Node;
94  typedef typename Node::Key Key;
95 
96 protected:
97  inline Tpf &Yapf() { return *static_cast<Tpf*>(this); }
98 
99 private:
100  std::vector<CYapfRegionPatchNodeKey> origin_keys;
101 
102 public:
103  void AddOrigin(const WaterRegionPatchDesc &water_region_patch)
104  {
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 });
107  }
108 
109  bool HasOrigin(const WaterRegionPatchDesc &water_region_patch)
110  {
111  return std::find(this->origin_keys.begin(), this->origin_keys.end(), CYapfRegionPatchNodeKey{ water_region_patch }) != this->origin_keys.end();
112  }
113 
114  void PfSetStartupNodes()
115  {
116  for (const CYapfRegionPatchNodeKey &origin_key : this->origin_keys) {
117  Node &node = Yapf().CreateNewNode();
118  node.Set(nullptr, origin_key);
119  Yapf().AddStartupNode(node);
120  }
121  }
122 };
123 
125 template <class Types>
127 {
128 public:
129  typedef typename Types::Tpf Tpf;
130  typedef typename Types::NodeList::Titem Node;
131  typedef typename Node::Key Key;
132 
133 protected:
134  Key dest;
135 
136 public:
137  void SetDestination(const WaterRegionPatchDesc &water_region_patch)
138  {
139  this->dest.Set(water_region_patch);
140  }
141 
142 protected:
143  Tpf &Yapf() { return *static_cast<Tpf*>(this); }
144 
145 public:
146  inline bool PfDetectDestination(Node &n) const
147  {
148  return n.key == this->dest;
149  }
150 
151  inline bool PfCalcEstimate(Node &n)
152  {
153  if (this->PfDetectDestination(n)) {
154  n.estimate = n.cost;
155  return true;
156  }
157 
158  n.estimate = n.cost + ManhattanDistance(n.key, this->dest);
159 
160  return true;
161  }
162 };
163 
165 template <class Types>
167 {
168 public:
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;
173 
174 protected:
175  inline Tpf &Yapf() { return *static_cast<Tpf*>(this); }
176 
177 public:
178  inline void PfFollowNode(Node &old_node)
179  {
180  TVisitWaterRegionPatchCallBack visitFunc = [&](const WaterRegionPatchDesc &water_region_patch)
181  {
182  Node &node = Yapf().CreateNewNode();
183  node.Set(&old_node, water_region_patch);
184  Yapf().AddNewNode(node, TrackFollower{});
185  };
186  VisitWaterRegionPatchNeighbors(old_node.key.water_region_patch, visitFunc);
187  }
188 
189  inline char TransportTypeChar() const { return '^'; }
190 
191  static std::vector<WaterRegionPatchDesc> FindWaterRegionPath(const Ship *v, TileIndex start_tile, int max_returned_path_length)
192  {
193  const WaterRegionPatchDesc start_water_region_patch = GetWaterRegionPatchInfo(start_tile);
194 
195  /* We reserve 4 nodes (patches) per water region. The vast majority of water regions have 1 or 2 regions so this should be a pretty
196  * safe limit. We cap the limit at 65536 which is at a region size of 16x16 is equivalent to one node per region for a 4096x4096 map. */
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);
199 
200  if (v->current_order.IsType(OT_GOTO_STATION)) {
201  DestinationID station_id = v->current_order.GetDestination();
202  const BaseStation *station = BaseStation::Get(station_id);
203  TileArea tile_area;
204  station->GetTileArea(&tile_area, STATION_DOCK);
205  for (const auto &tile : tile_area) {
206  if (IsDockingTile(tile) && IsShipDestinationTile(tile, station_id)) {
207  pf.AddOrigin(GetWaterRegionPatchInfo(tile));
208  }
209  }
210  } else {
211  TileIndex tile = v->dest_tile;
212  pf.AddOrigin(GetWaterRegionPatchInfo(tile));
213  }
214 
215  /* If origin and destination are the same we simply return that water patch. */
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;
219 
220  /* Find best path. */
221  if (!pf.FindPath(v)) return {}; // Path not found.
222 
223  Node *node = pf.GetBestNode();
224  for (int i = 0; i < max_returned_path_length - 1; ++i) {
225  if (node != nullptr) {
226  node = node->parent;
227  if (node != nullptr) path.push_back(node->key.water_region_patch);
228  }
229  }
230 
231  assert(!path.empty());
232  return path;
233  }
234 };
235 
237 template <class Types>
239 {
240 public:
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;
245 
246 protected:
248  Tpf &Yapf() { return *static_cast<Tpf*>(this); }
249 
250 public:
256  inline bool PfCalcCost(Node &n, const TrackFollower *)
257  {
258  n.cost = n.parent->cost + ManhattanDistance(n.key, n.parent->key);
259 
260  /* Incentivise zigzagging by adding a slight penalty when the search continues in the same direction. */
261  Node *grandparent = n.parent->parent;
262  if (grandparent != nullptr) {
263  const DiagDirDiff dir_diff = DiagDirDifference(n.parent->GetDiagDirFromParent(), n.GetDiagDirFromParent());
264  if (dir_diff != DIAGDIRDIFF_90LEFT && dir_diff != DIAGDIRDIFF_90RIGHT) n.cost += 1;
265  }
266 
267  return true;
268  }
269 };
270 
271 /* We don't need a follower but YAPF requires one. */
272 struct DummyFollower : public CFollowTrackWater {};
273 
278 template <class Tpf_, class Tnode_list>
280 {
282  typedef Tpf_ Tpf;
284  typedef Tnode_list NodeList;
285  typedef Ship VehicleType;
286 
294 };
295 
297 
298 struct CYapfRegionWater : CYapfT<CYapfRegion_TypesT<CYapfRegionWater, CRegionNodeListWater>>
299 {
300  explicit CYapfRegionWater(int max_nodes) { this->max_search_nodes = max_nodes; }
301 };
302 
310 std::vector<WaterRegionPatchDesc> YapfShipFindWaterRegionPath(const Ship *v, TileIndex start_tile, int max_returned_path_length)
311 {
312  return CYapfRegionWater::FindWaterRegionPath(v, start_tile, max_returned_path_length);
313 }
Hash table based node list multi-container class.
Definition: nodelist.hpp:22
CYapfBaseT - A-star type path finder base class.
Definition: yapf_base.hpp:49
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.
@ DIAGDIR_NW
Northwest.
@ DIAGDIR_SE
Southeast.
@ INVALID_DIAGDIR
Flag for an invalid DiagDirection.
@ DIAGDIR_SW
Southwest.
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.
Definition: math_func.hpp:23
bool IsShipDestinationTile(TileIndex tile, StationID station)
Test if a tile is a docking tile for the given station.
Definition: ship_cmd.cpp:647
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.
Tpf_ Tpf
Pathfinder type.
CYapfCostRegionT< Types > PfCost
Cost provider.
Node of the link graph.
Definition: linkgraph.h:90
static debug_inline uint Size()
Get the size of the map.
Definition: map_func.h:288
DestinationID GetDestination() const
Gets the destination of this order.
Definition: order_base.h:103
bool IsType(OrderType type) const
Check whether this order is of the given type.
Definition: order_base.h:70
Represents the covered area of e.g.
Definition: tilearea_type.h:18
static Titem * Get(size_t index)
Returns Titem with given index.
Definition: pool_type.hpp:339
All ships have this type.
Definition: ship.h:24
Order current_order
The current order (+ status, like: loading)
Definition: vehicle_base.h:356
TileIndex dest_tile
Heading for this tile.
Definition: vehicle_base.h:271
Describes a single interconnected patch of water within a particular water region.
Definition: water_regions.h:27
TWaterRegionPatchLabel label
Unique label identifying the patch within the region.
Definition: water_regions.h:30
int y
The Y coordinate of the water region, i.e. Y=2 is the 3rd water region along the Y-axis.
Definition: water_regions.h:29
int x
The X coordinate of the water region, i.e. X=2 is the 3rd water region along the X-axis.
Definition: water_regions.h:28
bool IsDockingTile(Tile t)
Checks whether the tile is marked as a dockling tile.
Definition: water_map.h:371
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.