diff --git a/projects/openttd_vs140.vcxproj b/projects/openttd_vs140.vcxproj
--- a/projects/openttd_vs140.vcxproj
+++ b/projects/openttd_vs140.vcxproj
@@ -698,6 +698,7 @@
+
diff --git a/projects/openttd_vs140.vcxproj.filters b/projects/openttd_vs140.vcxproj.filters
--- a/projects/openttd_vs140.vcxproj.filters
+++ b/projects/openttd_vs140.vcxproj.filters
@@ -1182,6 +1182,9 @@
Header Files
+
+ Header Files
+
Header Files
diff --git a/projects/openttd_vs141.vcxproj b/projects/openttd_vs141.vcxproj
--- a/projects/openttd_vs141.vcxproj
+++ b/projects/openttd_vs141.vcxproj
@@ -698,6 +698,7 @@
+
diff --git a/projects/openttd_vs141.vcxproj.filters b/projects/openttd_vs141.vcxproj.filters
--- a/projects/openttd_vs141.vcxproj.filters
+++ b/projects/openttd_vs141.vcxproj.filters
@@ -1182,6 +1182,9 @@
Header Files
+
+ Header Files
+
Header Files
diff --git a/projects/openttd_vs142.vcxproj b/projects/openttd_vs142.vcxproj
--- a/projects/openttd_vs142.vcxproj
+++ b/projects/openttd_vs142.vcxproj
@@ -698,6 +698,7 @@
+
diff --git a/projects/openttd_vs142.vcxproj.filters b/projects/openttd_vs142.vcxproj.filters
--- a/projects/openttd_vs142.vcxproj.filters
+++ b/projects/openttd_vs142.vcxproj.filters
@@ -1182,6 +1182,9 @@
Header Files
+
+ Header Files
+
Header Files
diff --git a/source.list b/source.list
--- a/source.list
+++ b/source.list
@@ -385,6 +385,7 @@ vehicle_gui_base.h
vehicle_type.h
vehiclelist.h
viewport_func.h
+viewport_kdtree.h
viewport_sprite_sorter.h
viewport_type.h
water.h
diff --git a/src/misc.cpp b/src/misc.cpp
--- a/src/misc.cpp
+++ b/src/misc.cpp
@@ -30,6 +30,7 @@
#include "linkgraph/linkgraphschedule.h"
#include "station_kdtree.h"
#include "town_kdtree.h"
+#include "viewport_kdtree.h"
#include "safeguards.h"
@@ -79,6 +80,7 @@ void InitializeGame(uint size_x, uint si
RebuildStationKdtree();
RebuildTownKdtree();
+ RebuildViewportKdtree();
ResetPersistentNewGRFData();
diff --git a/src/saveload/afterload.cpp b/src/saveload/afterload.cpp
--- a/src/saveload/afterload.cpp
+++ b/src/saveload/afterload.cpp
@@ -19,6 +19,7 @@
#include "../network/network_func.h"
#include "../gfxinit.h"
#include "../viewport_func.h"
+#include "../viewport_kdtree.h"
#include "../industry.h"
#include "../clear_map.h"
#include "../vehicle_func.h"
@@ -221,6 +222,7 @@ void UpdateAllVirtCoords()
UpdateAllStationVirtCoords();
UpdateAllSignVirtCoords();
UpdateAllTownVirtCoords();
+ RebuildViewportKdtree();
}
/**
@@ -538,6 +540,9 @@ bool AfterLoadGame()
RebuildTownKdtree();
RebuildStationKdtree();
+ /* This needs to be done even before conversion, because some conversions will destroy objects
+ * that otherwise won't exist in the tree. */
+ RebuildViewportKdtree();
if (IsSavegameVersionBefore(SLV_98)) GamelogGRFAddList(_grfconfig);
diff --git a/src/signs_cmd.cpp b/src/signs_cmd.cpp
--- a/src/signs_cmd.cpp
+++ b/src/signs_cmd.cpp
@@ -16,6 +16,7 @@
#include "signs_func.h"
#include "command_func.h"
#include "tilehighlight_func.h"
+#include "viewport_kdtree.h"
#include "window_func.h"
#include "string_func.h"
@@ -57,7 +58,7 @@ CommandCost CmdPlaceSign(TileIndex tile,
if (!StrEmpty(text)) {
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;
}
@@ -98,7 +99,7 @@ CommandCost CmdRenameSign(TileIndex tile
}
} else { // Delete sign
if (flags & DC_EXEC) {
- si->sign.MarkDirty();
+ _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
--- a/src/station.cpp
+++ b/src/station.cpp
@@ -14,6 +14,7 @@
#include "company_base.h"
#include "roadveh.h"
#include "viewport_func.h"
+#include "viewport_kdtree.h"
#include "date_func.h"
#include "command_func.h"
#include "news_func.h"
@@ -163,6 +164,7 @@ Station::~Station()
CargoPacket::InvalidateAllFrom(this->index);
_station_kdtree.Remove(this->index);
+ _viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeStation(this->index));
}
diff --git a/src/station_cmd.cpp b/src/station_cmd.cpp
--- a/src/station_cmd.cpp
+++ b/src/station_cmd.cpp
@@ -14,6 +14,7 @@
#include "bridge_map.h"
#include "cmd_helper.h"
#include "viewport_func.h"
+#include "viewport_kdtree.h"
#include "command_func.h"
#include "town.h"
#include "news_func.h"
@@ -672,9 +673,11 @@ static void UpdateStationSignCoord(BaseS
/* clamp sign coord to be inside the station rect */
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) {
+ _viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeStation(st->index));
_station_kdtree.Remove(st->index);
st->xy = new_xy;
_station_kdtree.Insert(st->index);
+ _viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeStation(st->index));
st->UpdateVirtCoord();
}
@@ -715,6 +718,7 @@ static CommandCost BuildStationPart(Stat
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);
@@ -3975,6 +3979,7 @@ 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_cmd.cpp b/src/town_cmd.cpp
--- a/src/town_cmd.cpp
+++ b/src/town_cmd.cpp
@@ -14,6 +14,7 @@
#include "road_cmd.h"
#include "landscape.h"
#include "viewport_func.h"
+#include "viewport_kdtree.h"
#include "cmd_helper.h"
#include "command_func.h"
#include "industry.h"
@@ -1713,6 +1714,7 @@ static void DoCreateTown(Town *t, TileIn
t->townnameparts = townnameparts;
t->UpdateVirtCoord();
+ _viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeTown(t->index));
InvalidateWindowData(WC_TOWN_DIRECTORY, 0, 0);
t->InitializeLayout(layout);
@@ -2869,6 +2871,7 @@ CommandCost CmdDeleteTown(TileIndex tile
/* The town destructor will delete the other things related to the town. */
if (flags & DC_EXEC) {
_town_kdtree.Remove(t->index);
+ _viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeTown(t->index));
delete t;
}
diff --git a/src/viewport.cpp b/src/viewport.cpp
--- a/src/viewport.cpp
+++ b/src/viewport.cpp
@@ -82,6 +82,7 @@
#include "tilehighlight_func.h"
#include "window_gui.h"
#include "linkgraph/linkgraph_gui.h"
+#include "viewport_kdtree.h"
#include "viewport_sprite_sorter.h"
#include "bridge_map.h"
#include "company_base.h"
@@ -99,6 +100,10 @@
Point _tile_fract_coords;
+ViewportSignKdtree _viewport_sign_kdtree(&Kdtree_ViewportSignXYFunc);
+static int _viewport_sign_maxwidth = 0;
+
+
static const int MAX_TILE_EXTENT_LEFT = ZOOM_LVL_BASE * TILE_PIXELS; ///< Maximum left extent of tile relative to north corner.
static const int MAX_TILE_EXTENT_RIGHT = ZOOM_LVL_BASE * TILE_PIXELS; ///< Maximum right extent of tile relative to north corner.
static const int MAX_TILE_EXTENT_TOP = ZOOM_LVL_BASE * MAX_BUILDING_PIXELS; ///< Maximum top extent of tile relative to north corner (not considering bridges).
@@ -1214,62 +1219,117 @@ void ViewportAddString(const DrawPixelIn
}
}
-static void ViewportAddTownNames(DrawPixelInfo *dpi)
+static Rect ExpandRectWithViewportSignMargins(Rect r, ZoomLevel zoom)
{
- if (!HasBit(_display_opt, DO_SHOW_TOWN_NAMES) || _game_mode == GM_MENU) return;
-
- const Town *t;
- FOR_ALL_TOWNS(t) {
- ViewportAddString(dpi, ZOOM_LVL_OUT_16X, &t->cache.sign,
- _settings_client.gui.population_in_label ? STR_VIEWPORT_TOWN_POP : STR_VIEWPORT_TOWN,
- STR_VIEWPORT_TOWN_TINY_WHITE, STR_VIEWPORT_TOWN_TINY_BLACK,
- t->index, t->cache.population);
- }
+ /* Pessimistically always use normal font, but also assume small font is never larger in either dimension */
+ const int fh = FONT_HEIGHT_NORMAL;
+ const int max_tw = _viewport_sign_maxwidth / 2 + 1;
+ const int expand_y = ScaleByZoom(VPSM_TOP + fh + VPSM_BOTTOM, zoom);
+ const int expand_x = ScaleByZoom(VPSM_LEFT + max_tw + VPSM_RIGHT, zoom);
+
+ r.left -= expand_x;
+ r.right += expand_x;
+ r.top -= expand_y;
+ r.bottom += expand_y;
+
+ return r;
}
-
-static void ViewportAddStationNames(DrawPixelInfo *dpi)
+static void ViewportAddKdtreeSigns(DrawPixelInfo *dpi)
{
- if (!(HasBit(_display_opt, DO_SHOW_STATION_NAMES) || HasBit(_display_opt, DO_SHOW_WAYPOINT_NAMES)) || _game_mode == GM_MENU) return;
+ Rect search_rect{ dpi->left, dpi->top, dpi->left + dpi->width, dpi->top + dpi->height };
+ search_rect = ExpandRectWithViewportSignMargins(search_rect, dpi->zoom);
+
+ bool show_stations = HasBit(_display_opt, DO_SHOW_STATION_NAMES) && _game_mode != GM_MENU;
+ bool show_waypoints = HasBit(_display_opt, DO_SHOW_WAYPOINT_NAMES) && _game_mode != GM_MENU;
+ bool show_towns = HasBit(_display_opt, DO_SHOW_TOWN_NAMES) && _game_mode != GM_MENU;
+ bool show_signs = HasBit(_display_opt, DO_SHOW_SIGNS) && !IsInvisibilitySet(TO_SIGNS);
+ bool show_competitors = HasBit(_display_opt, DO_SHOW_COMPETITOR_SIGNS);
const BaseStation *st;
- FOR_ALL_BASE_STATIONS(st) {
- /* Check whether the base station is a station or a waypoint */
- bool is_station = Station::IsExpected(st);
-
- /* Don't draw if the display options are disabled */
- if (!HasBit(_display_opt, is_station ? DO_SHOW_STATION_NAMES : DO_SHOW_WAYPOINT_NAMES)) continue;
-
- /* Don't draw if station is owned by another company and competitor station names are hidden. Stations owned by none are never ignored. */
- if (!HasBit(_display_opt, DO_SHOW_COMPETITOR_SIGNS) && _local_company != st->owner && st->owner != OWNER_NONE) continue;
-
- ViewportAddString(dpi, ZOOM_LVL_OUT_16X, &st->sign,
- is_station ? STR_VIEWPORT_STATION : STR_VIEWPORT_WAYPOINT,
- (is_station ? STR_VIEWPORT_STATION : STR_VIEWPORT_WAYPOINT) + 1, STR_NULL,
+ const Sign *si;
+
+ /* Collect all the items first and draw afterwards, to ensure layering */
+ std::vector stations;
+ std::vector towns;
+ std::vector signs;
+
+ _viewport_sign_kdtree.FindContained(search_rect.left, search_rect.top, search_rect.right, search_rect.bottom, [&](const ViewportSignKdtreeItem & item) {
+ switch (item.type) {
+ case ViewportSignKdtreeItem::VKI_STATION:
+ if (!show_stations) break;
+ st = BaseStation::Get(item.id.station);
+
+ /* Don't draw if station is owned by another company and competitor station names are hidden. Stations owned by none are never ignored. */
+ if (!show_competitors && _local_company != st->owner && st->owner != OWNER_NONE) break;
+
+ stations.push_back(st);
+ break;
+
+ case ViewportSignKdtreeItem::VKI_WAYPOINT:
+ if (!show_waypoints) break;
+ st = BaseStation::Get(item.id.station);
+
+ /* Don't draw if station is owned by another company and competitor station names are hidden. Stations owned by none are never ignored. */
+ if (!show_competitors && _local_company != st->owner && st->owner != OWNER_NONE) break;
+
+ stations.push_back(st);
+ break;
+
+ case ViewportSignKdtreeItem::VKI_TOWN:
+ if (!show_towns) break;
+ towns.push_back(Town::Get(item.id.town));
+ break;
+
+ case ViewportSignKdtreeItem::VKI_SIGN:
+ if (!show_signs) break;
+ si = Sign::Get(item.id.sign);
+
+ /* Don't draw if sign is owned by another company and competitor signs should be hidden.
+ * Note: It is intentional that also signs owned by OWNER_NONE are hidden. Bankrupt
+ * companies can leave OWNER_NONE signs after them. */
+ if (!show_competitors && _local_company != si->owner && si->owner != OWNER_DEITY) break;
+
+ signs.push_back(si);
+ break;
+
+ default:
+ NOT_REACHED();
+ }
+ });
+
+ /* Layering order (bottom to top): Town names, signs, stations */
+
+ for (const auto *t : towns) {
+ ViewportAddString(dpi, ZOOM_LVL_OUT_16X, &t->cache.sign,
+ _settings_client.gui.population_in_label ? STR_VIEWPORT_TOWN_POP : STR_VIEWPORT_TOWN,
+ STR_VIEWPORT_TOWN_TINY_WHITE, STR_VIEWPORT_TOWN_TINY_BLACK,
+ t->index, t->cache.population);
+ }
+
+ for (const auto *si : signs) {
+ ViewportAddString(dpi, ZOOM_LVL_OUT_16X, &si->sign,
+ STR_WHITE_SIGN,
+ (IsTransparencySet(TO_SIGNS) || si->owner == OWNER_DEITY) ? STR_VIEWPORT_SIGN_SMALL_WHITE : STR_VIEWPORT_SIGN_SMALL_BLACK, STR_NULL,
+ si->index, 0, (si->owner == OWNER_NONE) ? COLOUR_GREY : (si->owner == OWNER_DEITY ? INVALID_COLOUR : _company_colours[si->owner]));
+ }
+
+ for (const auto *st : stations) {
+ if (Station::IsExpected(st)) {
+ /* Station */
+ ViewportAddString(dpi, ZOOM_LVL_OUT_16X, &st->sign,
+ STR_VIEWPORT_STATION, STR_VIEWPORT_STATION + 1, STR_NULL,
st->index, st->facilities, (st->owner == OWNER_NONE || !st->IsInUse()) ? COLOUR_GREY : _company_colours[st->owner]);
+ } else {
+ /* Waypoint */
+ ViewportAddString(dpi, ZOOM_LVL_OUT_16X, &st->sign,
+ STR_VIEWPORT_WAYPOINT, STR_VIEWPORT_WAYPOINT + 1, STR_NULL,
+ st->index, st->facilities, (st->owner == OWNER_NONE || !st->IsInUse()) ? COLOUR_GREY : _company_colours[st->owner]);
+ }
}
}
-static void ViewportAddSigns(DrawPixelInfo *dpi)
-{
- /* Signs are turned off or are invisible */
- if (!HasBit(_display_opt, DO_SHOW_SIGNS) || IsInvisibilitySet(TO_SIGNS)) return;
-
- const Sign *si;
- FOR_ALL_SIGNS(si) {
- /* Don't draw if sign is owned by another company and competitor signs should be hidden.
- * Note: It is intentional that also signs owned by OWNER_NONE are hidden. Bankrupt
- * companies can leave OWNER_NONE signs after them. */
- if (!HasBit(_display_opt, DO_SHOW_COMPETITOR_SIGNS) && _local_company != si->owner && si->owner != OWNER_DEITY) continue;
-
- ViewportAddString(dpi, ZOOM_LVL_OUT_16X, &si->sign,
- STR_WHITE_SIGN,
- (IsTransparencySet(TO_SIGNS) || si->owner == OWNER_DEITY) ? STR_VIEWPORT_SIGN_SMALL_WHITE : STR_VIEWPORT_SIGN_SMALL_BLACK, STR_NULL,
- si->index, 0, (si->owner == OWNER_NONE) ? COLOUR_GREY : (si->owner == OWNER_DEITY ? INVALID_COLOUR : _company_colours[si->owner]));
- }
-}
-
/**
* Update the position of the viewport sign.
* @param center the (preferred) center of the viewport sign
@@ -1520,9 +1580,7 @@ void ViewportDoDraw(const ViewPort *vp,
ViewportAddLandscape();
ViewportAddVehicles(&_vd.dpi);
- ViewportAddTownNames(&_vd.dpi);
- ViewportAddStationNames(&_vd.dpi);
- ViewportAddSigns(&_vd.dpi);
+ ViewportAddKdtreeSigns(&_vd.dpi);
DrawTextEffects(&_vd.dpi);
@@ -1930,75 +1988,202 @@ static bool CheckClickOnViewportSign(con
int sign_half_width = ScaleByZoom((small ? sign->width_small : sign->width_normal) / 2, vp->zoom);
int sign_height = ScaleByZoom(VPSM_TOP + (small ? FONT_HEIGHT_SMALL : FONT_HEIGHT_NORMAL) + VPSM_BOTTOM, vp->zoom);
- x = ScaleByZoom(x - vp->left, vp->zoom) + vp->virtual_left;
- y = ScaleByZoom(y - vp->top, vp->zoom) + vp->virtual_top;
-
return y >= sign->top && y < sign->top + sign_height &&
x >= sign->center - sign_half_width && x < sign->center + sign_half_width;
}
-static bool CheckClickOnTown(const ViewPort *vp, int x, int y)
+
+/**
+ * Check whether any viewport sign was clicked, and dispatch the click.
+ * @param vp the clicked viewport
+ * @param x X position of click
+ * @param y Y position of click
+ * @return true if the sign was hit
+ */
+static bool CheckClickOnViewportSign(const ViewPort *vp, int x, int y)
{
- if (!HasBit(_display_opt, DO_SHOW_TOWN_NAMES)) return false;
-
- const Town *t;
- FOR_ALL_TOWNS(t) {
- if (CheckClickOnViewportSign(vp, x, y, &t->cache.sign)) {
- ShowTownViewWindow(t->index);
- return true;
+ x = ScaleByZoom(x - vp->left, vp->zoom) + vp->virtual_left;
+ y = ScaleByZoom(y - vp->top, vp->zoom) + vp->virtual_top;
+
+ Rect search_rect{ x - 1, y - 1, x + 1, y + 1 };
+ search_rect = ExpandRectWithViewportSignMargins(search_rect, vp->zoom);
+
+ bool show_stations = HasBit(_display_opt, DO_SHOW_STATION_NAMES) && _game_mode != GM_MENU;
+ bool show_waypoints = HasBit(_display_opt, DO_SHOW_WAYPOINT_NAMES) && _game_mode != GM_MENU;
+ bool show_towns = HasBit(_display_opt, DO_SHOW_TOWN_NAMES) && _game_mode != GM_MENU;
+ bool show_signs = HasBit(_display_opt, DO_SHOW_SIGNS) && !IsInvisibilitySet(TO_SIGNS);
+ bool show_competitors = HasBit(_display_opt, DO_SHOW_COMPETITOR_SIGNS);
+
+ /* Topmost of each type that was hit */
+ BaseStation *st = NULL, *last_st = NULL;
+ Town *t = NULL, *last_t = NULL;
+ Sign *si = NULL, *last_si = NULL;
+
+ /* See ViewportAddKdtreeSigns() for details on the search logic */
+ _viewport_sign_kdtree.FindContained(search_rect.left, search_rect.top, search_rect.right, search_rect.bottom, [&](const ViewportSignKdtreeItem & item) {
+ switch (item.type) {
+ case ViewportSignKdtreeItem::VKI_STATION:
+ if (!show_stations) break;
+ st = BaseStation::Get(item.id.station);
+ if (!show_competitors && _local_company != st->owner && st->owner != OWNER_NONE) break;
+ if (CheckClickOnViewportSign(vp, x, y, &st->sign)) last_st = st;
+ break;
+
+ case ViewportSignKdtreeItem::VKI_WAYPOINT:
+ if (!show_waypoints) break;
+ st = BaseStation::Get(item.id.station);
+ if (!show_competitors && _local_company != st->owner && st->owner != OWNER_NONE) break;
+ if (CheckClickOnViewportSign(vp, x, y, &st->sign)) last_st = st;
+ break;
+
+ case ViewportSignKdtreeItem::VKI_TOWN:
+ if (!show_towns) break;
+ t = Town::Get(item.id.town);
+ if (CheckClickOnViewportSign(vp, x, y, &t->cache.sign)) last_t = t;
+ break;
+
+ case ViewportSignKdtreeItem::VKI_SIGN:
+ if (!show_signs) break;
+ si = Sign::Get(item.id.sign);
+ if (!show_competitors && _local_company != si->owner && si->owner != OWNER_DEITY) break;
+ if (CheckClickOnViewportSign(vp, x, y, &si->sign)) last_si = si;
+ break;
+
+ default:
+ NOT_REACHED();
}
+ });
+
+ /* Select which hit to handle based on priority */
+ if (last_st != NULL) {
+ if (Station::IsExpected(last_st)) {
+ ShowStationViewWindow(last_st->index);
+ } else {
+ ShowWaypointWindow(Waypoint::From(last_st));
+ }
+ return true;
+ } else if (last_t != NULL) {
+ ShowTownViewWindow(last_t->index);
+ return true;
+ } else if (last_si != NULL) {
+ HandleClickOnSign(last_si);
+ return true;
+ } else {
+ return false;
}
-
- return false;
}
-static bool CheckClickOnStation(const ViewPort *vp, int x, int y)
+
+ViewportSignKdtreeItem ViewportSignKdtreeItem::MakeStation(StationID id)
{
- if (!(HasBit(_display_opt, DO_SHOW_STATION_NAMES) || HasBit(_display_opt, DO_SHOW_WAYPOINT_NAMES)) || IsInvisibilitySet(TO_SIGNS)) return false;
-
- const BaseStation *st;
- FOR_ALL_BASE_STATIONS(st) {
- /* Check whether the base station is a station or a waypoint */
- bool is_station = Station::IsExpected(st);
-
- /* Don't check if the display options are disabled */
- if (!HasBit(_display_opt, is_station ? DO_SHOW_STATION_NAMES : DO_SHOW_WAYPOINT_NAMES)) continue;
-
- /* Don't check if competitor signs are not shown and the sign isn't owned by the local company */
- if (!HasBit(_display_opt, DO_SHOW_COMPETITOR_SIGNS) && _local_company != st->owner && st->owner != OWNER_NONE) continue;
-
- if (CheckClickOnViewportSign(vp, x, y, &st->sign)) {
- if (is_station) {
- ShowStationViewWindow(st->index);
- } else {
- ShowWaypointWindow(Waypoint::From(st));
- }
- return true;
- }
+ ViewportSignKdtreeItem item;
+ item.type = VKI_STATION;
+ item.id.station = id;
+
+ const Station *st = Station::Get(id);
+ Point pt = RemapCoords2(TileX(st->xy) * TILE_SIZE, TileY(st->xy) * TILE_SIZE);
+
+ 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;
+
+ /* Assume the sign can be a candidate for drawing, so measure its width */
+ _viewport_sign_maxwidth = max(_viewport_sign_maxwidth, st->sign.width_normal);
+
+ return item;
+}
+
+ViewportSignKdtreeItem ViewportSignKdtreeItem::MakeWaypoint(StationID id)
+{
+ ViewportSignKdtreeItem item;
+ item.type = VKI_WAYPOINT;
+ item.id.station = id;
+
+ const Waypoint *st = Waypoint::Get(id);
+ Point pt = RemapCoords2(TileX(st->xy) * TILE_SIZE, TileY(st->xy) * TILE_SIZE);
+
+ pt.y -= 32 * ZOOM_LVL_BASE;
+
+ item.center = pt.x;
+ item.top = pt.y;
+
+ /* Assume the sign can be a candidate for drawing, so measure its width */
+ _viewport_sign_maxwidth = max(_viewport_sign_maxwidth, st->sign.width_normal);
+
+ return item;
+}
+
+ViewportSignKdtreeItem ViewportSignKdtreeItem::MakeTown(TownID id)
+{
+ ViewportSignKdtreeItem item;
+ item.type = VKI_TOWN;
+ item.id.town = id;
+
+ const Town *town = Town::Get(id);
+ Point pt = RemapCoords2(TileX(town->xy) * TILE_SIZE, TileY(town->xy) * TILE_SIZE);
+
+ pt.y -= 24 * ZOOM_LVL_BASE;
+
+ item.center = pt.x;
+ item.top = pt.y;
+
+ /* Assume the sign can be a candidate for drawing, so measure its width */
+ _viewport_sign_maxwidth = max(_viewport_sign_maxwidth, town->cache.sign.width_normal);
+
+ return item;
+}
+
+ViewportSignKdtreeItem ViewportSignKdtreeItem::MakeSign(SignID id)
+{
+ ViewportSignKdtreeItem item;
+ item.type = VKI_SIGN;
+ 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;
+
+ /* Assume the sign can be a candidate for drawing, so measure its width */
+ _viewport_sign_maxwidth = max(_viewport_sign_maxwidth, sign->sign.width_normal);
+
+ return item;
+}
+
+void RebuildViewportKdtree()
+{
+ /* Reset biggest size sign seen */
+ _viewport_sign_maxwidth = 0;
+
+ std::vector items;
+ items.reserve(BaseStation::GetNumItems() + Town::GetNumItems() + Sign::GetNumItems());
+
+ const Station *st;
+ FOR_ALL_STATIONS(st) {
+ items.push_back(ViewportSignKdtreeItem::MakeStation(st->index));
}
- return false;
-}
-
-
-static bool CheckClickOnSign(const ViewPort *vp, int x, int y)
-{
- /* Signs are turned off, or they are transparent and invisibility is ON, or company is a spectator */
- if (!HasBit(_display_opt, DO_SHOW_SIGNS) || IsInvisibilitySet(TO_SIGNS) || _local_company == COMPANY_SPECTATOR) return false;
-
- const Sign *si;
- FOR_ALL_SIGNS(si) {
- /* If competitor signs are hidden, don't check signs that aren't owned by local company */
- if (!HasBit(_display_opt, DO_SHOW_COMPETITOR_SIGNS) && _local_company != si->owner && si->owner != OWNER_DEITY) continue;
- if (si->owner == OWNER_DEITY && _game_mode != GM_EDITOR) continue;
-
- if (CheckClickOnViewportSign(vp, x, y, &si->sign)) {
- HandleClickOnSign(si);
- return true;
- }
+ const Waypoint *wp;
+ FOR_ALL_WAYPOINTS(wp) {
+ items.push_back(ViewportSignKdtreeItem::MakeWaypoint(wp->index));
}
- return false;
+ const Town *town;
+ FOR_ALL_TOWNS(town) {
+ items.push_back(ViewportSignKdtreeItem::MakeTown(town->index));
+ }
+
+ const Sign *sign;
+ FOR_ALL_SIGNS(sign) {
+ items.push_back(ViewportSignKdtreeItem::MakeSign(sign->index));
+ }
+
+ _viewport_sign_kdtree.Build(items.begin(), items.end());
}
@@ -2045,9 +2230,7 @@ bool HandleViewportClicked(const ViewPor
return true;
}
- if (CheckClickOnTown(vp, x, y)) return true;
- if (CheckClickOnStation(vp, x, y)) return true;
- if (CheckClickOnSign(vp, x, y)) return true;
+ if (CheckClickOnViewportSign(vp, x, y)) return true;
bool result = CheckClickOnLandscape(vp, x, y);
if (v != NULL) {
diff --git a/src/viewport_kdtree.h b/src/viewport_kdtree.h
new file mode 100644
--- /dev/null
+++ b/src/viewport_kdtree.h
@@ -0,0 +1,83 @@
+/*
+* 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 .
+*/
+
+/** @file town_kdtree.h Declarations for accessing the k-d tree of towns */
+
+#ifndef VIEWPORT_KDTREE_H
+#define VIEWPORT_KDTREE_H
+
+#include "core/kdtree.hpp"
+#include "viewport_type.h"
+#include "station_base.h"
+#include "town_type.h"
+#include "signs_base.h"
+
+struct ViewportSignKdtreeItem {
+ enum ItemType : uint16 {
+ VKI_STATION,
+ VKI_WAYPOINT,
+ VKI_TOWN,
+ VKI_SIGN,
+ };
+ ItemType type;
+ union {
+ StationID station;
+ TownID town;
+ SignID sign;
+ } id;
+ int32 center;
+ int32 top;
+
+ bool operator== (const ViewportSignKdtreeItem &other) const
+ {
+ if (this->type != other.type) return false;
+ switch (this->type) {
+ case VKI_STATION:
+ case VKI_WAYPOINT:
+ return this->id.station == other.id.station;
+ case VKI_TOWN:
+ return this->id.town == other.id.town;
+ case VKI_SIGN:
+ return this->id.sign == other.id.sign;
+ default:
+ NOT_REACHED();
+ }
+ }
+
+ bool operator< (const ViewportSignKdtreeItem &other) const
+ {
+ if (this->type != other.type) return this->type < other.type;
+ switch (this->type) {
+ case VKI_STATION:
+ case VKI_WAYPOINT:
+ return this->id.station < other.id.station;
+ case VKI_TOWN:
+ return this->id.town < other.id.town;
+ case VKI_SIGN:
+ return this->id.sign < other.id.sign;
+ default:
+ NOT_REACHED();
+ }
+ }
+
+ static ViewportSignKdtreeItem MakeStation(StationID id);
+ static ViewportSignKdtreeItem MakeWaypoint(StationID id);
+ static ViewportSignKdtreeItem MakeTown(TownID id);
+ static ViewportSignKdtreeItem MakeSign(SignID id);
+};
+
+inline int32 Kdtree_ViewportSignXYFunc(const ViewportSignKdtreeItem &item, int dim)
+{
+ return (dim == 0) ? item.center : item.top;
+}
+
+typedef Kdtree ViewportSignKdtree;
+extern ViewportSignKdtree _viewport_sign_kdtree;
+
+void RebuildViewportKdtree();
+
+#endif
diff --git a/src/waypoint.cpp b/src/waypoint.cpp
--- a/src/waypoint.cpp
+++ b/src/waypoint.cpp
@@ -15,6 +15,7 @@
#include "window_func.h"
#include "newgrf_station.h"
#include "waypoint_base.h"
+#include "viewport_kdtree.h"
#include "safeguards.h"
@@ -54,4 +55,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));
}
diff --git a/src/waypoint_cmd.cpp b/src/waypoint_cmd.cpp
--- a/src/waypoint_cmd.cpp
+++ b/src/waypoint_cmd.cpp
@@ -20,6 +20,7 @@
#include "pathfinder/yapf/yapf_cache.h"
#include "strings_func.h"
#include "viewport_func.h"
+#include "viewport_kdtree.h"
#include "window_func.h"
#include "date_func.h"
#include "vehicle_func.h"
@@ -225,11 +226,15 @@ CommandCost CmdBuildRailWaypoint(TileInd
}
if (flags & DC_EXEC) {
+ bool need_sign_update = false;
if (wp == NULL) {
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);
@@ -244,6 +249,7 @@ CommandCost CmdBuildRailWaypoint(TileInd
if (wp->town == NULL) 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);
@@ -310,6 +316,7 @@ CommandCost CmdBuildBuoy(TileIndex tile,
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);
}
@@ -328,6 +335,7 @@ CommandCost CmdBuildBuoy(TileIndex tile,
MarkTileDirtyByTile(tile);
wp->UpdateVirtCoord();
+ _viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeWaypoint(wp->index));
InvalidateWindowData(WC_WAYPOINT_VIEW, wp->index);
}