cpp/openttd-patchpack/source Changeset - r23436:cfad304b5b27

Changeset - r23436:cfad304b5b27

Parent rev.

Child rev.

[Not reviewed]

master

0 13 1

Niels Martin Hansen - 5 years ago 2019-02-18 20:14:52
nielsm@indvikleren.dk

Codechange: Make a k-d tree index of stations

14 files changed with 127 insertions and 33 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/station.cpp

src/station_base.h

src/station_cmd.cpp

src/station_kdtree.h

src/town_cmd.cpp

0 comments (0 inline, 0 general)

projects/openttd_vs140.vcxproj

➞

Show inline comments

@@ @@ -643,12 +643,13 @@ @@
     <ClInclude Include="..\src\sound_type.h" />
     <ClInclude Include="..\src\sprite.h" />
     <ClInclude Include="..\src\spritecache.h" />
     <ClInclude Include="..\src\station_base.h" />
     <ClInclude Include="..\src\station_func.h" />
     <ClInclude Include="..\src\station_gui.h" />
     <ClInclude Include="..\src\station_kdtree.h" />
     <ClInclude Include="..\src\station_type.h" />
     <ClInclude Include="..\src\statusbar_gui.h" />
     <ClInclude Include="..\src\stdafx.h" />
     <ClInclude Include="..\src\story_base.h" />
     <ClInclude Include="..\src\story_type.h" />
     <ClInclude Include="..\src\strgen\strgen.h" />

projects/openttd_vs140.vcxproj.filters

➞

Show inline comments

@@ @@ -1023,12 +1023,15 @@ @@
     <ClInclude Include="..\src\station_func.h">
       <Filter>Header Files</Filter>
     </ClInclude>
     <ClInclude Include="..\src\station_gui.h">
       <Filter>Header Files</Filter>
     </ClInclude>
     <ClInclude Include="..\src\station_kdtree.h">
       <Filter>Header Files</Filter>
     </ClInclude>
     <ClInclude Include="..\src\station_type.h">
       <Filter>Header Files</Filter>
     </ClInclude>
     <ClInclude Include="..\src\statusbar_gui.h">
       <Filter>Header Files</Filter>
     </ClInclude>

projects/openttd_vs141.vcxproj

➞

Show inline comments

@@ @@ -643,12 +643,13 @@ @@
     <ClInclude Include="..\src\sound_type.h" />
     <ClInclude Include="..\src\sprite.h" />
     <ClInclude Include="..\src\spritecache.h" />
     <ClInclude Include="..\src\station_base.h" />
     <ClInclude Include="..\src\station_func.h" />
     <ClInclude Include="..\src\station_gui.h" />
     <ClInclude Include="..\src\station_kdtree.h" />
     <ClInclude Include="..\src\station_type.h" />
     <ClInclude Include="..\src\statusbar_gui.h" />
     <ClInclude Include="..\src\stdafx.h" />
     <ClInclude Include="..\src\story_base.h" />
     <ClInclude Include="..\src\story_type.h" />
     <ClInclude Include="..\src\strgen\strgen.h" />

projects/openttd_vs141.vcxproj.filters

➞

Show inline comments

@@ @@ -1023,12 +1023,15 @@ @@
     <ClInclude Include="..\src\station_func.h">
       <Filter>Header Files</Filter>
     </ClInclude>
     <ClInclude Include="..\src\station_gui.h">
       <Filter>Header Files</Filter>
     </ClInclude>
     <ClInclude Include="..\src\station_kdtree.h">
       <Filter>Header Files</Filter>
     </ClInclude>
     <ClInclude Include="..\src\station_type.h">
       <Filter>Header Files</Filter>
     </ClInclude>
     <ClInclude Include="..\src\statusbar_gui.h">
       <Filter>Header Files</Filter>
     </ClInclude>

projects/openttd_vs142.vcxproj

➞

Show inline comments

@@ @@ -643,12 +643,13 @@ @@
     <ClInclude Include="..\src\sound_type.h" />
     <ClInclude Include="..\src\sprite.h" />
     <ClInclude Include="..\src\spritecache.h" />
     <ClInclude Include="..\src\station_base.h" />
     <ClInclude Include="..\src\station_func.h" />
     <ClInclude Include="..\src\station_gui.h" />
     <ClInclude Include="..\src\station_kdtree.h" />
     <ClInclude Include="..\src\station_type.h" />
     <ClInclude Include="..\src\statusbar_gui.h" />
     <ClInclude Include="..\src\stdafx.h" />
     <ClInclude Include="..\src\story_base.h" />
     <ClInclude Include="..\src\story_type.h" />
     <ClInclude Include="..\src\strgen\strgen.h" />

projects/openttd_vs142.vcxproj.filters

➞

Show inline comments

@@ @@ -1023,12 +1023,15 @@ @@
     <ClInclude Include="..\src\station_func.h">
       <Filter>Header Files</Filter>
     </ClInclude>
     <ClInclude Include="..\src\station_gui.h">
       <Filter>Header Files</Filter>
     </ClInclude>
     <ClInclude Include="..\src\station_kdtree.h">
       <Filter>Header Files</Filter>
     </ClInclude>
     <ClInclude Include="..\src\station_type.h">
       <Filter>Header Files</Filter>
     </ClInclude>
     <ClInclude Include="..\src\statusbar_gui.h">
       <Filter>Header Files</Filter>
     </ClInclude>

source.list

➞

Show inline comments

@@ @@ -330,12 +330,13 @@ sound_func.h @@
 sound_type.h
 sprite.h
 spritecache.h
 station_base.h
 station_func.h
 station_gui.h
 station_kdtree.h
 station_type.h
 statusbar_gui.h
 stdafx.h
 story_base.h
 story_type.h
 strgen/strgen.h

src/misc.cpp

➞

Show inline comments

@@ @@ -25,12 +25,13 @@ @@
 #include "tilehighlight_func.h"
 #include "network/network_func.h"
 #include "window_func.h"
 #include "core/pool_type.hpp"
 #include "game/game.hpp"
 #include "linkgraph/linkgraphschedule.h"
 #include "station_kdtree.h"
 #include "town_kdtree.h"
 #include "safeguards.h"
 extern TileIndex _cur_tileloop_tile;
@@ @@ -73,12 +74,13 @@ void InitializeGame(uint size_x, uint si @@
 		InitializeOldNames();
+	}
 	LinkGraphSchedule::Clear();
 	PoolBase::Clean(PT_NORMAL);
 	RebuildStationKdtree();
 	RebuildTownKdtree();
 	ResetPersistentNewGRFData();
 	InitializeSound();
 	InitializeMusic();

src/saveload/afterload.cpp

➞

Show inline comments

@@ @@ -534,12 +534,13 @@ bool AfterLoadGame() @@
 	if (IsSavegameVersionBefore(SLV_98)) GamelogOldver();
 	GamelogTestRevision();
 	GamelogTestMode();
 	RebuildTownKdtree();
 	RebuildStationKdtree();
 	if (IsSavegameVersionBefore(SLV_98)) GamelogGRFAddList(_grfconfig);
 	if (IsSavegameVersionBefore(SLV_119)) {
 		_pause_mode = (_pause_mode == 2) ? PM_PAUSED_NORMAL : PM_UNPAUSED;
 	} else if (_network_dedicated && (_pause_mode & PM_PAUSED_ERROR) != 0) {

src/station.cpp

➞

Show inline comments

@@ @@ -18,12 +18,13 @@ @@
 #include "command_func.h"
 #include "news_func.h"
 #include "aircraft.h"
 #include "vehiclelist.h"
 #include "core/pool_func.hpp"
 #include "station_base.h"
 #include "station_kdtree.h"
 #include "roadstop_base.h"
 #include "industry.h"
 #include "town.h"
 #include "core/random_func.hpp"
 #include "linkgraph/linkgraph.h"
 #include "linkgraph/linkgraphschedule.h"
@@ @@ -33,12 +34,26 @@ @@
 #include "safeguards.h"
 /** The pool of stations. */
 StationPool _station_pool("Station");
 INSTANTIATE_POOL_METHODS(Station)
 StationKdtree _station_kdtree(Kdtree_StationXYFunc);
 void RebuildStationKdtree()
+{
 	std::vector<StationID> stids;
 	BaseStation *st;
 	FOR_ALL_STATIONS(st) {
 		stids.push_back(st->index);
+	}
 	_station_kdtree.Build(stids.begin(), stids.end());
+}
 BaseStation::~BaseStation()
+{
 	free(this->name);
 	free(this->speclist);
 	if (CleaningPool()) return;
@@ @@ -143,12 +158,14 @@ Station::~Station() @@
 	for (CargoID c = 0; c < NUM_CARGO; c++) {
 		this->goods[c].cargo.Truncate();
+	}
 	CargoPacket::InvalidateAllFrom(this->index);
 	_station_kdtree.Remove(this->index);
+}
 /**
  * Invalidating of the JoinStation window has to be done
  * after removing item from the pool.

src/station_base.h

➞

Show inline comments

@@ @@ -553,7 +553,9 @@ public: @@
 	virtual TileIterator *Clone() const
+	{
 		return new AirportTileIterator(*this);
+	}
 };
 void RebuildStationKdtree();
 #endif /* STATION_BASE_H */

src/station_cmd.cpp

➞

Show inline comments

@@ @@ -34,12 +34,13 @@ @@
 #include "date_func.h"
 #include "vehicle_func.h"
 #include "string_func.h"
 #include "animated_tile_func.h"
 #include "elrail_func.h"
 #include "station_base.h"
 #include "station_kdtree.h"
 #include "roadstop_base.h"
 #include "newgrf_railtype.h"
 #include "waypoint_base.h"
 #include "waypoint_func.h"
 #include "pbs.h"
 #include "debug.h"
@@ @@ -356,25 +357,27 @@ static StringID GenerateStationName(Stat @@
  * @param tile the tile to search from.
  * @return the closest station or NULL if too far.
  */
 static Station *GetClosestDeletedStation(TileIndex tile)
+{
 	uint threshold = 8;
 	Station *best_station = NULL;
 	Station *st;
 	FOR_ALL_STATIONS(st) {
 	ForAllStationsRadius(tile, threshold, [&](Station *st) {
 		if (!st->IsInUse() && st->owner == _current_company) {
 			uint cur_dist = DistanceManhattan(tile, st->xy);
 			if (cur_dist < threshold) {
 				threshold = cur_dist;
 				best_station = st;
 			} else if (cur_dist == threshold && best_station != NULL) {
 				/* In case of a tie, lowest station ID wins */
 				if (st->index < best_station->index) best_station = st;
+			}
+		}
+	}
+	});
 	return best_station;
+}
 void Station::GetTileArea(TileArea *ta, StationType type) const
@@ @@ -664,14 +667,19 @@ static void UpdateStationSignCoord(BaseS @@
+{
 	const StationRect *r = &st->rect;
 	if (r->IsEmpty()) return; // no tiles belong to this station
 	/* clamp sign coord to be inside the station rect */
 	st->xy = TileXY(ClampU(TileX(st->xy), r->left, r->right), ClampU(TileY(st->xy), r->top, r->bottom));
 	st->UpdateVirtCoord();
 	TileIndex new_xy = TileXY(ClampU(TileX(st->xy), r->left, r->right), ClampU(TileY(st->xy), r->top, r->bottom));
 	if (new_xy != st->xy) {
 		_station_kdtree.Remove(st->index);
 		st->xy = new_xy;
 		_station_kdtree.Insert(st->index);
 		st->UpdateVirtCoord();
+	}
 	if (!Station::IsExpected(st)) return;
 	Station *full_station = Station::From(st);
 	for (CargoID c = 0; c < NUM_CARGO; ++c) {
 		LinkGraphID lg = full_station->goods[c].link_graph;
 		if (!LinkGraph::IsValidID(lg)) continue;
@@ @@ -703,12 +711,13 @@ static CommandCost BuildStationPart(Stat @@
 	} else {
 		/* allocate and initialize new station */
 		if (!Station::CanAllocateItem()) return_cmd_error(STR_ERROR_TOO_MANY_STATIONS_LOADING);
 		if (flags & DC_EXEC) {
 			*st = new Station(area.tile);
 			_station_kdtree.Insert((*st)->index);
 			(*st)->town = ClosestTownFromTile(area.tile, UINT_MAX);
 			(*st)->string_id = GenerateStationName(*st, area.tile, name_class);
 			if (Company::IsValidID(_current_company)) {
 				SetBit((*st)->town->have_ratings, _current_company);
@@ @@ -3691,26 +3700,23 @@ void StationMonthlyLoop() @@
+	}
+}
 void ModifyStationRatingAround(TileIndex tile, Owner owner, int amount, uint radius)
+{
 	Station *st;
 	FOR_ALL_STATIONS(st) {
 		if (st->owner == owner &&
 				DistanceManhattan(tile, st->xy) <= radius) {
 	ForAllStationsRadius(tile, radius, [&](Station *st) {
 		if (st->owner == owner) {
 			for (CargoID i = 0; i < NUM_CARGO; i++) {
 				GoodsEntry *ge = &st->goods[i];
 				if (ge->status != 0) {
 					ge->rating = Clamp(ge->rating + amount, 0, 255);
+				}
+			}
+		}
+	}
+	});
+}
 static uint UpdateStationWaiting(Station *st, CargoID type, uint amount, SourceType source_type, SourceID source_id)
+{
 	/* We can't allocate a CargoPacket? Then don't do anything
 	 * at all; i.e. just discard the incoming cargo. */
@@ @@ -3944,12 +3950,13 @@ void BuildOilRig(TileIndex tile) @@
 	if (!Station::CanAllocateItem()) {
 		DEBUG(misc, 0, "Can't allocate station for oilrig at 0x%X, reverting to oilrig only", tile);
 		return;
+	}
 	Station *st = new Station(tile);
 	_station_kdtree.Insert(st->index);
 	st->town = ClosestTownFromTile(tile, UINT_MAX);
 	st->string_id = GenerateStationName(st, tile, STATIONNAMING_OILRIG);
 	assert(IsTileType(tile, MP_INDUSTRY));
 	/* Mark industry as associated both ways */

src/station_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 station_kdtree.h Declarations for accessing the k-d tree of stations */
 #ifndef STATION_KDTREE_H
 #define STATION_KDTREE_H
 #include "core/kdtree.hpp"
 #include "core/math_func.hpp"
 #include "station_base.h"
 #include "map_func.h"
 inline uint16 Kdtree_StationXYFunc(StationID stid, int dim) { return (dim == 0) ? TileX(BaseStation::Get(stid)->xy) : TileY(BaseStation::Get(stid)->xy); }
 typedef Kdtree<StationID, decltype(&Kdtree_StationXYFunc), uint16, int> StationKdtree;
 extern StationKdtree _station_kdtree;
 /**
  * Call a function on all stations whose sign is within a radius of a center tile.
  * @param center  Central tile to search around.
  * @param radius  Distance in both X and Y to search within.
  * @param func    The function to call, must take a single parameter which is Station*.
  */
 template <typename Func>
 void ForAllStationsRadius(TileIndex center, uint radius, Func func)
+{
 	uint16 x1, y1, x2, y2;
 	x1 = (uint16)max<int>(0, TileX(center) - radius);
 	x2 = (uint16)min<int>(TileX(center) + radius + 1, MapSizeX());
 	y1 = (uint16)max<int>(0, TileY(center) - radius);
 	y2 = (uint16)min<int>(TileY(center) + radius + 1, MapSizeY());
 	_station_kdtree.FindContained(x1, y1, x2, y2, [&](StationID id) {
 		func(Station::Get(id));
 	});
+}
 #endif

src/town_cmd.cpp

➞

Show inline comments

@@ @@ -15,12 +15,13 @@ @@
 #include "landscape.h"
 #include "viewport_func.h"
 #include "cmd_helper.h"
 #include "command_func.h"
 #include "industry.h"
 #include "station_base.h"
 #include "station_kdtree.h"
 #include "company_base.h"
 #include "news_func.h"
 #include "error.h"
 #include "object.h"
 #include "genworld.h"
 #include "newgrf_debug.h"
@@ @@ -3194,38 +3195,50 @@ CommandCost CmdDoTownAction(TileIndex ti @@
 		SetWindowDirty(WC_TOWN_AUTHORITY, p1);
+	}
 	return cost;
+}
 template <typename Func>
 static void ForAllStationsNearTown(Town *t, Func func)
+{
 	/* Ideally the search radius should be close to the actual town zone 0 radius.
 	 * The true radius is not stored or calculated anywhere, only the squared radius. */
 	/* The efficiency of this search might be improved for large towns and many stations on the map,
 	 * by using an integer square root approximation giving a value not less than the true square root. */
 	uint search_radius = t->cache.squared_town_zone_radius[0] / 2;
 	ForAllStationsRadius(t->xy, search_radius, [&](const Station * st) {
 		if (DistanceSquare(st->xy, t->xy) <= t->cache.squared_town_zone_radius[0]) {
 			func(st);
+		}
 	});
+}
 static void UpdateTownRating(Town *t)
+{
 	/* Increase company ratings if they're low */
 	const Company *c;
 	FOR_ALL_COMPANIES(c) {
 		if (t->ratings[c->index] < RATING_GROWTH_MAXIMUM) {
 			t->ratings[c->index] = min((int)RATING_GROWTH_MAXIMUM, t->ratings[c->index] + RATING_GROWTH_UP_STEP);
+		}
+	}
 	const Station *st;
 	FOR_ALL_STATIONS(st) {
 		if (DistanceSquare(st->xy, t->xy) <= t->cache.squared_town_zone_radius[0]) {
 			if (st->time_since_load <= 20 || st->time_since_unload <= 20) {
 				if (Company::IsValidID(st->owner)) {
 					int new_rating = t->ratings[st->owner] + RATING_STATION_UP_STEP;
 					t->ratings[st->owner] = min(new_rating, INT16_MAX); // do not let it overflow
+				}
 			} else {
 				if (Company::IsValidID(st->owner)) {
 					int new_rating = t->ratings[st->owner] + RATING_STATION_DOWN_STEP;
 					t->ratings[st->owner] = max(new_rating, INT16_MIN);
+				}
 	ForAllStationsNearTown(t, [&](const Station *st) {
 		if (st->time_since_load <= 20 || st->time_since_unload <= 20) {
 			if (Company::IsValidID(st->owner)) {
 				int new_rating = t->ratings[st->owner] + RATING_STATION_UP_STEP;
 				t->ratings[st->owner] = min(new_rating, INT16_MAX); // do not let it overflow
+			}
 		} else {
 			if (Company::IsValidID(st->owner)) {
 				int new_rating = t->ratings[st->owner] + RATING_STATION_DOWN_STEP;
 				t->ratings[st->owner] = max(new_rating, INT16_MIN);
+			}
+		}
+	}
+	});
 	/* clamp all ratings to valid values */
 	for (uint i = 0; i < MAX_COMPANIES; i++) {
 		t->ratings[i] = Clamp(t->ratings[i], RATING_MINIMUM, RATING_MAXIMUM);
+	}
@@ @@ -3254,20 +3267,17 @@ static void UpdateTownGrowCounter(Town * @@
  * @param t The town to calculate stations for
  * @returns Amount of active stations
  */
 static int CountActiveStations(Town *t)
+{
 	int n = 0;
 	const Station *st;
 	FOR_ALL_STATIONS(st) {
 		if (DistanceSquare(st->xy, t->xy) <= t->cache.squared_town_zone_radius[0]) {
 			if (st->time_since_load <= 20 || st->time_since_unload <= 20) {
 				n++;
+			}
 	ForAllStationsNearTown(t, [&](const Station * st) {
 		if (st->time_since_load <= 20 || st->time_since_unload <= 20) {
 			n++;
+		}
+	}
+	});
 	return n;
+}
 /**
  * Calculates town growth rate in normal conditions (custom growth rate not set).
  * If town growth speed is set to None(0) returns the same rate as if it was Normal(2).

0 comments (0 inline, 0 general)