From 81330b8d6edee68c38717462737fbfca6420701d Mon Sep 17 00:00:00 2001 From: Peter Nelson Date: Mon, 14 Jan 2019 23:33:42 +0000 Subject: Change: Add path cache for ships. --- src/order_cmd.cpp | 16 ++++++++-------- src/pathfinder/pathfinder_type.h | 3 +++ src/pathfinder/yapf/yapf.h | 3 ++- src/pathfinder/yapf/yapf_ship.cpp | 18 ++++++++++++++---- src/roadveh_cmd.cpp | 2 +- src/saveload/saveload.cpp | 3 ++- src/saveload/vehicle_sl.cpp | 3 ++- src/ship.h | 6 ++++++ src/ship_cmd.cpp | 26 ++++++++++++++++++++++++-- src/station_cmd.cpp | 4 ++-- src/vehicle.cpp | 2 +- src/vehicle_base.h | 2 ++ 12 files changed, 67 insertions(+), 21 deletions(-) diff --git a/src/order_cmd.cpp b/src/order_cmd.cpp index 093e4b9b5..d9d741dbc 100644 --- a/src/order_cmd.cpp +++ b/src/order_cmd.cpp @@ -2041,13 +2041,13 @@ bool UpdateOrderDest(Vehicle *v, const Order *order, int conditional_depth, bool { if (conditional_depth > v->GetNumOrders()) { v->current_order.Free(); - v->dest_tile = 0; + v->SetDestTile(0); return false; } switch (order->GetType()) { case OT_GOTO_STATION: - v->dest_tile = v->GetOrderStationLocation(order->GetDestination()); + v->SetDestTile(v->GetOrderStationLocation(order->GetDestination())); return true; case OT_GOTO_DEPOT: @@ -2068,7 +2068,7 @@ bool UpdateOrderDest(Vehicle *v, const Order *order, int conditional_depth, bool /* PBS reservations cannot reverse */ if (pbs_look_ahead && reverse) return false; - v->dest_tile = location; + v->SetDestTile(location); v->current_order.MakeGoToDepot(destination, v->current_order.GetDepotOrderType(), v->current_order.GetNonStopType(), (OrderDepotActionFlags)(v->current_order.GetDepotActionType() & ~ODATFB_NEAREST_DEPOT), v->current_order.GetRefitCargo()); /* If there is no depot in front, reverse automatically (trains only) */ @@ -2092,14 +2092,14 @@ bool UpdateOrderDest(Vehicle *v, const Order *order, int conditional_depth, bool v->IncrementRealOrderIndex(); } else { if (v->type != VEH_AIRCRAFT) { - v->dest_tile = Depot::Get(order->GetDestination())->xy; + v->SetDestTile(Depot::Get(order->GetDestination())->xy); } return true; } break; case OT_GOTO_WAYPOINT: - v->dest_tile = Waypoint::Get(order->GetDestination())->xy; + v->SetDestTile(Waypoint::Get(order->GetDestination())->xy); return true; case OT_CONDITIONAL: { @@ -2127,7 +2127,7 @@ bool UpdateOrderDest(Vehicle *v, const Order *order, int conditional_depth, bool } default: - v->dest_tile = 0; + v->SetDestTile(0); return false; } @@ -2143,7 +2143,7 @@ bool UpdateOrderDest(Vehicle *v, const Order *order, int conditional_depth, bool if (order == NULL) { v->current_order.Free(); - v->dest_tile = 0; + v->SetDestTile(0); return false; } @@ -2219,7 +2219,7 @@ bool ProcessOrders(Vehicle *v) } v->current_order.Free(); - v->dest_tile = 0; + v->SetDestTile(0); return false; } diff --git a/src/pathfinder/pathfinder_type.h b/src/pathfinder/pathfinder_type.h index 73031d5c8..0ecf00bbd 100644 --- a/src/pathfinder/pathfinder_type.h +++ b/src/pathfinder/pathfinder_type.h @@ -40,6 +40,9 @@ static const int YAPF_TILE_CORNER_LENGTH = 71; */ static const int YAPF_INFINITE_PENALTY = 1000 * YAPF_TILE_LENGTH; +/** Maximum length of ship path cache */ +static const int YAPF_SHIP_PATH_CACHE_LENGTH = 32; + /** * Helper container to find a depot */ diff --git a/src/pathfinder/yapf/yapf.h b/src/pathfinder/yapf/yapf.h index 00eb7e562..84bd35c8b 100644 --- a/src/pathfinder/yapf/yapf.h +++ b/src/pathfinder/yapf/yapf.h @@ -15,6 +15,7 @@ #include "../../direction_type.h" #include "../../track_type.h" #include "../../vehicle_type.h" +#include "../../ship.h" #include "../pathfinder_type.h" /** @@ -26,7 +27,7 @@ * @param path_found [out] Whether a path has been found (true) or has been guessed (false) * @return the best trackdir for next turn or INVALID_TRACK if the path could not be found */ -Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found); +Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found, ShipPathCache &path_cache); /** * Returns true if it is better to reverse the ship before leaving depot using YAPF. diff --git a/src/pathfinder/yapf/yapf_ship.cpp b/src/pathfinder/yapf/yapf_ship.cpp index 44a5c0cfa..7ca95ae69 100644 --- a/src/pathfinder/yapf/yapf_ship.cpp +++ b/src/pathfinder/yapf/yapf_ship.cpp @@ -54,7 +54,7 @@ public: return 'w'; } - static Trackdir ChooseShipTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found) + static Trackdir ChooseShipTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found, ShipPathCache &path_cache) { /* handle special case - when next tile is destination tile */ if (tile == v->dest_tile) { @@ -90,9 +90,17 @@ public: Node *pNode = pf.GetBestNode(); if (pNode != NULL) { + uint steps = 0; + for (Node *n = pNode; n->m_parent != NULL; n = n->m_parent) steps++; + /* walk through the path back to the origin */ Node *pPrevNode = NULL; while (pNode->m_parent != NULL) { + if (steps > 1 && --steps < YAPF_SHIP_PATH_CACHE_LENGTH) { + TrackdirByte td; + td = pNode->GetTrackdir(); + path_cache.push_front(td); + } pPrevNode = pNode; pNode = pNode->m_parent; } @@ -100,6 +108,8 @@ public: Node &best_next_node = *pPrevNode; assert(best_next_node.GetTile() == tile); next_trackdir = best_next_node.GetTrackdir(); + /* remove last element for the special case when tile == dest_tile */ + if (path_found && !path_cache.empty()) path_cache.pop_back(); } return next_trackdir; } @@ -222,10 +232,10 @@ struct CYapfShip2 : CYapfT > {}; /** Ship controller helper - path finder invoker */ -Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found) +Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found, ShipPathCache &path_cache) { /* default is YAPF type 2 */ - typedef Trackdir (*PfnChooseShipTrack)(const Ship*, TileIndex, DiagDirection, TrackBits, bool &path_found); + typedef Trackdir (*PfnChooseShipTrack)(const Ship*, TileIndex, DiagDirection, TrackBits, bool &path_found, ShipPathCache &path_cache); PfnChooseShipTrack pfnChooseShipTrack = CYapfShip2::ChooseShipTrack; // default: ExitDir, allow 90-deg /* check if non-default YAPF type needed */ @@ -235,7 +245,7 @@ Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, pfnChooseShipTrack = &CYapfShip1::ChooseShipTrack; // Trackdir, allow 90-deg } - Trackdir td_ret = pfnChooseShipTrack(v, tile, enterdir, tracks, path_found); + Trackdir td_ret = pfnChooseShipTrack(v, tile, enterdir, tracks, path_found, path_cache); return (td_ret != INVALID_TRACKDIR) ? TrackdirToTrack(td_ret) : INVALID_TRACK; } diff --git a/src/roadveh_cmd.cpp b/src/roadveh_cmd.cpp index 207a3f23b..bd7dced9b 100644 --- a/src/roadveh_cmd.cpp +++ b/src/roadveh_cmd.cpp @@ -1639,7 +1639,7 @@ static void CheckIfRoadVehNeedsService(RoadVehicle *v) SetBit(v->gv_flags, GVF_SUPPRESS_IMPLICIT_ORDERS); v->current_order.MakeGoToDepot(depot, ODTFB_SERVICE); - v->dest_tile = rfdd.tile; + v->SetDestTile(rfdd.tile); SetWindowWidgetDirty(WC_VEHICLE_VIEW, v->index, WID_VV_START_STOP); } diff --git a/src/saveload/saveload.cpp b/src/saveload/saveload.cpp index c60c8b6db..7f5b10ac5 100644 --- a/src/saveload/saveload.cpp +++ b/src/saveload/saveload.cpp @@ -272,8 +272,9 @@ * 200 #6805 Extend railtypes to 64, adding uint16 to map array. * 201 #6885 Extend NewGRF persistant storages. * 202 #6867 Increase industry cargo slots to 16 in, 16 out + * 203 #7072 Add path cache for ships */ -extern const uint16 SAVEGAME_VERSION = 202; ///< Current savegame version of OpenTTD. +extern const uint16 SAVEGAME_VERSION = 203; ///< Current savegame version of OpenTTD. SavegameType _savegame_type; ///< type of savegame we are loading FileToSaveLoad _file_to_saveload; ///< File to save or load in the openttd loop. diff --git a/src/saveload/vehicle_sl.cpp b/src/saveload/vehicle_sl.cpp index bb3db3fe3..1e01f3f67 100644 --- a/src/saveload/vehicle_sl.cpp +++ b/src/saveload/vehicle_sl.cpp @@ -753,7 +753,8 @@ const SaveLoad *GetVehicleDescription(VehicleType vt) static const SaveLoad _ship_desc[] = { SLE_WRITEBYTE(Vehicle, type, VEH_SHIP), SLE_VEH_INCLUDE(), - SLE_VAR(Ship, state, SLE_UINT8), + SLE_VAR(Ship, state, SLE_UINT8), + SLE_CONDDEQUE(Ship, path, SLE_UINT8, 203, SL_MAX_VERSION), SLE_CONDNULL(16, 2, 143), // old reserved space diff --git a/src/ship.h b/src/ship.h index 7fea5fc1d..6e73332a5 100644 --- a/src/ship.h +++ b/src/ship.h @@ -12,17 +12,22 @@ #ifndef SHIP_H #define SHIP_H +#include + #include "vehicle_base.h" #include "water_map.h" void GetShipSpriteSize(EngineID engine, uint &width, uint &height, int &xoffs, int &yoffs, EngineImageType image_type); WaterClass GetEffectiveWaterClass(TileIndex tile); +typedef std::deque ShipPathCache; + /** * All ships have this type. */ struct Ship FINAL : public SpecializedVehicle { TrackBitsByte state; ///< The "track" the ship is following. + ShipPathCache path; ///< Cached path. /** We don't want GCC to zero our struct! It already is zeroed and has an index! */ Ship() : SpecializedVehicleBase() {} @@ -46,6 +51,7 @@ struct Ship FINAL : public SpecializedVehicle { TileIndex GetOrderStationLocation(StationID station); bool FindClosestDepot(TileIndex *location, DestinationID *destination, bool *reverse); void UpdateCache(); + void SetDestTile(TileIndex tile); }; static const uint SHIP_MAX_ORDER_DISTANCE = 130; diff --git a/src/ship_cmd.cpp b/src/ship_cmd.cpp index ab1f59f11..7727aa608 100644 --- a/src/ship_cmd.cpp +++ b/src/ship_cmd.cpp @@ -193,7 +193,7 @@ static void CheckIfShipNeedsService(Vehicle *v) } v->current_order.MakeGoToDepot(depot->index, ODTFB_SERVICE); - v->dest_tile = depot->xy; + v->SetDestTile(depot->xy); SetWindowWidgetDirty(WC_VEHICLE_VIEW, v->index, WID_VV_START_STOP); } @@ -473,10 +473,24 @@ static Track ChooseShipTrack(Ship *v, TileIndex tile, DiagDirection enterdir, Tr } path_found = false; } else { + /* Attempt to follow cached path. */ + if (!v->path.empty()) { + track = TrackdirToTrack(v->path.front()); + + if (HasBit(tracks, track)) { + v->path.pop_front(); + /* HandlePathfindResult() is not called here because this is not a new pathfinder result. */ + return track; + } + + /* Cached path is invalid so continue with pathfinder. */ + } + + v->path.clear(); switch (_settings_game.pf.pathfinder_for_ships) { case VPF_OPF: track = OPFShipChooseTrack(v, tile, enterdir, tracks, path_found); break; case VPF_NPF: track = NPFShipChooseTrack(v, tile, enterdir, tracks, path_found); break; - case VPF_YAPF: track = YapfShipChooseTrack(v, tile, enterdir, tracks, path_found); break; + case VPF_YAPF: track = YapfShipChooseTrack(v, tile, enterdir, tracks, path_found, v->path); break; default: NOT_REACHED(); } } @@ -665,6 +679,7 @@ getout: reverse_direction: dir = ReverseDir(v->direction); v->direction = dir; + v->path.clear(); goto getout; } @@ -679,6 +694,13 @@ bool Ship::Tick() return true; } +void Ship::SetDestTile(TileIndex tile) +{ + if (tile == this->dest_tile) return; + this->path.clear(); + this->dest_tile = tile; +} + /** * Build a ship. * @param tile tile of the depot where ship is built. diff --git a/src/station_cmd.cpp b/src/station_cmd.cpp index 66a09c435..f088ccf6e 100644 --- a/src/station_cmd.cpp +++ b/src/station_cmd.cpp @@ -1980,7 +1980,7 @@ static CommandCost RemoveRoadStop(TileIndex tile, DoCommandFlag flags) FOR_ALL_ROADVEHICLES(v) { if (v->First() == v && v->current_order.IsType(OT_GOTO_STATION) && v->dest_tile == tile) { - v->dest_tile = v->GetOrderStationLocation(st->index); + v->SetDestTile(v->GetOrderStationLocation(st->index)); } } @@ -2604,7 +2604,7 @@ static CommandCost RemoveDock(TileIndex tile, DoCommandFlag flags) } if (s->dest_tile == docking_location) { - s->dest_tile = 0; + s->SetDestTile(0); s->current_order.Free(); } } diff --git a/src/vehicle.cpp b/src/vehicle.cpp index 1ed43c9b6..46141ce26 100644 --- a/src/vehicle.cpp +++ b/src/vehicle.cpp @@ -2337,7 +2337,7 @@ CommandCost Vehicle::SendToDepot(DoCommandFlag flags, DepotCommand command) SetBit(gv_flags, GVF_SUPPRESS_IMPLICIT_ORDERS); } - this->dest_tile = location; + this->SetDestTile(location); this->current_order.MakeGoToDepot(destination, ODTF_MANUAL); if (!(command & DEPOT_SERVICE)) this->current_order.SetDepotActionType(ODATFB_HALT); SetWindowWidgetDirty(WC_VEHICLE_VIEW, this->index, WID_VV_START_STOP); diff --git a/src/vehicle_base.h b/src/vehicle_base.h index b2a2a5d7a..d02d33e2c 100644 --- a/src/vehicle_base.h +++ b/src/vehicle_base.h @@ -749,6 +749,8 @@ public: */ virtual bool FindClosestDepot(TileIndex *location, DestinationID *destination, bool *reverse) { return false; } + virtual void SetDestTile(TileIndex tile) { this->dest_tile = tile; } + CommandCost SendToDepot(DoCommandFlag flags, DepotCommand command); void UpdateVisualEffect(bool allow_power_change = true); -- cgit v1.2.3-70-g09d2