src/pathfinder/yapf/yapf_ship.cpp

   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
   8 /** @file yapf_ship.cpp Implementation of YAPF for ships. */
   9
  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>
  21 class CYapfDestinationTileWaterT
  22 {
  23 public:
  24         typedef typename Types::Tpf Tpf;                     ///< the pathfinder class (derived from THIS class)
  25         typedef typename Types::TrackFollower TrackFollower;
  26         typedef typename Types::NodeList::Titem Node;        ///< this will be our node type
  27         typedef typename Node::Key Key;                      ///< key to hash tables
  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;
  44                         m_destTrackdirs = TrackStatusToTrackdirBits(GetTileTrackStatus(v->dest_tile, TRANSPORT_WATER, 0));
  45                 }
  46         }
  47
  48 protected:
  49         /** to access inherited path finder */
  50         inline Tpf& Yapf()
  51         {
  52                 return *static_cast<Tpf*>(this);
  53         }
  54
  55 public:
  56         /** Called by YAPF to detect if node ends in the desired destination */
  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
  71         /**
  72          * Called by YAPF to calculate cost estimate. Calculates distance to the destination
  73          *  adds it to the actual cost from origin and stores the sum to the Node::m_estimate
  74          */
  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
 102 /** Node Follower module of YAPF for ships */
 103 template <class Types>
 104 class CYapfFollowShipT
 105 {
 106 public:
 107         typedef typename Types::Tpf Tpf;                     ///< the pathfinder class (derived from THIS class)
 108         typedef typename Types::TrackFollower TrackFollower;
 109         typedef typename Types::NodeList::Titem Node;        ///< this will be our node type
 110         typedef typename Node::Key Key;                      ///< key to hash tables
 111
 112 protected:
 113         /** to access inherited path finder */
 114         inline Tpf& Yapf()
 115         {
 116                 return *static_cast<Tpf *>(this);
 117         }
 118
 119 public:
 120         /**
 121          * Called by YAPF to move from the given node to the next tile. For each
 122          *  reachable trackdir on the new tile creates new node, initializes it
 123          *  and adds it to the open list by calling Yapf().AddNewNode(n)
 124          */
 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
 133         /** return debug report character to identify the transportation type */
 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
 200         /**
 201          * Check whether a ship should reverse to reach its destination.
 202          * Called when leaving depot.
 203          * @param v Ship
 204          * @param tile Current position
 205          * @param td1 Forward direction
 206          * @param td2 Reverse direction
 207          * @return true if the reverse direction is better
 208          */
 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
 234 /** Cost Provider module of YAPF for ships */
 235 template <class Types>
 236 class CYapfCostShipT
 237 {
 238 public:
 239         typedef typename Types::Tpf Tpf;              ///< the pathfinder class (derived from THIS class)
 240         typedef typename Types::TrackFollower TrackFollower;
 241         typedef typename Types::NodeList::Titem Node; ///< this will be our node type
 242         typedef typename Node::Key Key;               ///< key to hash tables
 243
 244 protected:
 245         /** to access inherited path finder */
 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
 276         /**
 277          * Called by YAPF to calculate the cost from the origin to the given node.
 278          *  Calculates only the cost of given node, adds it to the parent node cost
 279          *  and stores the result into Node::m_cost member
 280          */
 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
 309 /**
 310  * Config struct of YAPF for ships.
 311  *  Defines all 6 base YAPF modules as classes providing services for CYapfBaseT.
 312  */
 313 template <class Tpf_, class Ttrack_follower, class Tnode_list>
 314 struct CYapfShip_TypesT
 315 {
 316         /** Types - shortcut for this struct type */
 317         typedef CYapfShip_TypesT<Tpf_, Ttrack_follower, Tnode_list>  Types;
 318
 319         /** Tpf - pathfinder type */
 320         typedef Tpf_                              Tpf;
 321         /** track follower helper class */
 322         typedef Ttrack_follower                   TrackFollower;
 323         /** node list type */
 324         typedef Tnode_list                        NodeList;
 325         typedef Ship                              VehicleType;
 326         /** pathfinder components (modules) */
 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          */
 347         return _settings_game.pf.yapf.ship_curve45_penalty != _settings_game.pf.yapf.ship_curve90_penalty;
 348 }
 349
 350 /** Ship controller helper - path finder invoker */
 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
 366 bool YapfShipCheckReverse(const Ship *v)
 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 }