(svn r7585) -Codechange: CheckStationSpreadOut() took too much CPU. Station rectangle is now maintained instead of calculating it each time by walking through whole map. Should help with the performance issue related to AIs trying to build road stops too often. (idea by Celestar)

2 files changed, 178 insertions, 34 deletions

diff --git a/station.h b/station.h
index 2018f0777..1d4c850a8 100644
--- a/station.h
+++ b/station.h
@@ -47,6 +47,15 @@ typedef struct StationSpecList {
 	uint8  localidx;   /// Station ID within GRF of station
 } StationSpecList;
 
+/** Station spread out rectangle (not saved) */
+typedef struct StationRect
+{
+	uint16 left;
+	uint16 top;
+	uint16 right;
+	uint16 bottom;
+} StationRect;
+
 struct Station {
 	TileIndex xy;
 	RoadStop *bus_stops;
@@ -94,6 +103,8 @@ struct Station {
 	byte truck_stop_status_obsolete;
 	byte bus_stop_status_obsolete;
 	byte blocked_months_obsolete;
+
+	StationRect rect;
 };
 
 enum {
diff --git a/station_cmd.c b/station_cmd.c
index 6402c79a6..cc2eb15e6 100644
--- a/station_cmd.c
+++ b/station_cmd.c
@@ -34,6 +34,14 @@
 #include "yapf/yapf.h"
 #include "date.h"
 
+static void StationRect_Init(Station *st);
+static bool StationRect_IsEmpty(Station *st);
+static bool StationRect_BeforeAddTile(Station *st, TileIndex tile, bool exec);
+static bool StationRect_BeforeAddRect(Station *st, TileIndex tile, uint16 w, uint16 h, bool exec);
+static bool StationRect_AfterRemoveTile(Station *st, TileIndex tile);
+static bool StationRect_AfterRemoveRect(Station *st, TileIndex tile, uint16 w, uint16 h);
+
+
 /**
  * Called if a new block is added to the station-pool
  */
@@ -468,6 +476,7 @@ static void StationInitialize(Station *st, TileIndex tile)
 	st->random_bits = Random();
 	st->waiting_triggers = 0;
 
+	StationRect_Init(st);
 }
 
 // Update the virtual coords needed to draw the station sign.
@@ -733,38 +742,14 @@ static void UpdateStationAcceptance(Station *st, bool show_msg)
 	InvalidateWindowWidget(WC_STATION_VIEW, st->index, 4);
 }
 
-static bool CheckStationSpreadOut(Station *st, TileIndex tile, int w, int h)
-{
-	StationID station_index = st->index;
-	uint x1 = TileX(tile);
-	uint y1 = TileY(tile);
-	ottd_Rectangle r = {x1, y1, x1 + w - 1, y1 + h - 1};
-	// get station bounding rect
-	for (tile = 0; tile < MapSize(); tile++) {
-		if (IsTileType(tile, MP_STATION) && GetStationIndex(tile) == station_index) MergePoint(&r, tile);
-	}
-	// check if bounding rect doesn't exceed the maximum station spread
-	if (r.max_x - r.min_x >= _patches.station_spread || r.max_y - r.min_y >= _patches.station_spread) {
-		_error_message = STR_306C_STATION_TOO_SPREAD_OUT;
-		return false;
-	}
-	return true;
-}
-
 static void UpdateStationSignCoord(Station *st)
 {
-	ottd_Rectangle r = {MapSizeX(), MapSizeY(), 0, 0};
-	TileIndex tile;
-
-	// get station bounding rect
-	for (tile = 0; tile < MapSize(); tile++) {
-		if (IsTileType(tile, MP_STATION) && GetStationIndex(tile) == st->index) MergePoint(&r, tile);
-	}
+	StationRect *r = &st->rect;
 
-	if (r.max_x < r.min_x) return; // no tiles belong to this station
+	if (StationRect_IsEmpty(st)) return; // no tiles belong to this station
 
-	// clamp sign coord to be inside the rect
-	st->xy = TileXY(clampu(TileX(st->xy), r.min_x, r.max_x), clampu(TileY(st->xy), r.min_y, r.max_y));
+	// clamp sign coord to be inside the station rect
+	st->xy = TileXY(clampu(TileX(st->xy), r->left, r->right), clampu(TileY(st->xy), r->top, r->bottom));
 	UpdateStationVirtCoordDirty(st);
 }
 
@@ -1041,7 +1026,7 @@ int32 CmdBuildRailroadStation(TileIndex tile_org, uint32 flags, uint32 p1, uint3
 		}
 
 		//XXX can't we pack this in the "else" part of the if above?
-		if (!CheckStationSpreadOut(st, tile_org, w_org, h_org)) return CMD_ERROR;
+		if (!StationRect_BeforeAddRect(st, tile_org, w_org, h_org, false)) return CMD_ERROR;
 	} else {
 		// Create a new station
 		st = AllocateStation();
@@ -1100,6 +1085,8 @@ int32 CmdBuildRailroadStation(TileIndex tile_org, uint32 flags, uint32 p1, uint3
 
 		st->build_date = _date;
 
+		StationRect_BeforeAddRect(st, tile_org, w_org, h_org, true);
+
 		tile_delta = (axis == AXIS_X ? TileDiffXY(1, 0) : TileDiffXY(0, 1));
 		track = AxisToTrack(axis);
 
@@ -1220,6 +1207,7 @@ int32 CmdRemoveFromRailroadStation(TileIndex tile, uint32 flags, uint32 p1, uint
 		uint specindex = GetCustomStationSpecIndex(tile);
 		Track track = GetRailStationTrack(tile);
 		DoClearSquare(tile);
+		StationRect_AfterRemoveTile(st, tile);
 		SetSignalsOnBothDir(tile, track);
 		YapfNotifyTrackLayoutChange(tile, track);
 
@@ -1336,7 +1324,10 @@ static int32 RemoveRailroadStation(Station *st, TileIndex tile, uint32 flags)
 	} while (--h);
 
 	if (flags & DC_EXEC) {
+		StationRect_AfterRemoveRect(st, st->train_tile, st->trainst_w, st->trainst_h);
+
 		st->train_tile = 0;
+		st->trainst_w = st->trainst_h = 0;
 		st->facilities &= ~FACIL_TRAIN;
 
 		free(st->speclist);
@@ -1462,7 +1453,7 @@ int32 CmdBuildRoadStop(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
 			return_cmd_error(STR_3009_TOO_CLOSE_TO_ANOTHER_STATION);
 		}
 
-		if (!CheckStationSpreadOut(st, tile, 1, 1)) return CMD_ERROR;
+		if (!StationRect_BeforeAddTile(st, tile, false)) return CMD_ERROR;
 
 		FindRoadStopSpot(type, st, &currstop, &prev);
 	} else {
@@ -1500,6 +1491,8 @@ int32 CmdBuildRoadStop(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
 
 		st->build_date = _date;
 
+		StationRect_BeforeAddTile(st, tile, true);
+
 		MakeRoadStop(tile, st->owner, st->index, type, p1);
 
 		UpdateStationVirtCoordDirty(st);
@@ -1547,6 +1540,7 @@ static int32 RemoveRoadStop(Station *st, uint32 flags, TileIndex tile)
 
 		DeleteRoadStop(cur_stop);
 		DoClearSquare(tile);
+		StationRect_AfterRemoveTile(st, tile);
 
 		UpdateStationVirtCoordDirty(st);
 		DeleteStationIfEmpty(st);
@@ -1708,8 +1702,7 @@ int32 CmdBuildAirport(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
 		if (st->owner != OWNER_NONE && st->owner != _current_player)
 			return_cmd_error(STR_3009_TOO_CLOSE_TO_ANOTHER_STATION);
 
-		if (!CheckStationSpreadOut(st, tile, 1, 1))
-			return CMD_ERROR;
+		if (!StationRect_BeforeAddRect(st, tile, w, h, false)) return CMD_ERROR;
 
 		if (st->airport_tile != 0)
 			return_cmd_error(STR_300D_TOO_CLOSE_TO_ANOTHER_AIRPORT);
@@ -1746,6 +1739,8 @@ int32 CmdBuildAirport(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
 
 		st->build_date = _date;
 
+		StationRect_BeforeAddRect(st, tile, w, h, true);
+
 		/* if airport was demolished while planes were en-route to it, the
 		 * positions can no longer be the same (v->u.air.pos), since different
 		 * airports have different indexes. So update all planes en-route to this
@@ -1808,6 +1803,8 @@ static int32 RemoveAirport(Station *st, uint32 flags)
 			);
 		}
 
+		StationRect_AfterRemoveRect(st, tile, w, h);
+
 		st->airport_tile = 0;
 		st->facilities &= ~FACIL_AIRPORT;
 
@@ -1977,7 +1974,7 @@ int32 CmdBuildDock(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
 		if (st->owner != OWNER_NONE && st->owner != _current_player)
 			return_cmd_error(STR_3009_TOO_CLOSE_TO_ANOTHER_STATION);
 
-		if (!CheckStationSpreadOut(st, tile, 1, 1)) return CMD_ERROR;
+		if (!StationRect_BeforeAddRect(st, tile, _dock_w_chk[direction], _dock_h_chk[direction], false)) return CMD_ERROR;
 
 		if (st->dock_tile != 0) return_cmd_error(STR_304C_TOO_CLOSE_TO_ANOTHER_DOCK);
 	} else {
@@ -2006,6 +2003,8 @@ int32 CmdBuildDock(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
 
 		st->build_date = _date;
 
+		StationRect_BeforeAddRect(st, tile, _dock_w_chk[direction], _dock_h_chk[direction], true);
+
 		MakeDock(tile, st->owner, st->index, direction);
 
 		UpdateStationVirtCoordDirty(st);
@@ -2031,8 +2030,11 @@ static int32 RemoveDock(Station *st, uint32 flags)
 
 	if (flags & DC_EXEC) {
 		DoClearSquare(tile1);
-
 		MakeWater(tile2);
+
+		StationRect_AfterRemoveTile(st, tile1);
+		StationRect_AfterRemoveTile(st, tile2);
+
 		MarkTileDirtyByTile(tile2);
 
 		st->dock_tile = 0;
@@ -2899,6 +2901,7 @@ void AfterLoadStations(void)
 {
 	Station *st;
 	uint i;
+	TileIndex tile;
 
 	/* Update the speclists of all stations to point to the currently loaded custom stations. */
 	FOR_ALL_STATIONS(st) {
@@ -2908,6 +2911,12 @@ void AfterLoadStations(void)
 			st->speclist[i].spec = GetCustomStationSpecByGrf(st->speclist[i].grfid, st->speclist[i].localidx);
 		}
 	}
+
+	for (tile = 0; tile < MapSize(); tile++) {
+		if (GetTileType(tile) != MP_STATION) continue;
+		st = GetStationByTile(tile);
+		StationRect_BeforeAddTile(st, tile, true);
+	}
 }
 
 
@@ -3138,3 +3147,127 @@ const ChunkHandler _station_chunk_handlers[] = {
 	{ 'STNS', Save_STNS,      Load_STNS,      CH_ARRAY },
 	{ 'ROAD', Save_ROADSTOP,  Load_ROADSTOP,  CH_ARRAY | CH_LAST},
 };
+
+
+#define my_min(a, b) (((a) < (b)) ? (a) : (b))
+#define my_max(a, b) (((a) > (b)) ? (a) : (b))
+#define my_value_in_range(v, a, b) ((a) <= (v) && (v) <= (b))
+#define my_pt_in_rect(r, x, y) (my_value_in_range(x, (r)->left, (r)->right) && my_value_in_range(y, (r)->top, (r)->bottom))
+
+static void StationRect_Init(Station *st)
+{
+	StationRect *r = &st->rect;
+	r->left = r->top = r->right = r->bottom = 0;
+}
+
+static bool StationRect_IsEmpty(Station *st)
+{
+	return (st->rect.left == 0 || st->rect.left > st->rect.right || st->rect.top > st->rect.bottom);
+}
+
+static bool StationRect_BeforeAddTile(Station *st, TileIndex tile, bool exec)
+{
+	StationRect *r = &st->rect;
+	uint16 x = TileX(tile);
+	uint16 y = TileY(tile);
+	if (StationRect_IsEmpty(st)) {
+		// we are adding the first station tile
+		r->left = r->right = x;
+		r->top = r->bottom = y;
+	} else if (!my_pt_in_rect(r, x, y)) {
+		// current rect is not empty and new point is outside this rect
+		// make new spread-out rectangle
+		StationRect new_rect = {my_min(x, r->left), my_min(y, r->top), my_max(x, r->right), my_max(y, r->bottom)};
+		// check new rect dimensions against preset max
+		uint16 w = new_rect.right - new_rect.left + 1;
+		uint16 h = new_rect.bottom - new_rect.top + 1;
+		if (w > _patches.station_spread || h > _patches.station_spread) {
+			assert(!exec);
+			_error_message = STR_306C_STATION_TOO_SPREAD_OUT;
+			return false;
+		}
+		// spread-out ok, return true
+		if (exec) {
+			// we should update the station rect
+			*r = new_rect;
+		}
+	} else {
+		; // new point is inside the rect, we don't need to do anything
+	}
+	return true;
+}
+
+static bool StationRect_BeforeAddRect(Station *st, TileIndex tile, uint16 w, uint16 h, bool exec)
+{
+	return StationRect_BeforeAddTile(st, tile, exec) && StationRect_BeforeAddTile(st, TILE_ADDXY(tile, w - 1, h - 1), exec);
+}
+
+static inline bool ScanRectForStationTiles(StationID st_id, uint16 left, uint16 top, uint16 right, uint16 bottom)
+{
+	TileIndex top_left = TileXY(left, top);
+	uint16 width = right - left + 1;
+	uint16 height = bottom - top + 1;
+	BEGIN_TILE_LOOP(tile, width, height, top_left)
+		if (IsTileType(tile, MP_STATION) && GetStationIndex(tile) == st_id) return true;
+	END_TILE_LOOP(tile, width, height, top_left);
+	return false;
+}
+
+static bool StationRect_AfterRemoveTile(Station *st, TileIndex tile)
+{
+	StationRect *r = &st->rect;
+	uint16 x = TileX(tile);
+	uint16 y = TileY(tile);
+	bool reduce_x, reduce_y;
+
+	// look if removed tile was on the bounding rect edge
+	// and try to reduce the rect by this edge
+	// do it until we have empty rect or nothing to do
+	for (;;) {
+		// check if removed tile is on rect edge
+		bool left_edge = (x == r->left);
+		bool right_edge = (x == r->right);
+		bool top_edge = (y == r->top);
+		bool bottom_edge = (y == r->bottom);
+		// can we reduce the rect in either direction?
+		reduce_x = ((left_edge || right_edge) && !ScanRectForStationTiles(st->index, x, r->top, x, r->bottom));
+		reduce_y = ((top_edge || bottom_edge) && !ScanRectForStationTiles(st->index, r->left, y, r->right, y));
+		if (!(reduce_x || reduce_y)) break; // nothing to do (can't reduce)
+		if (reduce_x) {
+			// reduce horizontally
+			if (left_edge) {
+				// move left edge right
+				r->left = x = x + 1;
+			} else {
+				// move right edge left
+				r->right = x = x - 1;
+			}
+		}
+		if (reduce_y) {
+			// reduce vertically
+			if (top_edge) {
+				// move top edge down
+				r->top = y = y + 1;
+			} else {
+				// move bottom edge up
+				r->bottom = y = y - 1;
+			}
+		}
+		if (r->left > r->right || r->top > r->bottom) {
+		// can't continue, if the remaining rectangle is empty
+			StationRect_Init(st);
+			return true; // empty remaining rect
+		}
+	}
+	return false; // non-empty remaining rect
+}
+
+static bool StationRect_AfterRemoveRect(Station *st, TileIndex tile, uint16 w, uint16 h)
+{
+	bool empty;
+	assert(my_pt_in_rect(&st->rect, TileX(tile), TileY(tile)));
+	assert(my_pt_in_rect(&st->rect, TileX(tile) + w - 1, TileY(tile) + h - 1));
+	empty = StationRect_AfterRemoveTile(st, tile);
+	if (w != 1 || h != 1) empty = empty || StationRect_AfterRemoveTile(st, TILE_ADDXY(tile, w - 1, h - 1));
+	return empty;
+}