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
  20         : CYapfNodeT<Tkey_, CYapfShipNodeT<Tkey_> >
  21 {
  22 };
  23
  24 /* now define two major node types (that differ by key type) */
  25 typedef CYapfShipNodeT<CYapfNodeKeyExitDir <ShipPathPos> > CYapfShipNodeExitDir;
  26 typedef CYapfShipNodeT<CYapfNodeKeyTrackDir<ShipPathPos> > CYapfShipNodeTrackDir;
  27
  28 /* Default Astar types */
  29 typedef Astar<CYapfShipNodeExitDir , 10, 12> AstarShipExitDir;
  30 typedef Astar<CYapfShipNodeTrackDir, 10, 12> AstarShipTrackDir;
  31
  32
  33 /** YAPF class for ships */
  34 template <class TAstar>
  35 class CYapfShipT : public TAstar
  36 {
  37 public:
  38         typedef typename TAstar::Node Node; ///< this will be our node type
  39
  40 protected:
  41         const YAPFSettings *const m_settings; ///< current settings (_settings_game.yapf)
  42         const Ship         *const m_veh;      ///< vehicle that we are trying to drive
  43         const Station      *const m_dest_station; ///< destination station, or NULL
  44         const TileIndex           m_dest_tile;    ///< destination tile
  45         CFollowTrackWater         tf;             ///< track follower
  46         const ShipVehicleInfo *const svi;         ///< ship vehicle info
  47
  48         CYapfShipT (const Ship *ship, bool allow_90deg)
  49                 : m_settings(&_settings_game.pf.yapf)
  50                 , m_veh(ship)
  51                 , m_dest_station (ship->current_order.IsType(OT_GOTO_STATION) ? Station::Get(ship->current_order.GetDestination()) : NULL)
  52                 , m_dest_tile    (ship->current_order.IsType(OT_GOTO_STATION) ? m_dest_station->GetClosestTile(ship->tile, STATION_DOCK) : ship->dest_tile)
  53                 , tf(allow_90deg)
  54                 , svi(ShipVehInfo(ship->engine_type))
  55         {
  56         }
  57
  58 public:
  59         /** Called by the A-star underlying class to find the neighbours of a node. */
  60         inline void Follow (Node *old_node)
  61         {
  62                 if (!tf.Follow(old_node->GetPos())) return;
  63
  64                 /* precompute trackdir-independent costs */
  65                 int cc = old_node->m_cost + YAPF_TILE_LENGTH * tf.m_tiles_skipped;
  66
  67                 /* Ocean/canal speed penalty. */
  68                 byte speed_frac = (GetEffectiveWaterClass(tf.m_new.tile) == WATER_CLASS_SEA) ? svi->ocean_speed_frac : svi->canal_speed_frac;
  69                 if (speed_frac > 0) cc += YAPF_TILE_LENGTH * (1 + tf.m_tiles_skipped) * speed_frac / (256 - speed_frac);
  70
  71                 /* the ship track follower does not step into wormholes */
  72                 assert (!tf.m_new.in_wormhole());
  73
  74                 /* detect destination */
  75                 bool is_target = (m_dest_station == NULL) ? (tf.m_new.tile == m_dest_tile) : m_dest_station->IsDockingTile(tf.m_new.tile);
  76
  77                 ShipPathPos pos = tf.m_new;
  78                 for (TrackdirBits rtds = tf.m_new.trackdirs; rtds != TRACKDIR_BIT_NONE; rtds = KillFirstBit(rtds)) {
  79                         pos.set_trackdir (FindFirstTrackdir(rtds));
  80                         Node *n = TAstar::CreateNewNode(old_node, pos);
  81
  82                         /* base tile cost depending on distance */
  83                         int c = IsDiagonalTrackdir(n->GetPos().td) ? YAPF_TILE_LENGTH : YAPF_TILE_CORNER_LENGTH;
  84                         /* additional penalty for curves */
  85                         if (n->GetPos().td != NextTrackdir(n->m_parent->GetPos().td)) {
  86                                 /* new trackdir does not match the next one when going straight */
  87                                 c += YAPF_TILE_LENGTH;
  88                         }
  89
  90                         /* apply it */
  91                         n->m_cost = cc + c;
  92
  93                         /* compute estimated cost */
  94                         if (is_target) {
  95                                 n->m_estimate = n->m_cost;
  96                                 TAstar::FoundTarget(n);
  97                         } else {
  98                                 n->m_estimate = n->m_cost + YapfCalcEstimate (n->GetPos(), m_dest_tile);
  99                                 assert(n->m_estimate >= n->m_parent->m_estimate);
 100                                 TAstar::InsertNode(n);
 101                         }
 102                 }
 103         }
 104
 105
 106         /** Call the node follower */
 107         static inline void Follow (CYapfShipT *pf, Node *n)
 108         {
 109                 pf->Follow(n);
 110         }
 111
 112         /** Invoke the underlying pathfinder. */
 113         inline bool FindPath (void)
 114         {
 115 #ifndef NO_DEBUG_MESSAGES
 116                 CPerformanceTimer perf;
 117                 perf.Start();
 118 #endif /* !NO_DEBUG_MESSAGES */
 119
 120                 bool bDestFound = TAstar::FindPath (Follow, m_settings->max_search_nodes);
 121
 122 #ifndef NO_DEBUG_MESSAGES
 123                 perf.Stop();
 124                 if (_debug_yapf_level >= 2) {
 125                         int t = perf.Get(1000000);
 126                         _total_pf_time_us += t;
 127
 128                         if (_debug_yapf_level >= 3) {
 129                                 int cost = bDestFound ? TAstar::best->m_cost : -1;
 130                                 int dist = bDestFound ? TAstar::best->m_estimate - TAstar::best->m_cost : -1;
 131
 132                                 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) -- ",
 133                                         bDestFound ? '-' : '!', m_veh->unitnumber, t, TAstar::num_steps, TAstar::OpenCount(), TAstar::ClosedCount(),
 134                                         cost, dist
 135                                 );
 136                         }
 137                 }
 138 #endif /* !NO_DEBUG_MESSAGES */
 139                 return bDestFound;
 140         }
 141 };
 142
 143 /* YAPF type 1 - uses TileIndex/Trackdir as Node key, allows 90-deg turns */
 144 struct CYapfShip1 : CYapfShipT<AstarShipTrackDir>
 145 {
 146         CYapfShip1 (const Ship *ship)
 147                 : CYapfShipT<AstarShipTrackDir> (ship, true)
 148         {
 149         }
 150 };
 151
 152 /* YAPF type 2 - uses TileIndex/DiagDirection as Node key, allows 90-deg turns */
 153 struct CYapfShip2 : CYapfShipT<AstarShipExitDir>
 154 {
 155         CYapfShip2 (const Ship *ship)
 156                 : CYapfShipT<AstarShipExitDir> (ship, true)
 157         {
 158         }
 159 };
 160
 161 /* YAPF type 3 - uses TileIndex/Trackdir as Node key, forbids 90-deg turns */
 162 struct CYapfShip3 : CYapfShipT<AstarShipTrackDir>
 163 {
 164         CYapfShip3 (const Ship *ship)
 165                 : CYapfShipT<AstarShipTrackDir> (ship, false)
 166         {
 167         }
 168 };
 169
 170
 171 template <class Tpf>
 172 static Trackdir ChooseShipTrack(const Ship *v, const ShipPathPos &pos, TrackdirBits trackdirs, bool &path_found)
 173 {
 174         /* create pathfinder instance */
 175         Tpf pf (v);
 176         /* set origin node */
 177         pf.InsertInitialNode (pf.CreateNewNode (NULL, pos));
 178         /* find best path */
 179         path_found = pf.FindPath();
 180
 181         typename Tpf::Node *n = pf.GetBestNode();
 182         if (n == NULL) return INVALID_TRACKDIR; // path not found
 183         assert (n->m_parent != NULL);
 184
 185         /* walk through the path back to the origin */
 186         while (n->m_parent->m_parent != NULL) {
 187                 n = n->m_parent;
 188         }
 189
 190         /* return trackdir from the best next node (direct child of origin) */
 191         assert(n->m_parent->GetPos().tile == pos.tile);
 192         return n->GetPos().td;
 193 }
 194
 195 /** Ship controller helper - path finder invoker */
 196 Trackdir YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool &path_found)
 197 {
 198         /* move back to the old tile/trackdir (where ship is coming from) */
 199         ShipPathPos pos = v->GetPos();
 200         assert(pos.tile == TileAddByDiagDir (tile, ReverseDiagDir(enterdir)));
 201         assert(IsValidTrackdir(pos.td));
 202
 203         /* handle special case - when next tile is destination tile */
 204         if (v->current_order.IsType(OT_GOTO_STATION) ?
 205                         Station::Get(v->current_order.GetDestination())->IsDockingTile(tile) :
 206                         tile == v->dest_tile) {
 207                 /* use vehicle's current direction if that's possible, otherwise use first usable one. */
 208                 Trackdir veh_dir = pos.td;
 209                 return ((trackdirs & TrackdirToTrackdirBits(veh_dir)) != 0) ? veh_dir : FindFirstTrackdir(trackdirs);
 210         }
 211
 212         /* default is YAPF type 2 */
 213         typedef Trackdir (*PfnChooseShipTrack)(const Ship*, const ShipPathPos&, TrackdirBits, bool &path_found);
 214         PfnChooseShipTrack pfnChooseShipTrack = ChooseShipTrack<CYapfShip2>; // default: ExitDir, allow 90-deg
 215
 216         /* check if non-default YAPF type needed */
 217         if (_settings_game.pf.forbid_90_deg) {
 218                 pfnChooseShipTrack = &ChooseShipTrack<CYapfShip3>; // Trackdir, forbid 90-deg
 219         } else if (_settings_game.pf.yapf.disable_node_optimization) {
 220                 pfnChooseShipTrack = &ChooseShipTrack<CYapfShip1>; // Trackdir, allow 90-deg
 221         }
 222
 223         return pfnChooseShipTrack(v, pos, trackdirs, path_found);
 224 }
 225
 226
 227 /**
 228  * Check whether a ship should reverse to reach its destination.
 229  * Called when leaving depot.
 230  * @param v Ship
 231  * @param pos Current position
 232  * @return true if the reverse direction is better
 233  */
 234 template <class Tpf>
 235 static bool CheckShipReverse(const Ship *v, const ShipPathPos &pos)
 236 {
 237         /* create pathfinder instance */
 238         Tpf pf (v);
 239         /* set origin nodes */
 240         pf.InsertInitialNode (pf.CreateNewNode (NULL, pos));
 241         pf.InsertInitialNode (pf.CreateNewNode (NULL, ShipPathPos(pos.tile, ReverseTrackdir(pos.td))));
 242         /* find best path */
 243         if (!pf.FindPath()) return false;
 244
 245         typename Tpf::Node *n = pf.GetBestNode();
 246         if (n == NULL) return false;
 247
 248         /* path was found; walk through the path back to the origin */
 249         while (n->m_parent != NULL) {
 250                 n = n->m_parent;
 251         }
 252
 253         Trackdir best_trackdir = n->GetPos().td;
 254         assert(best_trackdir == pos.td || best_trackdir == ReverseTrackdir(pos.td));
 255         return best_trackdir != pos.td;
 256 }
 257
 258 bool YapfShipCheckReverse(const Ship *v)
 259 {
 260         ShipPathPos pos = v->GetPos();
 261
 262         typedef bool (*PfnCheckReverseShip)(const Ship*, const ShipPathPos&);
 263         PfnCheckReverseShip pfnCheckReverseShip = CheckShipReverse<CYapfShip2>; // default: ExitDir, allow 90-deg
 264
 265         /* check if non-default YAPF type needed */
 266         if (_settings_game.pf.forbid_90_deg) {
 267                 pfnCheckReverseShip = &CheckShipReverse<CYapfShip3>; // Trackdir, forbid 90-deg
 268         } else if (_settings_game.pf.yapf.disable_node_optimization) {
 269                 pfnCheckReverseShip = &CheckShipReverse<CYapfShip1>; // Trackdir, allow 90-deg
 270         }
 271
 272         bool reverse = pfnCheckReverseShip(v, pos);
 273
 274         return reverse;
 275 }