Loading

Revision differences

Return to paste
Old revision #phoeeb6paNew revision #pbcgoaplf
1Index: src/pathfinder/follow_track.hpp  1Index: src/pathfinder/npf/npf.cpp
2===================================================================  2===================================================================
3--- src/pathfinder/follow_track.hpp    (revision 27829)  3--- src/pathfinder/npf/npf.cpp    (revision 27833)
4+++ src/pathfinder/follow_track.hpp    (working copy)  4+++ src/pathfinder/npf/npf.cpp    (working copy)
5@@ -438,6 +438,21 @@  5@@ -536,8 +536,13 @@
6                 return true;  6     AyStarUserData *user = (AyStarUserData *)as->user_data;
7             }  7     /* It's not worth caching the result with NPF_FLAG_IS_TARGET here as below,
8         }  8      * since checking the cache not that much faster than the actual check */
9+  9-    return IsDepotTypeTile(current->path.node.tile, user->type) ?
10+        if (IsWaterTT()) {  10-        AYSTAR_FOUND_END_NODE : AYSTAR_DONE;
11+            /* if we reached a dead end, we can reverse the ship and continue moving */  11+    if (user->type != TRANSPORT_WATER) {
12+            m_exitdir = ReverseDiagDir(m_exitdir);  12+        return IsDepotTypeTile(current->path.node.tile, user->type) ?
13+            /* new tile will be the same as old one */  13+            AYSTAR_FOUND_END_NODE : AYSTAR_DONE;
14+            m_new_tile = m_old_tile;  14+    } else {
15+            /* set new trackdir bits to all reachable trackdirs */  15+        return IsShipDepotTile(current->path.node.tile) && GetShipDepotPart(current->path.node.tile) == DEPOT_PART_NORTH && IsTileOwner(current->path.node.tile, user->owner) ?
16+            QueryNewTileTrackStatus();  16+            AYSTAR_FOUND_END_NODE : AYSTAR_DONE;
17+            m_new_td_bits &= DiagdirReachesTrackdirs(m_exitdir);  17+    }
18+            if (m_new_td_bits != TRACKDIR_BIT_NONE) {  18 }
19+                /* we have some trackdirs reachable after reversal */  19 
20+                return true;  20 /** Find any safe and free tile. */
21+            }  21@@ -1161,6 +1166,24 @@
22+        }  22 
23+  23 /*** Ships ***/
24         m_err = EC_NO_WAY;  24 
25         return false;  25+FindDepotData NPFShipFindNearestDepot(const Ship *v, int max_distance)
26     }  26+{
   27+    Trackdir trackdir = v->GetVehicleTrackdir();
   28+    Trackdir trackdir_rev = ReverseTrackdir(trackdir);
   29+    NPFFindStationOrTileData fstd;
   30+    fstd.v = v;
   31+    fstd.reserve_path = false;
   32+
   33+    assert(trackdir != INVALID_TRACKDIR);
   34+    AyStarUserData user = { v->owner, TRANSPORT_WATER, INVALID_RAILTYPES, ROADTYPES_NONE };
   35+    NPFFoundTargetData ftd = NPFRouteToDepotBreadthFirstTwoWay(v->tile, trackdir, false, v->tile, trackdir_rev, false, &fstd, &user, NPF_INFINITE_PENALTY);
   36+    if (ftd.best_bird_dist != 0) return FindDepotData();
   37+
   38+    /* Found target */
   39+    /* Our caller wants the distance to depot. We provide it in distance manhattan */
   40+    return FindDepotData(ftd.node.tile, DistanceManhattan(v->tile, ftd.node.tile), NPFGetFlag(&ftd.node, NPF_FLAG_REVERSE));
   41+}
   42+
   43 Track NPFShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found)
   44 {
   45     NPFFindStationOrTileData fstd;
   46Index: src/pathfinder/npf/npf_func.h
   47===================================================================
   48--- src/pathfinder/npf/npf_func.h    (revision 27833)
   49+++ src/pathfinder/npf/npf_func.h    (working copy)
   50@@ -39,6 +39,14 @@
   51 Trackdir NPFRoadVehicleChooseTrack(const RoadVehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool &path_found);
   52 
   53 /**
   54+ * Used when user sends ship to the nearest depot or if ship needs servicing using NPF
   55+ * @param v            ship that needs to go to some depot
   56+ * @param max_distance not used
   57+ * @return             the data about the depot
   58+ */
   59+FindDepotData NPFShipFindNearestDepot(const Ship *v, int max_distance);
   60+
   61+/**
   62  * Finds the best path for given ship using NPF.
   63  * @param v        the ship that needs to find a path
   64  * @param tile     the tile to find the path from (should be next tile the ship is about to enter)
   65Index: src/pathfinder/opf/opf_ship.cpp
   66===================================================================
   67--- src/pathfinder/opf/opf_ship.cpp    (revision 27833)
   68+++ src/pathfinder/opf/opf_ship.cpp    (working copy)
   69@@ -14,6 +14,7 @@
   70 #include "../../tunnelbridge.h"
   71 #include "../../ship.h"
   72 #include "../../core/random_func.hpp"
   73+#include "../pathfinder_type.h"
   74 
   75 #include "../../safeguards.h"
   76 
   77@@ -212,3 +213,8 @@
   78     if (dist <= distr) return track;
   79     return INVALID_TRACK; // We could better reverse
   80 }
   81+
   82+FindDepotData OPFShipFindNearestDepot(const Ship *v, int max_distance) // todo
   83+{
   84+    return FindDepotData();
   85+}
   86Index: src/pathfinder/opf/opf_ship.h
   87===================================================================
   88--- src/pathfinder/opf/opf_ship.h    (revision 27833)
   89+++ src/pathfinder/opf/opf_ship.h    (working copy)
   90@@ -28,4 +28,13 @@
   91  */
   92 Track OPFShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found);
   93 
   94+/**
   95+ * Used when user sends ship to the nearest depot or if ship needs servicing using OPF.
   96+ * @todo               this is just a placeholder, it's currently not implemented
   97+ * @param v            vehicle that needs to go to some depot
   98+ * @param max_distance not used
   99+ * @return             the data about the depot
   100+ */
   101+FindDepotData OPFShipFindNearestDepot(const Ship *v, int max_distance);
   102+
   103 #endif /* OPF_SHIP_H */
27Index: src/pathfinder/yapf/yapf.h  104Index: src/pathfinder/yapf/yapf.h  
28===================================================================  105===================================================================  
29--- src/pathfinder/yapf/yapf.h    (revision 27829)  29--- src/pathfinder/yapf/yapf.h    (revision 27833)
30+++ src/pathfinder/yapf/yapf.h    (working copy)  107+++ src/pathfinder/yapf/yapf.h    (working copy)  
31@@ -97,4 +97,14 @@  31@@ -97,4 +97,12 @@
32  */  109  */  
33 bool YapfTrainFindNearestSafeTile(const Train *v, TileIndex tile, Trackdir td, bool override_railtype);  110 bool YapfTrainFindNearestSafeTile(const Train *v, TileIndex tile, Trackdir td, bool override_railtype);  
34   111   
35+/**  112+/**  
36+ * Used when user sends ship to the nearest depot or if ship needs servicing using YAPF.  113+ * 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  114+ * @param v            vehicle that needs to go to some depot  
38+ * @param max_distance max distance (in pathfinder penalty) from the current vehicle position  38+ * @param max_distance not used
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  116+ * @return             the data about the depot  
42+ */  117+ */  
43+FindDepotData YapfShipFindNearestDepot(const Ship *v, int max_distance);  118+FindDepotData YapfShipFindNearestDepot(const Ship *v, int max_distance);  
44+  119+  
45 #endif /* YAPF_H */  120 #endif /* YAPF_H */  
46Index: 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;    
72Index: src/pathfinder/yapf/yapf_ship.cpp  121Index: src/pathfinder/yapf/yapf_ship.cpp  
73===================================================================  122===================================================================  
74--- src/pathfinder/yapf/yapf_ship.cpp    (revision 27829)  74--- src/pathfinder/yapf/yapf_ship.cpp    (revision 27833)
75+++ src/pathfinder/yapf/yapf_ship.cpp    (working copy)  124+++ src/pathfinder/yapf/yapf_ship.cpp    (working copy)  
76@@ -139,6 +139,31 @@  76@@ -139,6 +139,48 @@
77         assert(best_trackdir == td1 || best_trackdir == td2);  126         assert(best_trackdir == td1 || best_trackdir == td2);  
78         return best_trackdir == td2;  127         return best_trackdir == td2;  
79     }  128     }  
  129+  
  130+    static bool stFindNearestDepot(const Ship *v, TileIndex tile, Trackdir td1, Trackdir td2, TileIndex *depot_tile, bool *reversed)  
  131+    {  
  132+        Tpf pf;  
  133+        bool result = pf.FindNearestDepot(v, tile, td1, td2, depot_tile, reversed);  
  134+        return result;  
  135+    }  
80+  136+  
81+    /**  137+    /**  
82+     * Find the best depot for a ship.  138+     * Find the best depot for a ship.  
83+     * @param v Vehicle  139+     * @param v Vehicle  
84+     * @param tile Tile of the vehicle.  140+     * @param tile Tile of the vehicle.  
85+     * @param td Trackdir of the vehicle.  85+     * @param td1 Trackdir of the vehicle.
86+     * @param max_distance max length (penalty) for paths.  86+     * @param td2 reversed Trackdir of the vehicle.
87+     * @todo max_distance not used by YAPF for ships.  87+     * @param depot_tile the tile of the depot.
88+     *       It can be removed or copy the SetMaxCost() strategy  88+     * @param reversed whether the path to depot was found on reversed Trackdir.
89+     *       applied in YAPF for rail. The best depot can be at    
90+     *       a distance greater than max_distance.    
91+     */  145+     */  
92+    static FindDepotData FindNearestDepot(const Ship *v, TileIndex tile, Trackdir td, int max_distance)  92+    inline bool FindNearestDepot(const Ship *v, TileIndex tile, Trackdir td1, Trackdir td2, TileIndex *depot_tile, bool *reversed)
93+    {  147+    {  
94+        Tpf pf;  148+        Tpf pf;  
95+        /* Set origin. */  149+        /* Set origin. */  
96+        pf.SetOrigin(tile, TrackdirToTrackdirBits(td));  150+        pf.SetOrigin(tile, TrackdirToTrackdirBits(td1) | TrackdirToTrackdirBits(td2));
97+  151+
98+        /* Find the best path and return if no depot is found. */  152+        /* find the best path */
99+        if (!pf.FindPath(v)) return FindDepotData();  153+        bool bFound = pf.FindPath(v);
100+  154+        if (!bFound) return false;
101+        /* Return the cost of the best path and its depot. */  155+
   156+        /* some path found
   157+         * get found depot tile */
102+        Node *n = pf.GetBestNode();  158+        Node *n = pf.GetBestNode();  
103+        return FindDepotData(n->m_segment_last_tile, n->m_cost);  159+        *depot_tile = n->m_key.m_tile;
   160+
   161+        /* walk through the path back to the origin */
   162+        Node *pNode = n;
   163+        while (pNode->m_parent != NULL) {
   164+            pNode = pNode->m_parent;
   165+        }
   166+
   167+        /* if the origin node is the ship's Trackdir then we didn't reverse */
   168+        *reversed = (pNode->m_key.m_td != td1);
   169+        return true;
104+    }  170+    }  
105 };  171 };  
106   172   
107 /** Cost Provider module of YAPF for ships */  173 /** Cost Provider module of YAPF for ships */  
108@@ -188,15 +213,53 @@  108@@ -188,15 +230,54 @@
109     }  175     }  
110 };  176 };  
111   177   
… … 
127+    /** Called by YAPF to detect if node ends in the desired destination */  193+    /** Called by YAPF to detect if node ends in the desired destination */  
128+    inline bool PfDetectDestination(Node &n)  194+    inline bool PfDetectDestination(Node &n)  
129+    {  195+    {  
130+        bool bDest = IsShipDepotTile(n.m_segment_last_tile) && GetShipDepotPart(n.m_segment_last_tile) == DEPOT_PART_NORTH;  196+       
   197+        bool bDest = (IsShipDepotTile(n.m_key.m_tile) && GetShipDepotPart(n.m_key.m_tile) == DEPOT_PART_NORTH) && IsTileOwner(n.m_key.m_tile, Yapf().GetVehicle()->owner);
131+        return bDest;  198+        return bDest;  
132+    }  199+    }  
133+  200+  
134+    inline bool PfDetectDestinationTile(TileIndex tile, Trackdir trackdir)  201+    inline bool PfDetectDestinationTile(TileIndex tile, Trackdir trackdir)  
135+    {  202+    {  
136+        return IsShipDepotTile(n.m_segment_last_tile) && GetShipDepotPart(n.m_segment_last_tile) == DEPOT_PART_NORTH;  136+        return (IsShipDepotTile(n.m_key.m_tile) && GetShipDepotPart(n.m_key.m_tile) == DEPOT_PART_NORTH) && IsTileOwner(n.m_key.m_tile, Yapf().GetVehicle()->owner);
137+    }  204+    }  
138+  205+  
139+    /**  206+    /**  
… … 
161   228   
162     /** Tpf - pathfinder type */  229     /** Tpf - pathfinder type */  
163     typedef Tpf_                              Tpf;  230     typedef Tpf_                              Tpf;  
164@@ -215,12 +278,16 @@  164@@ -215,12 +296,16 @@
165 };  232 };  
166   233   
167 /* YAPF type 1 - uses TileIndex/Trackdir as Node key, allows 90-deg turns */  234 /* YAPF type 1 - uses TileIndex/Trackdir as Node key, allows 90-deg turns */  
168-struct CYapfShip1 : CYapfT<CYapfShip_TypesT<CYapfShip1, CFollowTrackWater    , CShipNodeListTrackDir> > {};  235-struct CYapfShip1 : CYapfT<CYapfShip_TypesT<CYapfShip1, CFollowTrackWater    , CShipNodeListTrackDir> > {};  
169+struct CYapfShip1         : CYapfT<CYapfShip_TypesT<CYapfShip1        , CFollowTrackWater    , CShipNodeListTrackDir, CYapfDestinationTileT > > {};  169+struct CYapfShip1         : CYapfT<CYapfShip_TypesT<CYapfShip1        , CFollowTrackWater    , CShipNodeListTrackDir, CYapfDestinationTileT> > {};
170 /* YAPF type 2 - uses TileIndex/DiagDirection as Node key, allows 90-deg turns */  237 /* YAPF type 2 - uses TileIndex/DiagDirection as Node key, allows 90-deg turns */  
171-struct CYapfShip2 : CYapfT<CYapfShip_TypesT<CYapfShip2, CFollowTrackWater    , CShipNodeListExitDir > > {};  238-struct CYapfShip2 : CYapfT<CYapfShip_TypesT<CYapfShip2, CFollowTrackWater    , CShipNodeListExitDir > > {};  
172+struct CYapfShip2         : CYapfT<CYapfShip_TypesT<CYapfShip2        , CFollowTrackWater    , CShipNodeListExitDir , CYapfDestinationTileT > > {};  172+struct CYapfShip2         : CYapfT<CYapfShip_TypesT<CYapfShip2        , CFollowTrackWater    , CShipNodeListExitDir , CYapfDestinationTileT> > {};
173 /* YAPF type 3 - uses TileIndex/Trackdir as Node key, forbids 90-deg turns */  240 /* YAPF type 3 - uses TileIndex/Trackdir as Node key, forbids 90-deg turns */  
174-struct CYapfShip3 : CYapfT<CYapfShip_TypesT<CYapfShip3, CFollowTrackWaterNo90, CShipNodeListTrackDir> > {};  241-struct CYapfShip3 : CYapfT<CYapfShip_TypesT<CYapfShip3, CFollowTrackWaterNo90, CShipNodeListTrackDir> > {};  
175+struct CYapfShip3         : CYapfT<CYapfShip_TypesT<CYapfShip3        , CFollowTrackWaterNo90, CShipNodeListTrackDir, CYapfDestinationTileT > > {};  175+struct CYapfShip3         : CYapfT<CYapfShip_TypesT<CYapfShip3        , CFollowTrackWaterNo90, CShipNodeListTrackDir, CYapfDestinationTileT> > {};
176   176 
177+struct CYapfShipAnyDepot1 : CYapfT<CYapfShip_TypesT<CYapfShipAnyDepot1, CFollowTrackWater    , CShipNodeListTrackDir, CYapfDestinationAnyDepotShipT > > {};  177+struct CYapfShipAnyDepot1 : CYapfT<CYapfShip_TypesT<CYapfShipAnyDepot1, CFollowTrackWater    , CShipNodeListTrackDir, CYapfDestinationAnyDepotShipT> > {};
178+struct CYapfShipAnyDepot2 : CYapfT<CYapfShip_TypesT<CYapfShipAnyDepot2, CFollowTrackWater    , CShipNodeListExitDir , CYapfDestinationAnyDepotShipT > > {};  178+struct CYapfShipAnyDepot2 : CYapfT<CYapfShip_TypesT<CYapfShipAnyDepot2, CFollowTrackWater    , CShipNodeListExitDir , CYapfDestinationAnyDepotShipT> > {};
179+struct CYapfShipAnyDepot3 : CYapfT<CYapfShip_TypesT<CYapfShipAnyDepot3, CFollowTrackWaterNo90, CShipNodeListTrackDir, CYapfDestinationAnyDepotShipT > > {};  179+struct CYapfShipAnyDepot3 : CYapfT<CYapfShip_TypesT<CYapfShipAnyDepot3, CFollowTrackWaterNo90, CShipNodeListTrackDir, CYapfDestinationAnyDepotShipT> > {};
180+  247+  
181 /** Ship controller helper - path finder invoker */  248 /** Ship controller helper - path finder invoker */  
182 Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found)  249 Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found)  
183 {  250 {  
184@@ -239,6 +306,27 @@  184@@ -239,6 +324,31 @@
185     return (td_ret != INVALID_TRACKDIR) ? TrackdirToTrack(td_ret) : INVALID_TRACK;  252     return (td_ret != INVALID_TRACKDIR) ? TrackdirToTrack(td_ret) : INVALID_TRACK;  
186 }  253 }  
187   254   
188+FindDepotData YapfShipFindNearestDepot(const Ship *v, int max_distance)  255+FindDepotData YapfShipFindNearestDepot(const Ship *v, int max_distance)  
189+{  256+{  
  257+    FindDepotData fdd;  
  258+  
  259+    Trackdir td = v->GetVehicleTrackdir();  
  260+    Trackdir td_rev = ReverseTrackdir(td);  
190+    TileIndex tile = v->tile;  261+    TileIndex tile = v->tile;  
191+    Trackdir trackdir = v->GetVehicleTrackdir();  191+
192+    if ((TrackStatusToTrackdirBits(GetTileTrackStatus(tile, TRANSPORT_WATER, 0)) & TrackdirToTrackdirBits(trackdir)) == 0) {    
193+        return FindDepotData();    
194+    }    
195+    /* default is YAPF type 2 */  263+    /* default is YAPF type 2 */  
196+    typedef FindDepotData(*PfnFindNearestDepot)(const Ship*, TileIndex, Trackdir, int);  196+    typedef bool(*PfnFindNearestDepot)(const Ship*, TileIndex, Trackdir, Trackdir, TileIndex*, bool*);
197+    PfnFindNearestDepot pfnFindNearestDepot = &CYapfShipAnyDepot2::FindNearestDepot;  197+    PfnFindNearestDepot pfnFindNearestDepot = &CYapfShipAnyDepot2::stFindNearestDepot;
198+  266+  
199+    /* check if non-default YAPF type should be used */  267+    /* check if non-default YAPF type should be used */  
200+    if (_settings_game.pf.forbid_90_deg) {  268+    if (_settings_game.pf.forbid_90_deg) {  
201+        pfnFindNearestDepot = &CYapfShipAnyDepot3::FindNearestDepot; // Trackdir, forbid 90-deg  201+        pfnFindNearestDepot = &CYapfShipAnyDepot3::stFindNearestDepot; // Trackdir, forbid 90-deg
202+    } else if (_settings_game.pf.yapf.disable_node_optimization) {  270+    } else if (_settings_game.pf.yapf.disable_node_optimization) {  
203+        pfnFindNearestDepot = &CYapfShipAnyDepot1::FindNearestDepot; // Trackdir, allow 90-deg  271+        pfnFindNearestDepot = &CYapfShipAnyDepot1::stFindNearestDepot; // Trackdir, allow 90-deg
204+    }  272+    }
205+  273+
206+    return pfnFindNearestDepot(v, tile, trackdir, max_distance);  274+    bool ret = pfnFindNearestDepot(v, tile, td, td_rev, &fdd.tile, &fdd.reverse);
   275+
   276+    fdd.best_length = ret ? DistanceManhattan(tile, fdd.tile) : UINT_MAX; // distance manhattan or NOT_FOUND
   277+    return fdd;
207+}  278+}  
208+  279+  
209 bool YapfShipCheckReverse(const Ship *v)  280 bool YapfShipCheckReverse(const Ship *v)  
… … 
211     Trackdir td = v->GetVehicleTrackdir();  282     Trackdir td = v->GetVehicleTrackdir();  
212Index: src/ship_cmd.cpp  283Index: src/ship_cmd.cpp  
213===================================================================  284===================================================================  
214--- src/ship_cmd.cpp    (revision 27829)  214--- src/ship_cmd.cpp    (revision 27833)
215+++ src/ship_cmd.cpp    (working copy)  286+++ src/ship_cmd.cpp    (working copy)  
216@@ -138,30 +138,17 @@  216@@ -138,7 +138,7 @@
217     result->Set(_ship_sprites[spritenum] + direction);  288     result->Set(_ship_sprites[spritenum] + direction);  
218 }  289 }  
219   290   
220-static const Depot *FindClosestShipDepot(const Vehicle *v, uint max_distance)  291-static const Depot *FindClosestShipDepot(const Vehicle *v, uint max_distance)  
  292+static FindDepotData FindClosestShipDepot(const Ship *v, uint max_distance)  
  293 {  
  294     /* Find the closest depot */  
  295     const Depot *depot;  
  296@@ -161,9 +161,27 @@  
  297         }  
  298     }  
  299   
  300-    return best_depot;  
  301+    FindDepotData fdd;  
  302+    if (best_depot != NULL) {  
  303+        fdd.best_length = best_dist;  
  304+        fdd.tile = best_depot->xy;  
  305+    }  
  306+    return fdd;  
  307 }  
  308   
221+static FindDepotData FindClosestReachableShipDepot(const Ship *v, int max_distance)  309+static FindDepotData FindClosestReachableShipDepot(const Ship *v, int max_distance)  
222 {  222+{
223-    /* Find the closest depot */  223+    if ((IsShipDepotTile(v->tile) && GetShipDepotPart(v->tile) == DEPOT_PART_NORTH) && IsTileOwner(v->tile, v->owner)) return FindDepotData(v->tile, 0);
224-    const Depot *depot;  224+
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) {  313+    switch (_settings_game.pf.pathfinder_for_ships) {  
244+//    case VPF_OPF: return OPFShipFindNearestDepot(v, max_distance); //TODO  244+    case VPF_OPF: return OPFShipFindNearestDepot(v, max_distance);
245+//    case VPF_NPF: return NPFShipFindNearestDepot(v, max_distance); //TODO  245+    case VPF_NPF: return NPFShipFindNearestDepot(v, max_distance);
246+    case VPF_YAPF: return YapfShipFindNearestDepot(v, max_distance);  316+    case VPF_YAPF: return YapfShipFindNearestDepot(v, max_distance);  
247+  317+  
248+    default: NOT_REACHED();  318+    default: NOT_REACHED();  
249     }  249+    }
250-  250+}
251-    return best_depot;  251+
252 }    
253     
254 static void CheckIfShipNeedsService(Vehicle *v)  322 static void CheckIfShipNeedsService(Vehicle *v)  
255@@ -180,9 +167,9 @@  323 {
   324     if (Company::Get(v->owner)->settings.vehicle.servint_ships == 0 || !v->NeedsAutomaticServicing()) return;
   325@@ -180,9 +198,9 @@
256         default: NOT_REACHED();  326         default: NOT_REACHED();  
257     }  327     }  
258   328   
259-    const Depot *depot = FindClosestShipDepot(v, max_distance);  329-    const Depot *depot = FindClosestShipDepot(v, max_distance);  
260+    const FindDepotData depot = FindClosestReachableShipDepot(Ship::From(v), max_distance);  260+    const FindDepotData sfdd = FindClosestReachableShipDepot(Ship::From(v), max_distance);
261   331   
262-    if (depot == NULL) {  332-    if (depot == NULL) {  
263+    if (depot.best_length == UINT_MAX) {  263+    if (sfdd.best_length == UINT_MAX || sfdd.best_length >= max_distance) {
264         if (v->current_order.IsType(OT_GOTO_DEPOT)) {  334         if (v->current_order.IsType(OT_GOTO_DEPOT)) {  
265             v->current_order.MakeDummy();  335             v->current_order.MakeDummy();  
266             SetWindowWidgetDirty(WC_VEHICLE_VIEW, v->index, WID_VV_START_STOP);  336             SetWindowWidgetDirty(WC_VEHICLE_VIEW, v->index, WID_VV_START_STOP);  
267@@ -190,8 +177,8 @@  267@@ -190,8 +208,8 @@
268         return;  338         return;  
269     }  339     }  
270   340   
271-    v->current_order.MakeGoToDepot(depot->index, ODTFB_SERVICE);  341-    v->current_order.MakeGoToDepot(depot->index, ODTFB_SERVICE);  
272-    v->dest_tile = depot->xy;  342-    v->dest_tile = depot->xy;  
273+    v->current_order.MakeGoToDepot(GetDepotIndex(depot.tile), ODTFB_SERVICE);  273+    v->current_order.MakeGoToDepot(GetDepotIndex(sfdd.tile), ODTFB_SERVICE);
274+    v->dest_tile = depot.tile;  274+    v->dest_tile = sfdd.tile;
275     SetWindowWidgetDirty(WC_VEHICLE_VIEW, v->index, WID_VV_START_STOP);  345     SetWindowWidgetDirty(WC_VEHICLE_VIEW, v->index, WID_VV_START_STOP);  
276 }  346 }  
277   347   
278@@ -712,12 +699,11 @@  278@@ -712,12 +730,15 @@
279   349   
280 bool Ship::FindClosestDepot(TileIndex *location, DestinationID *destination, bool *reverse)  350 bool Ship::FindClosestDepot(TileIndex *location, DestinationID *destination, bool *reverse)  
281 {  351 {  
282-    const Depot *depot = FindClosestShipDepot(this, 0);  352-    const Depot *depot = FindClosestShipDepot(this, 0);  
283+    FindDepotData rfdd = FindClosestReachableShipDepot(this, 0);  353+    FindDepotData sfdd = FindClosestReachableShipDepot(this, 0);
284+    if (rfdd.best_length == UINT_MAX) return false;  354+    if (sfdd.best_length == UINT_MAX) {
   355+        sfdd = FindClosestShipDepot(this, 0);
   356+        if (sfdd.best_length == UINT_MAX) return false;
   357+    }
285   358   
286-    if (depot == NULL) return false;  359-    if (depot == NULL) return false;  
287+    if (location != NULL) *location = rfdd.tile;  360+    if (location    != NULL) *location = sfdd.tile;
288+    if (destination != NULL) *destination = GetDepotIndex(rfdd.tile);  361+    if (destination != NULL) *destination = GetDepotIndex(sfdd.tile);
   362+    if (reverse     != NULL) *reverse = sfdd.reverse;
289   363   
290-    if (location    != NULL) *location    = depot->xy;  364-    if (location    != NULL) *location    = depot->xy;  
291-    if (destination != NULL) *destination = depot->index;  365-    if (destination != NULL) *destination = depot->index;