(svn r24481) -Feature [FS#5127]: Make the pathfinder decide whether ships shall leave depots towards north or south.

6 files changed, 117 insertions, 7 deletions

diff --git a/src/pathfinder/npf/npf.cpp b/src/pathfinder/npf/npf.cpp
index 976767319..1b8d2f17f 100644
--- a/src/pathfinder/npf/npf.cpp
+++ b/src/pathfinder/npf/npf.cpp
@@ -1178,6 +1178,23 @@ Track NPFShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir,
 	return TrackdirToTrack(ftd.best_trackdir);
 }
 
+bool NPFShipCheckReverse(const Ship *v)
+{
+	NPFFindStationOrTileData fstd;
+	NPFFoundTargetData ftd;
+
+	NPFFillWithOrderData(&fstd, v);
+
+	Trackdir trackdir = v->GetVehicleTrackdir();
+	Trackdir trackdir_rev = ReverseTrackdir(trackdir);
+	assert(trackdir != INVALID_TRACKDIR);
+	assert(trackdir_rev != INVALID_TRACKDIR);
+
+	ftd = NPFRouteToStationOrTileTwoWay(v->tile, trackdir, false, v->tile, trackdir_rev, false, &fstd, TRANSPORT_WATER, 0, v->owner, INVALID_RAILTYPES);
+	/* If we didn't find anything, just keep on going straight ahead, otherwise take the reverse flag */
+	return ftd.best_bird_dist == 0 && NPFGetFlag(&ftd.node, NPF_FLAG_REVERSE);
+}
+
 /*** Trains ***/
 
 FindDepotData NPFTrainFindNearestDepot(const Train *v, int max_penalty)
diff --git a/src/pathfinder/npf/npf_func.h b/src/pathfinder/npf/npf_func.h
index f83c06f13..6507f4ec5 100644
--- a/src/pathfinder/npf/npf_func.h
+++ b/src/pathfinder/npf/npf_func.h
@@ -50,6 +50,13 @@ Trackdir NPFRoadVehicleChooseTrack(const RoadVehicle *v, TileIndex tile, DiagDir
 Track NPFShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found);
 
 /**
+ * Returns true if it is better to reverse the ship before leaving depot using NPF.
+ * @param v the ship leaving the depot
+ * @return true if reversing is better
+ */
+bool NPFShipCheckReverse(const Ship *v);
+
+/**
  * Used when user sends train to the nearest depot or if train needs servicing using NPF
  * @param v            train that needs to go to some depot
  * @param max_penalty  max max_penalty (in pathfinder penalty) from the current train position
diff --git a/src/pathfinder/opf/opf_ship.cpp b/src/pathfinder/opf/opf_ship.cpp
index 9cf574484..850577de1 100644
--- a/src/pathfinder/opf/opf_ship.cpp
+++ b/src/pathfinder/opf/opf_ship.cpp
@@ -193,7 +193,8 @@ Track OPFShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir,
 	Track track;
 
 	/* Let's find out how far it would be if we would reverse first */
-	TrackBits b = TrackStatusToTrackBits(GetTileTrackStatus(tile2, TRANSPORT_WATER, 0)) & DiagdirReachesTracks(ReverseDiagDir(enterdir)) & v->state;
+	Trackdir trackdir = v->GetVehicleTrackdir();
+	TrackBits b = TrackStatusToTrackBits(GetTileTrackStatus(tile2, TRANSPORT_WATER, 0)) & DiagdirReachesTracks(ReverseDiagDir(enterdir)) & TrackdirBitsToTrackBits(TrackdirToTrackdirBits(trackdir));
 
 	uint distr = UINT_MAX; // distance if we reversed
 	if (b != 0) {
diff --git a/src/pathfinder/yapf/yapf.h b/src/pathfinder/yapf/yapf.h
index b02d9d0ee..00eb7e562 100644
--- a/src/pathfinder/yapf/yapf.h
+++ b/src/pathfinder/yapf/yapf.h
@@ -29,6 +29,13 @@
 Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found);
 
 /**
+ * Returns true if it is better to reverse the ship before leaving depot using YAPF.
+ * @param v the ship leaving the depot
+ * @return true if reversing is better
+ */
+bool YapfShipCheckReverse(const Ship *v);
+
+/**
  * Finds the best path for given road vehicle using YAPF.
  * @param v         the RV that needs to find a path
  * @param tile      the tile to find the path from (should be next tile the RV is about to enter)
diff --git a/src/pathfinder/yapf/yapf_ship.cpp b/src/pathfinder/yapf/yapf_ship.cpp
index dfcda3858..a4113144e 100644
--- a/src/pathfinder/yapf/yapf_ship.cpp
+++ b/src/pathfinder/yapf/yapf_ship.cpp
@@ -98,6 +98,42 @@ public:
 		}
 		return next_trackdir;
 	}
+
+	/**
+	 * Check whether a ship should reverse to reach its destination.
+	 * Called when leaving depot.
+	 * @param v Ship
+	 * @param tile Current position
+	 * @param td1 Forward direction
+	 * @param td2 Reverse direction
+	 * @return true if the reverse direction is better
+	 */
+	static bool CheckShipReverse(const Ship *v, TileIndex tile, Trackdir td1, Trackdir td2)
+	{
+		/* get available trackdirs on the destination tile */
+		TrackdirBits dest_trackdirs = TrackStatusToTrackdirBits(GetTileTrackStatus(v->dest_tile, TRANSPORT_WATER, 0));
+
+		/* create pathfinder instance */
+		Tpf pf;
+		/* set origin and destination nodes */
+		pf.SetOrigin(tile, TrackdirToTrackdirBits(td1) | TrackdirToTrackdirBits(td2));
+		pf.SetDestination(v->dest_tile, dest_trackdirs);
+		/* find best path */
+		if (!pf.FindPath(v)) return false;
+
+		Node *pNode = pf.GetBestNode();
+		if (pNode == NULL) return false;
+
+		/* path was found
+		 * walk through the path back to the origin */
+		while (pNode->m_parent != NULL) {
+			pNode = pNode->m_parent;
+		}
+
+		Trackdir best_trackdir = pNode->GetTrackdir();
+		assert(best_trackdir == td1 || best_trackdir == td2);
+		return best_trackdir == td2;
+	}
 };
 
 /** Cost Provider module of YAPF for ships */
@@ -197,3 +233,24 @@ Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir,
 	Trackdir td_ret = pfnChooseShipTrack(v, tile, enterdir, tracks, path_found);
 	return (td_ret != INVALID_TRACKDIR) ? TrackdirToTrack(td_ret) : INVALID_TRACK;
 }
+
+bool YapfShipCheckReverse(const Ship *v)
+{
+	Trackdir td = v->GetVehicleTrackdir();
+	Trackdir td_rev = ReverseTrackdir(td);
+	TileIndex tile = v->tile;
+
+	typedef bool (*PfnCheckReverseShip)(const Ship*, TileIndex, Trackdir, Trackdir);
+	PfnCheckReverseShip pfnCheckReverseShip = CYapfShip2::CheckShipReverse; // default: ExitDir, allow 90-deg
+
+	/* check if non-default YAPF type needed */
+	if (_settings_game.pf.forbid_90_deg) {
+		pfnCheckReverseShip = &CYapfShip3::CheckShipReverse; // Trackdir, forbid 90-deg
+	} else if (_settings_game.pf.yapf.disable_node_optimization) {
+		pfnCheckReverseShip = &CYapfShip1::CheckShipReverse; // Trackdir, allow 90-deg
+	}
+
+	bool reverse = pfnCheckReverseShip(v, tile, td, td_rev);
+
+	return reverse;
+}
diff --git a/src/ship_cmd.cpp b/src/ship_cmd.cpp
index 06a4b7390..ae2c819db 100644
--- a/src/ship_cmd.cpp
+++ b/src/ship_cmd.cpp
@@ -310,13 +310,34 @@ static bool CheckShipLeaveDepot(Ship *v)
 	TileIndex tile = v->tile;
 	Axis axis = GetShipDepotAxis(tile);
 
-	/* Check first (north) side */
-	if (DiagdirReachesTracks((DiagDirection)axis) & GetTileShipTrackStatus(TILE_ADD(tile, ToTileIndexDiff(_ship_leave_depot_offs[axis])))) {
-		v->direction = ReverseDir(AxisToDirection(axis));
-	/* Check second (south) side */
-	} else if (DiagdirReachesTracks((DiagDirection)(axis + 2)) & GetTileShipTrackStatus(TILE_ADD(tile, -2 * ToTileIndexDiff(_ship_leave_depot_offs[axis])))) {
-		v->direction = AxisToDirection(axis);
+	DiagDirection north_dir = ReverseDiagDir(AxisToDiagDir(axis));
+	TileIndex north_neighbour = TILE_ADD(tile, ToTileIndexDiff(_ship_leave_depot_offs[axis]));
+	DiagDirection south_dir = AxisToDiagDir(axis);
+	TileIndex south_neighbour = TILE_ADD(tile, -2 * ToTileIndexDiff(_ship_leave_depot_offs[axis]));
+
+	TrackBits north_tracks = DiagdirReachesTracks(north_dir) & GetTileShipTrackStatus(north_neighbour);
+	TrackBits south_tracks = DiagdirReachesTracks(south_dir) & GetTileShipTrackStatus(south_neighbour);
+	if (north_tracks && south_tracks) {
+		/* Ask pathfinder for best direction */
+		bool reverse = false;
+		bool path_found;
+		switch (_settings_game.pf.pathfinder_for_ships) {
+			case VPF_OPF: reverse = OPFShipChooseTrack(v, north_neighbour, north_dir, north_tracks, path_found) == INVALID_TRACK; break; // OPF always allows reversing
+			case VPF_NPF: reverse = NPFShipCheckReverse(v); break;
+			case VPF_YAPF: reverse = YapfShipCheckReverse(v); break;
+			default: NOT_REACHED();
+		}
+		if (reverse) north_tracks = TRACK_BIT_NONE;
+	}
+
+	if (north_tracks) {
+		/* Leave towards north */
+		v->direction = DiagDirToDir(north_dir);
+	} else if (south_tracks) {
+		/* Leave towards south */
+		v->direction = DiagDirToDir(south_dir);
 	} else {
+		/* Both ways blocked */
 		return false;
 	}