summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--projects/openttd_vs140.vcxproj1
-rw-r--r--projects/openttd_vs140.vcxproj.filters3
-rw-r--r--projects/openttd_vs141.vcxproj1
-rw-r--r--projects/openttd_vs141.vcxproj.filters3
-rw-r--r--projects/openttd_vs142.vcxproj1
-rw-r--r--projects/openttd_vs142.vcxproj.filters3
-rw-r--r--source.list1
-rw-r--r--src/misc.cpp3
-rw-r--r--src/saveload/afterload.cpp2
-rw-r--r--src/saveload/town_sl.cpp1
-rw-r--r--src/town.h3
-rw-r--r--src/town_cmd.cpp69
-rw-r--r--src/town_kdtree.h20
13 files changed, 74 insertions, 37 deletions
diff --git a/projects/openttd_vs140.vcxproj b/projects/openttd_vs140.vcxproj
index 7643a693e..1d5365216 100644
--- a/projects/openttd_vs140.vcxproj
+++ b/projects/openttd_vs140.vcxproj
@@ -680,6 +680,7 @@
<ClInclude Include="..\src\toolbar_gui.h" />
<ClInclude Include="..\src\town.h" />
<ClInclude Include="..\src\town_type.h" />
+ <ClInclude Include="..\src\town_kdtree.h" />
<ClInclude Include="..\src\townname_func.h" />
<ClInclude Include="..\src\townname_type.h" />
<ClInclude Include="..\src\track_func.h" />
diff --git a/projects/openttd_vs140.vcxproj.filters b/projects/openttd_vs140.vcxproj.filters
index c33036fcc..b06f9576d 100644
--- a/projects/openttd_vs140.vcxproj.filters
+++ b/projects/openttd_vs140.vcxproj.filters
@@ -1128,6 +1128,9 @@
<ClInclude Include="..\src\town_type.h">
<Filter>Header Files</Filter>
</ClInclude>
+ <ClInclude Include="..\src\town_kdtree.h">
+ <Filter>Header Files</Filter>
+ </ClInclude>
<ClInclude Include="..\src\townname_func.h">
<Filter>Header Files</Filter>
</ClInclude>
diff --git a/projects/openttd_vs141.vcxproj b/projects/openttd_vs141.vcxproj
index f7dcc166a..8d2a9dfc9 100644
--- a/projects/openttd_vs141.vcxproj
+++ b/projects/openttd_vs141.vcxproj
@@ -680,6 +680,7 @@
<ClInclude Include="..\src\toolbar_gui.h" />
<ClInclude Include="..\src\town.h" />
<ClInclude Include="..\src\town_type.h" />
+ <ClInclude Include="..\src\town_kdtree.h" />
<ClInclude Include="..\src\townname_func.h" />
<ClInclude Include="..\src\townname_type.h" />
<ClInclude Include="..\src\track_func.h" />
diff --git a/projects/openttd_vs141.vcxproj.filters b/projects/openttd_vs141.vcxproj.filters
index c33036fcc..b06f9576d 100644
--- a/projects/openttd_vs141.vcxproj.filters
+++ b/projects/openttd_vs141.vcxproj.filters
@@ -1128,6 +1128,9 @@
<ClInclude Include="..\src\town_type.h">
<Filter>Header Files</Filter>
</ClInclude>
+ <ClInclude Include="..\src\town_kdtree.h">
+ <Filter>Header Files</Filter>
+ </ClInclude>
<ClInclude Include="..\src\townname_func.h">
<Filter>Header Files</Filter>
</ClInclude>
diff --git a/projects/openttd_vs142.vcxproj b/projects/openttd_vs142.vcxproj
index dc132eeb0..56455c2f8 100644
--- a/projects/openttd_vs142.vcxproj
+++ b/projects/openttd_vs142.vcxproj
@@ -680,6 +680,7 @@
<ClInclude Include="..\src\toolbar_gui.h" />
<ClInclude Include="..\src\town.h" />
<ClInclude Include="..\src\town_type.h" />
+ <ClInclude Include="..\src\town_kdtree.h" />
<ClInclude Include="..\src\townname_func.h" />
<ClInclude Include="..\src\townname_type.h" />
<ClInclude Include="..\src\track_func.h" />
diff --git a/projects/openttd_vs142.vcxproj.filters b/projects/openttd_vs142.vcxproj.filters
index c33036fcc..b06f9576d 100644
--- a/projects/openttd_vs142.vcxproj.filters
+++ b/projects/openttd_vs142.vcxproj.filters
@@ -1128,6 +1128,9 @@
<ClInclude Include="..\src\town_type.h">
<Filter>Header Files</Filter>
</ClInclude>
+ <ClInclude Include="..\src\town_kdtree.h">
+ <Filter>Header Files</Filter>
+ </ClInclude>
<ClInclude Include="..\src\townname_func.h">
<Filter>Header Files</Filter>
</ClInclude>
diff --git a/source.list b/source.list
index d241e7e85..969d90b9c 100644
--- a/source.list
+++ b/source.list
@@ -367,6 +367,7 @@ timetable.h
toolbar_gui.h
town.h
town_type.h
+town_kdtree.h
townname_func.h
townname_type.h
track_func.h
diff --git a/src/misc.cpp b/src/misc.cpp
index 8151f2dd3..c3130d85b 100644
--- a/src/misc.cpp
+++ b/src/misc.cpp
@@ -28,6 +28,7 @@
#include "core/pool_type.hpp"
#include "game/game.hpp"
#include "linkgraph/linkgraphschedule.h"
+#include "town_kdtree.h"
#include "safeguards.h"
@@ -75,6 +76,8 @@ void InitializeGame(uint size_x, uint size_y, bool reset_date, bool reset_settin
LinkGraphSchedule::Clear();
PoolBase::Clean(PT_NORMAL);
+ RebuildTownKdtree();
+
ResetPersistentNewGRFData();
InitializeSound();
diff --git a/src/saveload/afterload.cpp b/src/saveload/afterload.cpp
index 87e870056..07de26038 100644
--- a/src/saveload/afterload.cpp
+++ b/src/saveload/afterload.cpp
@@ -536,6 +536,8 @@ bool AfterLoadGame()
GamelogTestRevision();
GamelogTestMode();
+ RebuildTownKdtree();
+
if (IsSavegameVersionBefore(SLV_98)) GamelogGRFAddList(_grfconfig);
if (IsSavegameVersionBefore(SLV_119)) {
diff --git a/src/saveload/town_sl.cpp b/src/saveload/town_sl.cpp
index a31c886ec..bc2ed8be6 100644
--- a/src/saveload/town_sl.cpp
+++ b/src/saveload/town_sl.cpp
@@ -28,6 +28,7 @@ void RebuildTownCaches()
{
Town *town;
InitializeBuildingCounts();
+ RebuildTownKdtree();
/* Reset town population and num_houses */
FOR_ALL_TOWNS(town) {
diff --git a/src/town.h b/src/town.h
index 6cff5f761..76c3b770d 100644
--- a/src/town.h
+++ b/src/town.h
@@ -145,6 +145,9 @@ void UpdateAllTownVirtCoords();
void ShowTownViewWindow(TownID town);
void ExpandTown(Town *t);
+void RebuildTownKdtree();
+
+
/**
* Action types that a company must ask permission for to a town authority.
* @see CheckforTownRating
diff --git a/src/town_cmd.cpp b/src/town_cmd.cpp
index 4aad76f44..e56cfd417 100644
--- a/src/town_cmd.cpp
+++ b/src/town_cmd.cpp
@@ -38,6 +38,7 @@
#include "subsidy_func.h"
#include "core/pool_func.hpp"
#include "town.h"
+#include "town_kdtree.h"
#include "townname_func.h"
#include "core/random_func.hpp"
#include "core/backup_type.hpp"
@@ -59,6 +60,20 @@ CargoTypes _town_cargoes_accepted; ///< Bitmap of all cargoes accepted by houses
TownPool _town_pool("Town");
INSTANTIATE_POOL_METHODS(Town)
+
+TownKdtree _town_kdtree(&Kdtree_TownXYFunc);
+
+void RebuildTownKdtree()
+{
+ std::vector<TownID> townids;
+ Town *town;
+ FOR_ALL_TOWNS(town) {
+ townids.push_back(town->index);
+ }
+ _town_kdtree.Build(townids.begin(), townids.end());
+}
+
+
/**
* Check if a town 'owns' a bridge.
* Bridges to not directly have an owner, so we check the tiles adjacent to the bridge ends.
@@ -366,30 +381,9 @@ static void AnimateTile_Town(TileIndex tile)
*/
static bool IsCloseToTown(TileIndex tile, uint dist)
{
- /* On a large map with many towns, it may be faster to check the surroundings of the tile.
- * An iteration in TILE_AREA_LOOP() is generally 2 times faster than one in FOR_ALL_TOWNS(). */
- if (Town::GetNumItems() > (size_t) (dist * dist * 2)) {
- const int tx = TileX(tile);
- const int ty = TileY(tile);
- TileArea tile_area = TileArea(
- TileXY(max(0, tx - (int) dist), max(0, ty - (int) dist)),
- TileXY(min(MapMaxX(), tx + (int) dist), min(MapMaxY(), ty + (int) dist))
- );
- TILE_AREA_LOOP(atile, tile_area) {
- if (GetTileType(atile) == MP_HOUSE) {
- Town *t = Town::GetByTile(atile);
- if (DistanceManhattan(tile, t->xy) < dist) return true;
- }
- }
- return false;
- }
-
- const Town *t;
-
- FOR_ALL_TOWNS(t) {
- if (DistanceManhattan(tile, t->xy) < dist) return true;
- }
- return false;
+ if (_town_kdtree.Count() == 0) return false;
+ Town *t = Town::Get(_town_kdtree.FindNearest(TileX(tile), TileY(tile)));
+ return DistanceManhattan(tile, t->xy) < dist;
}
/**
@@ -1682,6 +1676,8 @@ static void DoCreateTown(Town *t, TileIndex tile, uint32 townnameparts, TownSize
t->grow_counter = t->index % TOWN_GROWTH_TICKS;
t->growth_rate = TownTicksToGameTicks(250);
+ _town_kdtree.Insert(t->index);
+
/* Set the default cargo requirement for town growth */
switch (_settings_game.game_creation.landscape) {
case LT_ARCTIC:
@@ -2092,6 +2088,9 @@ bool GenerateTowns(TownLayout layout)
town_names.clear();
+ /* Build the town k-d tree again to make sure it's well balanced */
+ RebuildTownKdtree();
+
if (current_number != 0) return true;
/* If current_number is still zero at this point, it means that not a single town has been created.
@@ -2867,7 +2866,10 @@ CommandCost CmdDeleteTown(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32
}
/* The town destructor will delete the other things related to the town. */
- if (flags & DC_EXEC) delete t;
+ if (flags & DC_EXEC) {
+ _town_kdtree.Remove(t->index);
+ delete t;
+ }
return CommandCost();
}
@@ -3392,19 +3394,12 @@ CommandCost CheckIfAuthorityAllowsNewStation(TileIndex tile, DoCommandFlag flags
*/
Town *CalcClosestTownFromTile(TileIndex tile, uint threshold)
{
- Town *t;
- uint best = threshold;
- Town *best_town = NULL;
-
- FOR_ALL_TOWNS(t) {
- uint dist = DistanceManhattan(tile, t->xy);
- if (dist < best) {
- best = dist;
- best_town = t;
- }
- }
+ if (Town::GetNumItems() == 0) return NULL;
- return best_town;
+ TownID tid = _town_kdtree.FindNearest(TileX(tile), TileY(tile));
+ Town *town = Town::Get(tid);
+ if (DistanceManhattan(tile, town->xy) < threshold) return town;
+ return NULL;
}
/**
diff --git a/src/town_kdtree.h b/src/town_kdtree.h
new file mode 100644
index 000000000..ae6b9e4ea
--- /dev/null
+++ b/src/town_kdtree.h
@@ -0,0 +1,20 @@
+/*
+ * This file is part of OpenTTD.
+ * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
+ * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/** @file town_kdtree.h Declarations for accessing the k-d tree of towns */
+
+#ifndef TOWN_KDTREE_H
+#define TOWN_KDTREE_H
+
+#include "core/kdtree.hpp"
+#include "town.h"
+
+inline uint16 Kdtree_TownXYFunc(TownID tid, int dim) { return (dim == 0) ? TileX(Town::Get(tid)->xy) : TileY(Town::Get(tid)->xy); }
+typedef Kdtree<TownID, decltype(&Kdtree_TownXYFunc), uint16, int> TownKdtree;
+extern TownKdtree _town_kdtree;
+
+#endif
generated by cgit v1.2.3-70-g09d2 (git 2.47.0) at 2024-11-26 03:20:28 +0000