Index: src/pathfinder/yapf/yapf.h
===================================================================
--- src/pathfinder/yapf/yapf.h (revision 27829)
+++ src/pathfinder/yapf/yapf.h (working copy)
@@ -97,4 +97,14 @@
*/
bool YapfTrainFindNearestSafeTile(const Train *v, TileIndex tile, Trackdir td, bool override_railtype);
+/**
+ * Used when user sends ship to the nearest depot or if ship needs servicing using YAPF.
+ * @param v vehicle that needs to go to some depot
+ * @param max_distance max distance (in pathfinder penalty) from the current vehicle position
+ * (used also as optimization - the pathfinder can stop path finding if max_penalty
+ * was reached and no depot was seen)
+ * @return the data about the depot
+ */
+FindDepotData YapfShipFindNearestDepot(const Ship *v, int max_distance);
+
#endif /* YAPF_H */
Index: src/pathfinder/yapf/yapf_node_ship.hpp
===================================================================
--- src/pathfinder/yapf/yapf_node_ship.hpp (revision 27829)
+++ src/pathfinder/yapf/yapf_node_ship.hpp (working copy)
@@ -14,8 +14,20 @@
/** Yapf Node for ships */
template <class Tkey_>
-struct CYapfShipNodeT : CYapfNodeT<Tkey_, CYapfShipNodeT<Tkey_> > { };
+struct CYapfShipNodeT : CYapfNodeT<Tkey_, CYapfShipNodeT<Tkey_> > {
+ typedef CYapfNodeT<Tkey_, CYapfShipNodeT<Tkey_> > base;
+ TileIndex m_segment_last_tile;
+ Trackdir m_segment_last_td;
+
+ void Set(CYapfShipNodeT *parent, TileIndex tile, Trackdir td, bool is_choice)
+ {
+ base::Set(parent, tile, td, is_choice);
+ m_segment_last_tile = tile;
+ m_segment_last_td = td;
+ }
+};
+
/* now define two major node types (that differ by key type) */
typedef CYapfShipNodeT<CYapfNodeKeyExitDir> CYapfShipNodeExitDir;
typedef CYapfShipNodeT<CYapfNodeKeyTrackDir> CYapfShipNodeTrackDir;
Index: src/pathfinder/yapf/yapf_ship.cpp
===================================================================
--- src/pathfinder/yapf/yapf_ship.cpp (revision 27829)
+++ src/pathfinder/yapf/yapf_ship.cpp (working copy)
@@ -139,6 +139,43 @@
assert(best_trackdir == td1 || best_trackdir == td2);
return best_trackdir == td2;
}
+
+ static bool stFindNearestDepot(const Ship *v, TileIndex tile, Trackdir td1, Trackdir td2, TileIndex *depot_tile, bool *reversed)
+ {
+ Tpf pf;
+ bool result = pf.FindNearestDepot(v, tile, td1, td2, depot_tile, reversed);
+ return result;
+ }
+
+ /**
+ * Find the best depot for a ship.
+ * @param v Vehicle
+ * @param tile Tile of the vehicle.
+ * @param td1 Trackdir of the vehicle.
+ * @param td2 reversed Trackdir of the vehicle.
+ * @param depot_tile the tile of the depot.
+ * @param reversed whether the path to depot was found on reversed Trackdir.
+ */
+ inline bool FindNearestDepot(const Ship *v, TileIndex tile, Trackdir td1, Trackdir td2, TileIndex *depot_tile, bool *reversed)
+ {
+ Tpf pf1;
+ Tpf pf2;
+ /* Set origin. */
+ pf1.SetOrigin(tile, TrackdirToTrackdirBits(td1));
+ pf2.SetOrigin(tile, TrackdirToTrackdirBits(td2));
+
+ bool path_found1 = pf1.FindPath(v);
+ bool path_found2 = pf2.FindPath(v);
+ if (!path_found1 && !path_found2) return false;
+
+ Node *n;
+ if (path_found1 || path_found2) {
+ n = path_found1 ? pf1.GetBestNode() : pf2.GetBestNode();
+ *depot_tile = n->m_segment_last_tile;
+ *reversed = !path_found1 && path_found2;
+ }
+ return true;
+ }
};
/** Cost Provider module of YAPF for ships */
@@ -188,15 +225,53 @@
}
};
+template <class Types>
+class CYapfDestinationAnyDepotShipT
+{
+public:
+ typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class)
+ typedef typename Types::TrackFollower TrackFollower;
+ typedef typename Types::NodeList::Titem Node; ///< this will be our node type
+ typedef typename Node::Key Key; ///< key to hash tables
+
+ /** to access inherited path finder */
+ Tpf& Yapf()
+ {
+ return *static_cast<Tpf *>(this);
+ }
+
+ /** Called by YAPF to detect if node ends in the desired destination */
+ inline bool PfDetectDestination(Node &n)
+ {
+ bool bDest = IsShipDepotTile(n.m_segment_last_tile) && GetShipDepotPart(n.m_segment_last_tile) == DEPOT_PART_NORTH;
+ return bDest;
+ }
+
+ inline bool PfDetectDestinationTile(TileIndex tile, Trackdir trackdir)
+ {
+ return IsShipDepotTile(n.m_segment_last_tile) && GetShipDepotPart(n.m_segment_last_tile) == DEPOT_PART_NORTH;
+ }
+
+ /**
+ * Called by YAPF to calculate cost estimate. Calculates distance to the destination
+ * adds it to the actual cost from origin and stores the sum to the Node::m_estimate
+ */
+ inline bool PfCalcEstimate(Node &n)
+ {
+ n.m_estimate = n.m_cost;
+ return true;
+ }
+};
+
/**
* Config struct of YAPF for ships.
* Defines all 6 base YAPF modules as classes providing services for CYapfBaseT.
*/
-template <class Tpf_, class Ttrack_follower, class Tnode_list>
+template <class Tpf_, class Ttrack_follower, class Tnode_list, template <class Types> class CYapfDestinationTileT>
struct CYapfShip_TypesT
{
/** Types - shortcut for this struct type */
- typedef CYapfShip_TypesT<Tpf_, Ttrack_follower, Tnode_list> Types;
+ typedef CYapfShip_TypesT<Tpf_, Ttrack_follower, Tnode_list, CYapfDestinationTileT> Types;
/** Tpf - pathfinder type */
typedef Tpf_ Tpf;
@@ -215,12 +290,16 @@
};
/* YAPF type 1 - uses TileIndex/Trackdir as Node key, allows 90-deg turns */
-struct CYapfShip1 : CYapfT<CYapfShip_TypesT<CYapfShip1, CFollowTrackWater , CShipNodeListTrackDir> > {};
+struct CYapfShip1 : CYapfT<CYapfShip_TypesT<CYapfShip1 , CFollowTrackWater , CShipNodeListTrackDir, CYapfDestinationTileT > > {};
/* YAPF type 2 - uses TileIndex/DiagDirection as Node key, allows 90-deg turns */
-struct CYapfShip2 : CYapfT<CYapfShip_TypesT<CYapfShip2, CFollowTrackWater , CShipNodeListExitDir > > {};
+struct CYapfShip2 : CYapfT<CYapfShip_TypesT<CYapfShip2 , CFollowTrackWater , CShipNodeListExitDir , CYapfDestinationTileT > > {};
/* YAPF type 3 - uses TileIndex/Trackdir as Node key, forbids 90-deg turns */
-struct CYapfShip3 : CYapfT<CYapfShip_TypesT<CYapfShip3, CFollowTrackWaterNo90, CShipNodeListTrackDir> > {};
+struct CYapfShip3 : CYapfT<CYapfShip_TypesT<CYapfShip3 , CFollowTrackWaterNo90, CShipNodeListTrackDir, CYapfDestinationTileT > > {};
+struct CYapfShipAnyDepot1 : CYapfT<CYapfShip_TypesT<CYapfShipAnyDepot1, CFollowTrackWater , CShipNodeListTrackDir, CYapfDestinationAnyDepotShipT > > {};
+struct CYapfShipAnyDepot2 : CYapfT<CYapfShip_TypesT<CYapfShipAnyDepot2, CFollowTrackWater , CShipNodeListExitDir , CYapfDestinationAnyDepotShipT > > {};
+struct CYapfShipAnyDepot3 : CYapfT<CYapfShip_TypesT<CYapfShipAnyDepot3, CFollowTrackWaterNo90, CShipNodeListTrackDir, CYapfDestinationAnyDepotShipT > > {};
+
/** Ship controller helper - path finder invoker */
Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found)
{
@@ -239,6 +318,30 @@
return (td_ret != INVALID_TRACKDIR) ? TrackdirToTrack(td_ret) : INVALID_TRACK;
}
+FindDepotData YapfShipFindNearestDepot(const Ship *v, int max_penalty)
+{
+ FindDepotData fdd;
+
+ Trackdir td = v->GetVehicleTrackdir();
+ Trackdir td_rev = ReverseTrackdir(td);
+ TileIndex tile = v->tile;
+
+ /* default is YAPF type 2 */
+ typedef bool(*PfnFindNearestDepot)(const Ship*, TileIndex, Trackdir, Trackdir, TileIndex*, bool*);
+ PfnFindNearestDepot pfnFindNearestDepot = &CYapfShipAnyDepot2::stFindNearestDepot;
+
+ /* check if non-default YAPF type should be used */
+ if (_settings_game.pf.forbid_90_deg) {
+ pfnFindNearestDepot = &CYapfShipAnyDepot3::stFindNearestDepot; // Trackdir, forbid 90-deg
+ } else if (_settings_game.pf.yapf.disable_node_optimization) {
+ pfnFindNearestDepot = &CYapfShipAnyDepot1::stFindNearestDepot; // Trackdir, allow 90-deg
+ }
+
+ bool ret = pfnFindNearestDepot(v, tile, td, td_rev, &fdd.tile, &fdd.reverse);
+ fdd.best_length = ret ? max_penalty / 2 : UINT_MAX; // some fake distance or NOT_FOUND
+ return fdd;
+}
+
bool YapfShipCheckReverse(const Ship *v)
{
Trackdir td = v->GetVehicleTrackdir();
Index: src/ship_cmd.cpp
===================================================================
--- src/ship_cmd.cpp (revision 27829)
+++ src/ship_cmd.cpp (working copy)
@@ -138,30 +138,17 @@
result->Set(_ship_sprites[spritenum] + direction);
}
-static const Depot *FindClosestShipDepot(const Vehicle *v, uint max_distance)
+static FindDepotData FindClosestReachableShipDepot(const Ship *v, int max_distance)
{
- /* Find the closest depot */
- const Depot *depot;
- const Depot *best_depot = NULL;
- /* If we don't have a maximum distance, i.e. distance = 0,
- * we want to find any depot so the best distance of no
- * depot must be more than any correct distance. On the
- * other hand if we have set a maximum distance, any depot
- * further away than max_distance can safely be ignored. */
- uint best_dist = max_distance == 0 ? UINT_MAX : max_distance + 1;
+ if (IsShipDepotTile(v->tile) && GetShipDepotPart(v->tile) == DEPOT_PART_NORTH) return FindDepotData(v->tile, 0);
- FOR_ALL_DEPOTS(depot) {
- TileIndex tile = depot->xy;
- if (IsShipDepotTile(tile) && IsTileOwner(tile, v->owner)) {
- uint dist = DistanceManhattan(tile, v->tile);
- if (dist < best_dist) {
- best_dist = dist;
- best_depot = depot;
- }
- }
+ switch (_settings_game.pf.pathfinder_for_ships) {
+// case VPF_OPF: return OPFShipFindNearestDepot(v, max_distance); //TODO
+// case VPF_NPF: return NPFShipFindNearestDepot(v, max_distance); //TODO
+ case VPF_YAPF: return YapfShipFindNearestDepot(v, max_distance);
+
+ default: NOT_REACHED();
}
-
- return best_depot;
}
static void CheckIfShipNeedsService(Vehicle *v)
@@ -180,9 +167,9 @@
default: NOT_REACHED();
}
- const Depot *depot = FindClosestShipDepot(v, max_distance);
+ const FindDepotData depot = FindClosestReachableShipDepot(Ship::From(v), max_distance);
- if (depot == NULL) {
+ if (depot.best_length == UINT_MAX) {
if (v->current_order.IsType(OT_GOTO_DEPOT)) {
v->current_order.MakeDummy();
SetWindowWidgetDirty(WC_VEHICLE_VIEW, v->index, WID_VV_START_STOP);
@@ -190,8 +177,8 @@
return;
}
- v->current_order.MakeGoToDepot(depot->index, ODTFB_SERVICE);
- v->dest_tile = depot->xy;
+ v->current_order.MakeGoToDepot(GetDepotIndex(depot.tile), ODTFB_SERVICE);
+ v->dest_tile = depot.tile;
SetWindowWidgetDirty(WC_VEHICLE_VIEW, v->index, WID_VV_START_STOP);
}
@@ -712,12 +699,11 @@
bool Ship::FindClosestDepot(TileIndex *location, DestinationID *destination, bool *reverse)
{
- const Depot *depot = FindClosestShipDepot(this, 0);
+ FindDepotData sfdd = FindClosestReachableShipDepot(this, 0);
+ if (sfdd.best_length == UINT_MAX) return false;
- if (depot == NULL) return false;
+ if (location != NULL) *location = sfdd.tile;
+ if (destination != NULL) *destination = GetDepotIndex(sfdd.tile);
- if (location != NULL) *location = depot->xy;
- if (destination != NULL) *destination = depot->index;
-
return true;
}