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;
 }