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 
15 #include "yapf.hpp"
16 #include "yapf_node_ship.hpp"
17 
18 #include "../../safeguards.h"
19 
21 template <class Types>
23 {
24 public:
25  typedef typename Types::Tpf Tpf;
26  typedef typename Types::TrackFollower TrackFollower;
27  typedef typename Types::NodeList::Titem Node;
28  typedef typename Node::Key Key;
29 
30 protected:
32  inline Tpf& Yapf()
33  {
34  return *static_cast<Tpf *>(this);
35  }
36 
37 public:
43  inline void PfFollowNode(Node &old_node)
44  {
45  TrackFollower F(Yapf().GetVehicle());
46  if (F.Follow(old_node.m_key.m_tile, old_node.m_key.m_td)) {
47  Yapf().AddMultipleNodes(&old_node, F);
48  }
49  }
50 
52  inline char TransportTypeChar() const
53  {
54  return 'w';
55  }
56 
57  static Trackdir ChooseShipTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found, ShipPathCache &path_cache)
58  {
59  /* handle special case - when next tile is destination tile */
60  if (tile == v->dest_tile) {
61  /* convert tracks to trackdirs */
62  TrackdirBits trackdirs = TrackBitsToTrackdirBits(tracks);
63  /* limit to trackdirs reachable from enterdir */
64  trackdirs &= DiagdirReachesTrackdirs(enterdir);
65 
66  /* use vehicle's current direction if that's possible, otherwise use first usable one. */
67  Trackdir veh_dir = v->GetVehicleTrackdir();
68  return (HasTrackdir(trackdirs, veh_dir)) ? veh_dir : (Trackdir)FindFirstBit2x64(trackdirs);
69  }
70 
71  /* move back to the old tile/trackdir (where ship is coming from) */
72  TileIndex src_tile = TileAddByDiagDir(tile, ReverseDiagDir(enterdir));
73  Trackdir trackdir = v->GetVehicleTrackdir();
74  assert(IsValidTrackdir(trackdir));
75 
76  /* convert origin trackdir to TrackdirBits */
77  TrackdirBits trackdirs = TrackdirToTrackdirBits(trackdir);
78  /* get available trackdirs on the destination tile */
80 
81  /* create pathfinder instance */
82  Tpf pf;
83  /* set origin and destination nodes */
84  pf.SetOrigin(src_tile, trackdirs);
85  pf.SetDestination(v->dest_tile, dest_trackdirs);
86  /* find best path */
87  path_found = pf.FindPath(v);
88 
89  Trackdir next_trackdir = INVALID_TRACKDIR; // this would mean "path not found"
90 
91  Node *pNode = pf.GetBestNode();
92  if (pNode != NULL) {
93  uint steps = 0;
94  for (Node *n = pNode; n->m_parent != NULL; n = n->m_parent) steps++;
95 
96  /* walk through the path back to the origin */
97  Node *pPrevNode = NULL;
98  while (pNode->m_parent != NULL) {
99  if (steps > 1 && --steps < YAPF_SHIP_PATH_CACHE_LENGTH) {
100  TrackdirByte td;
101  td = pNode->GetTrackdir();
102  path_cache.push_front(td);
103  }
104  pPrevNode = pNode;
105  pNode = pNode->m_parent;
106  }
107  /* return trackdir from the best next node (direct child of origin) */
108  Node &best_next_node = *pPrevNode;
109  assert(best_next_node.GetTile() == tile);
110  next_trackdir = best_next_node.GetTrackdir();
111  /* remove last element for the special case when tile == dest_tile */
112  if (path_found && !path_cache.empty()) path_cache.pop_back();
113  }
114  return next_trackdir;
115  }
116 
126  static bool CheckShipReverse(const Ship *v, TileIndex tile, Trackdir td1, Trackdir td2)
127  {
128  /* get available trackdirs on the destination tile */
130 
131  /* create pathfinder instance */
132  Tpf pf;
133  /* set origin and destination nodes */
134  pf.SetOrigin(tile, TrackdirToTrackdirBits(td1) | TrackdirToTrackdirBits(td2));
135  pf.SetDestination(v->dest_tile, dest_trackdirs);
136  /* find best path */
137  if (!pf.FindPath(v)) return false;
138 
139  Node *pNode = pf.GetBestNode();
140  if (pNode == NULL) return false;
141 
142  /* path was found
143  * walk through the path back to the origin */
144  while (pNode->m_parent != NULL) {
145  pNode = pNode->m_parent;
146  }
147 
148  Trackdir best_trackdir = pNode->GetTrackdir();
149  assert(best_trackdir == td1 || best_trackdir == td2);
150  return best_trackdir == td2;
151  }
152 };
153 
155 template <class Types>
157 {
158 public:
159  typedef typename Types::Tpf Tpf;
160  typedef typename Types::TrackFollower TrackFollower;
161  typedef typename Types::NodeList::Titem Node;
162  typedef typename Node::Key Key;
163 
164 protected:
166  Tpf& Yapf()
167  {
168  return *static_cast<Tpf *>(this);
169  }
170 
171 public:
177  inline bool PfCalcCost(Node &n, const TrackFollower *tf)
178  {
179  /* base tile cost depending on distance */
180  int c = IsDiagonalTrackdir(n.GetTrackdir()) ? YAPF_TILE_LENGTH : YAPF_TILE_CORNER_LENGTH;
181  /* additional penalty for curves */
182  if (n.GetTrackdir() != NextTrackdir(n.m_parent->GetTrackdir())) {
183  /* new trackdir does not match the next one when going straight */
184  c += YAPF_TILE_LENGTH;
185  }
186 
187  /* Skipped tile cost for aqueducts. */
188  c += YAPF_TILE_LENGTH * tf->m_tiles_skipped;
189 
190  /* Ocean/canal speed penalty. */
191  const ShipVehicleInfo *svi = ShipVehInfo(Yapf().GetVehicle()->engine_type);
192  byte speed_frac = (GetEffectiveWaterClass(n.GetTile()) == WATER_CLASS_SEA) ? svi->ocean_speed_frac : svi->canal_speed_frac;
193  if (speed_frac > 0) c += YAPF_TILE_LENGTH * (1 + tf->m_tiles_skipped) * speed_frac / (256 - speed_frac);
194 
195  /* apply it */
196  n.m_cost = n.m_parent->m_cost + c;
197  return true;
198  }
199 };
200 
205 template <class Tpf_, class Ttrack_follower, class Tnode_list>
207 {
210 
212  typedef Tpf_ Tpf;
214  typedef Ttrack_follower TrackFollower;
216  typedef Tnode_list NodeList;
217  typedef Ship VehicleType;
219  typedef CYapfBaseT<Types> PfBase; // base pathfinder class
220  typedef CYapfFollowShipT<Types> PfFollow; // node follower
221  typedef CYapfOriginTileT<Types> PfOrigin; // origin provider
222  typedef CYapfDestinationTileT<Types> PfDestination; // destination/distance provider
223  typedef CYapfSegmentCostCacheNoneT<Types> PfCache; // segment cost cache provider
224  typedef CYapfCostShipT<Types> PfCost; // cost provider
225 };
226 
227 /* YAPF type 1 - uses TileIndex/Trackdir as Node key, allows 90-deg turns */
228 struct CYapfShip1 : CYapfT<CYapfShip_TypesT<CYapfShip1, CFollowTrackWater , CShipNodeListTrackDir> > {};
229 /* YAPF type 2 - uses TileIndex/DiagDirection as Node key, allows 90-deg turns */
230 struct CYapfShip2 : CYapfT<CYapfShip_TypesT<CYapfShip2, CFollowTrackWater , CShipNodeListExitDir > > {};
231 /* YAPF type 3 - uses TileIndex/Trackdir as Node key, forbids 90-deg turns */
232 struct CYapfShip3 : CYapfT<CYapfShip_TypesT<CYapfShip3, CFollowTrackWaterNo90, CShipNodeListTrackDir> > {};
233 
235 Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found, ShipPathCache &path_cache)
236 {
237  /* default is YAPF type 2 */
238  typedef Trackdir (*PfnChooseShipTrack)(const Ship*, TileIndex, DiagDirection, TrackBits, bool &path_found, ShipPathCache &path_cache);
239  PfnChooseShipTrack pfnChooseShipTrack = CYapfShip2::ChooseShipTrack; // default: ExitDir, allow 90-deg
240 
241  /* check if non-default YAPF type needed */
243  pfnChooseShipTrack = &CYapfShip3::ChooseShipTrack; // Trackdir, forbid 90-deg
245  pfnChooseShipTrack = &CYapfShip1::ChooseShipTrack; // Trackdir, allow 90-deg
246  }
247 
248  Trackdir td_ret = pfnChooseShipTrack(v, tile, enterdir, tracks, path_found, path_cache);
249  return (td_ret != INVALID_TRACKDIR) ? TrackdirToTrack(td_ret) : INVALID_TRACK;
250 }
251 
253 {
254  Trackdir td = v->GetVehicleTrackdir();
255  Trackdir td_rev = ReverseTrackdir(td);
256  TileIndex tile = v->tile;
257 
258  typedef bool (*PfnCheckReverseShip)(const Ship*, TileIndex, Trackdir, Trackdir);
259  PfnCheckReverseShip pfnCheckReverseShip = CYapfShip2::CheckShipReverse; // default: ExitDir, allow 90-deg
260 
261  /* check if non-default YAPF type needed */
263  pfnCheckReverseShip = &CYapfShip3::CheckShipReverse; // Trackdir, forbid 90-deg
265  pfnCheckReverseShip = &CYapfShip1::CheckShipReverse; // Trackdir, allow 90-deg
266  }
267 
268  bool reverse = pfnCheckReverseShip(v, tile, td, td_rev);
269 
270  return reverse;
271 }
Information about a ship vehicle.
Definition: engine_type.h:66
GameSettings _settings_game
Game settings of a running game or the scenario editor.
Definition: settings.cpp:77
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:209
Ttrack_follower TrackFollower
track follower helper class
Definition: yapf_ship.cpp:214
byte ocean_speed_frac
Fraction of maximum speed for ocean tiles.
Definition: engine_type.h:75
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:52
Track
These are used to specify a single track.
Definition: track_type.h:21
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:216
PathfinderSettings pf
settings for all pathfinders
static TileIndex TileAddByDiagDir(TileIndex tile, DiagDirection dir)
Adds a DiagDir to a tile.
Definition: map_func.h:384
Node::Key Key
key to hash tables
Definition: yapf_ship.cpp:162
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
bool forbid_90_deg
forbid trains to make 90 deg turns
static const int YAPF_SHIP_PATH_CACHE_LENGTH
Maximum length of ship path cache.
YAPF destination provider base class - used when destination is single tile / multiple trackdirs...
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
Tpf & Yapf()
to access inherited path finder
Definition: yapf_ship.cpp:166
CYapfBaseT< Types > PfBase
pathfinder components (modules)
Definition: yapf_ship.cpp:219
Types::NodeList::Titem Node
this will be our node type
Definition: yapf_ship.cpp:161
TrackBits
Bitfield corresponding to Track.
Definition: track_type.h:41
Cost Provider module of YAPF for ships.
Definition: yapf_ship.cpp:156
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:159
CYapfBaseT - A-star type path finder base class.
Definition: yapf_base.hpp:51
Tpf & Yapf()
to access inherited path finder
Definition: yapf_ship.cpp:32
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:206
YAPFSettings yapf
pathfinder settings for the yet another pathfinder
VehicleType
Available vehicle types.
Definition: vehicle_type.h:23
static TrackdirBits TrackdirToTrackdirBits(Trackdir trackdir)
Maps a Trackdir to the corresponding TrackdirBits value.
Definition: track_func.h:121
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:22
static const int YAPF_TILE_LENGTH
Length (penalty) of one tile with YAPF.
Trackdir
Enumeration for tracks and directions.
Definition: track_type.h:74
YAPF template that uses Ttypes template argument to determine all YAPF components (base classes) from...
TileIndex tile
Current tile index.
Definition: vehicle_base.h:230
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:126
DiagDirection
Enumeration for diagonal directions.
All ships have this type.
Definition: ship.h:28
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
Flag for an invalid track.
Definition: track_type.h:30
uint32 TileIndex
The index/ID of a Tile.
Definition: tile_type.h:80
Base includes/functions for YAPF.
Types::NodeList::Titem Node
this will be our node type
Definition: yapf_ship.cpp:27
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
static uint8 FindFirstBit2x64(const int value)
Finds the position of the first non-zero bit in an integer.
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:235
TrackdirBits
Enumeration of bitmasks for the TrackDirs.
Definition: track_type.h:106
static TrackdirBits TrackBitsToTrackdirBits(TrackBits bits)
Converts TrackBits to TrackdirBits while allowing both directions.
Definition: track_func.h:329
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:177
Flag for an invalid trackdir.
Definition: track_type.h:93
Tpf_ Tpf
Tpf - pathfinder type.
Definition: yapf_ship.cpp:212
static const int YAPF_TILE_CORNER_LENGTH
Length (penalty) of a corner with YAPF.
WaterClass GetEffectiveWaterClass(TileIndex tile)
Determine the effective WaterClass for a ship travelling on a tile.
Definition: ship_cmd.cpp:48
Node::Key Key
key to hash tables
Definition: yapf_ship.cpp:28
byte canal_speed_frac
Fraction of maximum speed for canal/river tiles.
Definition: engine_type.h:76
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:43
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
Definition: yapf_ship.cpp:25
bool YapfShipCheckReverse(const Ship *v)
Returns true if it is better to reverse the ship before leaving depot using YAPF. ...
Definition: yapf_ship.cpp:252
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:466