Index: src/pathfinder/npf/npf.cpp =================================================================== --- src/pathfinder/npf/npf.cpp (revision 27833) +++ src/pathfinder/npf/npf.cpp (working copy) @@ -536,8 +536,13 @@ AyStarUserData *user = (AyStarUserData *)as->user_data; /* It's not worth caching the result with NPF_FLAG_IS_TARGET here as below, * since checking the cache not that much faster than the actual check */ - return IsDepotTypeTile(current->path.node.tile, user->type) ? - AYSTAR_FOUND_END_NODE : AYSTAR_DONE; + if (user->type != TRANSPORT_WATER) { + return IsDepotTypeTile(current->path.node.tile, user->type) ? + AYSTAR_FOUND_END_NODE : AYSTAR_DONE; + } else { + return IsShipDepotTile(current->path.node.tile) && GetShipDepotPart(current->path.node.tile) == DEPOT_PART_NORTH && IsTileOwner(current->path.node.tile, user->owner) ? + AYSTAR_FOUND_END_NODE : AYSTAR_DONE; + } } /** Find any safe and free tile. */ @@ -1161,6 +1166,24 @@ /*** Ships ***/ +FindDepotData NPFShipFindNearestDepot(const Ship *v, int max_distance) +{ + Trackdir trackdir = v->GetVehicleTrackdir(); + Trackdir trackdir_rev = ReverseTrackdir(trackdir); + NPFFindStationOrTileData fstd; + fstd.v = v; + fstd.reserve_path = false; + + assert(trackdir != INVALID_TRACKDIR); + AyStarUserData user = { v->owner, TRANSPORT_WATER, INVALID_RAILTYPES, ROADTYPES_NONE }; + NPFFoundTargetData ftd = NPFRouteToDepotBreadthFirstTwoWay(v->tile, trackdir, false, v->tile, trackdir_rev, false, &fstd, &user, NPF_INFINITE_PENALTY); + if (ftd.best_bird_dist != 0) return FindDepotData(); + + /* Found target */ + /* Our caller wants the distance to depot. We provide it in distance manhattan */ + return FindDepotData(ftd.node.tile, DistanceManhattan(v->tile, ftd.node.tile), NPFGetFlag(&ftd.node, NPF_FLAG_REVERSE)); +} + Track NPFShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found) { NPFFindStationOrTileData fstd; Index: src/pathfinder/npf/npf_func.h =================================================================== --- src/pathfinder/npf/npf_func.h (revision 27833) +++ src/pathfinder/npf/npf_func.h (working copy) @@ -39,6 +39,14 @@ Trackdir NPFRoadVehicleChooseTrack(const RoadVehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool &path_found); /** + * Used when user sends ship to the nearest depot or if ship needs servicing using NPF + * @param v ship that needs to go to some depot + * @param max_distance not used + * @return the data about the depot + */ +FindDepotData NPFShipFindNearestDepot(const Ship *v, int max_distance); + +/** * Finds the best path for given ship using NPF. * @param v the ship that needs to find a path * @param tile the tile to find the path from (should be next tile the ship is about to enter) Index: src/pathfinder/opf/opf_ship.cpp =================================================================== --- src/pathfinder/opf/opf_ship.cpp (revision 27833) +++ src/pathfinder/opf/opf_ship.cpp (working copy) @@ -14,6 +14,7 @@ #include "../../tunnelbridge.h" #include "../../ship.h" #include "../../core/random_func.hpp" +#include "../pathfinder_type.h" #include "../../safeguards.h" @@ -212,3 +213,8 @@ if (dist <= distr) return track; return INVALID_TRACK; // We could better reverse } + +FindDepotData OPFShipFindNearestDepot(const Ship *v, int max_distance) // todo +{ + return FindDepotData(); +} Index: src/pathfinder/opf/opf_ship.h =================================================================== --- src/pathfinder/opf/opf_ship.h (revision 27833) +++ src/pathfinder/opf/opf_ship.h (working copy) @@ -28,4 +28,13 @@ */ Track OPFShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found); +/** + * Used when user sends ship to the nearest depot or if ship needs servicing using OPF. + * @todo this is just a placeholder, it's currently not implemented + * @param v vehicle that needs to go to some depot + * @param max_distance not used + * @return the data about the depot + */ +FindDepotData OPFShipFindNearestDepot(const Ship *v, int max_distance); + #endif /* OPF_SHIP_H */ Index: src/pathfinder/yapf/yapf.h =================================================================== --- src/pathfinder/yapf/yapf.h (revision 27833) +++ src/pathfinder/yapf/yapf.h (working copy) @@ -97,4 +97,12 @@ */ 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 not used + * @return the data about the depot + */ +FindDepotData YapfShipFindNearestDepot(const Ship *v, int max_distance); + #endif /* YAPF_H */ Index: src/pathfinder/yapf/yapf_ship.cpp =================================================================== --- src/pathfinder/yapf/yapf_ship.cpp (revision 27833) +++ src/pathfinder/yapf/yapf_ship.cpp (working copy) @@ -139,6 +139,48 @@ 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 pf; + /* Set origin. */ + pf.SetOrigin(tile, TrackdirToTrackdirBits(td1) | TrackdirToTrackdirBits(td2)); + + /* find the best path */ + bool bFound = pf.FindPath(v); + if (!bFound) return false; + + /* some path found + * get found depot tile */ + Node *n = pf.GetBestNode(); + *depot_tile = n->m_key.m_tile; + + /* walk through the path back to the origin */ + Node *pNode = n; + while (pNode->m_parent != NULL) { + pNode = pNode->m_parent; + } + + /* if the origin node is the ship's Trackdir then we didn't reverse */ + *reversed = (pNode->m_key.m_td != td1); + return true; + } }; /** Cost Provider module of YAPF for ships */ @@ -188,15 +230,54 @@ } }; +template +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(this); + } + + /** Called by YAPF to detect if node ends in the desired destination */ + inline bool PfDetectDestination(Node &n) + { + + 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); + return bDest; + } + + inline bool PfDetectDestinationTile(TileIndex tile, Trackdir trackdir) + { + 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); + } + + /** + * 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 +template class CYapfDestinationTileT> struct CYapfShip_TypesT { /** Types - shortcut for this struct type */ - typedef CYapfShip_TypesT Types; + typedef CYapfShip_TypesT Types; /** Tpf - pathfinder type */ typedef Tpf_ Tpf; @@ -215,12 +296,16 @@ }; /* YAPF type 1 - uses TileIndex/Trackdir as Node key, allows 90-deg turns */ -struct CYapfShip1 : CYapfT > {}; +struct CYapfShip1 : CYapfT > {}; /* YAPF type 2 - uses TileIndex/DiagDirection as Node key, allows 90-deg turns */ -struct CYapfShip2 : CYapfT > {}; +struct CYapfShip2 : CYapfT > {}; /* YAPF type 3 - uses TileIndex/Trackdir as Node key, forbids 90-deg turns */ -struct CYapfShip3 : CYapfT > {}; +struct CYapfShip3 : CYapfT > {}; +struct CYapfShipAnyDepot1 : CYapfT > {}; +struct CYapfShipAnyDepot2 : CYapfT > {}; +struct CYapfShipAnyDepot3 : CYapfT > {}; + /** Ship controller helper - path finder invoker */ Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found) { @@ -239,6 +324,31 @@ return (td_ret != INVALID_TRACKDIR) ? TrackdirToTrack(td_ret) : INVALID_TRACK; } +FindDepotData YapfShipFindNearestDepot(const Ship *v, int max_distance) +{ + 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 ? DistanceManhattan(tile, fdd.tile) : UINT_MAX; // distance manhattan or NOT_FOUND + return fdd; +} + bool YapfShipCheckReverse(const Ship *v) { Trackdir td = v->GetVehicleTrackdir(); Index: src/ship_cmd.cpp =================================================================== --- src/ship_cmd.cpp (revision 27833) +++ src/ship_cmd.cpp (working copy) @@ -138,7 +138,7 @@ result->Set(_ship_sprites[spritenum] + direction); } -static const Depot *FindClosestShipDepot(const Vehicle *v, uint max_distance) +static FindDepotData FindClosestShipDepot(const Ship *v, uint max_distance) { /* Find the closest depot */ const Depot *depot; @@ -161,9 +161,27 @@ } } - return best_depot; + FindDepotData fdd; + if (best_depot != NULL) { + fdd.best_length = best_dist; + fdd.tile = best_depot->xy; + } + return fdd; } +static FindDepotData FindClosestReachableShipDepot(const Ship *v, int max_distance) +{ + if ((IsShipDepotTile(v->tile) && GetShipDepotPart(v->tile) == DEPOT_PART_NORTH) && IsTileOwner(v->tile, v->owner)) return FindDepotData(v->tile, 0); + + switch (_settings_game.pf.pathfinder_for_ships) { + case VPF_OPF: return OPFShipFindNearestDepot(v, max_distance); + case VPF_NPF: return NPFShipFindNearestDepot(v, max_distance); + case VPF_YAPF: return YapfShipFindNearestDepot(v, max_distance); + + default: NOT_REACHED(); + } +} + static void CheckIfShipNeedsService(Vehicle *v) { if (Company::Get(v->owner)->settings.vehicle.servint_ships == 0 || !v->NeedsAutomaticServicing()) return; @@ -180,9 +198,9 @@ default: NOT_REACHED(); } - const Depot *depot = FindClosestShipDepot(v, max_distance); + const FindDepotData sfdd = FindClosestReachableShipDepot(Ship::From(v), max_distance); - if (depot == NULL) { + if (sfdd.best_length == UINT_MAX || sfdd.best_length >= max_distance) { if (v->current_order.IsType(OT_GOTO_DEPOT)) { v->current_order.MakeDummy(); SetWindowWidgetDirty(WC_VEHICLE_VIEW, v->index, WID_VV_START_STOP); @@ -190,8 +208,8 @@ return; } - v->current_order.MakeGoToDepot(depot->index, ODTFB_SERVICE); - v->dest_tile = depot->xy; + v->current_order.MakeGoToDepot(GetDepotIndex(sfdd.tile), ODTFB_SERVICE); + v->dest_tile = sfdd.tile; SetWindowWidgetDirty(WC_VEHICLE_VIEW, v->index, WID_VV_START_STOP); } @@ -712,12 +730,15 @@ 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) { + sfdd = FindClosestShipDepot(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 (reverse != NULL) *reverse = sfdd.reverse; - if (location != NULL) *location = depot->xy; - if (destination != NULL) *destination = depot->index; - return true; }