# yapf_ship.cpp

Go to the documentation of this file.

    00001 /* $Id: yapf_ship.cpp 15718 2009-03-15 00:32:18Z rubidium $ */
    00002
    00005 #include "../stdafx.h"
    00006
    00007 #include "yapf.hpp"
    00008
    00010 template <class Types>
    00011 class CYapfFollowShipT
    00012 {
    00013 public:
    00014   typedef typename Types::Tpf Tpf;
    00015   typedef typename Types::TrackFollower TrackFollower;
    00016   typedef typename Types::NodeList::Titem Node;
    00017   typedef typename Node::Key Key;
    00018
    00019 protected:
    00021   FORCEINLINE Tpf& Yapf()
    00022   {
    00023     return *static_cast<Tpf*>(this);
    00024   }
    00025
    00026 public:
    00030   inline void PfFollowNode(Node& old_node)
    00031   {
    00032     TrackFollower F(Yapf().GetVehicle());
    00033     if (F.Follow(old_node.m_key.m_tile, old_node.m_key.m_td)) {
    00034       Yapf().AddMultipleNodes(&old_node, F);
    00035     }
    00036   }
    00037
    00039   FORCEINLINE char TransportTypeChar() const
    00040   {
    00041     return 'w';
    00042   }
    00043
    00044   static Trackdir ChooseShipTrack(const Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks)
    00045   {
    00046     /* handle special case - when next tile is destination tile */
    00047     if (tile == v->dest_tile) {
    00048       /* convert tracks to trackdirs */
    00049       TrackdirBits trackdirs = (TrackdirBits)(tracks | ((int)tracks << 8));
    00050       /* choose any trackdir reachable from enterdir */
    00051       trackdirs &= DiagdirReachesTrackdirs(enterdir);
    00052       return (Trackdir)FindFirstBit2x64(trackdirs);
    00053     }
    00054
    00055     /* move back to the old tile/trackdir (where ship is coming from) */
    00056     TileIndex src_tile = TILE_ADD(tile, TileOffsByDiagDir(ReverseDiagDir(enterdir)));
    00057     Trackdir trackdir = GetVehicleTrackdir(v);
    00058     assert(IsValidTrackdir(trackdir));
    00059
    00060     /* convert origin trackdir to TrackdirBits */
    00061     TrackdirBits trackdirs = TrackdirToTrackdirBits(trackdir);
    00062     /* get available trackdirs on the destination tile */
    00063     TrackdirBits dest_trackdirs = TrackStatusToTrackdirBits(GetTileTrackStatus(v->dest_tile, TRANSPORT_WATER, 0));
    00064
    00065     /* create pathfinder instance */
    00066     Tpf pf;
    00067     /* set origin and destination nodes */
    00068     pf.SetOrigin(src_tile, trackdirs);
    00069     pf.SetDestination(v->dest_tile, dest_trackdirs);
    00070     /* find best path */
    00071     pf.FindPath(v);
    00072
    00073     Trackdir next_trackdir = INVALID_TRACKDIR; // this would mean "path not found"
    00074
    00075     Node *pNode = pf.GetBestNode();
    00076     if (pNode != NULL) {
    00077       /* walk through the path back to the origin */
    00078       Node *pPrevNode = NULL;
    00079       while (pNode->m_parent != NULL) {
    00080         pPrevNode = pNode;
    00081         pNode = pNode->m_parent;
    00082       }
    00083       /* return trackdir from the best next node (direct child of origin) */
    00084       Node& best_next_node = *pPrevNode;
    00085       assert(best_next_node.GetTile() == tile);
    00086       next_trackdir = best_next_node.GetTrackdir();
    00087     }
    00088     return next_trackdir;
    00089   }
    00090 };
    00091
    00093 template <class Types>
    00094 class CYapfCostShipT
    00095 {
    00096 public:
    00097   typedef typename Types::Tpf Tpf;
    00098   typedef typename Types::TrackFollower TrackFollower;
    00099   typedef typename Types::NodeList::Titem Node;
    00100   typedef typename Node::Key Key;
    00101
    00102 protected:
    00104   Tpf& Yapf()
    00105   {
    00106     return *static_cast<Tpf*>(this);
    00107   }
    00108
    00109 public:
    00113   FORCEINLINE bool PfCalcCost(Node& n, const TrackFollower *tf)
    00114   {
    00115     /* base tile cost depending on distance */
    00116     int c = IsDiagonalTrackdir(n.GetTrackdir()) ? 10 : 7;
    00117     /* additional penalty for curves */
    00118     if (n.m_parent != NULL && n.GetTrackdir() != NextTrackdir(n.m_parent->GetTrackdir())) {
    00119       /* new trackdir does not match the next one when going straight */
    00120       c += 10;
    00121     }
    00122
    00123     c += YAPF_TILE_LENGTH * tf->m_tiles_skipped;
    00124
    00125     /* apply it */
    00126     n.m_cost = n.m_parent->m_cost + c;
    00127     return true;
    00128   }
    00129 };
    00130
    00134 template <class Tpf_, class Ttrack_follower, class Tnode_list>
    00135 struct CYapfShip_TypesT
    00136 {
    00138   typedef CYapfShip_TypesT<Tpf_, Ttrack_follower, Tnode_list>  Types;
    00139
    00141   typedef Tpf_                              Tpf;
    00143   typedef Ttrack_follower                   TrackFollower;
    00145   typedef Tnode_list                        NodeList;
    00147   typedef CYapfBaseT<Types>                 PfBase;        // base pathfinder class
    00148   typedef CYapfFollowShipT<Types>           PfFollow;      // node follower
    00149   typedef CYapfOriginTileT<Types>           PfOrigin;      // origin provider
    00150   typedef CYapfDestinationTileT<Types>      PfDestination; // destination/distance provider
    00151   typedef CYapfSegmentCostCacheNoneT<Types> PfCache;       // segment cost cache provider
    00152   typedef CYapfCostShipT<Types>             PfCost;        // cost provider
    00153 };
    00154
    00155 /* YAPF type 1 - uses TileIndex/Trackdir as Node key, allows 90-deg turns */
    00156 struct CYapfShip1 : CYapfT<CYapfShip_TypesT<CYapfShip1, CFollowTrackWater    , CShipNodeListTrackDir> > {};
    00157 /* YAPF type 2 - uses TileIndex/DiagDirection as Node key, allows 90-deg turns */
    00158 struct CYapfShip2 : CYapfT<CYapfShip_TypesT<CYapfShip2, CFollowTrackWater    , CShipNodeListExitDir > > {};
    00159 /* YAPF type 3 - uses TileIndex/Trackdir as Node key, forbids 90-deg turns */
    00160 struct CYapfShip3 : CYapfT<CYapfShip_TypesT<CYapfShip3, CFollowTrackWaterNo90, CShipNodeListTrackDir> > {};
    00161
    00163 Trackdir YapfChooseShipTrack(const Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks)
    00164 {
    00165   /* default is YAPF type 2 */
    00166   typedef Trackdir (*PfnChooseShipTrack)(const Vehicle*, TileIndex, DiagDirection, TrackBits);
    00167   PfnChooseShipTrack pfnChooseShipTrack = CYapfShip2::ChooseShipTrack; // default: ExitDir, allow 90-deg
    00168
    00169   /* check if non-default YAPF type needed */
    00170   if (_settings_game.pf.forbid_90_deg) {
    00171     pfnChooseShipTrack = &CYapfShip3::ChooseShipTrack; // Trackdir, forbid 90-deg
    00172   } else if (_settings_game.pf.yapf.disable_node_optimization) {
    00173     pfnChooseShipTrack = &CYapfShip1::ChooseShipTrack; // Trackdir, allow 90-deg
    00174   }
    00175
    00176   Trackdir td_ret = pfnChooseShipTrack(v, tile, enterdir, tracks);
    00177   return td_ret;
    00178 }
    00179
    00181 void *NpfBeginInterval()
    00182 {
    00183   CPerformanceTimer& perf = *new CPerformanceTimer;
    00184   perf.Start();
    00185   return &perf;
    00186 }
    00187
    00189 int NpfEndInterval(void *vperf)
    00190 {
    00191   CPerformanceTimer& perf = *(CPerformanceTimer*)vperf;
    00192   perf.Stop();
    00193   int t = perf.Get(1000000);
    00194   delete &perf;
    00195   return t;
    00196 }