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