Loading

FindClosestReachableShipD

Wrap Raw Revise
  1. Index: src/pathfinder/npf/npf.cpp
  2. ===================================================================
  3. --- src/pathfinder/npf/npf.cpp  (revision 27833)
  4. +++ src/pathfinder/npf/npf.cpp  (working copy)
  5. @@ -536,8 +536,13 @@
  6.     AyStarUserData *user = (AyStarUserData *)as->user_data;
  7.     /* It's not worth caching the result with NPF_FLAG_IS_TARGET here as below,
  8.      * since checking the cache not that much faster than the actual check */
  9. -   return IsDepotTypeTile(current->path.node.tile, user->type) ?
  10. -       AYSTAR_FOUND_END_NODE : AYSTAR_DONE;
  11. +   if (user->type != TRANSPORT_WATER) {
  12. +       return IsDepotTypeTile(current->path.node.tile, user->type) ?
  13. +           AYSTAR_FOUND_END_NODE : AYSTAR_DONE;
  14. +   } else {
  15. +       return IsShipDepotTile(current->path.node.tile) && GetShipDepotPart(current->path.node.tile) == DEPOT_PART_NORTH && IsTileOwner(current->path.node.tile, user->owner) ?
  16. +           AYSTAR_FOUND_END_NODE : AYSTAR_DONE;
  17. +   }
  18.  }
  19.  
  20.  /** Find any safe and free tile. */
  21. @@ -1161,6 +1166,24 @@
  22.  
  23.  /*** Ships ***/
  24.  
  25. +FindDepotData NPFShipFindNearestDepot(const Ship *v, int max_distance)
  26. +{
  27. +   Trackdir trackdir = v->GetVehicleTrackdir();
  28. +   Trackdir trackdir_rev = ReverseTrackdir(trackdir);
  29. +   NPFFindStationOrTileData fstd;
  30. +   fstd.v = v;
  31. +   fstd.reserve_path = false;
  32. +
  33. +   assert(trackdir != INVALID_TRACKDIR);
  34. +   AyStarUserData user = { v->owner, TRANSPORT_WATER, INVALID_RAILTYPES, ROADTYPES_NONE };
  35. +   NPFFoundTargetData ftd = NPFRouteToDepotBreadthFirstTwoWay(v->tile, trackdir, false, v->tile, trackdir_rev, false, &fstd, &user, NPF_INFINITE_PENALTY);
  36. +   if (ftd.best_bird_dist != 0) return FindDepotData();
  37. +
  38. +   /* Found target */
  39. +   /* Our caller wants the distance to depot. We provide it in distance manhattan */
  40. +   return FindDepotData(ftd.node.tile, DistanceManhattan(v->tile, ftd.node.tile), NPFGetFlag(&ftd.node, NPF_FLAG_REVERSE));
  41. +}
  42. +
  43.  Track NPFShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found)
  44.  {
  45.     NPFFindStationOrTileData fstd;
  46. Index: src/pathfinder/npf/npf_func.h
  47. ===================================================================
  48. --- src/pathfinder/npf/npf_func.h   (revision 27833)
  49. +++ src/pathfinder/npf/npf_func.h   (working copy)
  50. @@ -39,6 +39,14 @@
  51.  Trackdir NPFRoadVehicleChooseTrack(const RoadVehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool &path_found);
  52.  
  53.  /**
  54. + * Used when user sends ship to the nearest depot or if ship needs servicing using NPF
  55. + * @param v            ship that needs to go to some depot
  56. + * @param max_distance not used
  57. + * @return             the data about the depot
  58. + */
  59. +FindDepotData NPFShipFindNearestDepot(const Ship *v, int max_distance);
  60. +
  61. +/**
  62.   * Finds the best path for given ship using NPF.
  63.   * @param v        the ship that needs to find a path
  64.   * @param tile     the tile to find the path from (should be next tile the ship is about to enter)
  65. Index: src/pathfinder/opf/opf_ship.cpp
  66. ===================================================================
  67. --- src/pathfinder/opf/opf_ship.cpp (revision 27833)
  68. +++ src/pathfinder/opf/opf_ship.cpp (working copy)
  69. @@ -14,6 +14,7 @@
  70.  #include "../../tunnelbridge.h"
  71.  #include "../../ship.h"
  72.  #include "../../core/random_func.hpp"
  73. +#include "../pathfinder_type.h"
  74.  
  75.  #include "../../safeguards.h"
  76.  
  77. @@ -212,3 +213,8 @@
  78.     if (dist <= distr) return track;
  79.     return INVALID_TRACK; // We could better reverse
  80.  }
  81. +
  82. +FindDepotData OPFShipFindNearestDepot(const Ship *v, int max_distance) // todo
  83. +{
  84. +   return FindDepotData();
  85. +}
  86. Index: src/pathfinder/opf/opf_ship.h
  87. ===================================================================
  88. --- src/pathfinder/opf/opf_ship.h   (revision 27833)
  89. +++ src/pathfinder/opf/opf_ship.h   (working copy)
  90. @@ -28,4 +28,13 @@
  91.   */
  92.  Track OPFShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found);
  93.  
  94. +/**
  95. + * Used when user sends ship to the nearest depot or if ship needs servicing using OPF.
  96. + * @todo               this is just a placeholder, it's currently not implemented
  97. + * @param v            vehicle that needs to go to some depot
  98. + * @param max_distance not used
  99. + * @return             the data about the depot
  100. + */
  101. +FindDepotData OPFShipFindNearestDepot(const Ship *v, int max_distance);
  102. +
  103.  #endif /* OPF_SHIP_H */
  104. Index: src/pathfinder/yapf/yapf.h
  105. ===================================================================
  106. --- src/pathfinder/yapf/yapf.h  (revision 27833)
  107. +++ src/pathfinder/yapf/yapf.h  (working copy)
  108. @@ -97,4 +97,12 @@
  109.   */
  110.  bool YapfTrainFindNearestSafeTile(const Train *v, TileIndex tile, Trackdir td, bool override_railtype);
  111.  
  112. +/**
  113. + * Used when user sends ship to the nearest depot or if ship needs servicing using YAPF.
  114. + * @param v            vehicle that needs to go to some depot
  115. + * @param max_distance not used
  116. + * @return             the data about the depot
  117. + */
  118. +FindDepotData YapfShipFindNearestDepot(const Ship *v, int max_distance);
  119. +
  120.  #endif /* YAPF_H */
  121. Index: src/pathfinder/yapf/yapf_ship.cpp
  122. ===================================================================
  123. --- src/pathfinder/yapf/yapf_ship.cpp   (revision 27833)
  124. +++ src/pathfinder/yapf/yapf_ship.cpp   (working copy)
  125. @@ -139,6 +139,48 @@
  126.         assert(best_trackdir == td1 || best_trackdir == td2);
  127.         return best_trackdir == td2;
  128.     }
  129. +
  130. +   static bool stFindNearestDepot(const Ship *v, TileIndex tile, Trackdir td1, Trackdir td2, TileIndex *depot_tile, bool *reversed)
  131. +   {
  132. +       Tpf pf;
  133. +       bool result = pf.FindNearestDepot(v, tile, td1, td2, depot_tile, reversed);
  134. +       return result;
  135. +   }
  136. +
  137. +   /**
  138. +    * Find the best depot for a ship.
  139. +    * @param v Vehicle
  140. +    * @param tile Tile of the vehicle.
  141. +    * @param td1 Trackdir of the vehicle.
  142. +    * @param td2 reversed Trackdir of the vehicle.
  143. +    * @param depot_tile the tile of the depot.
  144. +    * @param reversed whether the path to depot was found on reversed Trackdir.
  145. +    */
  146. +   inline bool FindNearestDepot(const Ship *v, TileIndex tile, Trackdir td1, Trackdir td2, TileIndex *depot_tile, bool *reversed)
  147. +   {
  148. +       Tpf pf;
  149. +       /* Set origin. */
  150. +       pf.SetOrigin(tile, TrackdirToTrackdirBits(td1) | TrackdirToTrackdirBits(td2));
  151. +
  152. +       /* find the best path */
  153. +       bool bFound = pf.FindPath(v);
  154. +       if (!bFound) return false;
  155. +
  156. +       /* some path found
  157. +        * get found depot tile */
  158. +       Node *n = pf.GetBestNode();
  159. +       *depot_tile = n->m_key.m_tile;
  160. +
  161. +       /* walk through the path back to the origin */
  162. +       Node *pNode = n;
  163. +       while (pNode->m_parent != NULL) {
  164. +           pNode = pNode->m_parent;
  165. +       }
  166. +
  167. +       /* if the origin node is the ship's Trackdir then we didn't reverse */
  168. +       *reversed = (pNode->m_key.m_td != td1);
  169. +       return true;
  170. +   }
  171.  };
  172.  
  173.  /** Cost Provider module of YAPF for ships */
  174. @@ -188,15 +230,54 @@
  175.     }
  176.  };
  177.  
  178. +template <class Types>
  179. +class CYapfDestinationAnyDepotShipT
  180. +{
  181. +public:
  182. +   typedef typename Types::Tpf Tpf;                     ///< the pathfinder class (derived from THIS class)
  183. +   typedef typename Types::TrackFollower TrackFollower;
  184. +   typedef typename Types::NodeList::Titem Node;        ///< this will be our node type
  185. +   typedef typename Node::Key Key;                      ///< key to hash tables
  186. +
  187. +   /** to access inherited path finder */
  188. +   Tpf& Yapf()
  189. +   {
  190. +       return *static_cast<Tpf *>(this);
  191. +   }
  192. +
  193. +   /** Called by YAPF to detect if node ends in the desired destination */
  194. +   inline bool PfDetectDestination(Node &n)
  195. +   {
  196. +      
  197. +       bool bDest = (IsShipDepotTile(n.m_key.m_tile) && GetShipDepotPart(n.m_key.m_tile) == DEPOT_PART_NORTH) && IsTileOwner(n.m_key.m_tile, Yapf().GetVehicle()->owner);
  198. +       return bDest;
  199. +   }
  200. +
  201. +   inline bool PfDetectDestinationTile(TileIndex tile, Trackdir trackdir)
  202. +   {
  203. +       return (IsShipDepotTile(n.m_key.m_tile) && GetShipDepotPart(n.m_key.m_tile) == DEPOT_PART_NORTH) && IsTileOwner(n.m_key.m_tile, Yapf().GetVehicle()->owner);
  204. +   }
  205. +
  206. +   /**
  207. +    * Called by YAPF to calculate cost estimate. Calculates distance to the destination
  208. +    *  adds it to the actual cost from origin and stores the sum to the Node::m_estimate
  209. +    */
  210. +   inline bool PfCalcEstimate(Node &n)
  211. +   {
  212. +       n.m_estimate = n.m_cost;
  213. +       return true;
  214. +   }
  215. +};
  216. +
  217.  /**
  218.   * Config struct of YAPF for ships.
  219.   *  Defines all 6 base YAPF modules as classes providing services for CYapfBaseT.
  220.   */
  221. -template <class Tpf_, class Ttrack_follower, class Tnode_list>
  222. +template <class Tpf_, class Ttrack_follower, class Tnode_list, template <class Types> class CYapfDestinationTileT>
  223.  struct CYapfShip_TypesT
  224.  {
  225.     /** Types - shortcut for this struct type */
  226. -   typedef CYapfShip_TypesT<Tpf_, Ttrack_follower, Tnode_list>  Types;
  227. +   typedef CYapfShip_TypesT<Tpf_, Ttrack_follower, Tnode_list, CYapfDestinationTileT>  Types;
  228.  
  229.     /** Tpf - pathfinder type */
  230.     typedef Tpf_                              Tpf;
  231. @@ -215,12 +296,16 @@
  232.  };
  233.  
  234.  /* YAPF type 1 - uses TileIndex/Trackdir as Node key, allows 90-deg turns */
  235. -struct CYapfShip1 : CYapfT<CYapfShip_TypesT<CYapfShip1, CFollowTrackWater    , CShipNodeListTrackDir> > {};
  236. +struct CYapfShip1         : CYapfT<CYapfShip_TypesT<CYapfShip1        , CFollowTrackWater    , CShipNodeListTrackDir, CYapfDestinationTileT> > {};
  237.  /* YAPF type 2 - uses TileIndex/DiagDirection as Node key, allows 90-deg turns */
  238. -struct CYapfShip2 : CYapfT<CYapfShip_TypesT<CYapfShip2, CFollowTrackWater    , CShipNodeListExitDir > > {};
  239. +struct CYapfShip2         : CYapfT<CYapfShip_TypesT<CYapfShip2        , CFollowTrackWater    , CShipNodeListExitDir , CYapfDestinationTileT> > {};
  240.  /* YAPF type 3 - uses TileIndex/Trackdir as Node key, forbids 90-deg turns */
  241. -struct CYapfShip3 : CYapfT<CYapfShip_TypesT<CYapfShip3, CFollowTrackWaterNo90, CShipNodeListTrackDir> > {};
  242. +struct CYapfShip3         : CYapfT<CYapfShip_TypesT<CYapfShip3        , CFollowTrackWaterNo90, CShipNodeListTrackDir, CYapfDestinationTileT> > {};
  243.  
  244. +struct CYapfShipAnyDepot1 : CYapfT<CYapfShip_TypesT<CYapfShipAnyDepot1, CFollowTrackWater    , CShipNodeListTrackDir, CYapfDestinationAnyDepotShipT> > {};
  245. +struct CYapfShipAnyDepot2 : CYapfT<CYapfShip_TypesT<CYapfShipAnyDepot2, CFollowTrackWater    , CShipNodeListExitDir , CYapfDestinationAnyDepotShipT> > {};
  246. +struct CYapfShipAnyDepot3 : CYapfT<CYapfShip_TypesT<CYapfShipAnyDepot3, CFollowTrackWaterNo90, CShipNodeListTrackDir, CYapfDestinationAnyDepotShipT> > {};
  247. +
  248.  /** Ship controller helper - path finder invoker */
  249.  Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found)
  250.  {
  251. @@ -239,6 +324,31 @@
  252.     return (td_ret != INVALID_TRACKDIR) ? TrackdirToTrack(td_ret) : INVALID_TRACK;
  253.  }
  254.  
  255. +FindDepotData YapfShipFindNearestDepot(const Ship *v, int max_distance)
  256. +{
  257. +   FindDepotData fdd;
  258. +
  259. +   Trackdir td = v->GetVehicleTrackdir();
  260. +   Trackdir td_rev = ReverseTrackdir(td);
  261. +   TileIndex tile = v->tile;
  262. +
  263. +   /* default is YAPF type 2 */
  264. +   typedef bool(*PfnFindNearestDepot)(const Ship*, TileIndex, Trackdir, Trackdir, TileIndex*, bool*);
  265. +   PfnFindNearestDepot pfnFindNearestDepot = &CYapfShipAnyDepot2::stFindNearestDepot;
  266. +
  267. +   /* check if non-default YAPF type should be used */
  268. +   if (_settings_game.pf.forbid_90_deg) {
  269. +       pfnFindNearestDepot = &CYapfShipAnyDepot3::stFindNearestDepot; // Trackdir, forbid 90-deg
  270. +   } else if (_settings_game.pf.yapf.disable_node_optimization) {
  271. +       pfnFindNearestDepot = &CYapfShipAnyDepot1::stFindNearestDepot; // Trackdir, allow 90-deg
  272. +   }
  273. +
  274. +   bool ret = pfnFindNearestDepot(v, tile, td, td_rev, &fdd.tile, &fdd.reverse);
  275. +
  276. +   fdd.best_length = ret ? DistanceManhattan(tile, fdd.tile) : UINT_MAX; // distance manhattan or NOT_FOUND
  277. +   return fdd;
  278. +}
  279. +
  280.  bool YapfShipCheckReverse(const Ship *v)
  281.  {
  282.     Trackdir td = v->GetVehicleTrackdir();
  283. Index: src/ship_cmd.cpp
  284. ===================================================================
  285. --- src/ship_cmd.cpp    (revision 27833)
  286. +++ src/ship_cmd.cpp    (working copy)
  287. @@ -138,7 +138,7 @@
  288.     result->Set(_ship_sprites[spritenum] + direction);
  289.  }
  290.  
  291. -static const Depot *FindClosestShipDepot(const Vehicle *v, uint max_distance)
  292. +static FindDepotData FindClosestShipDepot(const Ship *v, uint max_distance)
  293.  {
  294.     /* Find the closest depot */
  295.     const Depot *depot;
  296. @@ -161,9 +161,27 @@
  297.         }
  298.     }
  299.  
  300. -   return best_depot;
  301. +   FindDepotData fdd;
  302. +   if (best_depot != NULL) {
  303. +       fdd.best_length = best_dist;
  304. +       fdd.tile = best_depot->xy;
  305. +   }
  306. +   return fdd;
  307.  }
  308.  
  309. +static FindDepotData FindClosestReachableShipDepot(const Ship *v, int max_distance)
  310. +{
  311. +   if ((IsShipDepotTile(v->tile) && GetShipDepotPart(v->tile) == DEPOT_PART_NORTH) && IsTileOwner(v->tile, v->owner)) return FindDepotData(v->tile, 0);
  312. +
  313. +   switch (_settings_game.pf.pathfinder_for_ships) {
  314. +   case VPF_OPF: return OPFShipFindNearestDepot(v, max_distance);
  315. +   case VPF_NPF: return NPFShipFindNearestDepot(v, max_distance);
  316. +   case VPF_YAPF: return YapfShipFindNearestDepot(v, max_distance);
  317. +
  318. +   default: NOT_REACHED();
  319. +   }
  320. +}
  321. +
  322.  static void CheckIfShipNeedsService(Vehicle *v)
  323.  {
  324.     if (Company::Get(v->owner)->settings.vehicle.servint_ships == 0 || !v->NeedsAutomaticServicing()) return;
  325. @@ -180,9 +198,9 @@
  326.         default: NOT_REACHED();
  327.     }
  328.  
  329. -   const Depot *depot = FindClosestShipDepot(v, max_distance);
  330. +   const FindDepotData sfdd = FindClosestReachableShipDepot(Ship::From(v), max_distance);
  331.  
  332. -   if (depot == NULL) {
  333. +   if (sfdd.best_length == UINT_MAX || sfdd.best_length >= max_distance) {
  334.         if (v->current_order.IsType(OT_GOTO_DEPOT)) {
  335.             v->current_order.MakeDummy();
  336.             SetWindowWidgetDirty(WC_VEHICLE_VIEW, v->index, WID_VV_START_STOP);
  337. @@ -190,8 +208,8 @@
  338.         return;
  339.     }
  340.  
  341. -   v->current_order.MakeGoToDepot(depot->index, ODTFB_SERVICE);
  342. -   v->dest_tile = depot->xy;
  343. +   v->current_order.MakeGoToDepot(GetDepotIndex(sfdd.tile), ODTFB_SERVICE);
  344. +   v->dest_tile = sfdd.tile;
  345.     SetWindowWidgetDirty(WC_VEHICLE_VIEW, v->index, WID_VV_START_STOP);
  346.  }
  347.  
  348. @@ -712,12 +730,15 @@
  349.  
  350.  bool Ship::FindClosestDepot(TileIndex *location, DestinationID *destination, bool *reverse)
  351.  {
  352. -   const Depot *depot = FindClosestShipDepot(this, 0);
  353. +   FindDepotData sfdd = FindClosestReachableShipDepot(this, 0);
  354. +   if (sfdd.best_length == UINT_MAX) {
  355. +       sfdd = FindClosestShipDepot(this, 0);
  356. +       if (sfdd.best_length == UINT_MAX) return false;
  357. +   }
  358.  
  359. -   if (depot == NULL) return false;
  360. +   if (location    != NULL) *location = sfdd.tile;
  361. +   if (destination != NULL) *destination = GetDepotIndex(sfdd.tile);
  362. +   if (reverse     != NULL) *reverse = sfdd.reverse;
  363.  
  364. -   if (location    != NULL) *location    = depot->xy;
  365. -   if (destination != NULL) *destination = depot->index;
  366. -
  367.     return true;
  368.  }
Posted by Anonymous at 29 Mar 2017, 19:00:10 UTC
Language: diff • Views: 728

Version history

Revision # Author Created at
pubn57tm0 Anonymous 26 Mar 2017, 23:25:37 UTC Diff
pxmwekzc2 Anonymous 26 Mar 2017, 23:13:14 UTC Diff
phoeeb6pa Anonymous 26 Mar 2017, 14:13:24 UTC Diff
ppqwyyw9s Anonymous 26 Mar 2017, 01:16:13 UTC Diff

Comments