Change: Add path cache for ships.

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);