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 /** Node Follower module of YAPF for ships */
  19 template <class Types>
  20 class CYapfFollowShipT
  21 {
  22 public:
  23         typedef typename Types::Tpf Tpf;                     ///< the pathfinder class (derived from THIS class)
  24         typedef typename Types::TrackFollower TrackFollower;
  25         typedef typename Types::NodeList::Titem Node;        ///< this will be our node type
  26         typedef typename Node::Key Key;                      ///< key to hash tables
  27
  28 protected:
  29         /** to access inherited path finder */
  30         inline Tpf& Yapf()
  31         {
  32                 return *static_cast<Tpf*>(this);
  33         }
  34
  35 public:
  36         /**
  37          * Called by YAPF to move from the given node to the next tile. For each
  38          *  reachable trackdir on the new tile creates new node, initializes it
  39          *  and adds it to the open list by calling Yapf().AddNewNode(n)
  40          */
  41         inline void PfFollowNode(Node& old_node)
  42         {
  43                 TrackFollower F(Yapf().GetVehicle());
  44                 if (F.Follow(old_node.GetPos())) {
  45                         Yapf().AddMultipleNodes(&old_node, F);
  46                 }
  47         }
  48
  49         /** return debug report character to identify the transportation type */
  50         inline char TransportTypeChar() const
  51         {
  52                 return 'w';
  53         }
  54
  55         static Trackdir ChooseShipTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool &path_found)
  56         {
  57                 /* move back to the old tile/trackdir (where ship is coming from) */
  58                 PathPos pos = v->GetPos();
  59                 assert(pos.tile == TILE_ADD(tile, TileOffsByDiagDir(ReverseDiagDir(enterdir))));
  60                 assert(IsValidTrackdir(pos.td));
  61
  62                 /* handle special case - when next tile is destination tile */
  63                 if (tile == v->dest_tile) {
  64                         /* use vehicle's current direction if that's possible, otherwise use first usable one. */
  65                         Trackdir veh_dir = pos.td;
  66                         return ((trackdirs & TrackdirToTrackdirBits(veh_dir)) != 0) ? veh_dir : FindFirstTrackdir(trackdirs);
  67                 }
  68
  69                 /* create pathfinder instance */
  70                 Tpf pf;
  71                 /* set origin and destination nodes */
  72                 pf.SetOrigin(pos);
  73                 pf.SetDestination(v);
  74                 /* find best path */
  75                 path_found = pf.FindPath(v);
  76
  77                 Node *pNode = pf.GetBestNode();
  78                 if (pNode == NULL) return INVALID_TRACKDIR; // path not found
  79
  80                 /* walk through the path back to the origin */
  81                 Node *pPrevNode = NULL;
  82                 while (pNode->m_parent != NULL) {
  83                         pPrevNode = pNode;
  84                         pNode = pNode->m_parent;
  85                 }
  86
  87                 /* return trackdir from the best next node (direct child of origin) */
  88                 Node& best_next_node = *pPrevNode;
  89                 assert(best_next_node.GetPos().tile == tile);
  90                 return best_next_node.GetPos().td;
  91         }
  92
  93         /**
  94          * Check whether a ship should reverse to reach its destination.
  95          * Called when leaving depot.
  96          * @param v Ship
  97          * @param pos Current position
  98          * @return true if the reverse direction is better
  99          */
 100         static bool CheckShipReverse(const Ship *v, const PathPos &pos)
 101         {
 102                 /* create pathfinder instance */
 103                 Tpf pf;
 104                 /* set origin and destination nodes */
 105                 pf.SetOrigin(pos.tile, TrackdirToTrackdirBits(pos.td) | TrackdirToTrackdirBits(ReverseTrackdir(pos.td)));
 106                 pf.SetDestination(v);
 107                 /* find best path */
 108                 if (!pf.FindPath(v)) return false;
 109
 110                 Node *pNode = pf.GetBestNode();
 111                 if (pNode == NULL) return false;
 112
 113                 /* path was found
 114                  * walk through the path back to the origin */
 115                 while (pNode->m_parent != NULL) {
 116                         pNode = pNode->m_parent;
 117                 }
 118
 119                 Trackdir best_trackdir = pNode->GetPos().td;
 120                 assert(best_trackdir == pos.td || best_trackdir == ReverseTrackdir(pos.td));
 121                 return best_trackdir != pos.td;
 122         }
 123 };
 124
 125 /** Cost Provider module of YAPF for ships */
 126 template <class Types>
 127 class CYapfCostShipT
 128 {
 129 public:
 130         typedef typename Types::Tpf Tpf;              ///< the pathfinder class (derived from THIS class)
 131         typedef typename Types::TrackFollower TrackFollower;
 132         typedef typename Types::NodeList::Titem Node; ///< this will be our node type
 133         typedef typename Node::Key Key;               ///< key to hash tables
 134
 135 protected:
 136         /** to access inherited path finder */
 137         Tpf& Yapf()
 138         {
 139                 return *static_cast<Tpf*>(this);
 140         }
 141
 142 public:
 143         /**
 144          * Called by YAPF to calculate the cost from the origin to the given node.
 145          *  Calculates only the cost of given node, adds it to the parent node cost
 146          *  and stores the result into Node::m_cost member
 147          */
 148         inline bool PfCalcCost(Node& n, const TrackFollower *tf)
 149         {
 150                 /* base tile cost depending on distance */
 151                 int c = IsDiagonalTrackdir(n.GetPos().td) ? YAPF_TILE_LENGTH : YAPF_TILE_CORNER_LENGTH;
 152                 /* additional penalty for curves */
 153                 if (n.GetPos().td != NextTrackdir(n.m_parent->GetPos().td)) {
 154                         /* new trackdir does not match the next one when going straight */
 155                         c += YAPF_TILE_LENGTH;
 156                 }
 157
 158                 /* Skipped tile cost for aqueducts. */
 159                 c += YAPF_TILE_LENGTH * tf->m_tiles_skipped;
 160
 161                 /* Ocean/canal speed penalty. */
 162                 const ShipVehicleInfo *svi = ShipVehInfo(Yapf().GetVehicle()->engine_type);
 163                 byte speed_frac = (GetEffectiveWaterClass(n.GetPos().tile) == WATER_CLASS_SEA) ? svi->ocean_speed_frac : svi->canal_speed_frac;
 164                 if (speed_frac > 0) c += YAPF_TILE_LENGTH * (1 + tf->m_tiles_skipped) * speed_frac / (256 - speed_frac);
 165
 166                 /* apply it */
 167                 n.m_cost = n.m_parent->m_cost + c;
 168                 return true;
 169         }
 170 };
 171
 172 /** Destination Provider module of YAPF for ships */
 173 template <class Types>
 174 class CYapfDestinationShipT
 175 {
 176 public:
 177         typedef typename Types::Tpf Tpf;              ///< the pathfinder class (derived from THIS class)
 178         typedef typename Types::NodeList::Titem Node; ///< this will be our node type
 179         typedef typename Node::Key Key;               ///< key to hash tables
 180
 181 protected:
 182         Station *m_dest_station;
 183         TileIndex m_dest_tile;
 184
 185 public:
 186         /** set the destination tile */
 187         void SetDestination(const Ship *v)
 188         {
 189                 if (v->current_order.IsType(OT_GOTO_STATION)) {
 190                         m_dest_station = Station::Get(v->current_order.GetDestination());
 191                         m_dest_tile    = m_dest_station->GetClosestTile(v->tile, STATION_DOCK);
 192                 } else {
 193                         m_dest_station = NULL;
 194                         m_dest_tile    = v->dest_tile;
 195                 }
 196         }
 197
 198 protected:
 199         /** to access inherited path finder */
 200         Tpf& Yapf()
 201         {
 202                 return *static_cast<Tpf*>(this);
 203         }
 204
 205 public:
 206         inline bool PfDetectDestination(const PathPos &pos)
 207         {
 208                 if (pos.in_wormhole()) return false;
 209
 210                 if (m_dest_station == NULL) return pos.tile == m_dest_tile;
 211
 212                 return m_dest_station->IsDockingTile(pos.tile);
 213         }
 214
 215         /** Called by YAPF to detect if node ends in the desired destination */
 216         inline bool PfDetectDestination(Node& n)
 217         {
 218                 return PfDetectDestination(n.GetPos());
 219         }
 220
 221         /**
 222          * Called by YAPF to calculate cost estimate. Calculates distance to the destination
 223          *  adds it to the actual cost from origin and stores the sum to the Node::m_estimate
 224          */
 225         inline bool PfCalcEstimate(Node& n)
 226         {
 227                 static const int dg_dir_to_x_offs[] = {-1, 0, 1, 0};
 228                 static const int dg_dir_to_y_offs[] = {0, 1, 0, -1};
 229                 if (PfDetectDestination(n)) {
 230                         n.m_estimate = n.m_cost;
 231                         return true;
 232                 }
 233
 234                 TileIndex tile = n.GetPos().tile;
 235                 DiagDirection exitdir = TrackdirToExitdir(n.GetPos().td);
 236                 int x1 = 2 * TileX(tile) + dg_dir_to_x_offs[(int)exitdir];
 237                 int y1 = 2 * TileY(tile) + dg_dir_to_y_offs[(int)exitdir];
 238                 int x2 = 2 * TileX(m_dest_tile);
 239                 int y2 = 2 * TileY(m_dest_tile);
 240                 int dx = abs(x1 - x2);
 241                 int dy = abs(y1 - y2);
 242                 int dmin = min(dx, dy);
 243                 int dxy = abs(dx - dy);
 244                 int d = dmin * YAPF_TILE_CORNER_LENGTH + (dxy - 1) * (YAPF_TILE_LENGTH / 2);
 245                 n.m_estimate = n.m_cost + d;
 246                 assert(n.m_estimate >= n.m_parent->m_estimate);
 247                 return true;
 248         }
 249 };
 250
 251 /**
 252  * Config struct of YAPF for ships.
 253  *  Defines all 6 base YAPF modules as classes providing services for CYapfBaseT.
 254  */
 255 template <class Tpf_, class Ttrack_follower, class Tnode_list>
 256 struct CYapfShip_TypesT
 257 {
 258         /** Types - shortcut for this struct type */
 259         typedef CYapfShip_TypesT<Tpf_, Ttrack_follower, Tnode_list>  Types;
 260
 261         /** Tpf - pathfinder type */
 262         typedef Tpf_                              Tpf;
 263         /** track follower helper class */
 264         typedef Ttrack_follower                   TrackFollower;
 265         /** node list type */
 266         typedef Tnode_list                        NodeList;
 267         typedef Ship                              VehicleType;
 268         /** pathfinder components (modules) */
 269         typedef CYapfBaseT<Types>                 PfBase;        // base pathfinder class
 270         typedef CYapfFollowShipT<Types>           PfFollow;      // node follower
 271         typedef CYapfOriginTileT<Types>           PfOrigin;      // origin provider
 272         typedef CYapfDestinationShipT<Types>      PfDestination; // destination/distance provider
 273         typedef CYapfSegmentCostCacheNoneT<Types> PfCache;       // segment cost cache provider
 274         typedef CYapfCostShipT<Types>             PfCost;        // cost provider
 275 };
 276
 277 /* YAPF type 1 - uses TileIndex/Trackdir as Node key, allows 90-deg turns */
 278 struct CYapfShip1 : CYapfT<CYapfShip_TypesT<CYapfShip1, CFollowTrackWater90  , CShipNodeListTrackDir> > {};
 279 /* YAPF type 2 - uses TileIndex/DiagDirection as Node key, allows 90-deg turns */
 280 struct CYapfShip2 : CYapfT<CYapfShip_TypesT<CYapfShip2, CFollowTrackWater90  , CShipNodeListExitDir > > {};
 281 /* YAPF type 3 - uses TileIndex/Trackdir as Node key, forbids 90-deg turns */
 282 struct CYapfShip3 : CYapfT<CYapfShip_TypesT<CYapfShip3, CFollowTrackWaterNo90, CShipNodeListTrackDir> > {};
 283
 284 /** Ship controller helper - path finder invoker */
 285 Trackdir YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool &path_found)
 286 {
 287         /* default is YAPF type 2 */
 288         typedef Trackdir (*PfnChooseShipTrack)(const Ship*, TileIndex, DiagDirection, TrackdirBits, bool &path_found);
 289         PfnChooseShipTrack pfnChooseShipTrack = CYapfShip2::ChooseShipTrack; // default: ExitDir, allow 90-deg
 290
 291         /* check if non-default YAPF type needed */
 292         if (_settings_game.pf.forbid_90_deg) {
 293                 pfnChooseShipTrack = &CYapfShip3::ChooseShipTrack; // Trackdir, forbid 90-deg
 294         } else if (_settings_game.pf.yapf.disable_node_optimization) {
 295                 pfnChooseShipTrack = &CYapfShip1::ChooseShipTrack; // Trackdir, allow 90-deg
 296         }
 297
 298         return pfnChooseShipTrack(v, tile, enterdir, trackdirs, path_found);
 299 }
 300
 301 bool YapfShipCheckReverse(const Ship *v)
 302 {
 303         PathPos pos = v->GetPos();
 304
 305         typedef bool (*PfnCheckReverseShip)(const Ship*, const PathPos&);
 306         PfnCheckReverseShip pfnCheckReverseShip = CYapfShip2::CheckShipReverse; // default: ExitDir, allow 90-deg
 307
 308         /* check if non-default YAPF type needed */
 309         if (_settings_game.pf.forbid_90_deg) {
 310                 pfnCheckReverseShip = &CYapfShip3::CheckShipReverse; // Trackdir, forbid 90-deg
 311         } else if (_settings_game.pf.yapf.disable_node_optimization) {
 312                 pfnCheckReverseShip = &CYapfShip1::CheckShipReverse; // Trackdir, allow 90-deg
 313         }
 314
 315         bool reverse = pfnCheckReverseShip(v, pos);
 316
 317         return reverse;
 318 }