OpenTTD Source 20241224-master-gf74b0cf984
yapf_ship.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#include "../../vehicle_func.h"
13
14#include "yapf.hpp"
15#include "yapf_node_ship.hpp"
16#include "yapf_ship_regions.h"
17#include "../water_regions.h"
18
19#include "../../safeguards.h"
20
21constexpr int NUMBER_OR_WATER_REGIONS_LOOKAHEAD = 4;
22constexpr int MAX_SHIP_PF_NODES = (NUMBER_OR_WATER_REGIONS_LOOKAHEAD + 1) * WATER_REGION_NUMBER_OF_TILES * 4; // 4 possible exit dirs per tile.
23
24constexpr int SHIP_LOST_PATH_LENGTH = 8; // The length of the (aimless) path assigned when a ship is lost.
25
26template <class Types>
28{
29public:
30 typedef typename Types::Tpf Tpf;
31 typedef typename Types::TrackFollower TrackFollower;
32 typedef typename Types::NodeList::Item Node;
33 typedef typename Node::Key Key;
34
35protected:
36 TileIndex dest_tile;
37 TrackdirBits dest_trackdirs;
38 StationID dest_station;
39
40 bool has_intermediate_dest = false;
41 TileIndex intermediate_dest_tile;
42 WaterRegionPatchDesc intermediate_dest_region_patch;
43
44public:
45 void SetDestination(const Ship *v)
46 {
47 if (v->current_order.IsType(OT_GOTO_STATION)) {
48 this->dest_station = v->current_order.GetDestination();
49 this->dest_tile = CalcClosestStationTile(this->dest_station, v->tile, STATION_DOCK);
50 this->dest_trackdirs = INVALID_TRACKDIR_BIT;
51 } else {
52 this->dest_station = INVALID_STATION;
53 this->dest_tile = v->dest_tile;
55 }
56 }
57
58 void SetIntermediateDestination(const WaterRegionPatchDesc &water_region_patch)
59 {
60 this->has_intermediate_dest = true;
61 this->intermediate_dest_tile = GetWaterRegionCenterTile(water_region_patch);
62 this->intermediate_dest_region_patch = water_region_patch;
63 }
64
65protected:
67 inline Tpf& Yapf()
68 {
69 return *static_cast<Tpf*>(this);
70 }
71
72public:
74 inline bool PfDetectDestination(Node &n)
75 {
76 return this->PfDetectDestinationTile(n.segment_last_tile, n.segment_last_td);
77 }
78
79 inline bool PfDetectDestinationTile(TileIndex tile, Trackdir trackdir)
80 {
81 if (this->has_intermediate_dest) {
82 /* GetWaterRegionInfo is much faster than GetWaterRegionPatchInfo so we try that first. */
83 if (GetWaterRegionInfo(tile) != this->intermediate_dest_region_patch) return false;
84 return GetWaterRegionPatchInfo(tile) == this->intermediate_dest_region_patch;
85 }
86
87 if (this->dest_station != INVALID_STATION) return IsDockingTile(tile) && IsShipDestinationTile(tile, this->dest_station);
88
89 return tile == this->dest_tile && ((this->dest_trackdirs & TrackdirToTrackdirBits(trackdir)) != TRACKDIR_BIT_NONE);
90 }
91
96 inline bool PfCalcEstimate(Node &n)
97 {
98 const TileIndex destination_tile = this->has_intermediate_dest ? this->intermediate_dest_tile : this->dest_tile;
99
100 static const int dg_dir_to_x_offs[] = { -1, 0, 1, 0 };
101 static const int dg_dir_to_y_offs[] = { 0, 1, 0, -1 };
102 if (this->PfDetectDestination(n)) {
103 n.estimate = n.cost;
104 return true;
105 }
106
107 TileIndex tile = n.segment_last_tile;
108 DiagDirection exitdir = TrackdirToExitdir(n.segment_last_td);
109 int x1 = 2 * TileX(tile) + dg_dir_to_x_offs[(int)exitdir];
110 int y1 = 2 * TileY(tile) + dg_dir_to_y_offs[(int)exitdir];
111 int x2 = 2 * TileX(destination_tile);
112 int y2 = 2 * TileY(destination_tile);
113 int dx = abs(x1 - x2);
114 int dy = abs(y1 - y2);
115 int dmin = std::min(dx, dy);
116 int dxy = abs(dx - dy);
117 int d = dmin * YAPF_TILE_CORNER_LENGTH + (dxy - 1) * (YAPF_TILE_LENGTH / 2);
118 n.estimate = n.cost + d;
119 assert(n.estimate >= n.parent->estimate);
120 return true;
121 }
122};
123
125template <class Types>
127{
128public:
129 typedef typename Types::Tpf Tpf;
130 typedef typename Types::TrackFollower TrackFollower;
131 typedef typename Types::NodeList::Item Node;
132 typedef typename Node::Key Key;
133
134protected:
136 inline Tpf &Yapf()
137 {
138 return *static_cast<Tpf*>(this);
139 }
140
141 std::vector<WaterRegionDesc> water_region_corridor;
142
143public:
149 inline void PfFollowNode(Node &old_node)
150 {
151 TrackFollower F(Yapf().GetVehicle());
152 if (F.Follow(old_node.key.tile, old_node.key.td)) {
153 if (this->water_region_corridor.empty()
154 || std::ranges::find(this->water_region_corridor, GetWaterRegionInfo(F.new_tile)) != this->water_region_corridor.end()) {
155 Yapf().AddMultipleNodes(&old_node, F);
156 }
157 }
158 }
159
161 inline void RestrictSearch(const std::vector<WaterRegionPatchDesc> &path)
162 {
163 this->water_region_corridor.clear();
164 for (const WaterRegionPatchDesc &path_entry : path) this->water_region_corridor.push_back(path_entry);
165 }
166
168 inline char TransportTypeChar() const
169 {
170 return 'w';
171 }
172
175 {
176 const int strip_amount = RandomRange(CountBits(trackdirs));
177 for (int s = 0; s < strip_amount; ++s) RemoveFirstTrackdir(&trackdirs);
178 return FindFirstTrackdir(trackdirs);
179 }
180
182 static std::pair<TileIndex, Trackdir> GetRandomFollowUpTileTrackdir(const Ship *v, TileIndex tile, Trackdir dir)
183 {
184 TrackFollower follower(v);
185 if (follower.Follow(tile, dir)) {
186 TrackdirBits dirs = follower.new_td_bits;
187 const TrackdirBits dirs_without_90_degree = dirs & ~TrackdirCrossesTrackdirs(dir);
188 if (dirs_without_90_degree != TRACKDIR_BIT_NONE) dirs = dirs_without_90_degree;
189 return { follower.new_tile, GetRandomTrackdir(dirs) };
190 }
191 return { follower.new_tile, INVALID_TRACKDIR };
192 }
193
195 static Trackdir CreateRandomPath(const Ship *v, ShipPathCache &path_cache, int path_length)
196 {
197 std::pair<TileIndex, Trackdir> tile_dir = { v->tile, v->GetVehicleTrackdir()};
198 for (int i = 0; i < path_length; ++i) {
199 tile_dir = GetRandomFollowUpTileTrackdir(v, tile_dir.first, tile_dir.second);
200 if (tile_dir.second == INVALID_TRACKDIR) break;
201 path_cache.push_back(tile_dir.second);
202 }
203
204 if (path_cache.empty()) return INVALID_TRACKDIR;
205
206 /* Reverse the path so we can take from the end. */
207 std::reverse(std::begin(path_cache), std::end(path_cache));
208
209 const Trackdir result = path_cache.back().trackdir;
210 path_cache.pop_back();
211 return result;
212 }
213
214 static Trackdir ChooseShipTrack(const Ship *v, TileIndex tile, TrackdirBits forward_dirs, TrackdirBits reverse_dirs,
215 bool &path_found, ShipPathCache &path_cache, Trackdir &best_origin_dir)
216 {
217 const std::vector<WaterRegionPatchDesc> high_level_path = YapfShipFindWaterRegionPath(v, tile, NUMBER_OR_WATER_REGIONS_LOOKAHEAD + 1);
218 if (high_level_path.empty()) {
219 path_found = false;
220 /* Make the ship move around aimlessly. This prevents repeated pathfinder calls and clearly indicates that the ship is lost. */
221 return CreateRandomPath(v, path_cache, SHIP_LOST_PATH_LENGTH);
222 }
223
224 /* Try one time without restricting the search area, which generally results in better and more natural looking paths.
225 * However the pathfinder can hit the node limit in certain situations such as long aqueducts or maze-like terrain.
226 * If that happens we run the pathfinder again, but restricted only to the regions provided by the region pathfinder. */
227 for (int attempt = 0; attempt < 2; ++attempt) {
228 Tpf pf(MAX_SHIP_PF_NODES);
229
230 /* Set origin and destination nodes */
231 pf.SetOrigin(v->tile, forward_dirs | reverse_dirs);
232 pf.SetDestination(v);
233 const bool is_intermediate_destination = static_cast<int>(high_level_path.size()) >= NUMBER_OR_WATER_REGIONS_LOOKAHEAD + 1;
234 if (is_intermediate_destination) pf.SetIntermediateDestination(high_level_path.back());
235
236 /* Restrict the search area to prevent the low level pathfinder from expanding too many nodes. This can happen
237 * when the terrain is very "maze-like" or when the high level path "teleports" via a very long aqueduct. */
238 if (attempt > 0) pf.RestrictSearch(high_level_path);
239
240 /* Find best path. */
241 path_found = pf.FindPath(v);
242 Node *node = pf.GetBestNode();
243 if (attempt == 0 && !path_found) continue; // Try again with restricted search area.
244
245 /* Make the ship move around aimlessly. This prevents repeated pathfinder calls and clearly indicates that the ship is lost. */
246 if (!path_found) return CreateRandomPath(v, path_cache, SHIP_LOST_PATH_LENGTH);
247
248 /* Return only the path within the current water region if an intermediate destination was returned. If not, cache the entire path
249 * to the final destination tile. The low-level pathfinder might actually prefer a different docking tile in a nearby region. Without
250 * caching the full path the ship can get stuck in a loop. */
251 const WaterRegionPatchDesc end_water_patch = GetWaterRegionPatchInfo(node->GetTile());
252 assert(GetWaterRegionPatchInfo(tile) == high_level_path.front());
253 const WaterRegionPatchDesc start_water_patch = high_level_path.front();
254 while (node->parent) {
255 const WaterRegionPatchDesc node_water_patch = GetWaterRegionPatchInfo(node->GetTile());
256
257 const bool node_water_patch_on_high_level_path = std::ranges::find(high_level_path, node_water_patch) != high_level_path.end();
258 const bool add_full_path = !is_intermediate_destination && node_water_patch != end_water_patch;
259
260 /* The cached path must always lead to a region patch that's on the high level path.
261 * This is what can happen when that's not the case https://github.com/OpenTTD/OpenTTD/issues/12176. */
262 if (add_full_path || !node_water_patch_on_high_level_path || node_water_patch == start_water_patch) {
263 path_cache.push_back(node->GetTrackdir());
264 } else {
265 path_cache.clear();
266 }
267 node = node->parent;
268 }
269 assert(node->GetTile() == v->tile);
270
271 /* Return INVALID_TRACKDIR to trigger a ship reversal if that is the best option. */
272 best_origin_dir = node->GetTrackdir();
273 if ((TrackdirToTrackdirBits(best_origin_dir) & forward_dirs) == TRACKDIR_BIT_NONE) {
274 path_cache.clear();
275 return INVALID_TRACKDIR;
276 }
277
278 /* A empty path means we are already at the destination. The pathfinder shouldn't have been called at all.
279 * Return a random reachable trackdir to hopefully nudge the ship out of this strange situation. */
280 if (path_cache.empty()) return CreateRandomPath(v, path_cache, 1);
281
282 /* Take out the last trackdir as the result. */
283 const Trackdir result = path_cache.back().trackdir;
284 path_cache.pop_back();
285
286 /* Clear path cache when in final water region patch. This is to allow ships to spread over different docking tiles dynamically. */
287 if (start_water_patch == end_water_patch) path_cache.clear();
288
289 return result;
290 }
291
292 return INVALID_TRACKDIR;
293 }
294
302 static bool CheckShipReverse(const Ship *v, Trackdir *trackdir)
303 {
304 bool path_found = false;
305 ShipPathCache dummy_cache;
306 Trackdir best_origin_dir = INVALID_TRACKDIR;
307
308 if (trackdir == nullptr) {
309 /* The normal case, typically called when ships leave a dock. */
310 const Trackdir reverse_dir = ReverseTrackdir(v->GetVehicleTrackdir());
311 const TrackdirBits forward_dirs = TrackdirToTrackdirBits(v->GetVehicleTrackdir());
312 const TrackdirBits reverse_dirs = TrackdirToTrackdirBits(reverse_dir);
313 (void)ChooseShipTrack(v, v->tile, forward_dirs, reverse_dirs, path_found, dummy_cache, best_origin_dir);
314 return path_found && best_origin_dir == reverse_dir;
315 } else {
316 /* This gets called when a ship suddenly can't move forward, e.g. due to terraforming. */
319 (void)ChooseShipTrack(v, v->tile, TRACKDIR_BIT_NONE, reverse_dirs, path_found, dummy_cache, best_origin_dir);
320 *trackdir = path_found && best_origin_dir != INVALID_TRACKDIR ? best_origin_dir : GetRandomTrackdir(reverse_dirs);
321 return true;
322 }
323 }
324};
325
327template <class Types>
329{
330public:
331 typedef typename Types::Tpf Tpf;
332 typedef typename Types::TrackFollower TrackFollower;
333 typedef typename Types::NodeList::Item Node;
334 typedef typename Node::Key Key;
335
338 {
339 return *static_cast<Tpf*>(this);
340 }
341
342public:
343 inline int CurveCost(Trackdir td1, Trackdir td2)
344 {
345 assert(IsValidTrackdir(td1));
346 assert(IsValidTrackdir(td2));
347
348 if (HasTrackdir(TrackdirCrossesTrackdirs(td1), td2)) {
349 /* 90-deg curve penalty. */
350 return Yapf().PfGetSettings().ship_curve90_penalty;
351 } else if (td2 != NextTrackdir(td1)) {
352 /* 45-deg curve penalty. */
353 return Yapf().PfGetSettings().ship_curve45_penalty;
354 }
355 return 0;
356 }
357
358 static Vehicle *CountShipProc(Vehicle *v, void *data)
359 {
360 uint *count = (uint*)data;
361 /* Ignore other vehicles (aircraft) and ships inside depot. */
362 if (v->type == VEH_SHIP && (v->vehstatus & VS_HIDDEN) == 0) (*count)++;
363
364 return nullptr;
365 }
366
372 inline bool PfCalcCost(Node &n, const TrackFollower *tf)
373 {
374 /* Base tile cost depending on distance. */
376 /* Additional penalty for curves. */
377 c += this->CurveCost(n.parent->GetTrackdir(), n.GetTrackdir());
378
379 if (IsDockingTile(n.GetTile())) {
380 /* Check docking tile for occupancy. */
381 uint count = 0;
382 HasVehicleOnPos(n.GetTile(), &count, &CountShipProc);
383 c += count * 3 * YAPF_TILE_LENGTH;
384 }
385
386 /* Skipped tile cost for aqueducts. */
387 c += YAPF_TILE_LENGTH * tf->tiles_skipped;
388
389 /* Ocean/canal speed penalty. */
390 const ShipVehicleInfo *svi = ShipVehInfo(Yapf().GetVehicle()->engine_type);
391 uint8_t speed_frac = (GetEffectiveWaterClass(n.GetTile()) == WATER_CLASS_SEA) ? svi->ocean_speed_frac : svi->canal_speed_frac;
392 if (speed_frac > 0) c += YAPF_TILE_LENGTH * (1 + tf->tiles_skipped) * speed_frac / (256 - speed_frac);
393
394 /* Apply it. */
395 n.cost = n.parent->cost + c;
396 return true;
397 }
398};
399
404template <class Tpf_, class Ttrack_follower, class Tnode_list>
421
422struct CYapfShip : CYapfT<CYapfShip_TypesT<CYapfShip, CFollowTrackWater, CShipNodeListExitDir > >
423{
424 explicit CYapfShip(int max_nodes) { this->max_search_nodes = max_nodes; }
425};
426
428Track YapfShipChooseTrack(const Ship *v, TileIndex tile, bool &path_found, ShipPathCache &path_cache)
429{
430 Trackdir best_origin_dir = INVALID_TRACKDIR;
432 const Trackdir td_ret = CYapfShip::ChooseShipTrack(v, tile, origin_dirs, TRACKDIR_BIT_NONE, path_found, path_cache, best_origin_dir);
433 return (td_ret != INVALID_TRACKDIR) ? TrackdirToTrack(td_ret) : INVALID_TRACK;
434}
435
436bool YapfShipCheckReverse(const Ship *v, Trackdir *trackdir)
437{
438 return CYapfShip::CheckShipReverse(v, trackdir);
439}
constexpr uint CountBits(T value)
Counts the number of set bits in a variable.
CYapfBaseT - A-star type path finder base class.
Definition yapf_base.hpp:49
Cost Provider module of YAPF for ships.
Node::Key Key
key to hash tables.
bool PfCalcCost(Node &n, const TrackFollower *tf)
Called by YAPF to calculate the cost from the origin to the given node.
Types::NodeList::Item Node
this will be our node type.
Tpf & Yapf()
to access inherited path finder
Types::Tpf Tpf
the pathfinder class (derived from THIS class).
Types::Tpf Tpf
the pathfinder class (derived from THIS class).
Definition yapf_ship.cpp:30
bool PfCalcEstimate(Node &n)
Called by YAPF to calculate cost estimate.
Definition yapf_ship.cpp:96
Types::NodeList::Item Node
this will be our node type.
Definition yapf_ship.cpp:32
bool PfDetectDestination(Node &n)
Called by YAPF to detect if node ends in the desired destination.
Definition yapf_ship.cpp:74
Node::Key Key
key to hash tables.
Definition yapf_ship.cpp:33
Tpf & Yapf()
To access inherited path finder.
Definition yapf_ship.cpp:67
Node Follower module of YAPF for ships.
static std::pair< TileIndex, Trackdir > GetRandomFollowUpTileTrackdir(const Ship *v, TileIndex tile, Trackdir dir)
Returns a random tile/trackdir that can be reached from the current tile/trackdir,...
char TransportTypeChar() const
Return debug report character to identify the transportation type.
void PfFollowNode(Node &old_node)
Called by YAPF to move from the given node to the next tile.
static Trackdir GetRandomTrackdir(TrackdirBits trackdirs)
Returns a random trackdir out of a set of trackdirs.
Node::Key Key
key to hash tables.
static Trackdir CreateRandomPath(const Ship *v, ShipPathCache &path_cache, int path_length)
Creates a random path, avoids 90 degree turns.
Types::NodeList::Item Node
this will be our node type.
Types::Tpf Tpf
the pathfinder class (derived from THIS class).
void RestrictSearch(const std::vector< WaterRegionPatchDesc > &path)
Restricts the search by creating corridor or water regions through which the ship is allowed to trave...
static bool CheckShipReverse(const Ship *v, Trackdir *trackdir)
Check whether a ship should reverse to reach its destination.
Tpf & Yapf()
to access inherited path finder
YAPF origin provider base class - used when origin is one tile / multiple trackdirs.
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
DiagDirection ReverseDiagDir(DiagDirection d)
Returns the reverse direction of the given DiagDirection.
DiagDirection
Enumeration for diagonal directions.
TrackStatus GetTileTrackStatus(TileIndex tile, TransportType mode, uint sub_mode, DiagDirection side)
Returns information about trackdirs and signal states.
static debug_inline uint TileY(TileIndex tile)
Get the Y component of a tile.
Definition map_func.h:425
static debug_inline uint TileX(TileIndex tile)
Get the X component of a tile.
Definition map_func.h:415
constexpr T abs(const T a)
Returns the absolute value of (scalar) variable.
Definition math_func.hpp:23
TileIndex CalcClosestStationTile(StationID station, TileIndex tile, StationType station_type)
Calculates the tile of given station that is closest to a given tile for this we assume the station i...
static const int YAPF_TILE_CORNER_LENGTH
Length (penalty) of a corner with YAPF.
static const int YAPF_TILE_LENGTH
Length (penalty) of one tile with YAPF.
uint32_t RandomRange(uint32_t limit, const std::source_location location=std::source_location::current())
Pick a random number between 0 and limit - 1, inclusive.
bool IsShipDestinationTile(TileIndex tile, StationID station)
Test if a tile is a docking tile for the given station.
Definition ship_cmd.cpp:647
WaterClass GetEffectiveWaterClass(TileIndex tile)
Determine the effective WaterClass for a ship travelling on a tile.
Definition ship_cmd.cpp:54
VehicleType type
Type of vehicle.
Config struct of YAPF for ships.
CYapfSegmentCostCacheNoneT< Types > PfCache
Segment cost cache provider.
CYapfShip_TypesT< Tpf_, Ttrack_follower, Tnode_list > Types
Shortcut for this struct type.
CYapfFollowShipT< Types > PfFollow
Node follower.
CYapfBaseT< Types > PfBase
Pathfinder components (modules).
CYapfOriginTileT< Types > PfOrigin
Origin provider.
Ttrack_follower TrackFollower
Track follower helper class.
CYapfDestinationTileWaterT< Types > PfDestination
Destination/distance provider.
Tpf_ Tpf
Pathfinder type.
CYapfCostShipT< Types > PfCost
Cost provider.
Node of the link graph.
Definition linkgraph.h:90
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
Information about a ship vehicle.
Definition engine_type.h:67
uint8_t ocean_speed_frac
Fraction of maximum speed for ocean tiles.
Definition engine_type.h:77
uint8_t canal_speed_frac
Fraction of maximum speed for canal/river tiles.
Definition engine_type.h:78
All ships have this type.
Definition ship.h:32
TrackBits state
The "track" the ship is following.
Definition ship.h:34
Trackdir GetVehicleTrackdir() const override
Returns the Trackdir on which the vehicle is currently located.
Definition ship_cmd.cpp:288
Vehicle data structure.
Direction direction
facing
Vehicle * first
NOSAVE: pointer to the first vehicle in the chain.
Order current_order
The current order (+ status, like: loading)
uint8_t vehstatus
Status.
TileIndex tile
Current tile index.
TileIndex dest_tile
Heading for this tile.
Describes a single interconnected patch of water within a particular water region.
Trackdir RemoveFirstTrackdir(TrackdirBits *trackdirs)
Removes first Trackdir from TrackdirBits and returns it.
Definition track_func.h:156
Track TrackdirToTrack(Trackdir trackdir)
Returns the Track that a given Trackdir represents.
Definition track_func.h:262
DiagDirection VehicleExitDir(Direction direction, TrackBits track)
Determine the side in which the vehicle will leave the tile.
Definition track_func.h:714
TrackdirBits TrackStatusToTrackdirBits(TrackStatus ts)
Returns the present-trackdir-information of a TrackStatus.
Definition track_func.h:352
Trackdir NextTrackdir(Trackdir trackdir)
Maps a trackdir to the trackdir that you will end up on if you go straight ahead.
Definition track_func.h:403
Trackdir ReverseTrackdir(Trackdir trackdir)
Maps a trackdir to the reverse trackdir.
Definition track_func.h:247
bool IsValidTrackdir(Trackdir trackdir)
Checks if a Trackdir is valid for non-road vehicles.
Definition track_func.h:52
Trackdir FindFirstTrackdir(TrackdirBits trackdirs)
Returns first Trackdir from TrackdirBits or INVALID_TRACKDIR.
Definition track_func.h:211
TrackdirBits TrackdirCrossesTrackdirs(Trackdir trackdir)
Maps a trackdir to all trackdirs that make 90 deg turns with it.
Definition track_func.h:606
TrackdirBits DiagdirReachesTrackdirs(DiagDirection diagdir)
Returns all trackdirs that can be reached when entering a tile from a given (diagonal) direction.
Definition track_func.h:555
bool IsDiagonalTrackdir(Trackdir trackdir)
Checks if a given Trackdir is diagonal.
Definition track_func.h:631
bool HasTrackdir(TrackdirBits trackdirs, Trackdir trackdir)
Checks whether a TrackdirBits has a given Trackdir.
Definition track_func.h:340
TrackdirBits TrackdirToTrackdirBits(Trackdir trackdir)
Maps a Trackdir to the corresponding TrackdirBits value.
Definition track_func.h:111
DiagDirection TrackdirToExitdir(Trackdir trackdir)
Maps a trackdir to the (4-way) direction the tile is exited when following that trackdir.
Definition track_func.h:439
Trackdir
Enumeration for tracks and directions.
Definition track_type.h:67
@ INVALID_TRACKDIR
Flag for an invalid trackdir.
Definition track_type.h:86
TrackdirBits
Allow incrementing of Trackdir variables.
Definition track_type.h:98
@ TRACKDIR_BIT_NONE
No track build.
Definition track_type.h:99
@ INVALID_TRACKDIR_BIT
Flag for an invalid trackdirbit value.
Definition track_type.h:114
Track
These are used to specify a single track.
Definition track_type.h:19
@ INVALID_TRACK
Flag for an invalid track.
Definition track_type.h:28
@ TRANSPORT_WATER
Transport over water.
bool HasVehicleOnPos(TileIndex tile, void *data, VehicleFromPosProc *proc)
Checks whether a vehicle is on a specific location.
Definition vehicle.cpp:520
@ VS_HIDDEN
Vehicle is not visible.
@ VEH_SHIP
Ship vehicle type.
@ WATER_CLASS_SEA
Sea.
Definition water_map.h:40
bool IsDockingTile(Tile t)
Checks whether the tile is marked as a dockling tile.
Definition water_map.h:371
WaterRegionDesc GetWaterRegionInfo(TileIndex tile)
Returns basic water region information for the provided tile.
WaterRegionPatchDesc GetWaterRegionPatchInfo(TileIndex tile)
Returns basic water region patch information for the provided tile.
TileIndex GetWaterRegionCenterTile(const WaterRegionDesc &water_region)
Returns the center tile of a particular water region.
Base includes/functions for YAPF.
Node tailored for ship pathfinding.
bool YapfShipCheckReverse(const Ship *v, Trackdir *trackdir)
Returns true if it is better to reverse the ship before leaving depot using YAPF.
Track YapfShipChooseTrack(const Ship *v, TileIndex tile, bool &path_found, ShipPathCache &path_cache)
Ship controller helper - path finder invoker.
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.