(svn r7198) -Codechange: Implement a circular tile search function.

Just provide the number of tiles per side, a pointer to a test function, the tile to start searching and voila.
Fixes [FS#364] by removing a lengthy and suboptimal random search pattern.
Thanks Rubidium.

5 files changed, 134 insertions, 87 deletions

diff --git a/industry_cmd.c b/industry_cmd.c
index 14f8660b6..5d6c78d67 100644
--- a/industry_cmd.c
+++ b/industry_cmd.c
@@ -845,51 +845,44 @@ static void MaybePlantFarmField(const Industry *i)
 	if (CHANCE16(1, 8)) PlantRandomFarmField(i);
 }
 
-static void ChopLumberMillTrees(Industry *i)
+/**
+ * Search callback function for ChopLumberMillTrees
+ * @param tile to test
+ * @param data that is passed by the caller.  In this case, nothing
+ * @result of the test
+ */
+static bool SearchLumberMillTrees(TileIndex tile, uint32 data)
 {
-	static const TileIndexDiffC _chop_dir[] = {
-		{ 0,  1},
-		{ 1,  0},
-		{ 0, -1},
-		{-1,  0}
-	};
-
-	TileIndex tile = i->xy;
-	int a;
-
-	if (!IsIndustryCompleted(tile)) return;
-
-	/* search outwards as a rectangular spiral */
-	for (a = 1; a != 41; a += 2) {
-		uint dir;
+	if (IsTileType(tile, MP_TREES)) {
+		PlayerID old_player = _current_player;
+		/* found a tree */
 
-		for (dir = 0; dir != 4; dir++) {
-			int j = a;
+		_current_player = OWNER_NONE;
+		_industry_sound_ctr = 1;
+		_industry_sound_tile = tile;
+		SndPlayTileFx(SND_38_CHAINSAW, tile);
 
-			do {
-				tile = TILE_MASK(tile);
-				if (IsTileType(tile, MP_TREES)) {
-					PlayerID old_player = _current_player;
-					/* found a tree */
+		DoCommand(tile, 0, 0, DC_EXEC, CMD_LANDSCAPE_CLEAR);
+		SetTropicZone(tile, TROPICZONE_INVALID);
 
-					_current_player = OWNER_NONE;
-					_industry_sound_ctr = 1;
-					_industry_sound_tile = tile;
-					SndPlayTileFx(SND_38_CHAINSAW, tile);
+		_current_player = old_player;
+		return true;
+	}
+	return false;
+}
 
-					DoCommand(tile, 0, 0, DC_EXEC, CMD_LANDSCAPE_CLEAR);
-					SetTropicZone(tile, TROPICZONE_INVALID);
+/**
+ * Perform a circular search around the Lumber Mill in order to find trees to cut
+ * @param i industry
+ */
+static void ChopLumberMillTrees(Industry *i)
+{
+	TileIndex tile = i->xy;
 
-					i->cargo_waiting[0] = min(0xffff, i->cargo_waiting[0] + 45);
+	if (!IsIndustryCompleted(tile)) return;  ///< Can't proceed if not completed
 
-					_current_player = old_player;
-					return;
-				}
-				tile += ToTileIndexDiff(_chop_dir[dir]);
-			} while (--j);
-		}
-		tile -= TileDiffXY(1, 1);
-	}
+	if (CircularTileSearch(tile, 40, SearchLumberMillTrees, 0)) ///< 40x40 tiles  to search
+		i->cargo_waiting[0] = min(0xffff, i->cargo_waiting[0] + 45); ///< Found a tree, add according value to waiting cargo
 }
 
 static const byte _industry_sounds[37][2] = {
diff --git a/main_gui.c b/main_gui.c
index 11b33067e..edfafbe20 100644
--- a/main_gui.c
+++ b/main_gui.c
@@ -1564,28 +1564,26 @@ static bool AnyTownExists(void)
 
 extern Industry *CreateNewIndustry(TileIndex tile, int type);
 
-static bool TryBuildIndustry(TileIndex tile, int type)
+/**
+ * Search callback function for TryBuildIndustry
+ * @param tile to test
+ * @param data that is passed by the caller.  In this case, the type of industry been tested
+ * @result of the operation
+ */
+static bool SearchTileForIndustry(TileIndex tile, uint32 data)
 {
-	int n;
-
-	if (CreateNewIndustry(tile, type)) return true;
-
-	n = 100;
-	do {
-		if (CreateNewIndustry(AdjustTileCoordRandomly(tile, 1), type)) return true;
-	} while (--n);
-
-	n = 200;
-	do {
-		if (CreateNewIndustry(AdjustTileCoordRandomly(tile, 2), type)) return true;
-	} while (--n);
-
-	n = 700;
-	do {
-		if (CreateNewIndustry(AdjustTileCoordRandomly(tile, 4), type)) return true;
-	} while (--n);
+	return CreateNewIndustry(tile, data) != NULL;
+}
 
-	return false;
+/**
+ * Perform a 9*9 tiles circular search around a tile
+ * in order to find a suitable zone to create the desired industry
+ * @param tile to start search for
+ * @param type of the desired industry
+ */
+static bool TryBuildIndustry(TileIndex tile, int type)
+{
+	return CircularTileSearch(tile, 9, SearchTileForIndustry, type);
 }
 
 
diff --git a/map.c b/map.c
index 7a1c565d0..cb97a69b2 100644
--- a/map.c
+++ b/map.c
@@ -6,6 +6,7 @@
 #include "functions.h"
 #include "macros.h"
 #include "map.h"
+#include "direction.h"
 
 #if defined(_MSC_VER) && _MSC_VER >= 1400 /* VStudio 2005 is stupid! */
 /* Why the hell is that not in all MSVC headers?? */
@@ -179,3 +180,67 @@ uint DistanceFromEdge(TileIndex tile)
 	const uint minh = xh < yh ? xh : yh;
 	return minl < minh ? minl : minh;
 }
+
+/**
+ * Function performing a search around a center tile and going outward, thus in circle.
+ * Although it really is a square search...
+ * Every tile will be tested by means of the callback function proc,
+ * which will determine if yes or no the given tile meets criteria of search.
+ * @param tile to start the search from
+ * @param size: number of tiles per side of the desired search area
+ * @param proc: callback testing function pointer.
+ * @param data to be passed to the callback function. Depends on the implementation
+ * @result of the search
+ * @pre proc != NULL
+ * @pre size > 0
+ */
+bool CircularTileSearch(TileIndex tile, uint size, TestTileOnSearchProc proc, uint32 data)
+{
+	uint n, x, y;
+	DiagDirection dir;
+
+	assert(proc != NULL);
+	assert(size > 0);
+
+	x = TileX(tile);
+	y = TileY(tile);
+
+	if (size % 2 == 1) {
+		/* If the length of the side is uneven, the center has to be checked
+		 * separately, as the pattern of uneven sides requires to go around the center */
+		n = 2;
+		if (proc(TileXY(x, y), data)) return true;
+
+		/* If tile test is not successfull, get one tile down and left,
+		 * ready for a test in first circle around center tile */
+		x += _tileoffs_by_dir[DIR_W].x;
+		y += _tileoffs_by_dir[DIR_W].y;
+	} else {
+		n = 1;
+		/* To use _tileoffs_by_diagdir's order, we must relocate to
+		 * another tile, as we now first go 'up', 'right', 'down', 'left'
+		 * instead of 'right', 'down', 'left', 'up', which the calling
+		 * function assume. */
+		x++;
+	}
+
+	for (; n < size; n += 2) {
+		for (dir = DIAGDIR_NE; dir < DIAGDIR_END; dir++) {
+			uint j;
+			for (j = n; j != 0; j--) {
+				if (x <= MapMaxX() && y <= MapMaxY() && ///< Is the tile within the map?
+						proc(TileXY(x, y), data)) {     ///< Is the callback successfulll?
+					return true;                        ///< then stop the search
+				}
+
+				/* Step to the next 'neighbour' in the circular line */
+				x += _tileoffs_by_diagdir[dir].x;
+				y += _tileoffs_by_diagdir[dir].y;
+			}
+		}
+		/* Jump to next circle to test */
+		x += _tileoffs_by_dir[DIR_W].x;
+		y += _tileoffs_by_dir[DIR_W].y;
+	}
+	return false;
+}
diff --git a/map.h b/map.h
index 661515edd..25e29ef06 100644
--- a/map.h
+++ b/map.h
@@ -176,6 +176,9 @@ static inline TileIndexDiff TileOffsByDir(uint dir)
 	return ToTileIndexDiff(_tileoffs_by_dir[dir]);
 }
 
+typedef bool TestTileOnSearchProc(TileIndex tile, uint32 data);
+bool CircularTileSearch(TileIndex tile, uint size, TestTileOnSearchProc proc, uint32 data);
+
 /* Approximation of the length of a straight track, relative to a diagonal
  * track (ie the size of a tile side). #defined instead of const so it can
  * stay integer. (no runtime float operations) Is this needed?
diff --git a/town_cmd.c b/town_cmd.c
index d9bc799ae..20be3354a 100644
--- a/town_cmd.c
+++ b/town_cmd.c
@@ -1476,39 +1476,27 @@ static bool DoBuildStatueOfCompany(TileIndex tile)
 	return true;
 }
 
+/**
+ * Search callback function for TownActionBuildStatue
+ * @param data that is passed by the caller.  In this case, nothing
+ * @result of the test
+ */
+static bool SearchTileForStatue(TileIndex tile, uint32 data)
+{
+	return DoBuildStatueOfCompany(tile);
+}
+
+/**
+ * Perform a 9x9 tiles circular search from the center of the town
+ * in order to find a free tile to place a statue
+ * @param t town to search in
+ */
 static void TownActionBuildStatue(Town* t)
 {
-	// Layouted as an outward spiral
-	static const TileIndexDiffC _statue_tiles[] = {
-		{-1, 0},
-		{ 0, 1},
-		{ 1, 0}, { 1, 0},
-		{ 0,-1}, { 0,-1},
-		{-1, 0}, {-1, 0}, {-1, 0},
-		{ 0, 1}, { 0, 1}, { 0, 1},
-		{ 1, 0}, { 1, 0}, { 1, 0}, { 1, 0},
-		{ 0,-1}, { 0,-1}, { 0,-1}, { 0,-1},
-		{-1, 0}, {-1, 0}, {-1, 0}, {-1, 0}, {-1, 0},
-		{ 0, 1}, { 0, 1}, { 0, 1}, { 0, 1}, { 0, 1},
-		{ 1, 0}, { 1, 0}, { 1, 0}, { 1, 0}, { 1, 0}, { 1, 0},
-		{ 0,-1}, { 0,-1}, { 0,-1}, { 0,-1}, { 0,-1}, { 0,-1},
-		{-1, 0}, {-1, 0}, {-1, 0}, {-1, 0}, {-1, 0}, {-1, 0}, {-1, 0},
-		{ 0, 1}, { 0, 1}, { 0, 1}, { 0, 1}, { 0, 1}, { 0, 1}, { 0, 1},
-		{ 1, 0}, { 1, 0}, { 1, 0}, { 1, 0}, { 1, 0}, { 1, 0}, { 1, 0}, { 1, 0},
-		{ 0,-1}, { 0,-1}, { 0,-1}, { 0,-1}, { 0,-1}, { 0,-1}, { 0,-1}, { 0,-1},
-		{-1, 0}, {-1, 0}, {-1, 0}, {-1, 0}, {-1, 0}, {-1, 0}, {-1, 0}, {-1, 0},
-		{ 0, 0}
-	};
 	TileIndex tile = t->xy;
-	const TileIndexDiffC *p;
 
-	for (p = _statue_tiles; p != endof(_statue_tiles); ++p) {
-		if (DoBuildStatueOfCompany(tile)) {
-			SETBIT(t->statues, _current_player);
-			return;
-		}
-		tile = TILE_ADD(tile, ToTileIndexDiff(*p));
-	}
+	if (CircularTileSearch(tile, 9, SearchTileForStatue, 0))
+		SETBIT(t->statues, _current_player); ///< Once found and built, "inform" the Town
 }
 
 static void TownActionFundBuildings(Town* t)