Loading

FindClosestReachableShipD

Wrap Raw Revise
  1. Index: src/pathfinder/yapf/yapf.h
  2. ===================================================================
  3. --- src/pathfinder/yapf/yapf.h  (revision 27829)
  4. +++ src/pathfinder/yapf/yapf.h  (working copy)
  5. @@ -97,4 +97,14 @@
  6.   */
  7.  bool YapfTrainFindNearestSafeTile(const Train *v, TileIndex tile, Trackdir td, bool override_railtype);
  8.  
  9. +/**
  10. + * Used when user sends ship to the nearest depot or if ship needs servicing using YAPF.
  11. + * @param v            vehicle that needs to go to some depot
  12. + * @param max_distance max distance (in pathfinder penalty) from the current vehicle position
  13. + *                     (used also as optimization - the pathfinder can stop path finding if max_penalty
  14. + *                     was reached and no depot was seen)
  15. + * @return             the data about the depot
  16. + */
  17. +FindDepotData YapfShipFindNearestDepot(const Ship *v, int max_distance);
  18. +
  19.  #endif /* YAPF_H */
  20. Index: src/pathfinder/yapf/yapf_node_ship.hpp
  21. ===================================================================
  22. --- src/pathfinder/yapf/yapf_node_ship.hpp  (revision 27829)
  23. +++ src/pathfinder/yapf/yapf_node_ship.hpp  (working copy)
  24. @@ -14,8 +14,20 @@
  25.  
  26.  /** Yapf Node for ships */
  27.  template <class Tkey_>
  28. -struct CYapfShipNodeT : CYapfNodeT<Tkey_, CYapfShipNodeT<Tkey_> > { };
  29. +struct CYapfShipNodeT : CYapfNodeT<Tkey_, CYapfShipNodeT<Tkey_> > {
  30. +   typedef CYapfNodeT<Tkey_, CYapfShipNodeT<Tkey_> > base;
  31.  
  32. +   TileIndex m_segment_last_tile;
  33. +   Trackdir  m_segment_last_td;
  34. +
  35. +   void Set(CYapfShipNodeT *parent, TileIndex tile, Trackdir td, bool is_choice)
  36. +   {
  37. +       base::Set(parent, tile, td, is_choice);
  38. +       m_segment_last_tile = tile;
  39. +       m_segment_last_td = td;
  40. +   }
  41. +};
  42. +
  43.  /* now define two major node types (that differ by key type) */
  44.  typedef CYapfShipNodeT<CYapfNodeKeyExitDir>  CYapfShipNodeExitDir;
  45.  typedef CYapfShipNodeT<CYapfNodeKeyTrackDir> CYapfShipNodeTrackDir;
  46. Index: src/pathfinder/yapf/yapf_ship.cpp
  47. ===================================================================
  48. --- src/pathfinder/yapf/yapf_ship.cpp   (revision 27829)
  49. +++ src/pathfinder/yapf/yapf_ship.cpp   (working copy)
  50. @@ -139,6 +139,31 @@
  51.         assert(best_trackdir == td1 || best_trackdir == td2);
  52.         return best_trackdir == td2;
  53.     }
  54. +
  55. +   /**
  56. +    * Find the best depot for a ship.
  57. +    * @param v Vehicle
  58. +    * @param tile Tile of the vehicle.
  59. +    * @param td Trackdir of the vehicle.
  60. +    * @param max_distance max length (penalty) for paths.
  61. +    * @todo max_distance not used by YAPF for ships.
  62. +    *       It can be removed or copy the SetMaxCost() strategy
  63. +    *       applied in YAPF for rail. The best depot can be at
  64. +    *       a distance greater than max_distance.
  65. +    */
  66. +   static FindDepotData FindNearestDepot(const Ship *v, TileIndex tile, Trackdir td, int max_distance)
  67. +   {
  68. +       Tpf pf;
  69. +       /* Set origin. */
  70. +       pf.SetOrigin(tile, TrackdirToTrackdirBits(td));
  71. +
  72. +       /* Find the best path and return if no depot is found. */
  73. +       if (!pf.FindPath(v)) return FindDepotData();
  74. +
  75. +       /* Return the cost of the best path and its depot. */
  76. +       Node *n = pf.GetBestNode();
  77. +       return FindDepotData(n->m_segment_last_tile, n->m_cost);
  78. +   }
  79.  };
  80.  
  81.  /** Cost Provider module of YAPF for ships */
  82. @@ -188,15 +213,53 @@
  83.     }
  84.  };
  85.  
  86. +template <class Types>
  87. +class CYapfDestinationAnyDepotShipT
  88. +{
  89. +public:
  90. +   typedef typename Types::Tpf Tpf;                     ///< the pathfinder class (derived from THIS class)
  91. +   typedef typename Types::TrackFollower TrackFollower;
  92. +   typedef typename Types::NodeList::Titem Node;        ///< this will be our node type
  93. +   typedef typename Node::Key Key;                      ///< key to hash tables
  94. +
  95. +   /** to access inherited path finder */
  96. +   Tpf& Yapf()
  97. +   {
  98. +       return *static_cast<Tpf *>(this);
  99. +   }
  100. +
  101. +   /** Called by YAPF to detect if node ends in the desired destination */
  102. +   inline bool PfDetectDestination(Node &n)
  103. +   {
  104. +       bool bDest = IsShipDepotTile(n.m_segment_last_tile);
  105. +       return bDest;
  106. +   }
  107. +
  108. +   inline bool PfDetectDestinationTile(TileIndex tile, Trackdir trackdir)
  109. +   {
  110. +       return IsShipDepotTile(tile);
  111. +   }
  112. +
  113. +   /**
  114. +    * Called by YAPF to calculate cost estimate. Calculates distance to the destination
  115. +    *  adds it to the actual cost from origin and stores the sum to the Node::m_estimate
  116. +    */
  117. +   inline bool PfCalcEstimate(Node &n)
  118. +   {
  119. +       n.m_estimate = n.m_cost;
  120. +       return true;
  121. +   }
  122. +};
  123. +
  124.  /**
  125.   * Config struct of YAPF for ships.
  126.   *  Defines all 6 base YAPF modules as classes providing services for CYapfBaseT.
  127.   */
  128. -template <class Tpf_, class Ttrack_follower, class Tnode_list>
  129. +template <class Tpf_, class Ttrack_follower, class Tnode_list, template <class Types> class CYapfDestinationTileT>
  130.  struct CYapfShip_TypesT
  131.  {
  132.     /** Types - shortcut for this struct type */
  133. -   typedef CYapfShip_TypesT<Tpf_, Ttrack_follower, Tnode_list>  Types;
  134. +   typedef CYapfShip_TypesT<Tpf_, Ttrack_follower, Tnode_list, CYapfDestinationTileT>  Types;
  135.  
  136.     /** Tpf - pathfinder type */
  137.     typedef Tpf_                              Tpf;
  138. @@ -215,12 +278,16 @@
  139.  };
  140.  
  141.  /* YAPF type 1 - uses TileIndex/Trackdir as Node key, allows 90-deg turns */
  142. -struct CYapfShip1 : CYapfT<CYapfShip_TypesT<CYapfShip1, CFollowTrackWater    , CShipNodeListTrackDir> > {};
  143. +struct CYapfShip1         : CYapfT<CYapfShip_TypesT<CYapfShip1        , CFollowTrackWater    , CShipNodeListTrackDir, CYapfDestinationTileT > > {};
  144.  /* YAPF type 2 - uses TileIndex/DiagDirection as Node key, allows 90-deg turns */
  145. -struct CYapfShip2 : CYapfT<CYapfShip_TypesT<CYapfShip2, CFollowTrackWater    , CShipNodeListExitDir > > {};
  146. +struct CYapfShip2         : CYapfT<CYapfShip_TypesT<CYapfShip2        , CFollowTrackWater    , CShipNodeListExitDir , CYapfDestinationTileT > > {};
  147.  /* YAPF type 3 - uses TileIndex/Trackdir as Node key, forbids 90-deg turns */
  148. -struct CYapfShip3 : CYapfT<CYapfShip_TypesT<CYapfShip3, CFollowTrackWaterNo90, CShipNodeListTrackDir> > {};
  149. +struct CYapfShip3         : CYapfT<CYapfShip_TypesT<CYapfShip3        , CFollowTrackWaterNo90, CShipNodeListTrackDir, CYapfDestinationTileT > > {};
  150.  
  151. +struct CYapfShipAnyDepot1 : CYapfT<CYapfShip_TypesT<CYapfShipAnyDepot1, CFollowTrackWater    , CShipNodeListTrackDir, CYapfDestinationAnyDepotShipT > > {};
  152. +struct CYapfShipAnyDepot2 : CYapfT<CYapfShip_TypesT<CYapfShipAnyDepot2, CFollowTrackWater    , CShipNodeListExitDir , CYapfDestinationAnyDepotShipT > > {};
  153. +struct CYapfShipAnyDepot3 : CYapfT<CYapfShip_TypesT<CYapfShipAnyDepot3, CFollowTrackWaterNo90, CShipNodeListTrackDir, CYapfDestinationAnyDepotShipT > > {};
  154. +
  155.  /** Ship controller helper - path finder invoker */
  156.  Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found)
  157.  {
  158. @@ -239,6 +306,27 @@
  159.     return (td_ret != INVALID_TRACKDIR) ? TrackdirToTrack(td_ret) : INVALID_TRACK;
  160.  }
  161.  
  162. +FindDepotData YapfShipFindNearestDepot(const Ship *v, int max_distance)
  163. +{
  164. +   TileIndex tile = v->tile;
  165. +   Trackdir trackdir = v->GetVehicleTrackdir();
  166. +   if ((TrackStatusToTrackdirBits(GetTileTrackStatus(tile, TRANSPORT_WATER, 0)) & TrackdirToTrackdirBits(trackdir)) == 0) {
  167. +       return FindDepotData();
  168. +   }
  169. +   /* default is YAPF type 2 */
  170. +   typedef FindDepotData(*PfnFindNearestDepot)(const Ship*, TileIndex, Trackdir, int);
  171. +   PfnFindNearestDepot pfnFindNearestDepot = &CYapfShipAnyDepot2::FindNearestDepot;
  172. +
  173. +   /* check if non-default YAPF type should be used */
  174. +   if (_settings_game.pf.forbid_90_deg) {
  175. +       pfnFindNearestDepot = &CYapfShipAnyDepot3::FindNearestDepot; // Trackdir, forbid 90-deg
  176. +   } else if (_settings_game.pf.yapf.disable_node_optimization) {
  177. +       pfnFindNearestDepot = &CYapfShipAnyDepot1::FindNearestDepot; // Trackdir, allow 90-deg
  178. +   }
  179. +
  180. +   return pfnFindNearestDepot(v, tile, trackdir, max_distance);
  181. +}
  182. +
  183.  bool YapfShipCheckReverse(const Ship *v)
  184.  {
  185.     Trackdir td = v->GetVehicleTrackdir();
  186. Index: src/ship_cmd.cpp
  187. ===================================================================
  188. --- src/ship_cmd.cpp    (revision 27829)
  189. +++ src/ship_cmd.cpp    (working copy)
  190. @@ -138,30 +138,17 @@
  191.     result->Set(_ship_sprites[spritenum] + direction);
  192.  }
  193.  
  194. -static const Depot *FindClosestShipDepot(const Vehicle *v, uint max_distance)
  195. +static FindDepotData FindClosestReachableShipDepot(const Ship *v, int max_distance)
  196.  {
  197. -   /* Find the closest depot */
  198. -   const Depot *depot;
  199. -   const Depot *best_depot = NULL;
  200. -   /* If we don't have a maximum distance, i.e. distance = 0,
  201. -    * we want to find any depot so the best distance of no
  202. -    * depot must be more than any correct distance. On the
  203. -    * other hand if we have set a maximum distance, any depot
  204. -    * further away than max_distance can safely be ignored. */
  205. -   uint best_dist = max_distance == 0 ? UINT_MAX : max_distance + 1;
  206. +   if (IsShipDepotTile(v->tile)) return FindDepotData(v->tile, 0);
  207.  
  208. -   FOR_ALL_DEPOTS(depot) {
  209. -       TileIndex tile = depot->xy;
  210. -       if (IsShipDepotTile(tile) && IsTileOwner(tile, v->owner)) {
  211. -           uint dist = DistanceManhattan(tile, v->tile);
  212. -           if (dist < best_dist) {
  213. -               best_dist = dist;
  214. -               best_depot = depot;
  215. -           }
  216. -       }
  217. +   switch (_settings_game.pf.pathfinder_for_ships) {
  218. +// case VPF_OPF: return OPFShipFindNearestDepot(v, max_distance); //TODO
  219. +// case VPF_NPF: return NPFShipFindNearestDepot(v, max_distance); //TODO
  220. +   case VPF_YAPF: return YapfShipFindNearestDepot(v, max_distance);
  221. +
  222. +   default: NOT_REACHED();
  223.     }
  224. -
  225. -   return best_depot;
  226.  }
  227.  
  228.  static void CheckIfShipNeedsService(Vehicle *v)
  229. @@ -180,9 +167,9 @@
  230.         default: NOT_REACHED();
  231.     }
  232.  
  233. -   const Depot *depot = FindClosestShipDepot(v, max_distance);
  234. +   const FindDepotData depot = FindClosestReachableShipDepot(Ship::From(v), max_distance);
  235.  
  236. -   if (depot == NULL) {
  237. +   if (depot.best_length == UINT_MAX) {
  238.         if (v->current_order.IsType(OT_GOTO_DEPOT)) {
  239.             v->current_order.MakeDummy();
  240.             SetWindowWidgetDirty(WC_VEHICLE_VIEW, v->index, WID_VV_START_STOP);
  241. @@ -190,8 +177,8 @@
  242.         return;
  243.     }
  244.  
  245. -   v->current_order.MakeGoToDepot(depot->index, ODTFB_SERVICE);
  246. -   v->dest_tile = depot->xy;
  247. +   v->current_order.MakeGoToDepot(GetDepotIndex(depot.tile), ODTFB_SERVICE);
  248. +   v->dest_tile = depot.tile;
  249.     SetWindowWidgetDirty(WC_VEHICLE_VIEW, v->index, WID_VV_START_STOP);
  250.  }
  251.  
  252. @@ -712,12 +699,11 @@
  253.  
  254.  bool Ship::FindClosestDepot(TileIndex *location, DestinationID *destination, bool *reverse)
  255.  {
  256. -   const Depot *depot = FindClosestShipDepot(this, 0);
  257. +   FindDepotData rfdd = FindClosestReachableShipDepot(this, 0);
  258. +   if (rfdd.best_length == UINT_MAX) return false;
  259.  
  260. -   if (depot == NULL) return false;
  261. +   if (location != NULL) *location = rfdd.tile;
  262. +   if (destination != NULL) *destination = GetDepotIndex(rfdd.tile);
  263.  
  264. -   if (location    != NULL) *location    = depot->xy;
  265. -   if (destination != NULL) *destination = depot->index;
  266. -
  267.     return true;
  268.  }
Posted by Anonymous at 26 Mar 2017, 23:13:14 UTC
Language: diff • Views: 739

Version history

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

Comments