(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)
--- a/docs/landscape.html Sat Oct 25 10:26:23 2008 +0000
+++ b/docs/landscape.html Sat Oct 25 13:51:47 2008 +0000
@@ -513,6 +513,7 @@
<td valign=top nowrap> </td>
<td>
<ul>
+ <li>m2: Index into the array of towns (owning town for town roads; closest town otherwise, INVALID_TOWN if not yet calculated)</li>
<li>m3 bit 7 set = on snow or desert</li>
<li>m7 bits 7..5: present road types
<table>
@@ -534,7 +535,6 @@
</li>
<li>m5 bits 7 clear: road or level-crossing
<ul>
- <li>m2: Index into the array of towns, 0 for non-town roads</li>
<li>m3 bits 6..4:
<table>
<tr>
--- a/docs/landscape_grid.html Sat Oct 25 10:26:23 2008 +0000
+++ b/docs/landscape_grid.html Sat Oct 25 13:51:47 2008 +0000
@@ -157,7 +157,7 @@
<td class="caption">road depot</td>
<td class="bits">-inherit-</td>
<td class="bits">-inherit-</td>
- <td class="bits"><span class="free">OOOO OOOO OOOO OOOO</span></td>
+ <td class="bits">-inherit-</td>
<td class="bits">X<span class="free">OOO OOOO</span></td>
<td class="bits"><span class="free">OOOO OOOO</span></td>
<td class="bits">XX<span class="free">OO OO</span>XX</td>
--- a/src/openttd.cpp Sat Oct 25 10:26:23 2008 +0000
+++ b/src/openttd.cpp Sat Oct 25 13:51:47 2008 +0000
@@ -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 @@
}
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) {
--- a/src/road_cmd.cpp Sat Oct 25 10:26:23 2008 +0000
+++ b/src/road_cmd.cpp Sat Oct 25 13:51:47 2008 +0000
@@ -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 @@
/* 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 @@
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 @@
/* 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 @@
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 @@
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 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;
--- a/src/road_cmd.h Sat Oct 25 10:26:23 2008 +0000
+++ b/src/road_cmd.h Sat Oct 25 13:51:47 2008 +0000
@@ -8,5 +8,6 @@
#include "direction_type.h"
void DrawRoadDepotSprite(int x, int y, DiagDirection dir, RoadType rt);
+void InvalidateTownForRoadTile();
#endif /* ROAD_CMD_H */
--- a/src/road_map.h Sat Oct 25 10:26:23 2008 +0000
+++ b/src/road_map.h Sat Oct 25 13:51:47 2008 +0000
@@ -189,7 +189,7 @@
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 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;
--- a/src/station_cmd.cpp Sat Oct 25 10:26:23 2008 +0000
+++ b/src/station_cmd.cpp Sat Oct 25 13:51:47 2008 +0000
@@ -1590,7 +1590,7 @@
/* 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);
}
--- a/src/town_cmd.cpp Sat Oct 25 10:26:23 2008 +0000
+++ b/src/town_cmd.cpp Sat Oct 25 13:51:47 2008 +0000
@@ -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 @@
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 @@
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 @@
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);
}
--- a/src/town_gui.cpp Sat Oct 25 10:26:23 2008 +0000
+++ b/src/town_gui.cpp Sat Oct 25 13:51:47 2008 +0000
@@ -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 @@
ShowErrorMessage(STR_NO_SPACE_FOR_TOWN, STR_CANNOT_GENERATE_TOWN, 0, 0);
} else {
ScrollMainWindowToTile(t->xy);
+ InvalidateTownForRoadTile();
}
} break;
@@ -738,7 +740,11 @@
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 @@
if (_game_mode != GM_EDITOR && !IsValidCompanyID(_current_company)) return;
AllocateWindowDescFront<ScenarioEditorTownGenerationWindow>(&_scen_edit_town_gen_desc, 0);
}
-