OpenTTD
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 "../../industry.h"
13 #include "../../vehicle_func.h"
14 
15 #include "yapf.hpp"
16 #include "yapf_node_ship.hpp"
17 
18 #include "../../safeguards.h"
19 
20 template <class Types>
22 {
23 public:
24  typedef typename Types::Tpf Tpf;
25  typedef typename Types::TrackFollower TrackFollower;
26  typedef typename Types::NodeList::Titem Node;
27  typedef typename Node::Key Key;
28 
29 protected:
30  TileIndex m_destTile;
31  TrackdirBits m_destTrackdirs;
32  StationID m_destStation;
33 
34 public:
35  void SetDestination(const Ship *v)
36  {
37  if (v->current_order.IsType(OT_GOTO_STATION)) {
38  m_destStation = v->current_order.GetDestination();
39  m_destTile = CalcClosestStationTile(m_destStation, v->tile, STATION_DOCK);
40  m_destTrackdirs = INVALID_TRACKDIR_BIT;
41  } else {
42  m_destStation = INVALID_STATION;
43  m_destTile = v->dest_tile;
45  }
46  }
47 
48 protected:
50  inline Tpf& Yapf()
51  {
52  return *static_cast<Tpf*>(this);
53  }
54 
55 public:
57  inline bool PfDetectDestination(Node& n)
58  {
59  return PfDetectDestinationTile(n.m_segment_last_tile, n.m_segment_last_td);
60  }
61 
62  inline bool PfDetectDestinationTile(TileIndex tile, Trackdir trackdir)
63  {
64  if (m_destStation != INVALID_STATION) {
65  return IsDockingTile(tile) && IsShipDestinationTile(tile, m_destStation);
66  }
67 
68  return tile == m_destTile && ((m_destTrackdirs & TrackdirToTrackdirBits(trackdir)) != TRACKDIR_BIT_NONE);
69  }
70 
75  inline bool PfCalcEstimate(Node& n)
76  {
77  static const int dg_dir_to_x_offs[] = {-1, 0, 1, 0};
78  static const int dg_dir_to_y_offs[] = {0, 1, 0, -1};
79  if (PfDetectDestination(n)) {
80  n.m_estimate = n.m_cost;
81  return true;
82  }
83 
84  TileIndex tile = n.m_segment_last_tile;
85  DiagDirection exitdir = TrackdirToExitdir(n.m_segment_last_td);
86  int x1 = 2 * TileX(tile) + dg_dir_to_x_offs[(int)exitdir];
87  int y1 = 2 * TileY(tile) + dg_dir_to_y_offs[(int)exitdir];
88  int x2 = 2 * TileX(m_destTile);
89  int y2 = 2 * TileY(m_destTile);
90  int dx = abs(x1 - x2);
91  int dy = abs(y1 - y2);
92  int dmin = min(dx, dy);
93  int dxy = abs(dx - dy);
94  int d = dmin * YAPF_TILE_CORNER_LENGTH + (dxy - 1) * (YAPF_TILE_LENGTH / 2);
95  n.m_estimate = n.m_cost + d;
96  assert(n.m_estimate >= n.m_parent->m_estimate);
97  return true;
98  }
99 };
100 
101 
103 template <class Types>
105 {
106 public:
107  typedef typename Types::Tpf Tpf;
108  typedef typename Types::TrackFollower TrackFollower;
109  typedef typename Types::NodeList::Titem Node;
110  typedef typename Node::Key Key;
111 
112 protected:
114  inline Tpf& Yapf()
115  {
116  return *static_cast<Tpf *>(this);
117  }
118 
119 public:
125  inline void PfFollowNode(Node &old_node)
126  {
127  TrackFollower F(Yapf().GetVehicle());
128  if (F.Follow(old_node.m_key.m_tile, old_node.m_key.m_td)) {
129  Yapf().AddMultipleNodes(&old_node, F);
130  }
131  }
132 
134  inline char TransportTypeChar() const
135  {
136  return 'w';
137  }
138 
139  static Trackdir ChooseShipTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found, ShipPathCache &path_cache)
140  {
141  /* handle special case - when next tile is destination tile */
142  if (tile == v->dest_tile) {
143  /* convert tracks to trackdirs */
144  TrackdirBits trackdirs = TrackBitsToTrackdirBits(tracks);
145  /* limit to trackdirs reachable from enterdir */
146  trackdirs &= DiagdirReachesTrackdirs(enterdir);
147 
148  /* use vehicle's current direction if that's possible, otherwise use first usable one. */
149  Trackdir veh_dir = v->GetVehicleTrackdir();
150  return (HasTrackdir(trackdirs, veh_dir)) ? veh_dir : (Trackdir)FindFirstBit2x64(trackdirs);
151  }
152 
153  /* move back to the old tile/trackdir (where ship is coming from) */
154  TileIndex src_tile = TileAddByDiagDir(tile, ReverseDiagDir(enterdir));
155  Trackdir trackdir = v->GetVehicleTrackdir();
156  assert(IsValidTrackdir(trackdir));
157 
158  /* convert origin trackdir to TrackdirBits */
159  TrackdirBits trackdirs = TrackdirToTrackdirBits(trackdir);
160 
161  /* create pathfinder instance */
162  Tpf pf;
163  /* set origin and destination nodes */
164  pf.SetOrigin(src_tile, trackdirs);
165  pf.SetDestination(v);
166  /* find best path */
167  path_found = pf.FindPath(v);
168 
169  Trackdir next_trackdir = INVALID_TRACKDIR; // this would mean "path not found"
170 
171  Node *pNode = pf.GetBestNode();
172  if (pNode != nullptr) {
173  uint steps = 0;
174  for (Node *n = pNode; n->m_parent != nullptr; n = n->m_parent) steps++;
175  uint skip = 0;
176  if (path_found) skip = YAPF_SHIP_PATH_CACHE_LENGTH / 2;
177 
178  /* walk through the path back to the origin */
179  Node *pPrevNode = nullptr;
180  while (pNode->m_parent != nullptr) {
181  steps--;
182  /* Skip tiles at end of path near destination. */
183  if (skip > 0) skip--;
184  if (skip == 0 && steps > 0 && steps < YAPF_SHIP_PATH_CACHE_LENGTH) {
185  path_cache.push_front(pNode->GetTrackdir());
186  }
187  pPrevNode = pNode;
188  pNode = pNode->m_parent;
189  }
190  /* return trackdir from the best next node (direct child of origin) */
191  Node &best_next_node = *pPrevNode;
192  assert(best_next_node.GetTile() == tile);
193  next_trackdir = best_next_node.GetTrackdir();
194  /* remove last element for the special case when tile == dest_tile */
195  if (path_found && !path_cache.empty()) path_cache.pop_back();
196  }
197  return next_trackdir;
198  }
199 
209  static bool CheckShipReverse(const Ship *v, TileIndex tile, Trackdir td1, Trackdir td2)
210  {
211  /* create pathfinder instance */
212  Tpf pf;
213  /* set origin and destination nodes */
214  pf.SetOrigin(tile, TrackdirToTrackdirBits(td1) | TrackdirToTrackdirBits(td2));
215  pf.SetDestination(v);
216  /* find best path */
217  if (!pf.FindPath(v)) return false;
218 
219  Node *pNode = pf.GetBestNode();
220  if (pNode == nullptr) return false;
221 
222  /* path was found
223  * walk through the path back to the origin */
224  while (pNode->m_parent != nullptr) {
225  pNode = pNode->m_parent;
226  }
227 
228  Trackdir best_trackdir = pNode->GetTrackdir();
229  assert(best_trackdir == td1 || best_trackdir == td2);
230  return best_trackdir == td2;
231  }
232 };
233 
235 template <class Types>
237 {
238 public:
239  typedef typename Types::Tpf Tpf;
240  typedef typename Types::TrackFollower TrackFollower;
241  typedef typename Types::NodeList::Titem Node;
242  typedef typename Node::Key Key;
243 
244 protected:
246  Tpf& Yapf()
247  {
248  return *static_cast<Tpf *>(this);
249  }
250 
251 public:
252  inline int CurveCost(Trackdir td1, Trackdir td2)
253  {
254  assert(IsValidTrackdir(td1));
255  assert(IsValidTrackdir(td2));
256 
257  if (HasTrackdir(TrackdirCrossesTrackdirs(td1), td2)) {
258  /* 90-deg curve penalty */
259  return Yapf().PfGetSettings().ship_curve90_penalty;
260  } else if (td2 != NextTrackdir(td1)) {
261  /* 45-deg curve penalty */
262  return Yapf().PfGetSettings().ship_curve45_penalty;
263  }
264  return 0;
265  }
266 
267  static Vehicle *CountShipProc(Vehicle *v, void *data)
268  {
269  uint *count = (uint *)data;
270  /* Ignore other vehicles (aircraft) and ships inside depot. */
271  if (v->type == VEH_SHIP && (v->vehstatus & VS_HIDDEN) == 0) (*count)++;
272 
273  return nullptr;
274  }
275 
281  inline bool PfCalcCost(Node &n, const TrackFollower *tf)
282  {
283  /* base tile cost depending on distance */
284  int c = IsDiagonalTrackdir(n.GetTrackdir()) ? YAPF_TILE_LENGTH : YAPF_TILE_CORNER_LENGTH;
285  /* additional penalty for curves */
286  c += CurveCost(n.m_parent->GetTrackdir(), n.GetTrackdir());
287 
288  if (IsDockingTile(n.GetTile())) {
289  /* Check docking tile for occupancy */
290  uint count = 1;
291  HasVehicleOnPos(n.GetTile(), &count, &CountShipProc);
292  c += count * 3 * YAPF_TILE_LENGTH;
293  }
294 
295  /* Skipped tile cost for aqueducts. */
296  c += YAPF_TILE_LENGTH * tf->m_tiles_skipped;
297 
298  /* Ocean/canal speed penalty. */
299  const ShipVehicleInfo *svi = ShipVehInfo(Yapf().GetVehicle()->engine_type);
300  byte speed_frac = (GetEffectiveWaterClass(n.GetTile()) == WATER_CLASS_SEA) ? svi->ocean_speed_frac : svi->canal_speed_frac;
301  if (speed_frac > 0) c += YAPF_TILE_LENGTH * (1 + tf->m_tiles_skipped) * speed_frac / (256 - speed_frac);
302 
303  /* apply it */
304  n.m_cost = n.m_parent->m_cost + c;
305  return true;
306  }
307 };
308 
313 template <class Tpf_, class Ttrack_follower, class Tnode_list>
315 {
318 
320  typedef Tpf_ Tpf;
322  typedef Ttrack_follower TrackFollower;
324  typedef Tnode_list NodeList;
325  typedef Ship VehicleType;
327  typedef CYapfBaseT<Types> PfBase; // base pathfinder class
328  typedef CYapfFollowShipT<Types> PfFollow; // node follower
329  typedef CYapfOriginTileT<Types> PfOrigin; // origin provider
330  typedef CYapfDestinationTileWaterT<Types> PfDestination; // destination/distance provider
331  typedef CYapfSegmentCostCacheNoneT<Types> PfCache; // segment cost cache provider
332  typedef CYapfCostShipT<Types> PfCost; // cost provider
333 };
334 
335 /* YAPF type 1 - uses TileIndex/Trackdir as Node key */
336 struct CYapfShip1 : CYapfT<CYapfShip_TypesT<CYapfShip1, CFollowTrackWater , CShipNodeListTrackDir> > {};
337 /* YAPF type 2 - uses TileIndex/DiagDirection as Node key */
338 struct CYapfShip2 : CYapfT<CYapfShip_TypesT<CYapfShip2, CFollowTrackWater , CShipNodeListExitDir > > {};
339 
340 static inline bool RequireTrackdirKey()
341 {
342  /* If the two curve penalties are not equal, then it is not possible to use the
343  * ExitDir keyed node list, as it there will be key overlap. Using Trackdir keyed
344  * nodes means potentially more paths are tested, which would be wasteful if it's
345  * not necessary.
346  */
348 }
349 
351 Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found, ShipPathCache &path_cache)
352 {
353  /* default is YAPF type 2 */
354  typedef Trackdir (*PfnChooseShipTrack)(const Ship*, TileIndex, DiagDirection, TrackBits, bool &path_found, ShipPathCache &path_cache);
355  PfnChooseShipTrack pfnChooseShipTrack = CYapfShip2::ChooseShipTrack; // default: ExitDir
356 
357  /* check if non-default YAPF type needed */
358  if (_settings_game.pf.yapf.disable_node_optimization || RequireTrackdirKey()) {
359  pfnChooseShipTrack = &CYapfShip1::ChooseShipTrack; // Trackdir
360  }
361 
362  Trackdir td_ret = pfnChooseShipTrack(v, tile, enterdir, tracks, path_found, path_cache);
363  return (td_ret != INVALID_TRACKDIR) ? TrackdirToTrack(td_ret) : INVALID_TRACK;
364 }
365 
367 {
368  Trackdir td = v->GetVehicleTrackdir();
369  Trackdir td_rev = ReverseTrackdir(td);
370  TileIndex tile = v->tile;
371 
372  typedef bool (*PfnCheckReverseShip)(const Ship*, TileIndex, Trackdir, Trackdir);
373  PfnCheckReverseShip pfnCheckReverseShip = CYapfShip2::CheckShipReverse; // default: ExitDir
374 
375  /* check if non-default YAPF type needed */
376  if (_settings_game.pf.yapf.disable_node_optimization || RequireTrackdirKey()) {
377  pfnCheckReverseShip = &CYapfShip1::CheckShipReverse; // Trackdir
378  }
379 
380  bool reverse = pfnCheckReverseShip(v, tile, td, td_rev);
381 
382  return reverse;
383 }
Information about a ship vehicle.
Definition: engine_type.h:65
bool HasVehicleOnPos(TileIndex tile, void *data, VehicleFromPosProc *proc)
Checks whether a vehicle is on a specific location.
Definition: vehicle.cpp:511
GameSettings _settings_game
Game settings of a running game or the scenario editor.
Definition: settings.cpp:79
TrackdirBits
Enumeration of bitmasks for the TrackDirs.
Definition: track_type.h:101
No track build.
Definition: track_type.h:102
Flag for an invalid track.
Definition: track_type.h:28
YAPF origin provider base class - used when origin is one tile / multiple trackdirs.
Definition: yapf_common.hpp:15
CYapfShip_TypesT< Tpf_, Ttrack_follower, Tnode_list > Types
Types - shortcut for this struct type.
Definition: yapf_ship.cpp:317
Ttrack_follower TrackFollower
track follower helper class
Definition: yapf_ship.cpp:322
byte ocean_speed_frac
Fraction of maximum speed for ocean tiles.
Definition: engine_type.h:74
static Track TrackdirToTrack(Trackdir trackdir)
Returns the Track that a given Trackdir represents.
Definition: track_func.h:270
char TransportTypeChar() const
return debug report character to identify the transportation type
Definition: yapf_ship.cpp:134
Trackdir
Enumeration for tracks and directions.
Definition: track_type.h:70
Ship vehicle type.
Definition: vehicle_type.h:26
VehicleType
Available vehicle types.
Definition: vehicle_type.h:21
TileIndex dest_tile
Heading for this tile.
Definition: vehicle_base.h:235
Transport over water.
CYapfSegmentCostCacheNoneT - the formal only yapf cost cache provider that implements PfNodeCacheFetc...
Tnode_list NodeList
node list type
Definition: yapf_ship.cpp:324
bool PfCalcEstimate(Node &n)
Called by YAPF to calculate cost estimate.
Definition: yapf_ship.cpp:75
static uint TileX(TileIndex tile)
Get the X component of a tile.
Definition: map_func.h:205
PathfinderSettings pf
settings for all pathfinders
static TileIndex TileAddByDiagDir(TileIndex tile, DiagDirection dir)
Adds a DiagDir to a tile.
Definition: map_func.h:382
Vehicle data structure.
Definition: vehicle_base.h:210
Node::Key Key
key to hash tables
Definition: yapf_ship.cpp:242
static 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:411
static const int YAPF_SHIP_PATH_CACHE_LENGTH
Maximum length of ship path cache.
static TrackdirBits DiagdirReachesTrackdirs(DiagDirection diagdir)
Returns all trackdirs that can be reached when entering a tile from a given (diagonal) direction...
Definition: track_func.h:563
byte vehstatus
Status.
Definition: vehicle_base.h:315
static DiagDirection TrackdirToExitdir(Trackdir trackdir)
Maps a trackdir to the (4-way) direction the tile is exited when following that trackdir.
Definition: track_func.h:447
Tpf & Yapf()
to access inherited path finder
Definition: yapf_ship.cpp:246
bool PfDetectDestination(Node &n)
Called by YAPF to detect if node ends in the desired destination.
Definition: yapf_ship.cpp:57
CYapfBaseT< Types > PfBase
pathfinder components (modules)
Definition: yapf_ship.cpp:327
Types::NodeList::Titem Node
this will be our node type
Definition: yapf_ship.cpp:241
Cost Provider module of YAPF for ships.
Definition: yapf_ship.cpp:236
static bool IsValidTrackdir(Trackdir trackdir)
Checks if a Trackdir is valid for non-road vehicles.
Definition: track_func.h:60
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
Definition: yapf_ship.cpp:239
CYapfBaseT - A-star type path finder base class.
Definition: yapf_base.hpp:49
Tpf & Yapf()
to access inherited path finder
Definition: yapf_ship.cpp:114
bool disable_node_optimization
whether to use exit-dir instead of trackdir in node key
Config struct of YAPF for ships.
Definition: yapf_ship.cpp:314
YAPFSettings yapf
pathfinder settings for the yet another pathfinder
static TrackdirBits TrackdirToTrackdirBits(Trackdir trackdir)
Maps a Trackdir to the corresponding TrackdirBits value.
Definition: track_func.h:119
bool IsType(OrderType type) const
Check whether this order is of the given type.
Definition: order_base.h:61
static DiagDirection ReverseDiagDir(DiagDirection d)
Returns the reverse direction of the given DiagDirection.
static bool HasTrackdir(TrackdirBits trackdirs, Trackdir trackdir)
Checks whether a TrackdirBits has a given Trackdir.
Definition: track_func.h:348
Node Follower module of YAPF for ships.
Definition: yapf_ship.cpp:104
Types::NodeList::Titem Node
this will be our node type
Definition: yapf_ship.cpp:26
Flag for an invalid trackdir.
Definition: track_type.h:89
static const int YAPF_TILE_LENGTH
Length (penalty) of one tile with YAPF.
YAPF template that uses Ttypes template argument to determine all YAPF components (base classes) from...
static bool IsDockingTile(TileIndex t)
Checks whether the tile is marked as a dockling tile.
Definition: water_map.h:365
Node::Key Key
key to hash tables
Definition: yapf_ship.cpp:27
TrackBits
Bitfield corresponding to Track.
Definition: track_type.h:38
TileIndex tile
Current tile index.
Definition: vehicle_base.h:228
uint32 ship_curve45_penalty
penalty for 45-deg curve for ships
static bool CheckShipReverse(const Ship *v, TileIndex tile, Trackdir td1, Trackdir td2)
Check whether a ship should reverse to reach its destination.
Definition: yapf_ship.cpp:209
bool IsShipDestinationTile(TileIndex tile, StationID station)
Test if a tile is a docking tile for the given station.
Definition: ship_cmd.cpp:605
static T min(const T a, const T b)
Returns the minimum of two values.
Definition: math_func.hpp:40
Tpf & Yapf()
to access inherited path finder
Definition: yapf_ship.cpp:50
All ships have this type.
Definition: ship.h:26
static 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 Trackdir ReverseTrackdir(Trackdir trackdir)
Maps a trackdir to the reverse trackdir.
Definition: track_func.h:255
TrackStatus GetTileTrackStatus(TileIndex tile, TransportType mode, uint sub_mode, DiagDirection side)
Returns information about trackdirs and signal states.
Definition: landscape.cpp:589
DestinationID GetDestination() const
Gets the destination of this order.
Definition: order_base.h:94
uint32 TileIndex
The index/ID of a Tile.
Definition: tile_type.h:78
Base includes/functions for YAPF.
Track
These are used to specify a single track.
Definition: track_type.h:19
static uint TileY(TileIndex tile)
Get the Y component of a tile.
Definition: map_func.h:215
static T abs(const T a)
Returns the absolute value of (scalar) variable.
Definition: math_func.hpp:81
Types::NodeList::Titem Node
this will be our node type
Definition: yapf_ship.cpp:109
static bool IsDiagonalTrackdir(Trackdir trackdir)
Checks if a given Trackdir is diagonal.
Definition: track_func.h:639
Trackdir GetVehicleTrackdir() const
Returns the Trackdir on which the vehicle is currently located.
Definition: ship_cmd.cpp:250
VehicleType type
Type of vehicle.
Definition: vehicle_type.h:52
static uint8 FindFirstBit2x64(const int value)
Finds the position of the first non-zero bit in an integer.
uint32 ship_curve90_penalty
penalty for 90-deg curve for ships
Vehicle is not visible.
Definition: vehicle_base.h:30
Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found, ShipPathCache &path_cache)
Ship controller helper - path finder invoker.
Definition: yapf_ship.cpp:351
DiagDirection
Enumeration for diagonal directions.
static TrackdirBits TrackBitsToTrackdirBits(TrackBits bits)
Converts TrackBits to TrackdirBits while allowing both directions.
Definition: track_func.h:327
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
Definition: yapf_ship.cpp:24
bool PfCalcCost(Node &n, const TrackFollower *tf)
Called by YAPF to calculate the cost from the origin to the given node.
Definition: yapf_ship.cpp:281
Tpf_ Tpf
Tpf - pathfinder type.
Definition: yapf_ship.cpp:320
static const int YAPF_TILE_CORNER_LENGTH
Length (penalty) of a corner with YAPF.
Flag for an invalid trackdirbit value.
Definition: track_type.h:117
WaterClass GetEffectiveWaterClass(TileIndex tile)
Determine the effective WaterClass for a ship travelling on a tile.
Definition: ship_cmd.cpp:47
Node::Key Key
key to hash tables
Definition: yapf_ship.cpp:110
static TrackdirBits TrackdirCrossesTrackdirs(Trackdir trackdir)
Maps a trackdir to all trackdirs that make 90 deg turns with it.
Definition: track_func.h:614
byte canal_speed_frac
Fraction of maximum speed for canal/river tiles.
Definition: engine_type.h:75
static TrackdirBits TrackStatusToTrackdirBits(TrackStatus ts)
Returns the present-trackdir-information of a TrackStatus.
Definition: track_func.h:360
void PfFollowNode(Node &old_node)
Called by YAPF to move from the given node to the next tile.
Definition: yapf_ship.cpp:125
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
Definition: yapf_ship.cpp:107
Order current_order
The current order (+ status, like: loading)
Definition: vehicle_base.h:316
bool YapfShipCheckReverse(const Ship *v)
Returns true if it is better to reverse the ship before leaving depot using YAPF. ...
Definition: yapf_ship.cpp:366
Node tailored for ship pathfinding.
static Track ChooseShipTrack(Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks)
Runs the pathfinder to choose a track to continue along.
Definition: ship_cmd.cpp:461