summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/order_cmd.cpp16
-rw-r--r--src/pathfinder/pathfinder_type.h3
-rw-r--r--src/pathfinder/yapf/yapf.h3
-rw-r--r--src/pathfinder/yapf/yapf_ship.cpp18
-rw-r--r--src/roadveh_cmd.cpp2
-rw-r--r--src/saveload/saveload.cpp3
-rw-r--r--src/saveload/vehicle_sl.cpp3
-rw-r--r--src/ship.h6
-rw-r--r--src/ship_cmd.cpp26
-rw-r--r--src/station_cmd.cpp4
-rw-r--r--src/vehicle.cpp2
-rw-r--r--src/vehicle_base.h2
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<CYapfShip_TypesT<CYapfShip2, CFollowTrackWater , C
struct CYapfShip3 : CYapfT<CYapfShip_TypesT<CYapfShip3, CFollowTrackWaterNo90, CShipNodeListTrackDir> > {};
/** 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 <deque>
+
#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<TrackdirByte> ShipPathCache;
+
/**
* All ships have this type.
*/
struct Ship FINAL : public SpecializedVehicle<Ship, VEH_SHIP> {
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<Ship, VEH_SHIP> {
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);
generated by cgit v1.2.3-54-g00ecf (git 2.44.0) at 2024-07-06 09:10:10 +0000