OpenTTD Source 20241224-master-gf74b0cf984
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
19constexpr int DIRECT_NEIGHBOR_COST = 100;
20constexpr int NODES_PER_REGION = 4;
21constexpr 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
36inline 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
42template <class Tkey_>
43struct 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
75template <class Types>
77{
78public:
79 typedef typename Types::Tpf Tpf;
80 typedef typename Types::NodeList::Item Node;
81 typedef typename Node::Key Key;
82
83protected:
84 inline Tpf &Yapf() { return *static_cast<Tpf*>(this); }
85
86private:
87 std::vector<CYapfRegionPatchNodeKey> origin_keys;
88
89public:
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::ranges::find(this->origin_keys, 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
112template <class Types>
114{
115public:
116 typedef typename Types::Tpf Tpf;
117 typedef typename Types::NodeList::Item Node;
118 typedef typename Node::Key Key;
119
120protected:
121 Key dest;
122
123public:
124 void SetDestination(const WaterRegionPatchDesc &water_region_patch)
125 {
126 this->dest.Set(water_region_patch);
127 }
128
129protected:
130 Tpf &Yapf() { return *static_cast<Tpf*>(this); }
131
132public:
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
152template <class Types>
154{
155public:
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
161protected:
162 inline Tpf &Yapf() { return *static_cast<Tpf*>(this); }
163
164public:
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
224template <class Types>
226{
227public:
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
233protected:
235 Tpf &Yapf() { return *static_cast<Tpf*>(this); }
236
237public:
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. */
260
265template <class Tpf_, class Tnode_list>
282
284
285struct CYapfRegionWater : CYapfT<CYapfRegion_TypesT<CYapfRegionWater, CRegionNodeListWater>>
286{
287 explicit CYapfRegionWater(int max_nodes) { this->max_search_nodes = max_nodes; }
288};
289
297std::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).
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.
Tpf & Yapf()
To access inherited path finder.
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
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.
static Titem * Get(size_t index)
Returns Titem with given index.
All ships have this type.
Definition ship.h:32
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.
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.