(svn r14528) -Codechange: cache the closest town for all road tiles instead of only roads owned by tiles. This replaces a O(n) search over all towns from the road's tileloop with a O(1) lookup (PhilSophus)

7 files changed, 62 insertions, 8 deletions

diff --git a/src/openttd.cpp b/src/openttd.cpp
index 66c416557..b3ccfcb83 100644
--- a/src/openttd.cpp
+++ b/src/openttd.cpp
@@ -71,6 +71,7 @@
 #include "tree_map.h"
 #include "rail_map.h"
 #include "road_map.h"
+#include "road_cmd.h"
 #include "station_map.h"
 #include "town_map.h"
 #include "industry_map.h"
@@ -2561,6 +2562,9 @@ bool AfterLoadGame()
 	}
 
 	if (CheckSavegameVersion(103)) {
+		/* Non-town-owned roads now store the closest town */
+		InvalidateTownForRoadTile();
+
 		/* signs with invalid owner left from older savegames */
 		Sign *si;
 		FOR_ALL_SIGNS(si) {
diff --git a/src/road_cmd.cpp b/src/road_cmd.cpp
index 02c1ed6b2..bfa5075d1 100644
--- a/src/road_cmd.cpp
+++ b/src/road_cmd.cpp
@@ -4,6 +4,7 @@
 
 #include "stdafx.h"
 #include "openttd.h"
+#include "map_func.h"
 #include "bridge_map.h"
 #include "bridge.h"
 #include "cmd_helper.h"
@@ -317,6 +318,11 @@ static CommandCost RemoveRoad(TileIndex tile, uint32 flags, RoadBits pieces, Roa
 						/* Includes MarkTileDirtyByTile() */
 						DoClearSquare(tile);
 					} else {
+						if (rt == ROADTYPE_ROAD && IsRoadOwner(tile, ROADTYPE_ROAD, OWNER_TOWN)) {
+							/* Promote ownership from tram or highway and invalidate town index */
+							SetRoadOwner(tile, ROADTYPE_ROAD, GetRoadOwner(tile, (HasBit(rts, ROADTYPE_TRAM) ? ROADTYPE_TRAM : ROADTYPE_HWAY)));
+							SetTownIndex(tile, (TownID)INVALID_TOWN);
+						}
 						SetRoadBits(tile, ROAD_NONE, rt);
 						SetRoadTypes(tile, rts);
 						MarkTileDirtyByTile(tile);
@@ -354,6 +360,7 @@ static CommandCost RemoveRoad(TileIndex tile, uint32 flags, RoadBits pieces, Roa
 					if (reserved) SetTrackReservation(tile, tracks);
 				} else {
 					SetRoadTypes(tile, rts);
+					/* If we ever get HWAY and it is possible without road then we will need to promote ownership and invalidate town index here, too */
 				}
 				MarkTileDirtyByTile(tile);
 				YapfNotifyTrackLayoutChange(tile, FindFirstTrack(GetTrackBits(tile)));
@@ -479,6 +486,10 @@ CommandCost CmdBuildRoad(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
 	/* Road pieces are max 4 bitset values (NE, NW, SE, SW) and town can only be non-zero
 	 * if a non-company is building the road */
 	if ((IsValidCompanyID(_current_company) && p2 != 0) || (_current_company == OWNER_TOWN && !IsValidTownID(p2))) return CMD_ERROR;
+	if (_current_company != OWNER_TOWN) {
+		const Town *town = CalcClosestTownFromTile(tile, UINT_MAX);
+		p2 = (town != NULL) ? town->index : (TownID)INVALID_TOWN;
+	}
 
 	RoadBits pieces = Extract<RoadBits, 0>(p1);
 
@@ -654,7 +665,7 @@ do_clear:;
 				if (existing == ROAD_NONE || rtt == ROAD_TILE_CROSSING) {
 					SetRoadTypes(tile, GetRoadTypes(tile) | RoadTypeToRoadTypes(rt));
 					SetRoadOwner(tile, rt, _current_company);
-					if (_current_company == OWNER_TOWN && rt == ROADTYPE_ROAD) SetTownIndex(tile, p2);
+					if (rt == ROADTYPE_ROAD) SetTownIndex(tile, p2);
 				}
 				if (rtt != ROAD_TILE_CROSSING) SetRoadBits(tile, existing | pieces, rt);
 			} break;
@@ -886,7 +897,7 @@ CommandCost CmdBuildRoadDepot(TileIndex tile, uint32 flags, uint32 p1, uint32 p2
 		Depot *dep = new Depot(tile);
 		dep->town_index = ClosestTownFromTile(tile, UINT_MAX)->index;
 
-		MakeRoadDepot(tile, _current_company, dir, rt);
+		MakeRoadDepot(tile, _current_company, dir, rt, dep->town_index);
 		MarkTileDirtyByTile(tile);
 	}
 	return cost.AddCost(_price.build_road_depot);
@@ -1263,6 +1274,18 @@ void DrawRoadDepotSprite(int x, int y, DiagDirection dir, RoadType rt)
 	}
 }
 
+void InvalidateTownForRoadTile()
+{
+	TileIndex map_size = MapSize();
+
+	for (TileIndex t = 0; t < map_size; t++) {
+		if (IsTileType(t, MP_ROAD) && GetRoadOwner(t, ROADTYPE_ROAD) != OWNER_TOWN) {
+			/* GetRoadOwner(t, ROADTYPE_ROAD) is valid for road tiles even when there is no road */
+			SetTownIndex(t, (TownID)INVALID_TOWN);
+		}
+	}
+}
+
 static uint GetSlopeZ_Road(TileIndex tile, uint x, uint y)
 {
 	uint z;
diff --git a/src/road_cmd.h b/src/road_cmd.h
index 6597bb1b0..df92ecb3f 100644
--- a/src/road_cmd.h
+++ b/src/road_cmd.h
@@ -8,5 +8,6 @@
 #include "direction_type.h"
 
 void DrawRoadDepotSprite(int x, int y, DiagDirection dir, RoadType rt);
+void InvalidateTownForRoadTile();
 
 #endif /* ROAD_CMD_H */
diff --git a/src/road_map.h b/src/road_map.h
index dfd88ae3f..bc6639245 100644
--- a/src/road_map.h
+++ b/src/road_map.h
@@ -189,7 +189,7 @@ static inline void SetRoadOwner(TileIndex t, RoadType rt, Owner o)
 
 static inline bool IsRoadOwner(TileIndex t, RoadType rt, Owner o)
 {
-	assert(HasTileRoadType(t, rt));
+	assert(rt == ROADTYPE_ROAD || HasTileRoadType(t, rt));
 	return (GetRoadOwner(t, rt) == o);
 }
 
@@ -451,11 +451,11 @@ static inline void MakeRoadCrossing(TileIndex t, Owner road, Owner tram, Owner h
 }
 
 
-static inline void MakeRoadDepot(TileIndex t, Owner owner, DiagDirection dir, RoadType rt)
+static inline void MakeRoadDepot(TileIndex t, Owner owner, DiagDirection dir, RoadType rt, TownID town)
 {
 	SetTileType(t, MP_ROAD);
 	SetTileOwner(t, owner);
-	_m[t].m2 = 0;
+	_m[t].m2 = town;
 	_m[t].m3 = 0;
 	_m[t].m4 = 0;
 	_m[t].m5 = ROAD_TILE_DEPOT << 6 | dir;
diff --git a/src/station_cmd.cpp b/src/station_cmd.cpp
index 5bd1feb21..ecddffc75 100644
--- a/src/station_cmd.cpp
+++ b/src/station_cmd.cpp
@@ -1590,7 +1590,7 @@ CommandCost CmdRemoveRoadStop(TileIndex tile, uint32 flags, uint32 p1, uint32 p2
 		/* Rebuild the drive throuhg road stop. As a road stop can only be
 		 * removed by the owner of the roadstop, _current_company is the
 		 * owner of the road stop. */
-		MakeRoadNormal(tile, road_bits, rts, is_towns_road ? ClosestTownFromTile(tile, UINT_MAX)->index : 0,
+		MakeRoadNormal(tile, road_bits, rts, ClosestTownFromTile(tile, UINT_MAX)->index,
 				is_towns_road ? OWNER_TOWN : _current_company, _current_company, _current_company);
 	}
 
diff --git a/src/town_cmd.cpp b/src/town_cmd.cpp
index e55781b99..daa8a298b 100644
--- a/src/town_cmd.cpp
+++ b/src/town_cmd.cpp
@@ -8,6 +8,7 @@
 #include "debug.h"
 #include "road_map.h"
 #include "road_internal.h" /* Cleaning up road bits */
+#include "road_cmd.h"
 #include "landscape.h"
 #include "town_map.h"
 #include "tunnel_map.h"
@@ -93,6 +94,12 @@ Town::~Town()
 				break;
 
 			case MP_ROAD:
+				if (!IsRoadOwner(tile, ROADTYPE_ROAD, OWNER_TOWN) && GetTownIndex(tile) == this->index) {
+					/* Town-owned roads get cleared soon, anyway */
+					SetTownIndex(tile, (TownID)INVALID_TOWN);
+					break;
+				}
+				/* Fall-through */
 			case MP_TUNNELBRIDGE:
 				if (IsTileOwner(tile, OWNER_TOWN) &&
 						ClosestTownFromTile(tile, UINT_MAX) == this)
@@ -1558,6 +1565,7 @@ CommandCost CmdBuildTown(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
 		Town *t = new Town(tile);
 		_generating_world = true;
 		DoCreateTown(t, tile, townnameparts, (TownSizeMode)p2, p1);
+		InvalidateTownForRoadTile();
 		_generating_world = false;
 	}
 	return CommandCost();
@@ -2468,6 +2476,19 @@ Town *ClosestTownFromTile(TileIndex tile, uint threshold)
 				IsRoadOwner(tile, ROADTYPE_ROAD, OWNER_TOWN)
 			)) {
 		return GetTownByTile(tile);
+	} else if (IsTileType(tile, MP_ROAD)) {
+		TownID town_id = GetTownIndex(tile);
+		Town *town;
+
+		if (town_id == INVALID_TOWN) {
+			town = CalcClosestTownFromTile(tile, UINT_MAX);
+			if (town != NULL) SetTownIndex(tile, town->index);
+		} else {
+			town = GetTown(town_id);
+		}
+
+		if (town != NULL && town->IsValid() && DistanceManhattan(tile, town->xy) < threshold) return town;
+		return NULL;
 	} else {
 		return CalcClosestTownFromTile(tile, threshold);
 	}
diff --git a/src/town_gui.cpp b/src/town_gui.cpp
index aee252892..48f8524b1 100644
--- a/src/town_gui.cpp
+++ b/src/town_gui.cpp
@@ -25,6 +25,7 @@
 #include "tilehighlight_func.h"
 #include "string_func.h"
 #include "sortlist_type.h"
+#include "road_cmd.h"
 
 #include "table/sprites.h"
 #include "table/strings.h"
@@ -731,6 +732,7 @@ public:
 					ShowErrorMessage(STR_NO_SPACE_FOR_TOWN, STR_CANNOT_GENERATE_TOWN, 0, 0);
 				} else {
 					ScrollMainWindowToTile(t->xy);
+					InvalidateTownForRoadTile();
 				}
 			} break;
 
@@ -738,7 +740,11 @@ public:
 				this->HandleButtonClick(TSEW_MANYRANDOMTOWNS);
 
 				_generating_world = true;
-				if (!GenerateTowns()) ShowErrorMessage(STR_NO_SPACE_FOR_TOWN, STR_CANNOT_GENERATE_TOWN, 0, 0);
+				if (!GenerateTowns()) {
+					ShowErrorMessage(STR_NO_SPACE_FOR_TOWN, STR_CANNOT_GENERATE_TOWN, 0, 0);
+				} else {
+					InvalidateTownForRoadTile();
+				}
 				_generating_world = false;
 				break;
 
@@ -783,4 +789,3 @@ void ShowBuildTownWindow()
 	if (_game_mode != GM_EDITOR && !IsValidCompanyID(_current_company)) return;
 	AllocateWindowDescFront<ScenarioEditorTownGenerationWindow>(&_scen_edit_town_gen_desc, 0);
 }
-