OpenTTD Source  20241121-master-g67a0fccfad
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_>
43 struct CYapfRegionNodeT : CYapfNodeT<Tkey_, CYapfRegionNodeT<Tkey_> > {
44  typedef Tkey_ Key;
46 
47  inline void Set(Node *parent, const WaterRegionPatchDesc &water_region_patch)
48  {
49  this->key.Set(water_region_patch);
50  this->hash_next = nullptr;
51  this->parent = parent;
52  this->cost = 0;
53  this->estimate = 0;
54  }
55 
56  inline void Set(Node *parent, const Key &key)
57  {
58  this->Set(parent, key.water_region_patch);
59  }
60 
61  DiagDirection GetDiagDirFromParent() const
62  {
63  if (this->parent == nullptr) return INVALID_DIAGDIR;
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;
66  if (dx > 0 && dy == 0) return DIAGDIR_SW;
67  if (dx < 0 && dy == 0) return DIAGDIR_NE;
68  if (dx == 0 && dy > 0) return DIAGDIR_SE;
69  if (dx == 0 && dy < 0) return DIAGDIR_NW;
70  return INVALID_DIAGDIR;
71  }
72 };
73 
75 template <class Types>
77 {
78 public:
79  typedef typename Types::Tpf Tpf;
80  typedef typename Types::NodeList::Item Node;
81  typedef typename Node::Key Key;
82 
83 protected:
84  inline Tpf &Yapf() { return *static_cast<Tpf*>(this); }
85 
86 private:
87  std::vector<CYapfRegionPatchNodeKey> origin_keys;
88 
89 public:
90  void AddOrigin(const WaterRegionPatchDesc &water_region_patch)
91  {
92  if (water_region_patch.label == INVALID_WATER_REGION_PATCH) return;
93  if (!HasOrigin(water_region_patch)) this->origin_keys.push_back(CYapfRegionPatchNodeKey{ water_region_patch });
94  }
95 
96  bool HasOrigin(const WaterRegionPatchDesc &water_region_patch)
97  {
98  return std::find(this->origin_keys.begin(), this->origin_keys.end(), CYapfRegionPatchNodeKey{ water_region_patch }) != this->origin_keys.end();
99  }
100 
101  void PfSetStartupNodes()
102  {
103  for (const CYapfRegionPatchNodeKey &origin_key : this->origin_keys) {
104  Node &node = Yapf().CreateNewNode();
105  node.Set(nullptr, origin_key);
106  Yapf().AddStartupNode(node);
107  }
108  }
109 };
110 
112 template <class Types>
114 {
115 public:
116  typedef typename Types::Tpf Tpf;
117  typedef typename Types::NodeList::Item Node;
118  typedef typename Node::Key Key;
119 
120 protected:
121  Key dest;
122 
123 public:
124  void SetDestination(const WaterRegionPatchDesc &water_region_patch)
125  {
126  this->dest.Set(water_region_patch);
127  }
128 
129 protected:
130  Tpf &Yapf() { return *static_cast<Tpf*>(this); }
131 
132 public:
133  inline bool PfDetectDestination(Node &n) const
134  {
135  return n.key == this->dest;
136  }
137 
138  inline bool PfCalcEstimate(Node &n)
139  {
140  if (this->PfDetectDestination(n)) {
141  n.estimate = n.cost;
142  return true;
143  }
144 
145  n.estimate = n.cost + ManhattanDistance(n.key, this->dest);
146 
147  return true;
148  }
149 };
150 
152 template <class Types>
154 {
155 public:
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;
160 
161 protected:
162  inline Tpf &Yapf() { return *static_cast<Tpf*>(this); }
163 
164 public:
165  inline void PfFollowNode(Node &old_node)
166  {
167  TVisitWaterRegionPatchCallBack visitFunc = [&](const WaterRegionPatchDesc &water_region_patch)
168  {
169  Node &node = Yapf().CreateNewNode();
170  node.Set(&old_node, water_region_patch);
171  Yapf().AddNewNode(node, TrackFollower{});
172  };
173  VisitWaterRegionPatchNeighbors(old_node.key.water_region_patch, visitFunc);
174  }
175 
176  inline char TransportTypeChar() const { return '^'; }
177 
178  static std::vector<WaterRegionPatchDesc> FindWaterRegionPath(const Ship *v, TileIndex start_tile, int max_returned_path_length)
179  {
180  const WaterRegionPatchDesc start_water_region_patch = GetWaterRegionPatchInfo(start_tile);
181 
182  /* 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
183  * 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. */
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);
186 
187  if (v->current_order.IsType(OT_GOTO_STATION)) {
188  DestinationID station_id = v->current_order.GetDestination();
189  const BaseStation *station = BaseStation::Get(station_id);
190  TileArea tile_area;
191  station->GetTileArea(&tile_area, STATION_DOCK);
192  for (const auto &tile : tile_area) {
193  if (IsDockingTile(tile) && IsShipDestinationTile(tile, station_id)) {
194  pf.AddOrigin(GetWaterRegionPatchInfo(tile));
195  }
196  }
197  } else {
198  TileIndex tile = v->dest_tile;
199  pf.AddOrigin(GetWaterRegionPatchInfo(tile));
200  }
201 
202  /* If origin and destination are the same we simply return that water patch. */
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;
206 
207  /* Find best path. */
208  if (!pf.FindPath(v)) return {}; // Path not found.
209 
210  Node *node = pf.GetBestNode();
211  for (int i = 0; i < max_returned_path_length - 1; ++i) {
212  if (node != nullptr) {
213  node = node->parent;
214  if (node != nullptr) path.push_back(node->key.water_region_patch);
215  }
216  }
217 
218  assert(!path.empty());
219  return path;
220  }
221 };
222 
224 template <class Types>
226 {
227 public:
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;
232 
233 protected:
235  Tpf &Yapf() { return *static_cast<Tpf*>(this); }
236 
237 public:
243  inline bool PfCalcCost(Node &n, const TrackFollower *)
244  {
245  n.cost = n.parent->cost + ManhattanDistance(n.key, n.parent->key);
246 
247  /* Incentivise zigzagging by adding a slight penalty when the search continues in the same direction. */
248  Node *grandparent = n.parent->parent;
249  if (grandparent != nullptr) {
250  const DiagDirDiff dir_diff = DiagDirDifference(n.parent->GetDiagDirFromParent(), n.GetDiagDirFromParent());
251  if (dir_diff != DIAGDIRDIFF_90LEFT && dir_diff != DIAGDIRDIFF_90RIGHT) n.cost += 1;
252  }
253 
254  return true;
255  }
256 };
257 
258 /* We don't need a follower but YAPF requires one. */
259 struct DummyFollower : public CFollowTrackWater {};
260 
265 template <class Tpf_, class Tnode_list>
267 {
269  typedef Tpf_ Tpf;
271  typedef Tnode_list NodeList;
272  typedef Ship VehicleType;
273 
281 };
282 
284 
285 struct CYapfRegionWater : CYapfT<CYapfRegion_TypesT<CYapfRegionWater, CRegionNodeListWater>>
286 {
287  explicit CYapfRegionWater(int max_nodes) { this->max_search_nodes = max_nodes; }
288 };
289 
297 std::vector<WaterRegionPatchDesc> YapfShipFindWaterRegionPath(const Ship *v, TileIndex start_tile, int max_returned_path_length)
298 {
299  return CYapfRegionWater::FindWaterRegionPath(v, start_tile, max_returned_path_length);
300 }
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.
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.
Definition: nodelist.hpp:21
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 base.
Definition: yapf_node.hpp:62
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:32
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.