From a14ad77a36c836fd3f6940eadeb8161e7ad02f92 Mon Sep 17 00:00:00 2001 From: rubidium Date: Sat, 25 Oct 2008 13:51:47 +0000 Subject: (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) --- src/openttd.cpp | 4 ++++ src/road_cmd.cpp | 27 +++++++++++++++++++++++++-- src/road_cmd.h | 1 + src/road_map.h | 6 +++--- src/station_cmd.cpp | 2 +- src/town_cmd.cpp | 21 +++++++++++++++++++++ src/town_gui.cpp | 9 +++++++-- 7 files changed, 62 insertions(+), 8 deletions(-) (limited to 'src') 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(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(&_scen_edit_town_gen_desc, 0); } - -- cgit v1.2.3-54-g00ecf