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
  17 /** Yapf Node for ships */
  18 template <class Tkey_>
  19 struct CYapfShipNodeT : CYapfNodeT<Tkey_, CYapfShipNodeT<Tkey_> > {
  20         CYapfShipNodeT (const CYapfShipNodeT *parent, const ShipPathPos &pos)
  21                 : CYapfNodeT<Tkey_, CYapfShipNodeT<Tkey_> > (parent, pos)
  22         {
  23         }
  24 };
  25
  26 /* now define two major node types (that differ by key type) */
  27 typedef CYapfShipNodeT<CYapfNodeKeyExitDir <ShipPathPos> > CYapfShipNodeExitDir;
  28 typedef CYapfShipNodeT<CYapfNodeKeyTrackDir<ShipPathPos> > CYapfShipNodeTrackDir;
  29
  30 /* Default Astar types */
  31 typedef Astar<CYapfShipNodeExitDir , 10, 12> AstarShipExitDir;
  32 typedef Astar<CYapfShipNodeTrackDir, 10, 12> AstarShipTrackDir;
  33
  34
  35 /** YAPF class for ships */
  36 template <class TAstar>
  37 class CYapfShipT : public TAstar {
  38 public:
  39         typedef typename TAstar::Node Node; ///< this will be our node type
  40
  41 protected:
  42         const Ship         *const m_veh;      ///< vehicle that we are trying to drive
  43         const Station      *const m_dest_station; ///< destination station, or NULL if target is not a station
  44         const TileIndex           m_dest_tile;    ///< destination tile, or the special marker INVALID_TILE to search for any depot
  45         const ShipVehicleInfo *const svi;         ///< ship vehicle info
  46         const bool                m_allow_90deg;  ///< whether to allow 90-degree turns
  47
  48         CYapfShipT (const Ship *ship, bool allow_90deg, bool depot = false)
  49                 : m_veh(ship)
  50                 , m_dest_station (!depot && ship->current_order.IsType(OT_GOTO_STATION) ? Station::Get(ship->current_order.GetDestination()) : NULL)
  51                 , m_dest_tile    (depot ? INVALID_TILE :
  52                                 ship->current_order.IsType (OT_GOTO_STATION) ?
  53                                         m_dest_station->GetClosestTile (ship->tile, m_dest_station->dock_area) :
  54                                 ship->dest_tile)
  55                 , svi(ShipVehInfo(ship->engine_type))
  56                 , m_allow_90deg(allow_90deg)
  57         {
  58         }
  59
  60 public:
  61         /** Called by the A-star underlying class to find the neighbours of a node. */
  62         inline void Follow (const Node *old_node)
  63         {
  64                 const ShipPathPos &old_pos = old_node->GetPos();
  65                 DiagDirection exitdir = TrackdirToExitdir (old_pos.td);
  66
  67                 assert((GetTileWaterwayStatus(old_pos.tile) & TrackdirToTrackdirBits(old_pos.td)) != 0);
  68
  69                 PathMPos<ShipPathPos> new_pos;
  70                 int tiles_skipped;
  71                 if (IsAqueductTile(old_pos.tile) && exitdir == GetTunnelBridgeDirection(old_pos.tile)) {
  72                         /* we are entering the aqueduct */
  73                         TileIndex other_end = GetOtherBridgeEnd (old_pos.tile);
  74                         tiles_skipped = GetTunnelBridgeLength (old_pos.tile, other_end);
  75                         new_pos.set (other_end, DiagDirToDiagTrackdir (exitdir));
  76                 } else {
  77                         /* normal tile, do one step */
  78                         new_pos.set_tile (TileAddByDiagDir (old_pos.tile, exitdir));
  79                         tiles_skipped = 0;
  80
  81                         if (IsAqueductTile (new_pos.tile)) {
  82                                 /* aqueducts can be entered only from proper direction */
  83                                 if (GetTunnelBridgeDirection (new_pos.tile) != exitdir) {
  84                                         return;
  85                                 }
  86
  87                                 new_pos.set_trackdir (DiagDirToDiagTrackdir (exitdir));
  88                         } else {
  89                                 TrackdirBits trackdirs = GetTileWaterwayStatus(new_pos.tile) & DiagdirReachesTrackdirs(exitdir);
  90                                 if (trackdirs == TRACKDIR_BIT_NONE) return;
  91
  92                                 if (!m_allow_90deg) {
  93                                         trackdirs &= (TrackdirBits)~(int)TrackdirCrossesTrackdirs(old_pos.td);
  94                                         if (trackdirs == TRACKDIR_BIT_NONE) return;
  95                                 }
  96
  97                                 new_pos.set_trackdirs (trackdirs);
  98                         }
  99                 }
 100
 101                 /* precompute trackdir-independent costs */
 102                 int cc = old_node->m_cost + YAPF_TILE_LENGTH * tiles_skipped;
 103
 104                 /* Ocean/canal speed penalty. */
 105                 byte speed_frac = (GetEffectiveWaterClass(new_pos.tile) == WATER_CLASS_SEA) ? svi->ocean_speed_frac : svi->canal_speed_frac;
 106                 if (speed_frac > 0) cc += YAPF_TILE_LENGTH * (1 + tiles_skipped) * speed_frac / (256 - speed_frac);
 107
 108                 /* detect destination */
 109                 TileIndex new_tile = new_pos.tile;
 110                 bool is_target = (m_dest_station != NULL) ? m_dest_station->IsDockingTile (new_tile) :
 111                                 (m_dest_tile != INVALID_TILE) ? (new_tile == m_dest_tile) :
 112                                 IsShipDepotTile (new_tile) && IsTileOwner (new_tile, m_veh->owner);
 113
 114                 for (TrackdirBits rtds = new_pos.trackdirs; rtds != TRACKDIR_BIT_NONE; rtds = KillFirstBit(rtds)) {
 115                         Trackdir td = FindFirstTrackdir (rtds);
 116
 117                         /* base tile cost depending on distance */
 118                         int c = IsDiagonalTrackdir(td) ? YAPF_TILE_LENGTH : YAPF_TILE_CORNER_LENGTH;
 119                         /* additional penalty for curves */
 120                         if (td != NextTrackdir (old_node->GetPos().td)) {
 121                                 /* new trackdir does not match the next one when going straight */
 122                                 c += YAPF_TILE_LENGTH;
 123                         }
 124
 125                         /* create the node */
 126                         Node n (old_node, ShipPathPos (new_tile, td));
 127                         n.m_cost = cc + c;
 128
 129                         /* compute estimated cost */
 130                         if (is_target) {
 131                                 n.m_estimate = n.m_cost;
 132                                 TAstar::InsertTarget (n);
 133                         } else {
 134                                 if (m_dest_tile == INVALID_TILE) {
 135                                         n.m_estimate = n.m_cost;
 136                                 } else {
 137                                         n.m_estimate = n.m_cost + YapfCalcEstimate (n.GetPos(), m_dest_tile);
 138                                         assert (n.m_estimate >= n.m_parent->m_estimate);
 139                                 }
 140
 141                                 TAstar::InsertNode(n);
 142                         }
 143                 }
 144         }
 145
 146
 147         /** Call the node follower */
 148         static inline void Follow (CYapfShipT *pf, const Node *n)
 149         {
 150                 pf->Follow(n);
 151         }
 152
 153         /** Invoke the underlying pathfinder. */
 154         inline bool FindPath (void)
 155         {
 156 #ifndef NO_DEBUG_MESSAGES
 157                 CPerformanceTimer perf;
 158                 perf.Start();
 159 #endif /* !NO_DEBUG_MESSAGES */
 160
 161                 bool bDestFound = TAstar::FindPath (Follow, _settings_game.pf.yapf.max_search_nodes);
 162
 163 #ifndef NO_DEBUG_MESSAGES
 164                 perf.Stop();
 165                 if (_debug_yapf_level >= 2) {
 166                         int t = perf.Get(1000000);
 167                         _total_pf_time_us += t;
 168
 169                         if (_debug_yapf_level >= 3) {
 170                                 int cost = bDestFound ? TAstar::best->m_cost : -1;
 171                                 int dist = bDestFound ? TAstar::best->m_estimate - TAstar::best->m_cost : -1;
 172
 173                                 DEBUG(yapf, 3, "[YAPFw]%c%4d- %d us - %d rounds - %d open - %d closed - CHR  0.0%% - C %d D %d - c0(sc0, ts0, o0) -- ",
 174                                         bDestFound ? '-' : '!', m_veh->unitnumber, t, TAstar::num_steps, TAstar::OpenCount(), TAstar::ClosedCount(),
 175                                         cost, dist
 176                                 );
 177                         }
 178                 }
 179 #endif /* !NO_DEBUG_MESSAGES */
 180                 return bDestFound;
 181         }
 182 };
 183
 184 /* Template proxy */
 185 template <class TAstar, bool allow_90deg>
 186 struct CYapfShip : CYapfShipT<TAstar> {
 187         CYapfShip (const Ship *ship, bool depot = false)
 188                 : CYapfShipT<TAstar> (ship, allow_90deg, depot)
 189         {
 190         }
 191 };
 192
 193 /* YAPF type 1 - uses TileIndex/Trackdir as Node key, allows 90-deg turns */
 194 typedef CYapfShip <AstarShipTrackDir, true>  CYapfShip1;
 195
 196 /* YAPF type 2 - uses TileIndex/DiagDirection as Node key, allows 90-deg turns */
 197 typedef CYapfShip <AstarShipExitDir,  true>  CYapfShip2;
 198
 199 /* YAPF type 3 - uses TileIndex/Trackdir as Node key, forbids 90-deg turns */
 200 typedef CYapfShip <AstarShipTrackDir, false> CYapfShip3;
 201
 202
 203 template <class Tpf>
 204 static Trackdir ChooseShipTrack(const Ship *v, const ShipPathPos &pos, TrackdirBits trackdirs, bool &path_found)
 205 {
 206         /* create pathfinder instance */
 207         Tpf pf (v);
 208         /* set origin node */
 209         pf.InsertInitialNode (typename Tpf::Node (NULL, pos));
 210         /* find best path */
 211         path_found = pf.FindPath();
 212
 213         const typename Tpf::Node *n = pf.GetBestNode();
 214         if (n == NULL) return INVALID_TRACKDIR; // path not found
 215         assert (n->m_parent != NULL);
 216
 217         /* walk through the path back to the origin */
 218         while (n->m_parent->m_parent != NULL) {
 219                 n = n->m_parent;
 220         }
 221
 222         /* return trackdir from the best next node (direct child of origin) */
 223         assert(n->m_parent->GetPos().tile == pos.tile);
 224         return n->GetPos().td;
 225 }
 226
 227 /** Ship controller helper - path finder invoker */
 228 Trackdir YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool &path_found)
 229 {
 230         /* move back to the old tile/trackdir (where ship is coming from) */
 231         ShipPathPos pos = v->GetPos();
 232         assert(pos.tile == TileAddByDiagDir (tile, ReverseDiagDir(enterdir)));
 233         assert(IsValidTrackdir(pos.td));
 234
 235         /* handle special case - when next tile is destination tile */
 236         if (v->current_order.IsType(OT_GOTO_STATION) ?
 237                         Station::Get(v->current_order.GetDestination())->IsDockingTile(tile) :
 238                         tile == v->dest_tile) {
 239                 /* use vehicle's current direction if that's possible, otherwise use first usable one. */
 240                 Trackdir veh_dir = pos.td;
 241                 return ((trackdirs & TrackdirToTrackdirBits(veh_dir)) != 0) ? veh_dir : FindFirstTrackdir(trackdirs);
 242         }
 243
 244         /* default is YAPF type 2 */
 245         typedef Trackdir (*PfnChooseShipTrack)(const Ship*, const ShipPathPos&, TrackdirBits, bool &path_found);
 246         PfnChooseShipTrack pfnChooseShipTrack = ChooseShipTrack<CYapfShip2>; // default: ExitDir, allow 90-deg
 247
 248         /* check if non-default YAPF type needed */
 249         if (_settings_game.pf.forbid_90_deg) {
 250                 pfnChooseShipTrack = &ChooseShipTrack<CYapfShip3>; // Trackdir, forbid 90-deg
 251         } else if (_settings_game.pf.yapf.disable_node_optimization) {
 252                 pfnChooseShipTrack = &ChooseShipTrack<CYapfShip1>; // Trackdir, allow 90-deg
 253         }
 254
 255         return pfnChooseShipTrack(v, pos, trackdirs, path_found);
 256 }
 257
 258
 259 /**
 260  * Check whether a ship should reverse to reach its destination.
 261  * Called when leaving depot.
 262  * @param v Ship
 263  * @param pos Current position
 264  * @return true if the reverse direction is better
 265  */
 266 template <class Tpf>
 267 static bool CheckShipReverse(const Ship *v, const ShipPathPos &pos)
 268 {
 269         /* create pathfinder instance */
 270         Tpf pf (v);
 271         /* set origin nodes */
 272         pf.InsertInitialNode (typename Tpf::Node (NULL, pos));
 273         pf.InsertInitialNode (typename Tpf::Node (NULL,
 274                         ShipPathPos (pos.tile, ReverseTrackdir (pos.td))));
 275         /* find best path */
 276         if (!pf.FindPath()) return false;
 277
 278         const typename Tpf::Node *n = pf.GetBestNode();
 279         if (n == NULL) return false;
 280
 281         /* path was found; walk through the path back to the origin */
 282         while (n->m_parent != NULL) {
 283                 n = n->m_parent;
 284         }
 285
 286         Trackdir best_trackdir = n->GetPos().td;
 287         assert(best_trackdir == pos.td || best_trackdir == ReverseTrackdir(pos.td));
 288         return best_trackdir != pos.td;
 289 }
 290
 291 bool YapfShipCheckReverse(const Ship *v)
 292 {
 293         ShipPathPos pos = v->GetPos();
 294
 295         typedef bool (*PfnCheckReverseShip)(const Ship*, const ShipPathPos&);
 296         PfnCheckReverseShip pfnCheckReverseShip = CheckShipReverse<CYapfShip2>; // default: ExitDir, allow 90-deg
 297
 298         /* check if non-default YAPF type needed */
 299         if (_settings_game.pf.forbid_90_deg) {
 300                 pfnCheckReverseShip = &CheckShipReverse<CYapfShip3>; // Trackdir, forbid 90-deg
 301         } else if (_settings_game.pf.yapf.disable_node_optimization) {
 302                 pfnCheckReverseShip = &CheckShipReverse<CYapfShip1>; // Trackdir, allow 90-deg
 303         }
 304
 305         bool reverse = pfnCheckReverseShip(v, pos);
 306
 307         return reverse;
 308 }
 309
 310
 311 /**
 312  * Find the nearest depot to a ship
 313  * @param v ship
 314  * @param max_distance maximum allowed distance, or 0 for any distance
 315  * @return the tile of the nearest depot
 316  */
 317 template <class Tpf>
 318 static TileIndex FindNearestDepot (const Ship *v, uint max_distance)
 319 {
 320         Tpf pf (v, true);
 321         pf.InsertInitialNode (typename Tpf::Node (NULL, v->GetPos()));
 322         if (!pf.FindPath()) return INVALID_TILE;
 323
 324         /* some path found; get found depot tile */
 325         const typename Tpf::Node *n = pf.GetBestNode();
 326         if (max_distance > 0 && n->m_cost > 0 && (uint)n->m_cost > max_distance) return INVALID_TILE;
 327         return n->GetPos().tile;
 328 }
 329
 330 TileIndex YapfShipFindNearestDepot (const Ship *v, uint max_distance)
 331 {
 332         if (_settings_game.pf.forbid_90_deg) {
 333                 return FindNearestDepot<CYapfShip3> (v, max_distance);
 334         } else if (_settings_game.pf.yapf.disable_node_optimization) {
 335                 return FindNearestDepot<CYapfShip1> (v, max_distance);
 336         } else {
 337                 return FindNearestDepot<CYapfShip2> (v, max_distance);
 338         }
 339 }