-
-
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 closest town lookups with cache #7120
Conversation
Remember to run the |
This should really use euclidean distance, not manhattan. |
As someone also mentioned on IRC, the map overlay of every tile within the town boundary highlighting might be a bit excessive. I think it'd be better to only highlight the borders of the "town zone", and then draw that highlight over the top of station catchment area, so both are visible. Perhaps also add a line to the station build window showing the name of the town the station will be named after, below the accepts/supplies lines. |
What do you mean? To change the distance measurements in the whole game to euclidean?
The visualization won't be a part of this PR. However there are other options, like using smaller highlights so both the catchment and the town zone can be seen, or using a full-tile, homogeneous, mostly transparent fill for all the tiles in the town zone. |
all fibres in my mathematical knowledge scream at me "voronoi makes no sense with distances other than euclidean", so i would start to make the voronoi with that, and then consider each place that uses "distance to town" whether to switch it to euclidean by using this voronoi diagram. |
there used to be a tile highlighting patch that enabled showing two layers of data simultaneously |
I think you got is backwards. I wanted to make a map cache array for the CalcClosestTown for each tile, and named it voronoi, so your suggestion should be that I should rename the function and file. |
I put most of the code into a class, and now I feel it was a bad idea. |
ac32056
to
8c3c884
Compare
I've dropped the idea to put the diagram in a class.
|
Don't use fprintf for debug stuff, that breaks regression tests. We have a DEBUG macro for that and you can probably add a debug category if needed |
For the functions only used within town_voronoi.cpp, can you mark them with static? |
I deleted all the debug messages, they were there only for the development phase of the commit.
Done. |
The industry founding related part is now deleted, only the closest town visualization part remained for the duration of the review (it will/should be deleted before merge). |
When the town visualization part is removed, what do these changes do actually do? I think "Feature: " should be reserved for user-visible changes, which I don't think this counts as by itself. |
Agree with @PeterN, the title should rather be "Add: Nearest town cache" or "Change: Improve performance of nearest town lookups with cache" |
Both of you are right, I am renaming the commits. I am using "Codehange" instead of "Change", as there is no visible change for users.
It will help the implementation of new features which were held back by the performance of the closest town search. One of these is the industry founding pre-check (see previous gif), though I have to implement a viewport refresh improvement first for this check. |
src/town_voronoi.cpp
Outdated
bool _hold_next_add; | ||
TownID _town_on_hold; | ||
|
||
typedef GUIList<const Town*> 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.
Could this not be a std::vector? I think the plan is to scrap our custom implementations and use std classes where we can.
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.
Done. (I'll just have to remove the shortlist include part.)
It seems you're adding an extra uint16 map array for your cache which basically means increasing OpenTTD memory usage by 20%. That's quite a significant number especially for servers that run multiple OpenTTD processes. And so far I don't see any evidence of nearest town calculation being an actual performance issue. It may be needed for a potential town zone patch but it's own necessity is questionable (especially for servers) and there are lots of ways of doing it much more efficiently in regard to memory consumption. |
please consider leaving the town visualisation in, it would be really useful. |
@ldpl: You are right in case of the dedicated servers, but I think this increase in memory usage should not be a problem for clients and non dedicated servers. As the town visualization is useless in dedicated servers, this problem can be solved with a check, and in case of a dedicated server, the current |
@Moth-Tolias: the town visualization is a separate feature, but the main goal is to have that, and this PR is a preparation work for that. The current visualization is really crude so there is quite some work with this :) |
@Gabda87 IMO even in a client case you're trading too much memory for a too little performance gain. It's such a heavy memory usage that in some cases like random requests you can even lose in performance to some memory-effecient structure due to CPU cache misses. Not that random requests are of any use in openttd anyway but just for town visualization there are ways of doing it more memory-efficient. Since you only need to query in a rectangular area even something as simple as presorting tows by distance and using heuristics to update when moving to the next tile should be fast enough with almost zero memory cost. Also keep in mind there are some players requesting larger maps like 16k. And if that ever makes it into the game cache usage will be even more of a concern. |
@ldpl The bigger the map, the more performance gain can be achieved with this modification. Of course if we only look at the number of calls in the current version, this mem usage - performance trade does not worth it. 20 % mem increase seems like a lot, but in case of a 4k x 4k map, it is 32 MB, and it shouldn't be an issue with not dedicated servers (as a map of this size requires quite a CPU, and the mem next a CPU of this kind can handle the 32 MB increase). |
If it could be improved, please do. We shouldn't be too concerned about map sizes that are not implemented though. |
Check this: https://bitbucket.org/citymania/cmclient/commits/70195ad6d3252c569ed234ccc9d3c4ba1e3b8c23 It's a very crude implementation of an even simpler idea but it's already enough to use manhattan-based zones without any lags. |
I really like the idea where you stop the search in the sorted list after |
I tried making two optimized builds of OpenTTD, one with just the ai-framerate patch (#7178), and one with this patch + ai-framerate, both builds rebased onto origin/master. I then created a new game on a 2048x1024 map with 5 AI players all starting immediately, saved this game on January 1st, and loaded the same save both both builds. Then opened the Framerate window, placed the two games side by side, and unpaused both. The build with this patch runs upwards 25% faster in this test case, and in fast-forward mode quickly pulls ahead in simulation date. |
On a note, the terrain highlight still happens when you use the land area information tool (? button on main toolbar), is that intended? |
@Gabda87 I know it's far from a perfect solution. I just made it to show that even a simplest check can take advantage of a fact that there isn't much difference between neighboring tiles. If you properly adjust it to tile rendering order and mb use some clever structures it can perform even better. Also I didn't want to change zoning patch too much and it works with every tile individually. If you know the whole rendering zone beforehand you can find all the relevant towns in even more efficient way as you basically need to find intersections of rendering rectangle with Voronoi diagram edges. As for viewports I don't think it's an issue as long as they render separately (not sure if that's true). Sorting towns isn't that slow, it's ok to do that for each viewport. Also even if you don't take advantage of neighboring tiles there are plenty of 2d structures that can solve NNS effeciently: https://core.ac.uk/download/pdf/82472164.pdf |
@nielsmh Thank you for the performance measurement! |
Caching closest town information for all tiles. The cache is a map sized Voronoi diagram with Manhattan distances.
It seems like most of the data structures that uses O(#towns) space needs O(log(#towns)) time, which is better the the current linear time, but not the constant time like in this PR. I still like the idea of being able to spam the closest town calls, so I think a settings option to enable/disable this function would be better than to use another structure. |
I'm wondering what dedicated server is going to have issues with an additional 2MB (for a large 1024x1024 map) per instance? |
Had a quick play around, the nearest town shapes are quite surprising! |
Wondering if this can be made more generic, as some interesting landscape generation could be done with voronoi... |
You mean dropping random points to the map (independently from the towns), make the Voronoi diagram, and have some fun with map generation? I can think of an island map (or if we invert that, some lake), or rivers on the domain borders. |
@GabdaZM mostly when placing stations and other infrastructure, so as to avoid the wrath of towns i've previously gotten into poor standing with =] i'm very glad to know this visualisation is in the works! |
@Moth-Tolias Hmm, the tile highlight color could even correlate with the company rating in the town. |
No option to turn this caching on and off then :) |
This pull request has been automatically marked as stale because it has not had any activity in the last month. |
Work in progress.
Works only with the first map loaded, have to restart the whole game for a new map.
To see what it does, you have to select land info, or a construction function (station, tree, ...).
I only put part into the viewport to see how it works. It is by no means a good place to initialize. (I might need help with where to put initializations and destructions).
I plan to move the whole thing into a class. Question: should I out the map array part into the class as well?
No function to add or remove a town, it will be added later.