-
-
Notifications
You must be signed in to change notification settings - Fork 945
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
K-d tree data structure for spatial lookups #7250
Conversation
Looks like this needs some more work. Regressions are failing, and letting the Wentbourne save run for a while with master and this branch side by side has this branch slowly fall behind. |
Tried performing the same test as in the Voronoi patch and this also shows some improvement. Not quite as big, but still around 15%-20% better performance early on in a game with five AI players, set on fast-forward. |
Another thing to be aware of is that this can cause iteration order to become effectively randomized. Any use of FindContained in game code must be sure to have the same result regardless of iteration order. This is because the indexes are built on game load, but only updated during most operations, so clients that have joined a game at different times can have differently shaped indexes. |
Currently if two towns have equal distance from a tile, and you call CalcClosestTownFromTile, it returns the town with the lower index. Do you have/can you add this index check? |
That's a really good point, and probably a bug. I'm not sure exactly how to address that problem. |
This should solve the insufficiently defined results from FindNearest when multiple points had the same lowest distance. I've only tested it with the simplest case of two towns, and no formal proof, but I have a gut feeling this is correct :P |
Just so I mentioned it here too: this begs for UnitTests :D (not blaming you if you don't, as we have none to start with) |
If I can make the viewport signs (stations, waypoints, towns, signs) indexing right and not flicker/glitch the drawing, it can offer upwards a factor 10 improvement in drawing speed, depending on number of signs. I'm not sure why the regressions are now failing on some platforms but not all. |
After it works well, it might be better to store town signs in a separate tree, as these signs are not added/removed during a game, and you don't have to rebuild it after a certain amount of station build/deletion. |
Town names should probably be separated for visual purposes regardless. I think they're supposed to be drawn below any station and player signs, with this they can often end up drawn on top of those. |
Towns can be founded in game, and removed in the scenario editor. It's less common, but also station signs being added/moved/removed does not happen very often, so I don't think that would be necessary. EDIT: Of course that other reason sounds like a good reason. |
It appears there is a case of undefined behaviour in somewhere in the code, that causes some builds to produce wrong results for tree lookups, or maybe build incorrect trees. Enabling the CheckInvariant debugging does not trigger any asserts when the tree returns wrong results for a lookup, so it appears the error is somewhere in the recursive search algorithm. |
This resolves #7274. According to @SamuXarick his world-gen time on a 4096^2 map with 9000+ towns went from 40 minutes down to 95 seconds. |
Those numbers match an asymptotic improvement from Θ(n²) to Ω(n log n) quite well. √(40 * 60) ≈ 49 So that matches an improvement from 2400 seconds down to below 100 seconds, apart from some constants. |
Apparently the voronoi version was about 6 seconds faster (but these tests would need repeating to give stable results), however memory usage was up by the appropriate 32MB for 4096^2 (absolute figure ws 841MB vs 875MB, which is just a 4% increase.) |
Worldgen test with
#7284 also fixes disconnected towns which this doesn't address. |
Searching for closest town for 2 x 256 x 256 tiles (~ the number of tiles you can see in fullHD resolution when max zoomed out) takes about 100 ms when there are ~37k towns. I've tried to add the town boundary visualization, and with (unnecessarily) heavy mouse movement (frequent |
So in short, for "nearest town" display across the entire screen some bitmappy caching is still necessary. |
Note the TGP map gen makes only up to around 13,000 towns on a 4096² map |
Idea for another representation during building a station, the brown line indicates the town border (and is faked in this picture), and the current town the station would belong to is shown in the build window. The border line is intentionally not drawn outside the catchment area, a fixed 9x9 tile area or similar might also be reasonable. (This is obviously not relevant for the k-d tree itself, and should probably be in a separate PR.) |
I think this is stable enough, except for maybe the viewport sign search range. |
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.
I think most of the times auto
can be replaced with node
or It
from the template.
618f67c
to
fdc9804
Compare
…n sign moved. Code based on the patch by JGRennison. JGRennison/OpenTTD-patches@ac84f34
…moved. Code based on the patch by JGRennison. JGRennison/OpenTTD-patches@ac84f34
…n sign moved. Code based on the patch by JGRennison. JGRennison/OpenTTD-patches@ac84f34
Implements a k-d tree data structure for spatial indexes of map objects that don't move very often. Right now this is used for stations and towns (their sign location).
The k-d tree allows fast lookup of the nearest indexed point to a given point, and fast iteration of indexed points within a rectangle (orthogonal tile area).
Currently, testing shows no particular improvement. This is expected since almost all the operations changed to use the tree currently are responses to player commands, i.e. building and removing stations.