Fix #7847: Use ViewportSign coordinates for sign Kdtree coordinates (#7849)

Ensure the same coordinates are used for station/town/player signs regardless of how the landscape changes below it after the coordinates were first determined.

By keeping track of whether each ViewportSign is valid for Kdtree use (and only ever registering the viewport sign when the object is valid) a lot of code can be simplified and become more robust at the same time.

12 files changed, 68 insertions, 60 deletions

diff --git a/src/base_station_base.h b/src/base_station_base.h
index 112fa722b..a23a7bf51 100644
--- a/src/base_station_base.h
+++ b/src/base_station_base.h
@@ -51,7 +51,7 @@ struct StationRect : public Rect {
 /** Base class for all station-ish types */
 struct BaseStation : StationPool::PoolItem<&_station_pool> {
 	TileIndex xy;                   ///< Base tile of the station
-	ViewportSign sign;              ///< NOSAVE: Dimensions of sign
+	TrackedViewportSign sign;       ///< NOSAVE: Dimensions of sign
 	byte delete_ctr;                ///< Delete counter. If greater than 0 then it is decremented until it reaches 0; the waypoint is then is deleted.
 
 	char *name;                     ///< Custom name
diff --git a/src/signs.cpp b/src/signs.cpp
index 407ab8606..c42644269 100644
--- a/src/signs.cpp
+++ b/src/signs.cpp
@@ -13,6 +13,7 @@
 #include "signs_func.h"
 #include "strings_func.h"
 #include "core/pool_func.hpp"
+#include "viewport_kdtree.h"
 
 #include "table/strings.h"
 
@@ -46,8 +47,13 @@ Sign::~Sign()
 void Sign::UpdateVirtCoord()
 {
 	Point pt = RemapCoords(this->x, this->y, this->z);
+
+	if (this->sign.kdtree_valid) _viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeSign(this->index));
+
 	SetDParam(0, this->index);
 	this->sign.UpdatePosition(pt.x, pt.y - 6 * ZOOM_LVL_BASE, STR_WHITE_SIGN);
+
+	_viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeSign(this->index));
 }
 
 /** Update the coordinates of all signs */
diff --git a/src/signs_base.h b/src/signs_base.h
index 1c677db17..e92a05e2f 100644
--- a/src/signs_base.h
+++ b/src/signs_base.h
@@ -19,12 +19,12 @@ typedef Pool<Sign, SignID, 16, 64000> SignPool;
 extern SignPool _sign_pool;
 
 struct Sign : SignPool::PoolItem<&_sign_pool> {
-	char *name;
-	ViewportSign sign;
-	int32        x;
-	int32        y;
-	int32        z;
-	Owner        owner; // placed by this company. Anyone can delete them though. OWNER_NONE for gray signs from old games.
+	char               *name;
+	TrackedViewportSign sign;
+	int32               x;
+	int32               y;
+	int32               z;
+	Owner               owner; // placed by this company. Anyone can delete them though. OWNER_NONE for gray signs from old games.
 
 	Sign(Owner owner = INVALID_OWNER);
 	~Sign();
diff --git a/src/signs_cmd.cpp b/src/signs_cmd.cpp
index 8b074e46b..d2caa4a23 100644
--- a/src/signs_cmd.cpp
+++ b/src/signs_cmd.cpp
@@ -57,7 +57,6 @@ CommandCost CmdPlaceSign(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32
 			si->name = stredup(text);
 		}
 		si->UpdateVirtCoord();
-		_viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeSign(si->index));
 		InvalidateWindowData(WC_SIGN_LIST, 0, 0);
 		_new_sign_id = si->index;
 	}
@@ -99,7 +98,7 @@ CommandCost CmdRenameSign(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32
 	} else { // Delete sign
 		if (flags & DC_EXEC) {
 			si->sign.MarkDirty();
-			_viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeSign(si->index));
+			if (si->sign.kdtree_valid) _viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeSign(si->index));
 			delete si;
 
 			InvalidateWindowData(WC_SIGN_LIST, 0, 0);
diff --git a/src/station.cpp b/src/station.cpp
index 7e89bc1e2..59fee57da 100644
--- a/src/station.cpp
+++ b/src/station.cpp
@@ -162,7 +162,7 @@ Station::~Station()
 	CargoPacket::InvalidateAllFrom(this->index);
 
 	_station_kdtree.Remove(this->index);
-	_viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeStation(this->index));
+	if (this->sign.kdtree_valid) _viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeStation(this->index));
 }
 
 
diff --git a/src/station_cmd.cpp b/src/station_cmd.cpp
index cb64873b6..78a0896ea 100644
--- a/src/station_cmd.cpp
+++ b/src/station_cmd.cpp
@@ -420,10 +420,14 @@ void Station::UpdateVirtCoord()
 	pt.y -= 32 * ZOOM_LVL_BASE;
 	if ((this->facilities & FACIL_AIRPORT) && this->airport.type == AT_OILRIG) pt.y -= 16 * ZOOM_LVL_BASE;
 
+	if (this->sign.kdtree_valid) _viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeStation(this->index));
+
 	SetDParam(0, this->index);
 	SetDParam(1, this->facilities);
 	this->sign.UpdatePosition(pt.x, pt.y, STR_VIEWPORT_STATION);
 
+	_viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeStation(this->index));
+
 	SetWindowDirty(WC_STATION_VIEW, this->index);
 }
 
@@ -435,13 +439,11 @@ void Station::MoveSign(TileIndex new_xy)
 {
 	if (this->xy == new_xy) return;
 
-	_viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeStation(this->index));
 	_station_kdtree.Remove(this->index);
 
 	this->BaseStation::MoveSign(new_xy);
 
 	_station_kdtree.Insert(this->index);
-	_viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeStation(this->index));
 }
 
 /** Update the virtual coords needed to draw the station sign for all stations. */
@@ -692,7 +694,6 @@ static CommandCost BuildStationPart(Station **st, DoCommandFlag flags, bool reus
 		if (flags & DC_EXEC) {
 			*st = new Station(area.tile);
 			_station_kdtree.Insert((*st)->index);
-			_viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeStation((*st)->index));
 
 			(*st)->town = ClosestTownFromTile(area.tile, UINT_MAX);
 			(*st)->string_id = GenerateStationName(*st, area.tile, name_class);
@@ -4157,7 +4158,6 @@ void BuildOilRig(TileIndex tile)
 	st->rect.BeforeAddTile(tile, StationRect::ADD_FORCE);
 
 	st->UpdateVirtCoord();
-	_viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeStation(st->index));
 	st->RecomputeCatchment();
 	UpdateStationAcceptance(st, false);
 }
diff --git a/src/town.h b/src/town.h
index 818ee643b..d07f9cc23 100644
--- a/src/town.h
+++ b/src/town.h
@@ -43,7 +43,7 @@ extern TownPool _town_pool;
 struct TownCache {
 	uint32 num_houses;                        ///< Amount of houses
 	uint32 population;                        ///< Current population of people
-	ViewportSign sign;                        ///< Location of name sign, UpdateVirtCoord updates this
+	TrackedViewportSign sign;                 ///< Location of name sign, UpdateVirtCoord updates this
 	PartOfSubsidy part_of_subsidy;            ///< Is this town a source/destination of a subsidy?
 	uint32 squared_town_zone_radius[HZB_END]; ///< UpdateTownRadius updates this given the house count
 	BuildingCounts<uint16> building_counts;   ///< The number of each type of building in the town
diff --git a/src/town_cmd.cpp b/src/town_cmd.cpp
index 139e0217d..fbfd87492 100644
--- a/src/town_cmd.cpp
+++ b/src/town_cmd.cpp
@@ -394,12 +394,17 @@ static bool IsCloseToTown(TileIndex tile, uint dist)
 void Town::UpdateVirtCoord()
 {
 	Point pt = RemapCoords2(TileX(this->xy) * TILE_SIZE, TileY(this->xy) * TILE_SIZE);
+
+	if (this->cache.sign.kdtree_valid) _viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeTown(this->index));
+
 	SetDParam(0, this->index);
 	SetDParam(1, this->cache.population);
 	this->cache.sign.UpdatePosition(pt.x, pt.y - 24 * ZOOM_LVL_BASE,
 		_settings_client.gui.population_in_label ? STR_VIEWPORT_TOWN_POP : STR_VIEWPORT_TOWN,
 		STR_VIEWPORT_TOWN);
 
+	_viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeTown(this->index));
+
 	SetWindowDirty(WC_TOWN_VIEW, this->index);
 }
 
@@ -1782,7 +1787,6 @@ static void DoCreateTown(Town *t, TileIndex tile, uint32 townnameparts, TownSize
 	t->townnameparts = townnameparts;
 
 	t->UpdateVirtCoord();
-	_viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeTown(t->index));
 	InvalidateWindowData(WC_TOWN_DIRECTORY, 0, 0);
 
 	t->InitializeLayout(layout);
@@ -2942,7 +2946,7 @@ 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) {
 		_town_kdtree.Remove(t->index);
-		_viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeTown(t->index));
+		if (t->cache.sign.kdtree_valid) _viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeTown(t->index));
 		delete t;
 	}
 
diff --git a/src/viewport.cpp b/src/viewport.cpp
index 552fb467d..94245cf6c 100644
--- a/src/viewport.cpp
+++ b/src/viewport.cpp
@@ -2178,13 +2178,9 @@ ViewportSignKdtreeItem ViewportSignKdtreeItem::MakeStation(StationID id)
 	item.id.station = id;
 
 	const Station *st = Station::Get(id);
-	Point pt = RemapCoords(TileX(st->xy) * TILE_SIZE, TileY(st->xy) * TILE_SIZE, GetTileMaxZ(st->xy) * TILE_HEIGHT);
-
-	pt.y -= 32 * ZOOM_LVL_BASE;
-	if ((st->facilities & FACIL_AIRPORT) && st->airport.type == AT_OILRIG) pt.y -= 16 * ZOOM_LVL_BASE;
-
-	item.center = pt.x;
-	item.top = pt.y;
+	assert(st->sign.kdtree_valid);
+	item.center = st->sign.center;
+	item.top = st->sign.top;
 
 	/* Assume the sign can be a candidate for drawing, so measure its width */
 	_viewport_sign_maxwidth = max<int>(_viewport_sign_maxwidth, st->sign.width_normal);
@@ -2199,12 +2195,9 @@ ViewportSignKdtreeItem ViewportSignKdtreeItem::MakeWaypoint(StationID id)
 	item.id.station = id;
 
 	const Waypoint *st = Waypoint::Get(id);
-	Point pt = RemapCoords(TileX(st->xy) * TILE_SIZE, TileY(st->xy) * TILE_SIZE, GetTileMaxZ(st->xy) * TILE_HEIGHT);
-
-	pt.y -= 32 * ZOOM_LVL_BASE;
-
-	item.center = pt.x;
-	item.top = pt.y;
+	assert(st->sign.kdtree_valid);
+	item.center = st->sign.center;
+	item.top = st->sign.top;
 
 	/* Assume the sign can be a candidate for drawing, so measure its width */
 	_viewport_sign_maxwidth = max<int>(_viewport_sign_maxwidth, st->sign.width_normal);
@@ -2219,14 +2212,9 @@ ViewportSignKdtreeItem ViewportSignKdtreeItem::MakeTown(TownID id)
 	item.id.town = id;
 
 	const Town *town = Town::Get(id);
-	/* Avoid using RemapCoords2, it has dependency on the foundations status of the tile, and that can be unavailable during saveload, leading to crashes.
-	 * Instead "fake" foundations by taking the highest Z coordinate of any corner of the tile. */
-	Point pt = RemapCoords(TileX(town->xy) * TILE_SIZE, TileY(town->xy) * TILE_SIZE, GetTileMaxZ(town->xy) * TILE_HEIGHT);
-
-	pt.y -= 24 * ZOOM_LVL_BASE;
-
-	item.center = pt.x;
-	item.top = pt.y;
+	assert(town->cache.sign.kdtree_valid);
+	item.center = town->cache.sign.center;
+	item.top = town->cache.sign.top;
 
 	/* Assume the sign can be a candidate for drawing, so measure its width */
 	_viewport_sign_maxwidth = max<int>(_viewport_sign_maxwidth, town->cache.sign.width_normal);
@@ -2241,12 +2229,9 @@ ViewportSignKdtreeItem ViewportSignKdtreeItem::MakeSign(SignID id)
 	item.id.sign = id;
 
 	const Sign *sign = Sign::Get(id);
-	Point pt = RemapCoords(sign->x, sign->y, sign->z);
-
-	pt.y -= 6 * ZOOM_LVL_BASE;
-
-	item.center = pt.x;
-	item.top = pt.y;
+	assert(sign->sign.kdtree_valid);
+	item.center = sign->sign.center;
+	item.top = sign->sign.top;
 
 	/* Assume the sign can be a candidate for drawing, so measure its width */
 	_viewport_sign_maxwidth = max<int>(_viewport_sign_maxwidth, sign->sign.width_normal);
@@ -2264,22 +2249,22 @@ void RebuildViewportKdtree()
 
 	const Station *st;
 	FOR_ALL_STATIONS(st) {
-		items.push_back(ViewportSignKdtreeItem::MakeStation(st->index));
+		if (st->sign.kdtree_valid) items.push_back(ViewportSignKdtreeItem::MakeStation(st->index));
 	}
 
 	const Waypoint *wp;
 	FOR_ALL_WAYPOINTS(wp) {
-		items.push_back(ViewportSignKdtreeItem::MakeWaypoint(wp->index));
+		if (wp->sign.kdtree_valid) items.push_back(ViewportSignKdtreeItem::MakeWaypoint(wp->index));
 	}
 
 	const Town *town;
 	FOR_ALL_TOWNS(town) {
-		items.push_back(ViewportSignKdtreeItem::MakeTown(town->index));
+		if (town->cache.sign.kdtree_valid) items.push_back(ViewportSignKdtreeItem::MakeTown(town->index));
 	}
 
 	const Sign *sign;
 	FOR_ALL_SIGNS(sign) {
-		items.push_back(ViewportSignKdtreeItem::MakeSign(sign->index));
+		if (sign->sign.kdtree_valid) items.push_back(ViewportSignKdtreeItem::MakeSign(sign->index));
 	}
 
 	_viewport_sign_kdtree.Build(items.begin(), items.end());
diff --git a/src/viewport_type.h b/src/viewport_type.h
index 2d986493e..f6a9ce4ae 100644
--- a/src/viewport_type.h
+++ b/src/viewport_type.h
@@ -53,6 +53,26 @@ struct ViewportSign {
 	void MarkDirty(ZoomLevel maxzoom = ZOOM_LVL_MAX) const;
 };
 
+/** Specialised ViewportSign that tracks whether it is valid for entering into a Kdtree */
+struct TrackedViewportSign : ViewportSign {
+	bool kdtree_valid; ///< Are the sign data valid for use with the _viewport_sign_kdtree?
+
+	/**
+	 * Update the position of the viewport sign.
+	 * Note that this function hides the base class function.
+	 */
+	void UpdatePosition(int center, int top, StringID str, StringID str_small = STR_NULL)
+	{
+		this->kdtree_valid = true;
+		this->ViewportSign::UpdatePosition(center, top, str, str_small);
+	}
+
+
+	TrackedViewportSign() : kdtree_valid{ false }
+	{
+	}
+};
+
 /**
  * Directions of zooming.
  * @see DoZoomInOutWindow
diff --git a/src/waypoint.cpp b/src/waypoint.cpp
index cf3e746d7..f602eee6d 100644
--- a/src/waypoint.cpp
+++ b/src/waypoint.cpp
@@ -53,5 +53,5 @@ Waypoint::~Waypoint()
 	if (CleaningPool()) return;
 	DeleteWindowById(WC_WAYPOINT_VIEW, this->index);
 	RemoveOrderFromAllVehicles(OT_GOTO_WAYPOINT, this->index);
-	_viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeWaypoint(this->index));
+	if (this->sign.kdtree_valid) _viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeWaypoint(this->index));
 }
diff --git a/src/waypoint_cmd.cpp b/src/waypoint_cmd.cpp
index 70a6fea83..d55b1b459 100644
--- a/src/waypoint_cmd.cpp
+++ b/src/waypoint_cmd.cpp
@@ -39,8 +39,13 @@
 void Waypoint::UpdateVirtCoord()
 {
 	Point pt = RemapCoords2(TileX(this->xy) * TILE_SIZE, TileY(this->xy) * TILE_SIZE);
+	if (this->sign.kdtree_valid) _viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeWaypoint(this->index));
+
 	SetDParam(0, this->index);
 	this->sign.UpdatePosition(pt.x, pt.y - 32 * ZOOM_LVL_BASE, STR_VIEWPORT_WAYPOINT);
+
+	_viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeWaypoint(this->index));
+
 	/* Recenter viewport */
 	InvalidateWindowData(WC_WAYPOINT_VIEW, this->index);
 }
@@ -53,11 +58,7 @@ void Waypoint::MoveSign(TileIndex new_xy)
 {
 	if (this->xy == new_xy) return;
 
-	_viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeWaypoint(this->index));
-
 	this->BaseStation::MoveSign(new_xy);
-
-	_viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeWaypoint(this->index));
 }
 
 /**
@@ -239,15 +240,11 @@ CommandCost CmdBuildRailWaypoint(TileIndex start_tile, DoCommandFlag flags, uint
 	}
 
 	if (flags & DC_EXEC) {
-		bool need_sign_update = false;
 		if (wp == nullptr) {
 			wp = new Waypoint(start_tile);
-			need_sign_update = true;
 		} else if (!wp->IsInUse()) {
 			/* Move existing (recently deleted) waypoint to the new location */
-			_viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeWaypoint(wp->index));
 			wp->xy = start_tile;
-			need_sign_update = true;
 		}
 		wp->owner = GetTileOwner(start_tile);
 
@@ -262,7 +259,6 @@ CommandCost CmdBuildRailWaypoint(TileIndex start_tile, DoCommandFlag flags, uint
 		if (wp->town == nullptr) MakeDefaultName(wp);
 
 		wp->UpdateVirtCoord();
-		if (need_sign_update) _viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeWaypoint(wp->index));
 
 		const StationSpec *spec = StationClass::Get(spec_class)->GetSpec(spec_index);
 		byte *layout_ptr = AllocaM(byte, count);
@@ -329,7 +325,6 @@ CommandCost CmdBuildBuoy(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32
 			wp = new Waypoint(tile);
 		} else {
 			/* Move existing (recently deleted) buoy to the new location */
-			_viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeWaypoint(wp->index));
 			wp->xy = tile;
 			InvalidateWindowData(WC_WAYPOINT_VIEW, wp->index);
 		}
@@ -349,7 +344,6 @@ CommandCost CmdBuildBuoy(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32
 		MarkTileDirtyByTile(tile);
 
 		wp->UpdateVirtCoord();
-		_viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeWaypoint(wp->index));
 		InvalidateWindowData(WC_WAYPOINT_VIEW, wp->index);
 	}