cpp/openttd-patchpack/source Changeset - r23435:0f8f3f8f40ec

Changeset - r23435:0f8f3f8f40ec

Parent rev.

Child rev.

[Not reviewed]

master

0 12 1

Niels Martin Hansen - 6 years ago 2019-02-18 16:32:53
nielsm@indvikleren.dk

Codechange: Make a k-d tree index of towns

13 files changed with 75 insertions and 38 deletions:

projects/openttd_vs140.vcxproj

projects/openttd_vs140.vcxproj.filters

projects/openttd_vs141.vcxproj

projects/openttd_vs141.vcxproj.filters

projects/openttd_vs142.vcxproj

projects/openttd_vs142.vcxproj.filters

source.list

src/misc.cpp

src/saveload/afterload.cpp

src/saveload/town_sl.cpp

src/town.h

src/town_cmd.cpp

src/town_kdtree.h

0 comments (0 inline, 0 general)

projects/openttd_vs140.vcxproj

➞

Show inline comments

@@ @@ -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" />

projects/openttd_vs140.vcxproj.filters

➞

Show inline comments

@@ @@ -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>

projects/openttd_vs141.vcxproj

➞

Show inline comments

@@ @@ -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" />

projects/openttd_vs141.vcxproj.filters

➞

Show inline comments

@@ @@ -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>

projects/openttd_vs142.vcxproj

➞

Show inline comments

@@ @@ -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" />

projects/openttd_vs142.vcxproj.filters

➞

Show inline comments

@@ @@ -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>

source.list

➞

Show inline comments

@@ @@ -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

src/misc.cpp

➞

Show inline comments

@@ @@ -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 si @@
 	LinkGraphSchedule::Clear();
 	PoolBase::Clean(PT_NORMAL);
 	RebuildTownKdtree();
 	ResetPersistentNewGRFData();
 	InitializeSound();

src/saveload/afterload.cpp

➞

Show inline comments

@@ @@ -536,6 +536,8 @@ bool AfterLoadGame() @@
 	GamelogTestRevision();
 	GamelogTestMode();
 	RebuildTownKdtree();
 	if (IsSavegameVersionBefore(SLV_98)) GamelogGRFAddList(_grfconfig);
 	if (IsSavegameVersionBefore(SLV_119)) {

src/saveload/town_sl.cpp

➞

Show inline comments

@@ @@ -28,6 +28,7 @@ void RebuildTownCaches() @@
+{
 	Town *town;
 	InitializeBuildingCounts();
 	RebuildTownKdtree();
 	/* Reset town population and num_houses */
 	FOR_ALL_TOWNS(town) {

src/town.h

➞

Show inline comments

@@ @@ -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

src/town_cmd.cpp

➞

Show inline comments

@@ @@ -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; ///< @@
 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 t @@
  */
 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, TileIn @@
 	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 @@
+	}
 	/* 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 CheckIfAuthorityAllowsNewSta @@
  */
 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;
+		}
+	}
 	return best_town;
 	if (Town::GetNumItems() == 0) return NULL;
 	TownID tid = _town_kdtree.FindNearest(TileX(tile), TileY(tile));
 	Town *town = Town::Get(tid);
 	if (DistanceManhattan(tile, town->xy) < threshold) return town;
 	return NULL;
+}
 /**

src/town_kdtree.h

➞

Show inline comments

@@ new file 100644 @@
 /*
  * 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

0 comments (0 inline, 0 general)