src/pathfinder/yapf/yapf_ship.cpp

   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
  10 /** @file yapf_ship.cpp Implementation of YAPF for ships. */
  11
  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
  20 /** Node Follower module of YAPF for ships */
  21 template <class Types>
  22 class CYapfFollowShipT
  23 {
  24 public:
  25         typedef typename Types::Tpf Tpf;                     ///< the pathfinder class (derived from THIS class)
  26         typedef typename Types::TrackFollower TrackFollower;
  27         typedef typename Types::NodeList::Titem Node;        ///< this will be our node type
  28         typedef typename Node::Key Key;                      ///< key to hash tables
  29
  30 protected:
  31         /** to access inherited path finder */
  32         inline Tpf& Yapf()
  33         {
  34                 return *static_cast<Tpf *>(this);
  35         }
  36
  37 public:
  38         /**
  39          * Called by YAPF to move from the given node to the next tile. For each
  40          *  reachable trackdir on the new tile creates new node, initializes it
  41          *  and adds it to the open list by calling Yapf().AddNewNode(n)
  42          */
  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
  51         /** return debug report character to identify the transportation type */
  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)
  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 = (TrackdirBits)(tracks | ((int)tracks << 8));
  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 ((trackdirs & TrackdirToTrackdirBits(veh_dir)) != 0) ? veh_dir : (Trackdir)FindFirstBit2x64(trackdirs);
  69                 }
  70
  71                 /* move back to the old tile/trackdir (where ship is coming from) */
  72                 TileIndex src_tile = TILE_ADD(tile, TileOffsByDiagDir(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 */
  79                 TrackdirBits dest_trackdirs = TrackStatusToTrackdirBits(GetTileTrackStatus(v->dest_tile, TRANSPORT_WATER, 0));
  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                         /* walk through the path back to the origin */
  94                         Node *pPrevNode = NULL;
  95                         while (pNode->m_parent != NULL) {
  96                                 pPrevNode = pNode;
  97                                 pNode = pNode->m_parent;
  98                         }
  99                         /* return trackdir from the best next node (direct child of origin) */
 100                         Node &best_next_node = *pPrevNode;
 101                         assert(best_next_node.GetTile() == tile);
 102                         next_trackdir = best_next_node.GetTrackdir();
 103                 }
 104                 return next_trackdir;
 105         }
 106
 107         /**
 108          * Check whether a ship should reverse to reach its destination.
 109          * Called when leaving depot.
 110          * @param v Ship
 111          * @param tile Current position
 112          * @param td1 Forward direction
 113          * @param td2 Reverse direction
 114          * @return true if the reverse direction is better
 115          */
 116         static bool CheckShipReverse(const Ship *v, TileIndex tile, Trackdir td1, Trackdir td2)
 117         {
 118                 /* get available trackdirs on the destination tile */
 119                 TrackdirBits dest_trackdirs = TrackStatusToTrackdirBits(GetTileTrackStatus(v->dest_tile, TRANSPORT_WATER, 0));
 120
 121                 /* create pathfinder instance */
 122                 Tpf pf;
 123                 /* set origin and destination nodes */
 124                 pf.SetOrigin(tile, TrackdirToTrackdirBits(td1) | TrackdirToTrackdirBits(td2));
 125                 pf.SetDestination(v->dest_tile, dest_trackdirs);
 126                 /* find best path */
 127                 if (!pf.FindPath(v)) return false;
 128
 129                 Node *pNode = pf.GetBestNode();
 130                 if (pNode == NULL) return false;
 131
 132                 /* path was found
 133                  * walk through the path back to the origin */
 134                 while (pNode->m_parent != NULL) {
 135                         pNode = pNode->m_parent;
 136                 }
 137
 138                 Trackdir best_trackdir = pNode->GetTrackdir();
 139                 assert(best_trackdir == td1 || best_trackdir == td2);
 140                 return best_trackdir == td2;
 141         }
 142 };
 143
 144 /** Cost Provider module of YAPF for ships */
 145 template <class Types>
 146 class CYapfCostShipT
 147 {
 148 public:
 149         typedef typename Types::Tpf Tpf;              ///< the pathfinder class (derived from THIS class)
 150         typedef typename Types::TrackFollower TrackFollower;
 151         typedef typename Types::NodeList::Titem Node; ///< this will be our node type
 152         typedef typename Node::Key Key;               ///< key to hash tables
 153
 154 protected:
 155         /** to access inherited path finder */
 156         Tpf& Yapf()
 157         {
 158                 return *static_cast<Tpf *>(this);
 159         }
 160
 161 public:
 162         /**
 163          * Called by YAPF to calculate the cost from the origin to the given node.
 164          *  Calculates only the cost of given node, adds it to the parent node cost
 165          *  and stores the result into Node::m_cost member
 166          */
 167         inline bool PfCalcCost(Node &n, const TrackFollower *tf)
 168         {
 169                 /* base tile cost depending on distance */
 170                 int c = IsDiagonalTrackdir(n.GetTrackdir()) ? YAPF_TILE_LENGTH : YAPF_TILE_CORNER_LENGTH;
 171                 /* additional penalty for curves */
 172                 if (n.GetTrackdir() != NextTrackdir(n.m_parent->GetTrackdir())) {
 173                         /* new trackdir does not match the next one when going straight */
 174                         c += YAPF_TILE_LENGTH;
 175                 }
 176
 177                 /* Skipped tile cost for aqueducts. */
 178                 c += YAPF_TILE_LENGTH * tf->m_tiles_skipped;
 179
 180                 /* Ocean/canal speed penalty. */
 181                 const ShipVehicleInfo *svi = ShipVehInfo(Yapf().GetVehicle()->engine_type);
 182                 byte speed_frac = (GetEffectiveWaterClass(n.GetTile()) == WATER_CLASS_SEA) ? svi->ocean_speed_frac : svi->canal_speed_frac;
 183                 if (speed_frac > 0) c += YAPF_TILE_LENGTH * (1 + tf->m_tiles_skipped) * speed_frac / (256 - speed_frac);
 184
 185                 /* apply it */
 186                 n.m_cost = n.m_parent->m_cost + c;
 187                 return true;
 188         }
 189 };
 190
 191 /**
 192  * Config struct of YAPF for ships.
 193  *  Defines all 6 base YAPF modules as classes providing services for CYapfBaseT.
 194  */
 195 template <class Tpf_, class Ttrack_follower, class Tnode_list>
 196 struct CYapfShip_TypesT
 197 {
 198         /** Types - shortcut for this struct type */
 199         typedef CYapfShip_TypesT<Tpf_, Ttrack_follower, Tnode_list>  Types;
 200
 201         /** Tpf - pathfinder type */
 202         typedef Tpf_                              Tpf;
 203         /** track follower helper class */
 204         typedef Ttrack_follower                   TrackFollower;
 205         /** node list type */
 206         typedef Tnode_list                        NodeList;
 207         typedef Ship                              VehicleType;
 208         /** pathfinder components (modules) */
 209         typedef CYapfBaseT<Types>                 PfBase;        // base pathfinder class
 210         typedef CYapfFollowShipT<Types>           PfFollow;      // node follower
 211         typedef CYapfOriginTileT<Types>           PfOrigin;      // origin provider
 212         typedef CYapfDestinationTileT<Types>      PfDestination; // destination/distance provider
 213         typedef CYapfSegmentCostCacheNoneT<Types> PfCache;       // segment cost cache provider
 214         typedef CYapfCostShipT<Types>             PfCost;        // cost provider
 215 };
 216
 217 /* YAPF type 1 - uses TileIndex/Trackdir as Node key, allows 90-deg turns */
 218 struct CYapfShip1 : CYapfT<CYapfShip_TypesT<CYapfShip1, CFollowTrackWater    , CShipNodeListTrackDir> > {};
 219 /* YAPF type 2 - uses TileIndex/DiagDirection as Node key, allows 90-deg turns */
 220 struct CYapfShip2 : CYapfT<CYapfShip_TypesT<CYapfShip2, CFollowTrackWater    , CShipNodeListExitDir > > {};
 221 /* YAPF type 3 - uses TileIndex/Trackdir as Node key, forbids 90-deg turns */
 222 struct CYapfShip3 : CYapfT<CYapfShip_TypesT<CYapfShip3, CFollowTrackWaterNo90, CShipNodeListTrackDir> > {};
 223
 224 /** Ship controller helper - path finder invoker */
 225 Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found)
 226 {
 227         /* default is YAPF type 2 */
 228         typedef Trackdir (*PfnChooseShipTrack)(const Ship*, TileIndex, DiagDirection, TrackBits, bool &path_found);
 229         PfnChooseShipTrack pfnChooseShipTrack = CYapfShip2::ChooseShipTrack; // default: ExitDir, allow 90-deg
 230
 231         /* check if non-default YAPF type needed */
 232         if (_settings_game.pf.forbid_90_deg) {
 233                 pfnChooseShipTrack = &CYapfShip3::ChooseShipTrack; // Trackdir, forbid 90-deg
 234         } else if (_settings_game.pf.yapf.disable_node_optimization) {
 235                 pfnChooseShipTrack = &CYapfShip1::ChooseShipTrack; // Trackdir, allow 90-deg
 236         }
 237
 238         Trackdir td_ret = pfnChooseShipTrack(v, tile, enterdir, tracks, path_found);
 239         return (td_ret != INVALID_TRACKDIR) ? TrackdirToTrack(td_ret) : INVALID_TRACK;
 240 }
 241
 242 bool YapfShipCheckReverse(const Ship *v)
 243 {
 244         Trackdir td = v->GetVehicleTrackdir();
 245         Trackdir td_rev = ReverseTrackdir(td);
 246         TileIndex tile = v->tile;
 247
 248         typedef bool (*PfnCheckReverseShip)(const Ship*, TileIndex, Trackdir, Trackdir);
 249         PfnCheckReverseShip pfnCheckReverseShip = CYapfShip2::CheckShipReverse; // default: ExitDir, allow 90-deg
 250
 251         /* check if non-default YAPF type needed */
 252         if (_settings_game.pf.forbid_90_deg) {
 253                 pfnCheckReverseShip = &CYapfShip3::CheckShipReverse; // Trackdir, forbid 90-deg
 254         } else if (_settings_game.pf.yapf.disable_node_optimization) {
 255                 pfnCheckReverseShip = &CYapfShip1::CheckShipReverse; // Trackdir, allow 90-deg
 256         }
 257
 258         bool reverse = pfnCheckReverseShip(v, tile, td, td_rev);
 259
 260         return reverse;
 261 }