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