diff options
| -rw-r--r-- | projects/openttd_vs140.vcxproj | 1 | ||||
| -rw-r--r-- | projects/openttd_vs140.vcxproj.filters | 3 | ||||
| -rw-r--r-- | projects/openttd_vs141.vcxproj | 1 | ||||
| -rw-r--r-- | projects/openttd_vs141.vcxproj.filters | 3 | ||||
| -rw-r--r-- | projects/openttd_vs142.vcxproj | 1 | ||||
| -rw-r--r-- | projects/openttd_vs142.vcxproj.filters | 3 | ||||
| -rw-r--r-- | source.list | 1 | ||||
| -rw-r--r-- | src/misc.cpp | 2 | ||||
| -rw-r--r-- | src/saveload/afterload.cpp | 5 | ||||
| -rw-r--r-- | src/signs_cmd.cpp | 5 | ||||
| -rw-r--r-- | src/station.cpp | 2 | ||||
| -rw-r--r-- | src/station_cmd.cpp | 5 | ||||
| -rw-r--r-- | src/town_cmd.cpp | 3 | ||||
| -rw-r--r-- | src/viewport.cpp | 361 | ||||
| -rw-r--r-- | src/viewport_kdtree.h | 83 | ||||
| -rw-r--r-- | src/waypoint.cpp | 2 | ||||
| -rw-r--r-- | src/waypoint_cmd.cpp | 8 |
17 files changed, 398 insertions, 91 deletions
diff --git a/projects/openttd_vs140.vcxproj b/projects/openttd_vs140.vcxproj index c1a23497a..63aa57f56 100644 --- a/projects/openttd_vs140.vcxproj +++ b/projects/openttd_vs140.vcxproj @@ -698,6 +698,7 @@ <ClInclude Include="..\src\vehicle_type.h" /> <ClInclude Include="..\src\vehiclelist.h" /> <ClInclude Include="..\src\viewport_func.h" /> + <ClInclude Include="..\src\viewport_kdtree.h" /> <ClInclude Include="..\src\viewport_sprite_sorter.h" /> <ClInclude Include="..\src\viewport_type.h" /> <ClInclude Include="..\src\water.h" /> diff --git a/projects/openttd_vs140.vcxproj.filters b/projects/openttd_vs140.vcxproj.filters index 9bd33721a..3c4fc43d9 100644 --- a/projects/openttd_vs140.vcxproj.filters +++ b/projects/openttd_vs140.vcxproj.filters @@ -1182,6 +1182,9 @@ <ClInclude Include="..\src\viewport_func.h"> <Filter>Header Files</Filter> </ClInclude> + <ClInclude Include="..\src\viewport_kdtree.h"> + <Filter>Header Files</Filter> + </ClInclude> <ClInclude Include="..\src\viewport_sprite_sorter.h"> <Filter>Header Files</Filter> </ClInclude> diff --git a/projects/openttd_vs141.vcxproj b/projects/openttd_vs141.vcxproj index 2b6c5c178..c65269eab 100644 --- a/projects/openttd_vs141.vcxproj +++ b/projects/openttd_vs141.vcxproj @@ -698,6 +698,7 @@ <ClInclude Include="..\src\vehicle_type.h" /> <ClInclude Include="..\src\vehiclelist.h" /> <ClInclude Include="..\src\viewport_func.h" /> + <ClInclude Include="..\src\viewport_kdtree.h" /> <ClInclude Include="..\src\viewport_sprite_sorter.h" /> <ClInclude Include="..\src\viewport_type.h" /> <ClInclude Include="..\src\water.h" /> diff --git a/projects/openttd_vs141.vcxproj.filters b/projects/openttd_vs141.vcxproj.filters index 9bd33721a..3c4fc43d9 100644 --- a/projects/openttd_vs141.vcxproj.filters +++ b/projects/openttd_vs141.vcxproj.filters @@ -1182,6 +1182,9 @@ <ClInclude Include="..\src\viewport_func.h"> <Filter>Header Files</Filter> </ClInclude> + <ClInclude Include="..\src\viewport_kdtree.h"> + <Filter>Header Files</Filter> + </ClInclude> <ClInclude Include="..\src\viewport_sprite_sorter.h"> <Filter>Header Files</Filter> </ClInclude> diff --git a/projects/openttd_vs142.vcxproj b/projects/openttd_vs142.vcxproj index 66b07576a..0ffaf9f38 100644 --- a/projects/openttd_vs142.vcxproj +++ b/projects/openttd_vs142.vcxproj @@ -698,6 +698,7 @@ <ClInclude Include="..\src\vehicle_type.h" /> <ClInclude Include="..\src\vehiclelist.h" /> <ClInclude Include="..\src\viewport_func.h" /> + <ClInclude Include="..\src\viewport_kdtree.h" /> <ClInclude Include="..\src\viewport_sprite_sorter.h" /> <ClInclude Include="..\src\viewport_type.h" /> <ClInclude Include="..\src\water.h" /> diff --git a/projects/openttd_vs142.vcxproj.filters b/projects/openttd_vs142.vcxproj.filters index 9bd33721a..3c4fc43d9 100644 --- a/projects/openttd_vs142.vcxproj.filters +++ b/projects/openttd_vs142.vcxproj.filters @@ -1182,6 +1182,9 @@ <ClInclude Include="..\src\viewport_func.h"> <Filter>Header Files</Filter> </ClInclude> + <ClInclude Include="..\src\viewport_kdtree.h"> + <Filter>Header Files</Filter> + </ClInclude> <ClInclude Include="..\src\viewport_sprite_sorter.h"> <Filter>Header Files</Filter> </ClInclude> diff --git a/source.list b/source.list index 74068d48d..d744101ea 100644 --- 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 index b1d480d82..4e3086fce 100644 --- 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 size_y, bool reset_date, bool reset_settin RebuildStationKdtree(); RebuildTownKdtree(); + RebuildViewportKdtree(); ResetPersistentNewGRFData(); diff --git a/src/saveload/afterload.cpp b/src/saveload/afterload.cpp index a80114f91..ea7882e89 100644 --- 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 index 4badd3605..69fde2559 100644 --- 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, DoCommandFlag flags, uint32 p1, uint32 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, DoCommandFlag flags, uint32 p1, uint32 } } 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 index 5722fcdcf..3c50ef94f 100644 --- 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 index 67ea4daf5..f7eb353a0 100644 --- 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(BaseStation *st) /* 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(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); @@ -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 index 0f1ccbba3..ee2f49d93 100644 --- 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, 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); @@ -2869,6 +2871,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.Insert(ViewportSignKdtreeItem::MakeTown(t->index)); delete t; } diff --git a/src/viewport.cpp b/src/viewport.cpp index 894595119..5e8297143 100644 --- 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 DrawPixelInfo *dpi, ZoomLevel small_from, const Vie } } -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; + /* 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); - 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); - } -} + 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); + const Sign *si; - /* Don't draw if the display options are disabled */ - if (!HasBit(_display_opt, is_station ? DO_SHOW_STATION_NAMES : DO_SHOW_WAYPOINT_NAMES)) continue; + /* Collect all the items first and draw afterwards, to ensure layering */ + std::vector<const BaseStation *> stations; + std::vector<const Town *> towns; + std::vector<const Sign *> signs; - /* 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; + _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); - 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, - st->index, st->facilities, (st->owner == OWNER_NONE || !st->IsInUse()) ? COLOUR_GREY : _company_colours[st->owner]); - } -} + /* 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; -static void ViewportAddSigns(DrawPixelInfo *dpi) -{ - /* Signs are turned off or are invisible */ - if (!HasBit(_display_opt, DO_SHOW_SIGNS) || IsInvisibilitySet(TO_SIGNS)) return; + case ViewportSignKdtreeItem::VKI_WAYPOINT: + if (!show_waypoints) break; + st = BaseStation::Get(item.id.station); - 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; + /* 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])); + 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]); + } } } + /** * 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, int left, int top, int right, int bottom 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(const ViewPort *vp, int x, int y, const Vie 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; + 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; - const Town *t; - FOR_ALL_TOWNS(t) { - if (CheckClickOnViewportSign(vp, x, y, &t->cache.sign)) { - ShowTownViewWindow(t->index); - return true; + 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; + +ViewportSignKdtreeItem ViewportSignKdtreeItem::MakeStation(StationID id) +{ + 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<int>(_viewport_sign_maxwidth, st->sign.width_normal); + + return item; } -static bool CheckClickOnStation(const ViewPort *vp, int x, int y) +ViewportSignKdtreeItem ViewportSignKdtreeItem::MakeWaypoint(StationID id) { - if (!(HasBit(_display_opt, DO_SHOW_STATION_NAMES) || HasBit(_display_opt, DO_SHOW_WAYPOINT_NAMES)) || IsInvisibilitySet(TO_SIGNS)) return false; + ViewportSignKdtreeItem item; + item.type = VKI_WAYPOINT; + item.id.station = id; - 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); + const Waypoint *st = Waypoint::Get(id); + Point pt = RemapCoords2(TileX(st->xy) * TILE_SIZE, TileY(st->xy) * TILE_SIZE); - /* Don't check if the display options are disabled */ - if (!HasBit(_display_opt, is_station ? DO_SHOW_STATION_NAMES : DO_SHOW_WAYPOINT_NAMES)) continue; + pt.y -= 32 * ZOOM_LVL_BASE; - /* 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; + item.center = pt.x; + item.top = pt.y; - if (CheckClickOnViewportSign(vp, x, y, &st->sign)) { - if (is_station) { - ShowStationViewWindow(st->index); - } else { - ShowWaypointWindow(Waypoint::From(st)); - } - return true; - } - } + /* 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); - return false; + 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; -static bool CheckClickOnSign(const ViewPort *vp, int x, int y) + 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<int>(_viewport_sign_maxwidth, town->cache.sign.width_normal); + + return item; +} + +ViewportSignKdtreeItem ViewportSignKdtreeItem::MakeSign(SignID id) { - /* 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; + ViewportSignKdtreeItem item; + item.type = VKI_SIGN; + item.id.sign = id; - 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 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<int>(_viewport_sign_maxwidth, sign->sign.width_normal); + + return item; +} + +void RebuildViewportKdtree() +{ + /* Reset biggest size sign seen */ + _viewport_sign_maxwidth = 0; + + std::vector<ViewportSignKdtreeItem> 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; + const Waypoint *wp; + FOR_ALL_WAYPOINTS(wp) { + items.push_back(ViewportSignKdtreeItem::MakeWaypoint(wp->index)); + } + + 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 ViewPort *vp, int x, int y) 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 index 000000000..93344a5e6 --- /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 <http://www.gnu.org/licenses/>. +*/ + +/** @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<ViewportSignKdtreeItem, decltype(&Kdtree_ViewportSignXYFunc), int32, int32> ViewportSignKdtree; +extern ViewportSignKdtree _viewport_sign_kdtree; + +void RebuildViewportKdtree(); + +#endif diff --git a/src/waypoint.cpp b/src/waypoint.cpp index 857f8ba87..8452ff618 100644 --- 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 index 639dce13b..0fd5942c0 100644 --- 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(TileIndex start_tile, DoCommandFlag flags, uint } 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(TileIndex start_tile, DoCommandFlag flags, uint 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, 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); } @@ -328,6 +335,7 @@ 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); } |