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