(svn r4259) -[multistop] Fix/Feature/Codechange:

1) Improved the road vehicle allocation (aka slotting) for multistop. Stops can now accept unlimited, er... 256, vehicles.
2) Removed the "wait for stop" feature, because it did not work in practise.
3) Slotting now ignores unreachable stations. Uses NPF at the moment because the old pathfinder cannot do it (yet)
4) Now matter how many vehicles approach a station, they will always be distributed evenly over existing stops.
5) Hopefully the last fundamental change to multistop

11 files changed, 56 insertions, 145 deletions

diff --git a/console_cmds.c b/console_cmds.c
index 7b044b4d9..c843f1a10 100644
--- a/console_cmds.c
+++ b/console_cmds.c
@@ -92,30 +92,6 @@ static void IConsoleHelp(const char *str)
 	IConsolePrintF(_icolour_warn, "- %s", str);
 }
 
-DEF_CONSOLE_CMD(ConResetSlots)
-{
-	Vehicle *v;
-	RoadStop *rs;
-	if (argc == 0) {
-		IConsoleHelp("Resets all slots in the game. For debugging only. Usage: 'clearslots'");
-		return true;
-	}
-
-	FOR_ALL_VEHICLES(v) {
-		if (IsValidVehicle(v)) {
-			if (v->type == VEH_Road)
-				ClearSlot(v);
-		}
-	}
-
-	FOR_ALL_ROADSTOPS(rs) {
-		int i;
-		for (i = 0; i < NUM_SLOTS; i++) rs->slot[i] = INVALID_VEHICLE;
-	}
-
-	return true;
-}
-
 DEF_CONSOLE_CMD(ConStopAllVehicles)
 {
 	Vehicle* v;
@@ -1389,7 +1365,6 @@ void IConsoleStdLibRegister(void)
 	IConsoleCmdRegister("cd",           ConChangeDirectory);
 	IConsoleCmdRegister("pwd",          ConPrintWorkingDirectory);
 	IConsoleCmdRegister("clear",        ConClearBuffer);
-	IConsoleCmdRegister("clearslots",   ConResetSlots);
 	IConsoleCmdRegister("stopall",      ConStopAllVehicles);
 
 	IConsoleAliasRegister("dir",      "ls");
diff --git a/lang/english.txt b/lang/english.txt
index 2b3f9e44e..03880fb72 100644
--- a/lang/english.txt
+++ b/lang/english.txt
@@ -2494,7 +2494,6 @@ STR_8860_RELIABILITY_BREAKDOWNS                                 :{BLACK}Reliabil
 STR_8861_STOPPED                                                :{RED}Stopped
 STR_8862_CAN_T_MAKE_TRAIN_PASS_SIGNAL                           :{WHITE}Can't make train pass signal at danger...
 STR_8863_CRASHED                                                :{RED}Crashed!
-STR_8864_WAIT_FOR_SLOT                                          :{YELLOW}Waiting for a free stop
 
 STR_8865_NAME_TRAIN                                             :{WHITE}Name train
 STR_8866_CAN_T_NAME_TRAIN                                       :{WHITE}Can't name train...
diff --git a/oldloader.c b/oldloader.c
index f8d9c975e..7d01fc18b 100644
--- a/oldloader.c
+++ b/oldloader.c
@@ -356,7 +356,6 @@ static void FixOldTowns(void)
 static void FixOldStations(void)
 {
 	Station *st;
-	int i;
 
 	FOR_ALL_STATIONS(st) {
 		/* Check if we need to swap width and height for the station */
@@ -373,7 +372,7 @@ static void FixOldStations(void)
 			st->bus_stops->station = st->index;
 			st->bus_stops->next = NULL;
 			st->bus_stops->prev = NULL;
-			for (i = 0; i < NUM_SLOTS; i++) st->bus_stops->slot[i] = INVALID_VEHICLE;
+			st->bus_stops->num_vehicles = 0;
 		}
 
 		if (st->lorry_tile_obsolete != 0) {
@@ -384,7 +383,7 @@ static void FixOldStations(void)
 			st->truck_stops->station = st->index;
 			st->truck_stops->next = NULL;
 			st->truck_stops->prev = NULL;
-			for (i = 0; i < NUM_SLOTS; i++) st->truck_stops->slot[i] = INVALID_VEHICLE;
+			st->truck_stops->num_vehicles = 0;
 		}
 	}
 }
diff --git a/openttd.c b/openttd.c
index b41295d0e..8a97a46fa 100644
--- a/openttd.c
+++ b/openttd.c
@@ -1391,6 +1391,17 @@ bool AfterLoadGame(void)
 
 	if (CheckSavegameVersion(22))  UpdatePatches();
 
+	if (CheckSavegameVersion(25)) {
+		Vehicle *v;
+		FOR_ALL_VEHICLES(v) {
+			if (v->type == VEH_Road) {
+				v->vehstatus &= ~0x40;
+				v->u.road.slot = NULL;
+				v->u.road.slot_age = 0;
+			}
+		}
+	}
+
 	FOR_ALL_PLAYERS(p) p->avail_railtypes = GetPlayerRailtypes(p->index);
 
 	return true;
diff --git a/roadveh_cmd.c b/roadveh_cmd.c
index 33473f517..f552136ad 100644
--- a/roadveh_cmd.c
+++ b/roadveh_cmd.c
@@ -1,5 +1,6 @@
 /* $Id$ */
 
+#include <limits.h>
 #include "stdafx.h"
 #include "openttd.h"
 #include "debug.h"
@@ -164,10 +165,6 @@ int32 CmdBuildRoadVeh(int x, int y, uint32 flags, uint32 p1, uint32 p2)
 //	v->u.road.unk2 = 0;
 //	v->u.road.overtaking = 0;
 
-		v->u.road.slot = NULL;
-		v->u.road.slotindex = 0;
-		v->u.road.slot_age = 0;
-
 		v->last_station_visited = INVALID_STATION;
 		v->max_speed = rvi->max_speed;
 		v->engine_type = (byte)p1;
@@ -238,10 +235,10 @@ void ClearSlot(Vehicle *v)
 	v->u.road.slot = NULL;
 	v->u.road.slot_age = 0;
 
-	// check that the slot is indeed assigned to the same vehicle
-	assert(rs->slot[v->u.road.slotindex] == v->index);
-	rs->slot[v->u.road.slotindex] = INVALID_VEHICLE;
-	DEBUG(ms, 3) ("Multistop: Clearing slot %d at 0x%x", v->u.road.slotindex, rs->xy);
+	assert(rs->num_vehicles != 0);
+	rs->num_vehicles--;
+
+	DEBUG(ms, 3) ("Multistop: Clearing slot at 0x%x", rs->xy);
 }
 
 /** Sell a road vehicle.
@@ -382,7 +379,6 @@ int32 CmdSendRoadVehToDepot(int x, int y, uint32 flags, uint32 p1, uint32 p2)
 
 	if (flags & DC_EXEC) {
 		ClearSlot(v);
-		v->vehstatus &= ~VS_WAIT_FOR_SLOT;
 		v->current_order.type = OT_GOTO_DEPOT;
 		v->current_order.flags = OF_NON_STOP | OF_HALT_IN_DEPOT;
 		v->current_order.station = dep->index;
@@ -408,7 +404,7 @@ int32 CmdTurnRoadVeh(int x, int y, uint32 flags, uint32 p1, uint32 p2)
 
 	if (v->type != VEH_Road || !CheckOwnership(v->owner)) return CMD_ERROR;
 
-	if (v->vehstatus & (VS_HIDDEN | VS_STOPPED | VS_WAIT_FOR_SLOT) ||
+	if (v->vehstatus & (VS_HIDDEN | VS_STOPPED) ||
 			v->u.road.crashed_ctr != 0 ||
 			v->breakdown_ctr != 0 ||
 			v->u.road.overtaking != 0 ||
@@ -633,7 +629,6 @@ static void ProcessRoadVehOrder(Vehicle *v)
 		v->current_order.flags = 0;
 		v->dest_tile = 0;
 		ClearSlot(v);
-		v->vehstatus &= ~VS_WAIT_FOR_SLOT;
 		return;
 	}
 
@@ -645,8 +640,6 @@ static void ProcessRoadVehOrder(Vehicle *v)
 
 	v->current_order = *order;
 	v->dest_tile = 0;
-	/* We have changed the destination STATION, so resume movement */
-	v->vehstatus &= ~VS_WAIT_FOR_SLOT;
 
 	if (order->type == OT_GOTO_STATION) {
 		const Station* st = GetStation(order->station);
@@ -907,7 +900,7 @@ static void RoadVehCheckOvertake(Vehicle *v, Vehicle *u)
 	od.u = u;
 
 	if (u->max_speed >= v->max_speed &&
-			!(u->vehstatus & (VS_STOPPED | VS_WAIT_FOR_SLOT)) &&
+			!(u->vehstatus & VS_STOPPED) &&
 			u->cur_speed != 0) {
 		return;
 	}
@@ -929,7 +922,7 @@ static void RoadVehCheckOvertake(Vehicle *v, Vehicle *u)
 	od.tile = v->tile + TileOffsByDir(DirToDiagDir(v->direction));
 	if (FindRoadVehToOvertake(&od)) return;
 
-	if (od.u->cur_speed == 0 || od.u->vehstatus& (VS_STOPPED | VS_WAIT_FOR_SLOT)) {
+	if (od.u->cur_speed == 0 || od.u->vehstatus& VS_STOPPED) {
 		v->u.road.overtaking_ctr = 0x11;
 		v->u.road.overtaking = 0x10;
 	} else {
@@ -1133,7 +1126,6 @@ found_best_track:;
 	return best_track;
 }
 
-#if 0 /* Commented out until NPF works properly here */
 static uint RoadFindPathToStop(const Vehicle *v, TileIndex tile)
 {
 	NPFFindStationOrTileData fstd;
@@ -1145,7 +1137,6 @@ static uint RoadFindPathToStop(const Vehicle *v, TileIndex tile)
 
 	return NPFRouteToStationOrTile(v->tile, trackdir, &fstd, TRANSPORT_ROAD, v->owner, INVALID_RAILTYPE).best_path_dist;
 }
-#endif
 
 typedef struct RoadDriveEntry {
 	byte x,y;
@@ -1191,7 +1182,7 @@ static void RoadVehController(Vehicle *v)
 		v->breakdown_ctr--;
 	}
 
-	if (v->vehstatus & (VS_STOPPED | VS_WAIT_FOR_SLOT)) return;
+	if (v->vehstatus & VS_STOPPED) return;
 
 	ProcessRoadVehOrder(v);
 	HandleRoadVehLoading(v);
@@ -1454,7 +1445,6 @@ again:
 			v->current_order.type = OT_NOTHING;
 			v->current_order.flags = 0;
 			ClearSlot(v);
-			v->vehstatus &= ~VS_WAIT_FOR_SLOT;
 		}
 		SETBIT(rs->status, 7);
 
@@ -1560,7 +1550,7 @@ static void CheckIfRoadVehNeedsService(Vehicle *v)
 
 	if (_patches.servint_roadveh == 0) return;
 	if (!VehicleNeedsService(v)) return;
-	if (v->vehstatus & (VS_STOPPED | VS_WAIT_FOR_SLOT)) return;
+	if (v->vehstatus & VS_STOPPED) return;
 	if (_patches.gotodepot && VehicleHasDepotOrders(v)) return;
 
 	// Don't interfere with a depot visit scheduled by the user, or a
@@ -1610,82 +1600,57 @@ void OnNewDay_RoadVeh(Vehicle *v)
 	CheckOrders(v);
 
 	//Current slot has expired
-	if (v->u.road.slot_age-- == 0 && v->u.road.slot != NULL) {
-		DEBUG(ms, 2) ("Multistop: Slot %d expired for vehicle %d (index %d) at stop 0x%x",
-			v->u.road.slotindex, v->unitnumber, v->index, v->u.road.slot->xy
-		);
+	if (v->current_order.type == OT_GOTO_STATION && v->u.road.slot_age-- == 0 && v->u.road.slot != NULL) {
+		DEBUG(ms, 2) ("Multistop: Slot expired for vehicle %d (index %d) at stop 0x%x",
+			v->unitnumber, v->index, v->u.road.slot->xy);
 		ClearSlot(v);
 	}
 
 	if (v->vehstatus & VS_STOPPED) return;
 
 	/* update destination */
-	if (v->current_order.type == OT_GOTO_STATION &&
-			v->u.road.slot == NULL &&
-			!IsLevelCrossing(v->tile) &&
-			v->u.road.overtaking == 0 &&
-			!(v->vehstatus & VS_CRASHED)) {
-		RoadStopType type = (v->cargo_type == CT_PASSENGERS) ? RS_BUS : RS_TRUCK;
+	if (v->current_order.type == OT_GOTO_STATION && v->u.road.slot == NULL && !(v->vehstatus & VS_CRASHED)) {
 		RoadStop *rs;
-		uint mindist = 0xFFFFFFFF;
-		int i;
-		RoadStop *nearest = NULL;
+		RoadStop *best = NULL;
 
 		st = GetStation(v->current_order.station);
-		rs = GetPrimaryRoadStop(st, type);
+		rs = GetPrimaryRoadStop(st, v->cargo_type == CT_PASSENGERS ? RS_BUS : RS_TRUCK);
 
 		if (rs != NULL) {
 			if (DistanceManhattan(v->tile, st->xy) < 16) {
-				int new_slot = -1;
+				uint dist, badness;
+				uint minbadness = UINT_MAX;
 
 				DEBUG(ms, 2) ("Multistop: Attempting to obtain a slot for vehicle %d (index %d) at station %d (0x%x)", v->unitnumber,
 						v->index, st->index, st->xy);
 				/* Now we find the nearest road stop that has a free slot */
-				for (i = 0; rs != NULL; rs = rs->next, i++) {
-					uint dist = 0xFFFFFFFF;
-					bool is_slot_free = false;
-					int k;
-					int last_free = -1;
-
-					for (k = 0; k < NUM_SLOTS; k++)
-						if (rs->slot[k] == INVALID_VEHICLE) {
-							is_slot_free = true;
-							last_free = k;
-							dist = DistanceManhattan(v->tile, st->xy);
-							break;
-						}
-
-					if (!is_slot_free) {
-						DEBUG(ms, 4) ("Multistop: ---- stop %d is full", i);
+				for (; rs != NULL; rs = rs->next) {
+					dist = RoadFindPathToStop(v, rs->xy);
+					if (dist == UINT_MAX) {
+						DEBUG(ms, 4) (" ---- stop 0x%x is not reachable, not treating further", rs->xy);
 						continue;
 					}
+					badness = (rs->num_vehicles + 1) * (rs->num_vehicles + 1) + dist / NPF_TILE_LENGTH;
+
+					DEBUG(ms, 4) (" ---- stop 0x%x has %d vehicle%s waiting", rs->xy, rs->num_vehicles, rs->num_vehicles == 1 ? "":"s");
+					DEBUG(ms, 4) (" ---- Distance is %u", dist);
+					DEBUG(ms, 4) (" -- Badness %u", badness);
 
-					DEBUG(ms, 4) ("Multistop: ---- distance to stop %d is %d", i, dist);
-					if (dist < mindist) {
-						nearest = rs;
-						mindist = dist;
-						new_slot = last_free;
+					if (badness < minbadness) {
+						best = rs;
+						minbadness = badness;
 					}
 				}
 
-				if (nearest != NULL) { /* We have a suitable stop */
-					DEBUG(ms, 3) ("Multistop: -- Slot %d of stop at 0x%x assinged.", new_slot, nearest->xy);
-					nearest->slot[new_slot] = v->index;
+				if (best != NULL) {
+					best->num_vehicles++;
+					DEBUG(ms, 3) (" -- Assigned to stop 0x%x", best->xy);
 
-					v->u.road.slot = nearest;
-					v->dest_tile = nearest->xy;
+					v->u.road.slot = best;
+					v->dest_tile = best->xy;
 					v->u.road.slot_age = 14;
-					v->u.road.slotindex = new_slot;
-
-					if (v->vehstatus & VS_WAIT_FOR_SLOT) {
-						DEBUG(ms, 4) ("Multistop: ---- stopped vehicle got a slot. resuming movement");
-						v->vehstatus &= ~VS_WAIT_FOR_SLOT;
-						InvalidateWindowWidget(WC_VEHICLE_VIEW, v->index, STATUS_BAR);
-					}
 				} else {
-					DEBUG(ms, 2) ("Multistop -- No free slot at station. Waiting");
-					v->vehstatus |= VS_WAIT_FOR_SLOT;
-					InvalidateWindowWidget(WC_VEHICLE_VIEW, v->index, STATUS_BAR);
+					DEBUG(ms, 3) (" -- Could not find a suitable stop");
 				}
 			} else {
 				DEBUG(ms, 5) ("Multistop: --- Distance from station too far. Postponing slotting for vehicle %d (index %d) at station %d, (0x%x)",
diff --git a/roadveh_gui.c b/roadveh_gui.c
index 32f53d364..0d5344495 100644
--- a/roadveh_gui.c
+++ b/roadveh_gui.c
@@ -247,8 +247,6 @@ static void RoadVehViewWndProc(Window *w, WindowEvent *e)
 			str = STR_885C_BROKEN_DOWN;
 		} else if (v->vehstatus & VS_STOPPED) {
 			str = STR_8861_STOPPED;
-		} else if (v->vehstatus & VS_WAIT_FOR_SLOT) {
-			str = STR_8864_WAIT_FOR_SLOT;
 		} else {
 			switch (v->current_order.type) {
 			case OT_GOTO_STATION: {
diff --git a/saveload.c b/saveload.c
index 75f75c6d0..2d936b8d6 100644
--- a/saveload.c
+++ b/saveload.c
@@ -30,7 +30,7 @@
 #include "variables.h"
 #include <setjmp.h>
 
-const uint16 SAVEGAME_VERSION = 24;
+const uint16 SAVEGAME_VERSION = 25;
 uint16 _sl_version;       /// the major savegame version identifier
 byte   _sl_minor_version; /// the minor savegame version, DO NOT USE!
 
diff --git a/station.h b/station.h
index ad458076a..02556c89f 100644
--- a/station.h
+++ b/station.h
@@ -28,7 +28,6 @@ typedef enum RoadStopType {
 
 enum {
 	INVALID_STATION = 0xFFFF,
-	NUM_SLOTS = 2,
 	ROAD_STOP_LIMIT = 16,
 };
 
@@ -37,7 +36,7 @@ typedef struct RoadStop {
 	bool used;
 	byte status;
 	uint32 index;
-	VehicleID slot[NUM_SLOTS];
+	byte num_vehicles;
 	StationID station;
 	uint8 type;
 	struct RoadStop *next;
diff --git a/station_cmd.c b/station_cmd.c
index c73072782..17edbd950 100644
--- a/station_cmd.c
+++ b/station_cmd.c
@@ -87,15 +87,13 @@ static void MarkStationDirty(const Station* st)
 
 static void InitializeRoadStop(RoadStop *road_stop, RoadStop *previous, TileIndex tile, StationID index)
 {
-	int i;
 	road_stop->xy = tile;
 	road_stop->used = true;
 	road_stop->status = 3; //stop is free
 	road_stop->next = NULL;
 	road_stop->prev = previous;
 	road_stop->station = index;
-
-	for (i = 0; i < NUM_SLOTS; i++) road_stop->slot[i] = INVALID_VEHICLE;
+	road_stop->num_vehicles = 0;
 }
 
 RoadStop* GetPrimaryRoadStop(const Station* st, RoadStopType type)
@@ -1412,17 +1410,8 @@ static int32 RemoveRoadStop(Station *st, uint32 flags, TileIndex tile)
 	if (!EnsureNoVehicle(tile)) return CMD_ERROR;
 
 	if (flags & DC_EXEC) {
-		uint i;
 		DoClearSquare(tile);
 
-		/* Clear all vehicles destined for this station */
-		for (i = 0; i != NUM_SLOTS; i++) {
-			if (cur_stop->slot[i] != INVALID_VEHICLE) {
-				Vehicle *v = GetVehicle(cur_stop->slot[i]);
-				ClearSlot(v);
-			}
-		}
-
 		cur_stop->used = false;
 		if (cur_stop->prev != NULL) cur_stop->prev->next = cur_stop->next;
 		if (cur_stop->next != NULL) cur_stop->next->prev = cur_stop->prev;
@@ -2254,27 +2243,6 @@ void DeleteAllPlayerStations(void)
 	}
 }
 
-static void CheckOrphanedSlots(const Station *st, RoadStopType rst)
-{
-	RoadStop *rs;
-	uint k;
-
-	for (rs = GetPrimaryRoadStop(st, rst); rs != NULL; rs = rs->next) {
-		for (k = 0; k < NUM_SLOTS; k++) {
-			if (rs->slot[k] != INVALID_VEHICLE) {
-				const Vehicle *v = GetVehicle(rs->slot[k]);
-
-				if (v->type != VEH_Road || v->u.road.slot != rs) {
-					DEBUG(ms, 0) (
-						"Multistop: Orphaned %s slot at 0x%X of station %d (don't panic)",
-						(rst == RS_BUS) ? "bus" : "truck", rs->xy, st->index);
-					rs->slot[k] = INVALID_VEHICLE;
-				}
-			}
-		}
-	}
-}
-
 /* this function is called for one station each tick */
 static void StationHandleBigTick(Station *st)
 {
@@ -2282,9 +2250,6 @@ static void StationHandleBigTick(Station *st)
 
 	if (st->facilities == 0 && ++st->delete_ctr >= 8) DeleteStation(st);
 
-	// Here we saveguard against orphaned slots
-	CheckOrphanedSlots(st, RS_BUS);
-	CheckOrphanedSlots(st, RS_TRUCK);
 }
 
 static inline void byte_inc_sat(byte *p) { byte b = *p + 1; if (b != 0) *p = b; }
@@ -2783,7 +2748,8 @@ static const SaveLoad _roadstop_desc[] = {
 	SLE_REF(RoadStop,next,         REF_ROADSTOPS),
 	SLE_REF(RoadStop,prev,         REF_ROADSTOPS),
 
-	SLE_ARR(RoadStop,slot,         SLE_UINT16, NUM_SLOTS),
+	SLE_CONDNULL(4, 0, 24),
+	SLE_CONDVAR(RoadStop, num_vehicles, SLE_UINT8, 25, SL_MAX_VERSION),
 
 	SLE_END()
 };
@@ -2952,6 +2918,7 @@ static void Load_ROADSTOP(void)
 			error("RoadStops: failed loading savegame: too many RoadStops");
 
 		rs = GetRoadStop(index);
+		rs->num_vehicles = 0;
 		SlObject(rs, _roadstop_desc);
 	}
 }
diff --git a/vehicle.c b/vehicle.c
index 3b8254323..5b0d9a960 100644
--- a/vehicle.c
+++ b/vehicle.c
@@ -2213,7 +2213,7 @@ static const SaveLoad _roadveh_desc[] = {
 	SLE_VARX(offsetof(Vehicle,u)+offsetof(VehicleRoad,reverse_ctr),			SLE_UINT8),
 
 	SLE_CONDREFX(offsetof(Vehicle,u)+offsetof(VehicleRoad,slot), REF_ROADSTOPS, 6, SL_MAX_VERSION),
-	SLE_CONDVARX(offsetof(Vehicle,u)+offsetof(VehicleRoad,slotindex), SLE_UINT8, 6, SL_MAX_VERSION),
+	SLE_CONDNULL(1, 6, SL_MAX_VERSION),
 	SLE_CONDVARX(offsetof(Vehicle,u)+offsetof(VehicleRoad,slot_age), SLE_UINT8, 6, SL_MAX_VERSION),
 	// reserve extra space in savegame here. (currently 16 bytes)
 	SLE_CONDNULL(16, 2, SL_MAX_VERSION),
diff --git a/vehicle.h b/vehicle.h
index 87d279449..b82319e63 100644
--- a/vehicle.h
+++ b/vehicle.h
@@ -24,7 +24,6 @@ enum VehStatus {
 	VS_TRAIN_SLOWING = 0x10,
 	VS_DISASTER = 0x20,
 	VS_AIRCRAFT_BROKEN = 0x40,
-	VS_WAIT_FOR_SLOT = 0x40,
 	VS_CRASHED = 0x80,
 };
 
@@ -111,7 +110,6 @@ typedef struct VehicleRoad {
 	uint16 crashed_ctr;
 	byte reverse_ctr;
 	struct RoadStop *slot;
-	byte slotindex;
 	byte slot_age;
 } VehicleRoad;