(svn r16654) -Codechange: cache industries in station's coverage area instead of searching them everytime payment is made

8 files changed, 174 insertions, 9 deletions

diff --git a/src/economy.cpp b/src/economy.cpp
index 887c6254c..5cc2788b6 100644
--- a/src/economy.cpp
+++ b/src/economy.cpp
@@ -905,6 +905,9 @@ Money GetTransportedGoodsIncome(uint num_pieces, uint dist, byte transit_days, C
 	return BigMulS(dist * time_factor * num_pieces, _cargo_payment_rates[cargo_type], 21);
 }
 
+/**
+ * @note THIS STRUCTURE WILL BE REMOVED SOON!
+ */
 struct FindIndustryToDeliverData {
 	const Rect *rect;            ///< Station acceptance rectangle
 	CargoID cargo_type;          ///< Cargo type that was delivered
@@ -914,6 +917,9 @@ struct FindIndustryToDeliverData {
 	uint cargo_index;            ///< Index of cargo_type in acceptance list of ind
 };
 
+/**
+ * @note THIS FUNCTION WILL BE REMOVED SOON!
+ */
 static bool FindIndustryToDeliver(TileIndex ind_tile, void *user_data)
 {
 	FindIndustryToDeliverData *callback_data = (FindIndustryToDeliverData *)user_data;
@@ -958,10 +964,11 @@ static bool FindIndustryToDeliver(TileIndex ind_tile, void *user_data)
  * @param cargo_type Type of cargo delivered
  * @param nun_pieces Amount of cargo delivered
  * @param industry_set The destination industry will be inserted into this set
+ * @note THIS FUNCTION WILL BE REMOVED SOON!
  */
-static void DeliverGoodsToIndustry(const Station *st, CargoID cargo_type, int num_pieces, SmallIndustryList *industry_set)
+static Industry *DeliverGoodsToIndustryCheckOldStyle(const Station *st, CargoID cargo_type, int num_pieces)
 {
-	if (st->rect.IsEmpty()) return;
+	if (st->rect.IsEmpty()) return NULL;
 
 	/* Compute acceptance rectangle */
 	int catchment_radius = st->GetCatchmentRadius();
@@ -992,16 +999,57 @@ static void DeliverGoodsToIndustry(const Station *st, CargoID cargo_type, int nu
 	 *  2) The industries in the catchment area temporarily reject the cargo, and the daily station loop has not yet updated station acceptance.
 	 *  3) The results of callbacks CBID_INDUSTRY_REFUSE_CARGO and CBID_INDTILE_CARGO_ACCEPTANCE are inconsistent. (documented behaviour)
 	 */
-	if (CircularTileSearch(&start_tile, 2 * max_radius + 1, FindIndustryToDeliver, &callback_data)) {
-		Industry *best = callback_data.ind;
-		uint accepted_cargo_index = callback_data.cargo_index;
-		assert(best != NULL);
+	if (CircularTileSearch(&start_tile, 2 * max_radius + 1, FindIndustryToDeliver, &callback_data)) return callback_data.ind;
+
+	return NULL;
+}
+
+
+/**
+ * Transfer goods from station to industry.
+ * All cargo is delivered to the nearest (Manhattan) industry to the station sign, which is inside the acceptance rectangle and actually accepts the cargo.
+ * @param st The station that accepted the cargo
+ * @param cargo_type Type of cargo delivered
+ * @param nun_pieces Amount of cargo delivered
+ * @param industry_set The destination industry will be inserted into this set
+ */
+static void DeliverGoodsToIndustry(const Station *st, CargoID cargo_type, int num_pieces, SmallIndustryList *industry_set)
+{
+	/* Find the nearest industrytile to the station sign inside the catchment area, whose industry accepts the cargo.
+	 * This fails in three cases:
+	 *  1) The station accepts the cargo because there are enough houses around it accepting the cargo.
+	 *  2) The industries in the catchment area temporarily reject the cargo, and the daily station loop has not yet updated station acceptance.
+	 *  3) The results of callbacks CBID_INDUSTRY_REFUSE_CARGO and CBID_INDTILE_CARGO_ACCEPTANCE are inconsistent. (documented behaviour)
+	 */
+
+	for (uint i = 0; i < st->industries_near.Length(); i++) {
+		Industry *ind = st->industries_near[i];
+		const IndustrySpec *indspec = GetIndustrySpec(ind->type);
+
+		uint cargo_index;
+		for (cargo_index = 0; cargo_index < lengthof(ind->accepts_cargo); cargo_index++) {
+			if (cargo_type == ind->accepts_cargo[cargo_index]) break;
+		}
+		/* Check if matching cargo has been found */
+		if (cargo_index >= lengthof(ind->accepts_cargo)) continue;
+
+		/* Check if industry temporarily refuses acceptance */
+		if (HasBit(indspec->callback_flags, CBM_IND_REFUSE_CARGO)) {
+			uint16 res = GetIndustryCallback(CBID_INDUSTRY_REFUSE_CARGO, 0, GetReverseCargoTranslation(cargo_type, indspec->grf_prop.grffile), ind, ind->type, ind->xy);
+			if (res == 0) continue;
+		}
 
 		/* Insert the industry into industry_set, if not yet contained */
-		if (industry_set != NULL) industry_set->Include(best);
+		if (industry_set != NULL) industry_set->Include(ind);
 
-		best->incoming_cargo_waiting[accepted_cargo_index] = min(num_pieces + best->incoming_cargo_waiting[accepted_cargo_index], 0xFFFF);
+		assert(DeliverGoodsToIndustryCheckOldStyle(st, cargo_type, num_pieces) == ind); // safety check, will be removed soon
+
+		ind->incoming_cargo_waiting[cargo_index] = min(num_pieces + ind->incoming_cargo_waiting[cargo_index], 0xFFFF);
+
+		return;
 	}
+
+	assert(DeliverGoodsToIndustryCheckOldStyle(st, cargo_type, num_pieces) == NULL); // safety check, will be removed soon
 }
 
 /**
diff --git a/src/industry_cmd.cpp b/src/industry_cmd.cpp
index 9f404d984..0d93e8c23 100644
--- a/src/industry_cmd.cpp
+++ b/src/industry_cmd.cpp
@@ -167,6 +167,8 @@ Industry::~Industry()
 	DeleteIndustryNews(this->index);
 	DeleteWindowById(WC_INDUSTRY_VIEW, this->index);
 	InvalidateWindowData(WC_INDUSTRY_DIRECTORY, 0, 0);
+
+	Station::RecomputeIndustriesNearForAll();
 }
 
 static void IndustryDrawSugarMine(const TileInfo *ti)
@@ -1576,6 +1578,8 @@ static void DoCreateNewIndustry(Industry *i, TileIndex tile, int type, const Ind
 		for (j = 0; j != 50; j++) PlantRandomFarmField(i);
 	}
 	InvalidateWindowData(WC_INDUSTRY_DIRECTORY, 0, 0);
+
+	Station::RecomputeIndustriesNearForAll();
 }
 
 /** Helper function for Build/Fund an industry
diff --git a/src/saveload/afterload.cpp b/src/saveload/afterload.cpp
index 8ddc8b5ee..2b1bd15e6 100644
--- a/src/saveload/afterload.cpp
+++ b/src/saveload/afterload.cpp
@@ -226,6 +226,8 @@ static bool InitializeWindowsAndCaches()
 
 	SetCachedEngineCounts();
 
+	Station::RecomputeIndustriesNearForAll();
+
 	/* Towns have a noise controlled number of airports system
 	 * So each airport's noise value must be added to the town->noise_reached value
 	 * Reset each town's noise_reached value to '0' before. */
diff --git a/src/settings.cpp b/src/settings.cpp
index fde35834e..451c5b365 100644
--- a/src/settings.cpp
+++ b/src/settings.cpp
@@ -961,6 +961,12 @@ static bool ChangeDynamicEngines(int32 p1)
 	return true;
 }
 
+static bool StationCatchmentChanged(int32 p1)
+{
+	Station::RecomputeIndustriesNearForAll();
+	return true;
+}
+
 #ifdef ENABLE_NETWORK
 
 static bool UpdateClientName(int32 p1)
diff --git a/src/station.cpp b/src/station.cpp
index 2503148d7..b9e9d2a98 100644
--- a/src/station.cpp
+++ b/src/station.cpp
@@ -24,6 +24,7 @@
 #include "core/pool_func.hpp"
 #include "station_base.h"
 #include "roadstop_base.h"
+#include "industry_map.h"
 
 #include "table/strings.h"
 
@@ -270,6 +271,88 @@ uint Station::GetCatchmentRadius() const
 	return ret;
 }
 
+/** Rect and pointer to IndustryVector */
+struct RectAndIndustryVector {
+	Rect rect;
+	IndustryVector *industries_near;
+};
+
+/**
+ * Callback function for  Station::RecomputeIndustriesNear()
+ * Tests whether tile is an industry and possibly adds
+ * the industry to station's industries_near list.
+ * @param ind_tile tile to check
+ * @param user_data pointer to RectAndIndustryVector
+ * @return always false, we want to search all tiles
+ */
+static bool FindIndustryToDeliver(TileIndex ind_tile, void *user_data)
+{
+	/* Only process industry tiles */
+	if (!IsTileType(ind_tile, MP_INDUSTRY)) return false;
+
+	RectAndIndustryVector *riv = (RectAndIndustryVector *)user_data;
+	Industry *ind = GetIndustryByTile(ind_tile);
+
+	/* Don't check further if this industry is already in the list */
+	if (riv->industries_near->Contains(ind)) return false;
+
+	/* Only process tiles in the station acceptance rectangle */
+	int x = TileX(ind_tile);
+	int y = TileY(ind_tile);
+	if (x < riv->rect.left || x > riv->rect.right || y < riv->rect.top || y > riv->rect.bottom) return false;
+
+	/* Include only industries that can accept cargo */
+	uint cargo_index;
+	for (cargo_index = 0; cargo_index < lengthof(ind->accepts_cargo); cargo_index++) {
+		if (ind->accepts_cargo[cargo_index] != CT_INVALID) break;
+	}
+	if (cargo_index >= lengthof(ind->accepts_cargo)) return false;
+
+	*riv->industries_near->Append() = ind;
+
+	return false;
+}
+
+/**
+ * Recomputes Station::industries_near, list of industries possibly
+ * accepting cargo in station's catchment radius
+ */
+void Station::RecomputeIndustriesNear()
+{
+	this->industries_near.Reset();
+	if (this->rect.IsEmpty()) return;
+
+	/* Compute acceptance rectangle */
+	int catchment_radius = this->GetCatchmentRadius();
+
+	RectAndIndustryVector riv = {
+		{
+			max<int>(this->rect.left   - catchment_radius, 0),
+			max<int>(this->rect.top    - catchment_radius, 0),
+			min<int>(this->rect.right  + catchment_radius, MapMaxX()),
+			min<int>(this->rect.bottom + catchment_radius, MapMaxY())
+		},
+		&this->industries_near
+	};
+
+	/* Compute maximum extent of acceptance rectangle wrt. station sign */
+	TileIndex start_tile = this->xy;
+	uint max_radius = max(
+		max(DistanceManhattan(start_tile, TileXY(riv.rect.left , riv.rect.top)), DistanceManhattan(start_tile, TileXY(riv.rect.left , riv.rect.bottom))),
+		max(DistanceManhattan(start_tile, TileXY(riv.rect.right, riv.rect.top)), DistanceManhattan(start_tile, TileXY(riv.rect.right, riv.rect.bottom)))
+	);
+
+	CircularTileSearch(&start_tile, 2 * max_radius + 1, &FindIndustryToDeliver, &riv);
+}
+
+/**
+ * Recomputes Station::industries_near for all stations
+ */
+/* static */ void Station::RecomputeIndustriesNearForAll()
+{
+	Station *st;
+	FOR_ALL_STATIONS(st) st->RecomputeIndustriesNear();
+}
 
 /************************************************************************/
 /*                     StationRect implementation                       */
diff --git a/src/station_base.h b/src/station_base.h
index 7f2303b0a..6cd60094e 100644
--- a/src/station_base.h
+++ b/src/station_base.h
@@ -77,6 +77,8 @@ struct StationRect : public Rect {
 	StationRect& operator = (Rect src);
 };
 
+typedef SmallVector<Industry *, 2> IndustryVector;
+
 /** Station data structure */
 struct Station : StationPool::PoolItem<&_station_pool> {
 public:
@@ -132,6 +134,8 @@ public:
 	std::list<Vehicle *> loading_vehicles;
 	GoodsEntry goods[NUM_CARGO];  ///< Goods at this station
 
+	IndustryVector industries_near; ///< Cached list of industries near the station that can accept cargo, @see DeliverGoodsToIndustry()
+
 	uint16 random_bits;
 	byte waiting_triggers;
 	uint8 cached_anim_triggers; ///< Combined animation trigger bitmask, used to determine if trigger processing should happen.
@@ -161,6 +165,9 @@ public:
 	uint GetPlatformLength(TileIndex tile) const;
 	bool IsBuoy() const;
 
+	void RecomputeIndustriesNear();
+	static void RecomputeIndustriesNearForAll();
+
 	uint GetCatchmentRadius() const;
 
 	static FORCEINLINE Station *GetByTile(TileIndex tile)
diff --git a/src/station_cmd.cpp b/src/station_cmd.cpp
index fbd513bfd..3054d3d76 100644
--- a/src/station_cmd.cpp
+++ b/src/station_cmd.cpp
@@ -1075,6 +1075,7 @@ CommandCost CmdBuildRailroadStation(TileIndex tile_org, DoCommandFlag flags, uin
 		st->MarkTilesDirty(false);
 		UpdateStationVirtCoordDirty(st);
 		UpdateStationAcceptance(st, false);
+		st->RecomputeIndustriesNear();
 		InvalidateWindowData(WC_SELECT_STATION, 0, 0);
 		InvalidateWindowData(WC_STATION_LIST, st->owner, 0);
 		InvalidateWindowWidget(WC_STATION_VIEW, st->index, SVW_TRAINS);
@@ -1241,6 +1242,8 @@ CommandCost CmdRemoveFromRailroadStation(TileIndex tile, DoCommandFlag flags, ui
 				UpdateStationVirtCoordDirty(st);
 				DeleteStationIfEmpty(st);
 			}
+
+			st->RecomputeIndustriesNear();
 		}
 	} END_TILE_LOOP(tile2, size_x, size_y, tile)
 
@@ -1313,6 +1316,7 @@ static CommandCost RemoveRailroadStation(Station *st, TileIndex tile, DoCommandF
 
 		InvalidateWindowWidget(WC_STATION_VIEW, st->index, SVW_TRAINS);
 		UpdateStationVirtCoordDirty(st);
+		st->RecomputeIndustriesNear();
 		DeleteStationIfEmpty(st);
 	}
 
@@ -1480,6 +1484,7 @@ CommandCost CmdBuildRoadStop(TileIndex tile, DoCommandFlag flags, uint32 p1, uin
 
 		UpdateStationVirtCoordDirty(st);
 		UpdateStationAcceptance(st, false);
+		st->RecomputeIndustriesNear();
 		InvalidateWindowData(WC_SELECT_STATION, 0, 0);
 		InvalidateWindowData(WC_STATION_LIST, st->owner, 0);
 		InvalidateWindowWidget(WC_STATION_VIEW, st->index, SVW_ROADVEHS);
@@ -1561,6 +1566,7 @@ static CommandCost RemoveRoadStop(Station *st, DoCommandFlag flags, TileIndex ti
 		st->rect.AfterRemoveTile(st, tile);
 
 		UpdateStationVirtCoordDirty(st);
+		st->RecomputeIndustriesNear();
 		DeleteStationIfEmpty(st);
 	}
 
@@ -1846,6 +1852,7 @@ CommandCost CmdBuildAirport(TileIndex tile, DoCommandFlag flags, uint32 p1, uint
 
 		UpdateStationVirtCoordDirty(st);
 		UpdateStationAcceptance(st, false);
+		st->RecomputeIndustriesNear();
 		InvalidateWindowData(WC_SELECT_STATION, 0, 0);
 		InvalidateWindowData(WC_STATION_LIST, st->owner, 0);
 		InvalidateWindowWidget(WC_STATION_VIEW, st->index, SVW_PLANES);
@@ -1912,6 +1919,7 @@ static CommandCost RemoveAirport(Station *st, DoCommandFlag flags)
 		}
 
 		UpdateStationVirtCoordDirty(st);
+		st->RecomputeIndustriesNear();
 		DeleteStationIfEmpty(st);
 	}
 
@@ -1957,6 +1965,7 @@ CommandCost CmdBuildBuoy(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32
 
 		UpdateStationVirtCoordDirty(st);
 		UpdateStationAcceptance(st, false);
+		st->RecomputeIndustriesNear();
 		InvalidateWindowData(WC_STATION_LIST, st->owner, 0);
 		InvalidateWindowWidget(WC_STATION_VIEW, st->index, SVW_SHIPS);
 	}
@@ -2013,6 +2022,7 @@ static CommandCost RemoveBuoy(Station *st, DoCommandFlag flags)
 		MarkTileDirtyByTile(tile);
 
 		UpdateStationVirtCoordDirty(st);
+		st->RecomputeIndustriesNear();
 		DeleteStationIfEmpty(st);
 	}
 
@@ -2128,6 +2138,7 @@ CommandCost CmdBuildDock(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32
 
 		UpdateStationVirtCoordDirty(st);
 		UpdateStationAcceptance(st, false);
+		st->RecomputeIndustriesNear();
 		InvalidateWindowData(WC_SELECT_STATION, 0, 0);
 		InvalidateWindowData(WC_STATION_LIST, st->owner, 0);
 		InvalidateWindowWidget(WC_STATION_VIEW, st->index, SVW_SHIPS);
@@ -2160,6 +2171,7 @@ static CommandCost RemoveDock(Station *st, DoCommandFlag flags)
 
 		InvalidateWindowWidget(WC_STATION_VIEW, st->index, SVW_SHIPS);
 		UpdateStationVirtCoordDirty(st);
+		st->RecomputeIndustriesNear();
 		DeleteStationIfEmpty(st);
 	}
 
@@ -2996,6 +3008,7 @@ void BuildOilRig(TileIndex tile)
 
 	UpdateStationVirtCoordDirty(st);
 	UpdateStationAcceptance(st, false);
+	st->RecomputeIndustriesNear();
 }
 
 void DeleteOilRig(TileIndex tile)
@@ -3013,6 +3026,7 @@ void DeleteOilRig(TileIndex tile)
 	st->rect.AfterRemoveTile(st, tile);
 
 	UpdateStationVirtCoordDirty(st);
+	st->RecomputeIndustriesNear();
 	if (st->facilities == 0) delete st;
 }
 
diff --git a/src/table/settings.h b/src/table/settings.h
index a8bafd943..92a53e171 100644
--- a/src/table/settings.h
+++ b/src/table/settings.h
@@ -24,6 +24,7 @@ static int32 ConvertLandscape(const char *value);
 static int32 CheckNoiseToleranceLevel(const char *value);
 static bool CheckFreeformEdges(int32 p1);
 static bool ChangeDynamicEngines(int32 p1);
+static bool StationCatchmentChanged(int32 p1);
 
 #ifdef ENABLE_NETWORK
 static bool UpdateClientName(int32 p1);
@@ -398,7 +399,7 @@ const SettingDesc _settings[] = {
 	    SDT_BOOL(GameSettings, station.nonuniform_stations,                                         0,NN,  true,                    STR_CONFIG_SETTING_NONUNIFORM_STATIONS,    NULL),
 	     SDT_VAR(GameSettings, station.station_spread,               SLE_UINT8,                     0, 0,    12,     4,      64, 0, STR_CONFIG_SETTING_STATION_SPREAD,         InvalidateStationBuildWindow),
 	    SDT_BOOL(GameSettings, order.serviceathelipad,                                              0, 0,  true,                    STR_CONFIG_SETTING_SERVICEATHELIPAD,       NULL),
-	    SDT_BOOL(GameSettings, station.modified_catchment,                                          0, 0,  true,                    STR_CONFIG_SETTING_CATCHMENT,              NULL),
+	    SDT_BOOL(GameSettings, station.modified_catchment,                                          0, 0,  true,                    STR_CONFIG_SETTING_CATCHMENT,              StationCatchmentChanged),
 	SDT_CONDBOOL(GameSettings, order.gradual_loading,                           40, SL_MAX_VERSION, 0, 0,  true,                    STR_CONFIG_SETTING_GRADUAL_LOADING,        NULL),
 	SDT_CONDBOOL(GameSettings, construction.road_stop_on_town_road,             47, SL_MAX_VERSION, 0, 0,  true,                    STR_CONFIG_SETTING_STOP_ON_TOWN_ROAD,      NULL),
 	SDT_CONDBOOL(GameSettings, construction.road_stop_on_competitor_road,      114, SL_MAX_VERSION, 0, 0,  true,                    STR_CONFIG_SETTING_STOP_ON_COMPETITOR_ROAD,NULL),