Index: src/pathfinder/follow_track.hpp
===================================================================
--- src/pathfinder/follow_track.hpp (revision 27829)
+++ src/pathfinder/follow_track.hpp (working copy)
@@ -438,6 +438,21 @@
return true;
}
}
+
+ if (IsWaterTT()) {
+ /* if we reached a dead end, we can reverse the ship and continue moving */
+ m_exitdir = ReverseDiagDir(m_exitdir);
+ /* new tile will be the same as old one */
+ m_new_tile = m_old_tile;
+ /* set new trackdir bits to all reachable trackdirs */
+ QueryNewTileTrackStatus();
+ m_new_td_bits &= DiagdirReachesTrackdirs(m_exitdir);
+ if (m_new_td_bits != TRACKDIR_BIT_NONE) {
+ /* we have some trackdirs reachable after reversal */
+ return true;
+ }
+ }
+
m_err = EC_NO_WAY;
return false;
}
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,31 @@
assert(best_trackdir == td1 || best_trackdir == td2);
return best_trackdir == td2;
}
+
+ /**
+ * Find the best depot for a ship.
+ * @param v Vehicle
+ * @param tile Tile of the vehicle.
+ * @param td Trackdir of the vehicle.
+ * @param max_distance max length (penalty) for paths.
+ * @todo max_distance not used by YAPF for ships.
+ * It can be removed or copy the SetMaxCost() strategy
+ * applied in YAPF for rail. The best depot can be at
+ * a distance greater than max_distance.
+ */
+ static FindDepotData FindNearestDepot(const Ship *v, TileIndex tile, Trackdir td, int max_distance)
+ {
+ Tpf pf;
+ /* Set origin. */
+ pf.SetOrigin(tile, TrackdirToTrackdirBits(td));
+
+ /* Find the best path and return if no depot is found. */
+ if (!pf.FindPath(v)) return FindDepotData();
+
+ /* Return the cost of the best path and its depot. */
+ Node *n = pf.GetBestNode();
+ return FindDepotData(n->m_segment_last_tile, n->m_cost);
+ }
};
/** Cost Provider module of YAPF for ships */
@@ -188,15 +213,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 +278,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 +306,27 @@
return (td_ret != INVALID_TRACKDIR) ? TrackdirToTrack(td_ret) : INVALID_TRACK;
}
+FindDepotData YapfShipFindNearestDepot(const Ship *v, int max_distance)
+{
+ TileIndex tile = v->tile;
+ Trackdir trackdir = v->GetVehicleTrackdir();
+ if ((TrackStatusToTrackdirBits(GetTileTrackStatus(tile, TRANSPORT_WATER, 0)) & TrackdirToTrackdirBits(trackdir)) == 0) {
+ return FindDepotData();
+ }
+ /* default is YAPF type 2 */
+ typedef FindDepotData(*PfnFindNearestDepot)(const Ship*, TileIndex, Trackdir, int);
+ PfnFindNearestDepot pfnFindNearestDepot = &CYapfShipAnyDepot2::FindNearestDepot;
+
+ /* check if non-default YAPF type should be used */
+ if (_settings_game.pf.forbid_90_deg) {
+ pfnFindNearestDepot = &CYapfShipAnyDepot3::FindNearestDepot; // Trackdir, forbid 90-deg
+ } else if (_settings_game.pf.yapf.disable_node_optimization) {
+ pfnFindNearestDepot = &CYapfShipAnyDepot1::FindNearestDepot; // Trackdir, allow 90-deg
+ }
+
+ return pfnFindNearestDepot(v, tile, trackdir, max_distance);
+}
+
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 rfdd = FindClosestReachableShipDepot(this, 0);
+ if (rfdd.best_length == UINT_MAX) return false;
- if (depot == NULL) return false;
+ if (location != NULL) *location = rfdd.tile;
+ if (destination != NULL) *destination = GetDepotIndex(rfdd.tile);
- if (location != NULL) *location = depot->xy;
- if (destination != NULL) *destination = depot->index;
-
return true;
}