(svn r2255) - Fix: [ 9680363 ] [NPF] Broken buoy handling for ships

Buoys will now try to get within 3 tiles of a buoy instead of a the actual buoy tile. This gets ships to got past buoys in a realistic (IMO) way instead of barging right through them.
- Fix: [NPF] Trains get curves penalties sometimes even when the track is straight.
- Add: [NPF] Ships get a penalty for going over buoys now, so they will try to go around.
- Add: [NPF] Ships get a penalty for curves too, yay for straight lines.
- Add: TrackdirToTrack(), TrackToTrackdir(), IsDiagonalTrack() and IsDiagonalTrackdir() helper functions.
- Add: IsBuoy() and IsBuoyTile() helper functions.
- Codechange: Rearranged part of the control flow of ShipController(), removing a goto. 

9 files changed, 120 insertions, 51 deletions

diff --git a/npf.c b/npf.c
index 49ee7c803..31dc31fb4 100644
--- a/npf.c
+++ b/npf.c
@@ -36,6 +36,11 @@ const uint16 _trackdir_reaches_trackdirs[14] = {
 	0x0520, 0x2A00, 0x2A00, 0x0520, 0x2A00, 0x1009
 };
 
+const uint16 _next_trackdir[14] = {
+	0,  1,  3,  2,  5,  4, 0, 0,
+	8,  9,  11, 10, 13, 12
+};
+
 /* Maps a trackdir to all trackdirs that make 90 deg turns with it. */
 const uint16 _trackdir_crosses_trackdirs[14] = {
 	0x0202, 0x0101, 0x3030, 0x3030, 0x0C0C, 0x0C0C, 0, 0,
@@ -273,7 +278,13 @@ int32 NPFWaterPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) {
 
 	cost = _trackdir_length[trackdir]; /* Should be different for diagonal tracks */
 
-	/* TODO Penalties? */
+	if (IsBuoyTile(current->tile) && IsDiagonalTrackdir(current->direction))
+		cost += _patches.npf_buoy_penalty; /* A small penalty for going over buoys */
+
+	if (current->direction != _next_trackdir[parent->path.node.direction])
+		cost += _patches.npf_water_curve_penalty;
+
+	/* TODO More penalties? */
 
 	return cost;
 }
@@ -385,7 +396,7 @@ int32 NPFRailPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) {
 	cost += NPFSlopeCost(current);
 
 	/* Check for turns */
-	if (current->direction != parent->path.node.direction)
+	if (current->direction != _next_trackdir[parent->path.node.direction])
 		cost += _patches.npf_rail_curve_penalty;
 	//TODO, with realistic acceleration, also the amount of straight track between
 	//      curves should be taken into account, as this affects the speed limit.
diff --git a/npf.h b/npf.h
index 338f7e100..1b6eabf45 100644
--- a/npf.h
+++ b/npf.h
@@ -118,6 +118,11 @@ const byte _signal_against_trackdir[14];
 const uint16 _trackdir_reaches_trackdirs[14];
 
 /**
+ * Maps a trackdir to the trackdir that you will end up on if you go straight
+ * ahead. This will be the same trackdir for diagonal trackdirs, but a
+ * different (alternating) one for straight trackdirs */
+const uint16 _next_trackdir[14];
+/**
  * Maps a trackdir to all trackdirs that make 90 deg turns with it.
  */
 const uint16 _trackdir_crosses_trackdirs[14];
@@ -161,6 +166,23 @@ const byte _reverse_dir[4];
  */
 const byte _reverse_trackdir[14];
 
+/* Returns the Track that a given Trackdir represents */
+static inline byte TrackdirToTrack(byte trackdir) { return trackdir & 0x7; }
+
+/* Returns a Trackdir for the given Track. Since every Track corresponds to
+ * two Trackdirs, we choose the one which points between N and SE.
+ * Note that the actual implementation is quite futile, but this might change
+ * in the future.
+ */
+static inline byte TrackToTrackdir(byte track) { return track; }
+
+/* Checks if a given Track is diagonal */
+static inline bool IsDiagonalTrack(byte track) { return track == 0x0 || track == 0x1; }
+
+/* Checks if a given Trackdir is diagonal. */
+static inline bool IsDiagonalTrackdir(byte trackdir) { return IsDiagonalTrack(TrackdirToTrack(trackdir)); }
+
+
 #define REVERSE_TRACKDIR(trackdir) (trackdir ^ 0x8)
 
 #endif // NPF_H
diff --git a/order_cmd.c b/order_cmd.c
index 63e017fea..5bdabc899 100644
--- a/order_cmd.c
+++ b/order_cmd.c
@@ -166,7 +166,7 @@ int32 CmdInsertOrder(int x, int y, uint32 flags, uint32 veh_sel, uint32 packed_o
 			st = GetStation(new_order.station);
 
 			if (!IsValidStation(st) ||
-					(st->airport_type != AT_OILRIG && !(st->had_vehicle_of_type & HVOT_BUOY) && !CheckOwnership(st->owner))) {
+					(st->airport_type != AT_OILRIG && !(IsBuoy(st)) && !CheckOwnership(st->owner))) {
 				return CMD_ERROR;
 			}
 
diff --git a/settings.c b/settings.c
index 878b9ad81..2b6d52787 100644
--- a/settings.c
+++ b/settings.c
@@ -944,8 +944,8 @@ const SettingDesc patch_settings[] = {
 	* penalty will further prevent this.
 	* We give presignal exits (and combo's) a different (larger) penalty, because we really
 	* don't want trains waiting in front of a presignal exit. */
-	{"npf_rail_firstred_penalty",   SDT_UINT32, (void*)(10 * NPF_TILE_LENGTH),  &_patches.npf_rail_firstred_penalty,		NULL},
-	{"npf_rail_firstred_exit_penalty", SDT_UINT32, (void*)(100 * NPF_TILE_LENGTH),	&_patches.npf_rail_firstred_exit_penalty,		NULL},
+	{"npf_rail_firstred_penalty",   SDT_UINT32, (void*)(10 * NPF_TILE_LENGTH),  &_patches.npf_rail_firstred_penalty,    NULL},
+	{"npf_rail_firstred_exit_penalty", SDT_UINT32, (void*)(100 * NPF_TILE_LENGTH), &_patches.npf_rail_firstred_exit_penalty, NULL},
 	/* This penalty is for when the last signal before the target is red.
 	 * This is useful for train stations, where there are multiple
 	 * platforms to choose from, which lie in different signal blocks.
@@ -960,11 +960,19 @@ const SettingDesc patch_settings[] = {
 	* a penalty of 1 tile for every station tile passed, the route will
 	* be around it.
 	*/
-	{"npf_rail_station_penalty",    SDT_UINT32, (void*)(1 * NPF_TILE_LENGTH),   &_patches.npf_rail_station_penalty, 		NULL},
-	{"npf_rail_slope_penalty",      SDT_UINT32, (void*)(1 * NPF_TILE_LENGTH),   &_patches.npf_rail_slope_penalty,				NULL},
-	{"npf_rail_curve_penalty",      SDT_UINT32, (void*)(1),                     &_patches.npf_rail_curve_penalty,				NULL},
-
-	{NULL,									0,					NULL,					NULL,																						NULL}
+	{"npf_rail_station_penalty",    SDT_UINT32, (void*)(1 * NPF_TILE_LENGTH),   &_patches.npf_rail_station_penalty,     NULL},
+	{"npf_rail_slope_penalty",      SDT_UINT32, (void*)(1 * NPF_TILE_LENGTH),   &_patches.npf_rail_slope_penalty,       NULL},
+	/* This penalty is applied when a train makes a turn. Its value of 1 makes
+	 * sure that it has a minimal impact on the pathfinding, only when two
+	 * paths have equal length it will make a difference */
+	{"npf_rail_curve_penalty",      SDT_UINT32, (void*)(1),                     &_patches.npf_rail_curve_penalty,       NULL},
+	{"npf_buoy_penalty",            SDT_UINT32, (void*)(2 * NPF_TILE_LENGTH),   &_patches.npf_buoy_penalty,             NULL},
+	/* This penalty is applied when a ship makes a turn. It is bigger than the
+	 * rail curve penalty, since ships (realisticly) have more trouble with
+	 * making turns */
+	{"npf_water_curve_penalty",     SDT_UINT32, (void*)(NPF_TILE_LENGTH / 4),   &_patches.npf_water_curve_penalty,      NULL},
+
+	{NULL,                          0,          NULL,                           NULL,                                   NULL}
 };
 
 static const SettingDesc currency_settings[] = {
diff --git a/ship_cmd.c b/ship_cmd.c
index b988d50f1..5e5c5c022 100644
--- a/ship_cmd.c
+++ b/ship_cmd.c
@@ -714,46 +714,58 @@ static void ShipController(Vehicle *v)
 			r = VehicleEnterTile(v, gp.new_tile, gp.x, gp.y);
 			if (r & 0x8) goto reverse_direction;
 
-			if (v->dest_tile != 0 && v->dest_tile == gp.new_tile) {
-				if (v->current_order.type == OT_GOTO_DEPOT) {
-					if ((gp.x&0xF)==8 && (gp.y&0xF)==8) {
-						ShipEnterDepot(v);
-						return;
-					}
-				} else if (v->current_order.type == OT_GOTO_STATION) {
-					Station *st;
-
-					v->last_station_visited = v->current_order.station;
-
-					/* Process station in the orderlist. Don't do that for buoys (HVOT_BUOY) */
-					st = GetStation(v->current_order.station);
-					if (!(st->had_vehicle_of_type & HVOT_BUOY)
-							&& (st->facilities & FACIL_DOCK)) { /* ugly, ugly workaround for problem with ships able to drop off cargo at wrong stations */
-						v->current_order.type = OT_LOADING;
-						v->current_order.flags &= OF_FULL_LOAD | OF_UNLOAD;
-						v->current_order.flags |= OF_NON_STOP;
-						ShipArrivesAt(v, st);
-
-						SET_EXPENSES_TYPE(EXPENSES_SHIP_INC);
-						if (LoadUnloadVehicle(v)) {
-							InvalidateWindow(WC_SHIPS_LIST, v->owner);
-							MarkShipDirty(v);
-						}
-						InvalidateWindowWidget(WC_VEHICLE_VIEW, v->index, STATUS_BAR);
-					} else { /* leave buoys right aways */
-						v->current_order.type = OT_LEAVESTATION;
-						v->current_order.flags = 0;
-						v->cur_order_index++;
-						InvalidateVehicleOrder(v);
-					}
-					goto else_end;
-				}
-			}
-
+			/* A leave station order only needs one tick to get processed, so we can
+			 * always skip ahead. */
 			if (v->current_order.type == OT_LEAVESTATION) {
 				v->current_order.type = OT_NOTHING;
 				v->current_order.flags = 0;
 				InvalidateWindowWidget(WC_VEHICLE_VIEW, v->index, STATUS_BAR);
+			} else if (v->dest_tile != 0) {
+				/* We have a target, let's see if we reached it... */
+				if (v->current_order.type == OT_GOTO_STATION &&
+						IsBuoyTile(v->dest_tile) &&
+						DistanceManhattan(v->dest_tile, gp.new_tile) <= 3) {
+					/* We got within 3 tiles of our target buoy, so let's skip to our
+					 * next order */
+					v->cur_order_index++;
+					v->current_order.type = OT_DUMMY;
+					InvalidateVehicleOrder(v);
+				} else {
+					/* Non-buoy orders really need to reach the tile */
+					if (v->dest_tile == gp.new_tile) {
+						if (v->current_order.type == OT_GOTO_DEPOT) {
+							if ((gp.x&0xF)==8 && (gp.y&0xF)==8) {
+								ShipEnterDepot(v);
+								return;
+							}
+						} else if (v->current_order.type == OT_GOTO_STATION) {
+							Station *st;
+
+							v->last_station_visited = v->current_order.station;
+
+							/* Process station in the orderlist. */
+							st = GetStation(v->current_order.station);
+							if (st->facilities & FACIL_DOCK) { /* ugly, ugly workaround for problem with ships able to drop off cargo at wrong stations */
+								v->current_order.type = OT_LOADING;
+								v->current_order.flags &= OF_FULL_LOAD | OF_UNLOAD;
+								v->current_order.flags |= OF_NON_STOP;
+								ShipArrivesAt(v, st);
+
+								SET_EXPENSES_TYPE(EXPENSES_SHIP_INC);
+								if (LoadUnloadVehicle(v)) {
+									InvalidateWindow(WC_SHIPS_LIST, v->owner);
+									MarkShipDirty(v);
+								}
+								InvalidateWindowWidget(WC_VEHICLE_VIEW, v->index, STATUS_BAR);
+							} else { /* leave stations without docks right aways */
+								v->current_order.type = OT_LEAVESTATION;
+								v->current_order.flags = 0;
+								v->cur_order_index++;
+								InvalidateVehicleOrder(v);
+							}
+						}
+					}
+				}
 			}
 		}
 	} else {
@@ -789,7 +801,6 @@ static void ShipController(Vehicle *v)
 
 		v->direction = b[2];
 	}
-else_end:;
 
 	/* update image of ship, as well as delta XY */
 	dir = ShipGetNewDirection(v, gp.x, gp.y);
diff --git a/ship_gui.c b/ship_gui.c
index 044b36c1f..1d3f275e8 100644
--- a/ship_gui.c
+++ b/ship_gui.c
@@ -890,7 +890,7 @@ static void DrawSmallOrderList(Vehicle *v, int x, int y) {
 		sel--;
 
 		if (order->type == OT_GOTO_STATION) {
-			if (!(GetStation(order->station)->had_vehicle_of_type & HVOT_BUOY)) {
+			if (!IsBuoy(GetStation(order->station))){
 				SetDParam(0, order->station);
 				DrawString(x, y, STR_A036, 0);
 
diff --git a/station.h b/station.h
index 6252c4328..413613b46 100644
--- a/station.h
+++ b/station.h
@@ -103,6 +103,8 @@ enum {
 	HVOT_TRUCK = 1 << 3,
 	HVOT_AIRCRAFT = 1 << 4,
 	HVOT_SHIP = 1 << 5,
+	/* This bit is used to mark stations. No, it does not belong here, but what
+	 * can we do? ;-) */
 	HVOT_BUOY = 1 << 6
 };
 
@@ -290,7 +292,7 @@ static inline bool IsCompatibleTrainStationTile(TileIndex tile, TileIndex ref)
 		(_map5[tile] & 0x01) == (_map5[ref] & 0x01); // same direction?
 }
 
-static inline bool IsRoadStationTile(uint tile) {
+static inline bool IsRoadStationTile(TileIndex tile) {
 	return IsTileType(tile, MP_STATION) && IS_BYTE_INSIDE(_map5[tile], 0x43, 0x4B);
 }
 
@@ -302,6 +304,15 @@ static inline bool IsValidStation(const Station *st)
 	return st->xy != 0; /* XXX: Replace by INVALID_TILE someday */
 }
 
+static inline bool IsBuoy(const Station* st)
+{
+	return st->had_vehicle_of_type & HVOT_BUOY; /* XXX: We should really ditch this ugly coding and switch to something sane... */
+}
+
+static inline bool IsBuoyTile(TileIndex tile) {
+	return IsTileType(tile, MP_STATION) && _map5[tile] == 0x52;
+}
+
 /* Get's the direction the station exit points towards. Ie, returns 0 for a
  * station with the exit NE. */
 static inline byte GetRoadStationDir(uint tile) {
diff --git a/station_cmd.c b/station_cmd.c
index 8cecba027..9042ce6ed 100644
--- a/station_cmd.c
+++ b/station_cmd.c
@@ -642,7 +642,7 @@ static void UpdateStationAcceptance(Station *st, bool show_msg)
 	rect.min_y = MapSizeY();
 	rect.max_x = rect.max_y = 0;
 	// Don't update acceptance for a buoy
-	if (st->had_vehicle_of_type & HVOT_BUOY)
+	if (IsBuoy(st))
 		return;
 
 	/* old accepted goods types */
@@ -1855,6 +1855,8 @@ int32 CmdBuildBuoy(int x, int y, uint32 flags, uint32 p1, uint32 p2)
 		StationInitialize(st, ti.tile);
 		st->dock_tile = ti.tile;
 		st->facilities |= FACIL_DOCK;
+		/* Buoys are marked in the Station struct by this flag. Yes, it is this
+		 * braindead.. */
 		st->had_vehicle_of_type |= HVOT_BUOY;
 		st->owner = OWNER_NONE;
 
@@ -1913,6 +1915,8 @@ static int32 RemoveBuoy(Station *st, uint32 flags)
 
 	if (flags & DC_EXEC) {
 		st->dock_tile = 0;
+		/* Buoys are marked in the Station struct by this flag. Yes, it is this
+		 * braindead.. */
 		st->facilities &= ~FACIL_DOCK;
 		st->had_vehicle_of_type &= ~HVOT_BUOY;
 
@@ -2706,7 +2710,7 @@ uint MoveGoodsToStation(uint tile, int w, int h, int type, uint amount)
 			for(i=0; i!=8; i++)	{
 				if (around[i] == INVALID_STATION) {
 					st = GetStation(st_index);
-					if ((st->had_vehicle_of_type & HVOT_BUOY) == 0 &&
+					if (!IsBuoy(st) &&
 							( !st->town->exclusive_counter || (st->town->exclusivity == st->owner) ) && // check exclusive transport rights
 							st->goods[type].rating != 0 &&
 							(!_patches.selectgoods || st->goods[type].last_speed) && // if last_speed is 0, no vehicle has been there.
diff --git a/variables.h b/variables.h
index 5a705214f..afd37d4f9 100644
--- a/variables.h
+++ b/variables.h
@@ -211,6 +211,8 @@ typedef struct Patches {
 	uint32 npf_rail_station_penalty; /* The penalty for station tiles */
 	uint32 npf_rail_slope_penalty; /* The penalty for sloping upwards */
 	uint32 npf_rail_curve_penalty; /* The penalty for curves */
+	uint32 npf_buoy_penalty; /* The penalty for going over (through) a buoy */
+	uint32 npf_water_curve_penalty; /* The penalty for curves */
 
 	bool population_in_label; // Show the population of a town in his label?
 } Patches;