-
-
Notifications
You must be signed in to change notification settings - Fork 949
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Codechange: Improve performance of town name refresh on viewports #7242
Conversation
src/town.h
Outdated
uint size; | ||
|
||
public: | ||
TownList(){ |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Space between )
and {
Also the constructor can be written as TownList() : needs_resort(true), initialized(false), size(0) { }
src/town.h
Outdated
@@ -295,4 +297,72 @@ static inline uint16 TownTicksToGameTicks(uint16 ticks) { | |||
|
|||
extern CargoTypes _town_cargoes_accepted; | |||
|
|||
/** Data structure with cached data of towns. */ | |||
/* ToDo: documentation */ | |||
/* ToDo: move function definitions to town_cmd.cpp */ |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Yes please!
Cache is never invalidated so does not handle creation of new towns. I'm not sure if towns ever get removed though. |
Yes, I forgot to add this to the ToDo. You can delete towns in scenario editor (and on random town generation can delete towns as well). |
Again instead of using a proper spatial structure you're making some knock-off that's not even any faster in the worst case :P. Same kd-tree/r-tree/... would easily solve both highlight problem and this range query. Also you probably can find some library to use so it would be even simpler to implement. |
I think sorting along the Y axis is a proper spatial structure. Sorting by the X axis would bring in lots of problems. Also kd-tree and r-tree are hard to balance, and in the scenario editor, you can add and remove towns. @PeterN: does/can this project use 3rd party open source libraries? |
Yes it can but we tend not to as it complicates cross-platform support. I don't think you need to worry about performance of removing or adding towns too much, it's not a hugely common occurrence and a few ms here and there for that is fine. |
With ~37k towns, instead of checking all signs, this approach can filter it down to about 300 (on the middle of the map, where most of the town can be found on a row). The sign redraw time can decrease from 2000 us to 50 us. As a single redraw of the whole screen (e.g. when zooming) can consist of more than 500 redraw calls even on small resolution, this could add up to a visible improvement. From the 50 us (with ~37k towns) 2-3 us is spent with finding the first town, the remaining time is needed to check the ~300 towns one by one. If the k-d tree in #7250 can be extended to include signs as well, it could speed it up even more, as the one by one check seems to be the most expensive part. |
3077c8f
to
9f0b1db
Compare
Instead of checking all town name signs, filter by the Y coordinate of the signs, and check only filtered town names.
9f0b1db
to
b2343d6
Compare
Closing in favor of #7250. |
Instead of checking all town name signs, filter by the Y coordinate of the signs, and check only filtered town names.
A town gets into the filtered town if the Y coordinate of its sign is between the lines marked by the redraw box top and bottom. There is no filtering by the X coordinates, as the width of the town names can change in a wide range.
Time complexities:
Performance improvement can be observed only in maps with high town count. On a 4096x4096 map with 30k towns (scenario editor) when scrolling on the map the time of viewport drawing went form 90 ms to 5 ms with this improvement (according to the framerate window).