(svn r18404) -Codechange: link drive through stops better together

-Feature: make penalty for road stop occupancy user configurable
-Fix [FS#1944]: road vehicles would not pick an empty drive through stop. Now they will *if* the penalty for driving around is less than the occupancy penalty
-Fix [FS#1495]: long (articulated) road vehicles could block loading of others when the following road vehicle already got 'permission' to go to the next bay even when it could not reach it
-Change: improve the throughput of the drive through road stops by letting them stop closer together

1 files changed, 285 insertions, 17 deletions

diff --git a/src/roadstop.cpp b/src/roadstop.cpp
index 6558a0bb4..9547814b7 100644
--- a/src/roadstop.cpp
+++ b/src/roadstop.cpp
@@ -14,6 +14,8 @@
 #include "core/pool_func.hpp"
 #include "roadstop_base.h"
 #include "station_base.h"
+#include "vehicle_func.h"
+#include "landscape.h"
 
 RoadStopPool _roadstop_pool("RoadStop");
 INSTANTIATE_POOL_METHODS(RoadStop)
@@ -23,6 +25,12 @@ INSTANTIATE_POOL_METHODS(RoadStop)
  */
 RoadStop::~RoadStop()
 {
+	/* When we are the head we need to free the entries */
+	if (HasBit(this->status, RSSFB_BASE_ENTRY)) {
+		delete this->east;
+		delete this->west;
+	}
+
 	if (CleaningPool()) return;
 }
 
@@ -47,18 +55,174 @@ RoadStop *RoadStop::GetNextRoadStop(const RoadVehicle *v) const
 }
 
 /**
+ * Join this road stop to another 'base' road stop if possible;
+ * fill all necessary data to become an actual drive through road stop.
+ * Also update the length etc.
+ */
+void RoadStop::MakeDriveThrough()
+{
+	assert(this->east == NULL && this->west == NULL);
+
+	RoadStopType rst = GetRoadStopType(this->xy);
+	DiagDirection dir = GetRoadStopDir(this->xy);
+	/* Use absolute so we always go towards the nortern tile */
+	TileIndexDiff offset = abs(TileOffsByDiagDir(dir));
+
+	/* Information about the tile north of us */
+	TileIndex north_tile = this->xy - offset;
+	bool north = IsDriveThroughRoadStopContinuation(this->xy, north_tile);
+	RoadStop *rs_north = north ? RoadStop::GetByTile(north_tile, rst) : NULL;
+
+	/* Information about the tile south of us */
+	TileIndex south_tile = this->xy + offset;
+	bool south = IsDriveThroughRoadStopContinuation(this->xy, south_tile);
+	RoadStop *rs_south = south ? RoadStop::GetByTile(south_tile, rst) : NULL;
+
+	/* Amount of road stops that will be added to the 'northern' head */
+	int added = 1;
+	if (north && rs_north->east != NULL) { // (east != NULL) == (west != NULL)
+		/* There is a more nothern one, so this can join them */
+		this->east = rs_north->east;
+		this->west = rs_north->west;
+
+		if (south && rs_south->east != NULL) { // (east != NULL) == (west != NULL)
+			/* There more southern tiles too, they must 'join' us too */
+			ClrBit(rs_south->status, RSSFB_BASE_ENTRY);
+			this->east->occupied += rs_south->east->occupied;
+			this->west->occupied += rs_south->west->occupied;
+
+			/* Free the now unneeded entry structs */
+			delete rs_south->east;
+			delete rs_south->west;
+
+			/* Make all 'children' of the southern tile take the new master */
+			for (; IsDriveThroughRoadStopContinuation(this->xy, south_tile); south_tile += offset) {
+				rs_south = RoadStop::GetByTile(south_tile, rst);
+				if (rs_south->east == NULL) break;
+				rs_south->east = rs_north->east;
+				rs_south->west = rs_north->west;
+				added++;
+			}
+		}
+	} else if (south && rs_south->east != NULL) { // (east != NULL) == (west != NULL)
+		/* There is one to the south, but not to the north... so we become 'parent' */
+		this->east = rs_south->east;
+		this->west = rs_south->west;
+		SetBit(this->status, RSSFB_BASE_ENTRY);
+		ClrBit(rs_south->status, RSSFB_BASE_ENTRY);
+	} else {
+		/* We are the only... so we are automatically the master */
+		this->east = new Entry();
+		this->west = new Entry();
+		SetBit(this->status, RSSFB_BASE_ENTRY);
+	}
+
+	/* Now update the lengths */
+	added *= TILE_SIZE;
+	this->east->length += added;
+	this->west->length += added;
+}
+
+/**
+ * Prepare for removal of this stop; update other neighbouring stops
+ * if needed. Also update the length etc.
+ */
+void RoadStop::ClearDriveThrough()
+{
+	assert(this->east != NULL && this->west != NULL);
+
+	RoadStopType rst = GetRoadStopType(this->xy);
+	DiagDirection dir = GetRoadStopDir(this->xy);
+	/* Use absolute so we always go towards the nortern tile */
+	TileIndexDiff offset = abs(TileOffsByDiagDir(dir));
+
+	/* Information about the tile north of us */
+	TileIndex north_tile = this->xy - offset;
+	bool north = IsDriveThroughRoadStopContinuation(this->xy, north_tile);
+	RoadStop *rs_north = north ? RoadStop::GetByTile(north_tile, rst) : NULL;
+
+	/* Information about the tile south of us */
+	TileIndex south_tile = this->xy + offset;
+	bool south = IsDriveThroughRoadStopContinuation(this->xy, south_tile);
+	RoadStop *rs_south = south ? RoadStop::GetByTile(south_tile, rst) : NULL;
+
+	/* Must only be cleared after we determined which neighbours are
+	 * part of our little entry 'queue' */
+	DoClearSquare(this->xy);
+
+	if (north) {
+		/* There is a tile to the north, so we can't clear ourselves. */
+		if (south) {
+			/* There are more southern tiles too, they must be split;
+			 * first make the new southern 'base' */
+			SetBit(rs_south->status, RSSFB_BASE_ENTRY);
+			rs_south->east = new Entry();
+			rs_south->west = new Entry();
+
+			/* Keep track of the base because we need it later on */
+			RoadStop *rs_south_base = rs_south;
+			TileIndex base_tile = south_tile;
+
+			/* Make all (even more) southern stops part of the new entry queue */
+			for (south_tile += offset; IsDriveThroughRoadStopContinuation(base_tile, south_tile); south_tile += offset) {
+				rs_south = RoadStop::GetByTile(south_tile, rst);
+				rs_south->east = rs_south_base->east;
+				rs_south->west = rs_south_base->west;
+			}
+
+			/* Find the other end; the northern most tile */
+			for (; IsDriveThroughRoadStopContinuation(base_tile, north_tile); north_tile -= offset) {
+				rs_north = RoadStop::GetByTile(north_tile, rst);
+			}
+
+			/* We have to rebuild the entries because we cannot easily determine
+			 * how full each part is. So instead of keeping and maintaining a list
+			 * of vehicles and using that to 'rebuild' the occupied state we just
+			 * rebuild it from scratch as that removes lots of maintainance code
+			 * for the vehicle list and it's faster in real games as long as you
+			 * do not keep split and merge road stop every tick by the millions. */
+			rs_south_base->east->Rebuild(rs_south_base);
+			rs_south_base->west->Rebuild(rs_south_base);
+
+			assert(HasBit(rs_north->status, RSSFB_BASE_ENTRY));
+			rs_north->east->Rebuild(rs_north);
+			rs_north->west->Rebuild(rs_north);
+		} else {
+			/* Only we left, so simple update the length. */
+			rs_north->east->length -= TILE_SIZE;
+			rs_north->west->length -= TILE_SIZE;
+		}
+	} else if (south) {
+		/* There is only something to the south. Hand over the base entry */
+		SetBit(rs_south->status, RSSFB_BASE_ENTRY);
+		rs_south->east->length -= TILE_SIZE;
+		rs_south->west->length -= TILE_SIZE;
+	} else {
+		/* We were the last */
+		delete this->east;
+		delete this->west;
+	}
+
+	/* Make sure we don't get used for something 'incorrect' */
+	ClrBit(this->status, RSSFB_BASE_ENTRY);
+	this->east = NULL;
+	this->west = NULL;
+}
+
+/**
  * Leave the road stop
  * @param rv the vehicle that leaves the stop
  */
 void RoadStop::Leave(RoadVehicle *rv)
 {
-	/* Vehicle is leaving a road stop tile, mark bay as free
-	 * For drive-through stops, only do it if the vehicle stopped here */
-	if (IsStandardRoadStopTile(rv->tile) || HasBit(rv->state, RVS_IS_STOPPING)) {
+	if (IsStandardRoadStopTile(rv->tile)) {
+		/* Vehicle is leaving a road stop tile, mark bay as free */
 		this->FreeBay(HasBit(rv->state, RVS_USING_SECOND_BAY));
-		ClrBit(rv->state, RVS_IS_STOPPING);
+		this->SetEntranceBusy(false);
+	} else {
+		/* Otherwise just leave the drive through's entry cache. */
+		this->GetEntry(DirToDiagDir(rv->direction))->Leave(rv);
 	}
-	if (IsStandardRoadStopTile(rv->tile)) this->SetEntranceBusy(false);
 }
 
 /**
@@ -85,19 +249,8 @@ bool RoadStop::Enter(RoadVehicle *rv)
 	}
 
 	/* Vehicles entering a drive-through stop from the 'normal' side use first bay (bay 0). */
-	byte side = ((DirToDiagDir(rv->direction) == ReverseDiagDir(GetRoadStopDir(this->xy))) == (rv->overtaking == 0)) ? 0 : 1;
+	this->GetEntry(DirToDiagDir(rv->direction))->Enter(rv);
 
-	if (!this->IsFreeBay(side)) return false;
-
-	/* Check if the vehicle is stopping at this road stop */
-	if (GetRoadStopType(this->xy) == (rv->IsBus() ? ROADSTOP_BUS : ROADSTOP_TRUCK) &&
-			rv->current_order.ShouldStopAtStation(rv, GetStationIndex(this->xy))) {
-		SetBit(rv->state, RVS_IS_STOPPING);
-		this->AllocateDriveThroughBay(side);
-	}
-
-	/* Indicate if vehicle is using second bay. */
-	if (side == 1) SetBit(rv->state, RVS_USING_SECOND_BAY);
 	/* Indicate a drive-through stop */
 	SetBit(rv->state, RVS_IN_DT_ROAD_STOP);
 	return true;
@@ -120,6 +273,121 @@ bool RoadStop::Enter(RoadVehicle *rv)
 	}
 }
 
+/**
+ * Leave the road stop
+ * @param rv the vehicle that leaves the stop
+ */
+void RoadStop::Entry::Leave(const RoadVehicle *rv)
+{
+	this->occupied -= rv->rcache.cached_veh_length;
+	assert(this->occupied >= 0);
+}
+
+/**
+ * Enter the road stop
+ * @param rv the vehicle that enters the stop
+ */
+void RoadStop::Entry::Enter(const RoadVehicle *rv)
+{
+	assert(this->occupied < this->length);
+	this->occupied += rv->rcache.cached_veh_length;
+}
+
+/**
+ * Checks whether the 'next' tile is still part of the road same drive through
+ * stop 'rs' in the same direction for the same vehicle.
+ * @param rs   the road stop tile to check against
+ * @param next the 'next' tile to check
+ * @return true if the 'next' tile is part of the road stop at 'next'.
+ */
+/* static */ bool RoadStop::IsDriveThroughRoadStopContinuation(TileIndex rs, TileIndex next)
+{
+	return IsTileType(next, MP_STATION) &&
+			GetStationIndex(next) == GetStationIndex(rs) &&
+			GetStationType(next) == GetStationType(rs) &&
+			GetRoadStopDir(next) == GetRoadStopDir(rs) &&
+			IsDriveThroughStopTile(next);
+}
+
+typedef std::list<const RoadVehicle *> RVList; ///< A list of road vehicles
+
+/** Helper for finding RVs in a road stop. */
+struct RoadStopEntryRebuilderHelper {
+	RVList vehicles;   ///< The list of vehicles to possibly add to.
+	DiagDirection dir; ///< The direction the vehicle has to face to be added.
+};
+
+/**
+ * Add road vehicles to the station's list if needed.
+ * @param v the found vehicle
+ * @param data the extra data used to make our decision
+ * @return always NULL
+ */
+Vehicle *FindVehiclesInRoadStop(Vehicle *v, void *data)
+{
+	RoadStopEntryRebuilderHelper *rserh = (RoadStopEntryRebuilderHelper*)data;
+	/* Not a RV or not in the right direction or crashed :( */
+	if (v->type != VEH_ROAD || DirToDiagDir(v->direction) != rserh->dir || !v->IsPrimaryVehicle() || (v->vehstatus & VS_CRASHED) != 0) return NULL;
+
+	RoadVehicle *rv = RoadVehicle::From(v);
+	/* Don't add ones not in a road stop */
+	if (rv->state < RVSB_IN_ROAD_STOP) return NULL;
+
+	/* Do not add duplicates! */
+	for (RVList::iterator it = rserh->vehicles.begin(); it != rserh->vehicles.end(); it++) {
+		if (rv == *it) return NULL;
+	}
+
+	rserh->vehicles.push_back(rv);
+	return NULL;
+}
+
+/**
+ * Rebuild, from scratch, the vehicles and other metadata on this stop.
+ * @param rs   the roadstop this entry is part of
+ * @param side the side of the road stop to look at
+ */
+void RoadStop::Entry::Rebuild(const RoadStop *rs, int side)
+{
+	assert(HasBit(rs->status, RSSFB_BASE_ENTRY));
+
+	DiagDirection dir = GetRoadStopDir(rs->xy);
+	if (side == -1) side = (rs->east == this);
+
+	RoadStopEntryRebuilderHelper rserh;
+	rserh.dir = side ? dir : ReverseDiagDir(dir);
+
+	this->length = 0;
+	TileIndexDiff offset = abs(TileOffsByDiagDir(dir));
+	for (TileIndex tile = rs->xy; IsDriveThroughRoadStopContinuation(rs->xy, tile); tile += offset) {
+		this->length += TILE_SIZE;
+		FindVehicleOnPos(tile, &rserh, FindVehiclesInRoadStop);
+	}
+
+	this->occupied = 0;
+	for (RVList::iterator it = rserh.vehicles.begin(); it != rserh.vehicles.end(); it++) {
+		this->occupied += (*it)->rcache.cached_veh_length;
+	}
+}
+
+
+/**
+ * Check the integrity of the data in this struct.
+ * @param rs the roadstop this entry is part of
+ */
+void RoadStop::Entry::CheckIntegrity(const RoadStop *rs) const
+{
+	if (!HasBit(rs->status, RSSFB_BASE_ENTRY)) return;
+
+	/* The tile 'before' the road stop must not be part of this 'line' */
+	assert(!IsDriveThroughRoadStopContinuation(rs->xy, rs->xy - abs(TileOffsByDiagDir(GetRoadStopDir(rs->xy)))));
+
+	Entry temp;
+	temp.Rebuild(rs, rs->east == this);
+	if (temp.length != this->length || temp.occupied != this->occupied) NOT_REACHED();
+}
+
+
 void InitializeRoadStops()
 {
 	_roadstop_pool.CleanPool();