cpp/openttd-patchpack/source Changeset - r26942:b4e367b734d9

Changeset - r26942:b4e367b734d9

Parent rev.

Child rev.

[Not reviewed]

master

0 2 0

Jonathan G Rennison - 5 years ago 2019-09-23 17:45:37
j.g.rennison@gmail.com

Fix: O(N^2) cost of Station::RecomputeCatchmentForAll

Station::RemoveFromAllNearbyLists does not need to be called when
all station nearby lists have been cleared and are being regenerated.

2 files changed with 7 insertions and 4 deletions:

src/station.cpp

src/station_base.h

0 comments (0 inline, 0 general)

src/station.cpp

➞

Show inline comments

@@ @@ -452,17 +452,18 @@ bool Station::CatchmentCoversTown(TownID @@
 	return false;
+}
 /**
  * Recompute tiles covered in our catchment area.
  * This will additionally recompute nearby towns and industries.
  * @param no_clear_nearby_lists If Station::RemoveFromAllNearbyLists does not need to be called.
  */
 void Station::RecomputeCatchment()
+void Station::RecomputeCatchment(bool no_clear_nearby_lists)
+{
 	this->industries_near.clear();
 	this->RemoveFromAllNearbyLists();
+	if (!no_clear_nearby_lists) this->RemoveFromAllNearbyLists();
 	if (this->rect.IsEmpty()) {
 		this->catchment_tiles.Reset();
 		return;
+	}
@@ @@ -523,13 +524,15 @@ void Station::RecomputeCatchment() @@
 /**
  * Recomputes catchment of all stations.
  * This will additionally recompute nearby stations for all towns and industries.
  */
 /* static */ void Station::RecomputeCatchmentForAll()
+{
 	for (Station *st : Station::Iterate()) { st->RecomputeCatchment(); }
 	for (Town *t : Town::Iterate()) { t->stations_near.clear(); }
 	for (Industry *i : Industry::Iterate()) { i->stations_near.clear(); }
 	for (Station *st : Station::Iterate()) { st->RecomputeCatchment(true); }
+}
 /************************************************************************/
 /*                     StationRect implementation                       */
 /************************************************************************/

src/station_base.h

➞

Show inline comments

@@ @@ -498,13 +498,13 @@ public: @@
 	void MoveSign(TileIndex new_xy) override;
 	void AfterStationTileSetChange(bool adding, StationType type);
 	uint GetPlatformLength(TileIndex tile, DiagDirection dir) const override;
 	uint GetPlatformLength(TileIndex tile) const override;
 	void RecomputeCatchment();
+	void RecomputeCatchment(bool no_clear_nearby_lists = false);
 	static void RecomputeCatchmentForAll();
 	uint GetCatchmentRadius() const;
 	Rect GetCatchmentRect() const;
 	bool CatchmentCoversTown(TownID t) const;
 	void AddIndustryToDeliver(Industry *ind, TileIndex tile);

0 comments (0 inline, 0 general)