Loading

FindClosestReachableShipD

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

Version history

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

Comments