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 -struct CYapfShipNodeT : CYapfNodeT > { }; +struct CYapfShipNodeT : CYapfNodeT > { + typedef CYapfNodeT > 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 CYapfShipNodeExitDir; typedef CYapfShipNodeT 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 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_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 +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 +278,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 +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; }