Skip to content
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

Merged
merged 4 commits into from Mar 9, 2019
Merged

Conversation

nielsmh
Copy link
Contributor

@nielsmh nielsmh commented Feb 19, 2019

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.

@nielsmh
Copy link
Contributor Author

nielsmh commented Feb 19, 2019

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.

@nielsmh
Copy link
Contributor Author

nielsmh commented Feb 19, 2019

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.

@nielsmh
Copy link
Contributor Author

nielsmh commented Feb 19, 2019

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.

@GabdaZM
Copy link
Contributor

GabdaZM commented Feb 19, 2019

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?

@nielsmh
Copy link
Contributor Author

nielsmh commented Feb 19, 2019

That's a really good point, and probably a bug. I'm not sure exactly how to address that problem.

@nielsmh
Copy link
Contributor Author

nielsmh commented Feb 19, 2019

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

@TrueBrain
Copy link
Member

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)

src/viewport.cpp Outdated Show resolved Hide resolved
@nielsmh
Copy link
Contributor Author

nielsmh commented Feb 22, 2019

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.

@GabdaZM
Copy link
Contributor

GabdaZM commented Feb 23, 2019

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.

@nielsmh
Copy link
Contributor Author

nielsmh commented Feb 23, 2019

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.

@PeterN
Copy link
Member

PeterN commented Feb 23, 2019

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.

@nielsmh
Copy link
Contributor Author

nielsmh commented Feb 24, 2019

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.

@PeterN
Copy link
Member

PeterN commented Feb 25, 2019

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.

@nielsmh
Copy link
Contributor Author

nielsmh commented Feb 25, 2019

Those numbers match an asymptotic improvement from Θ(n²) to Ω(n log n) quite well.

√(40 * 60) ≈ 49
49 * log(49) ≈ 83 seconds

So that matches an improvement from 2400 seconds down to below 100 seconds, apart from some constants.
It's worth keeping in mind the nearest item lookup in the k-d tree really only at best Ω(log n), but in worst case can be O(n), but should still be an improvement in nearly all non-pathological cases.

@PeterN
Copy link
Member

PeterN commented Feb 25, 2019

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.)

@PeterN
Copy link
Member

PeterN commented Feb 27, 2019

Worldgen test with time bin/openttd -v null g -G 1138:

#7284 also fixes disconnected towns which this doesn't address.

@GabdaZM
Copy link
Contributor

GabdaZM commented Mar 1, 2019

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 MarkWholeScreenDirty calls as different town boundaries are displayed), the simulation speed dropped to 0.4.

@nielsmh
Copy link
Contributor Author

nielsmh commented Mar 1, 2019

So in short, for "nearest town" display across the entire screen some bitmappy caching is still necessary.
However if a much simpler variation was implemented e.g. during building stations ("which town will this station belong to?") showing just town name for the currently hovered tile, k-d tree alone would be fine.

@PeterN
Copy link
Member

PeterN commented Mar 1, 2019

Note the TGP map gen makes only up to around 13,000 towns on a 4096² map

@nielsmh
Copy link
Contributor Author

nielsmh commented Mar 1, 2019

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.

image

(This is obviously not relevant for the k-d tree itself, and should probably be in a separate PR.)

@nielsmh nielsmh marked this pull request as ready for review March 3, 2019 21:59
@nielsmh
Copy link
Contributor Author

nielsmh commented Mar 3, 2019

I think this is stable enough, except for maybe the viewport sign search range.

Copy link
Contributor

@GabdaZM GabdaZM left a 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.

src/core/kdtree.hpp Outdated Show resolved Hide resolved
src/core/kdtree.hpp Outdated Show resolved Hide resolved
src/core/kdtree.hpp Outdated Show resolved Hide resolved
src/core/kdtree.hpp Outdated Show resolved Hide resolved
src/core/kdtree.hpp Show resolved Hide resolved
@nielsmh nielsmh force-pushed the kdtree branch 3 times, most recently from 618f67c to fdc9804 Compare March 4, 2019 21:04
src/core/kdtree.hpp Show resolved Hide resolved
src/core/kdtree.hpp Outdated Show resolved Hide resolved
src/core/kdtree.hpp Show resolved Hide resolved
src/core/kdtree.hpp Show resolved Hide resolved
src/core/kdtree.hpp Show resolved Hide resolved
src/core/kdtree.hpp Show resolved Hide resolved
src/core/kdtree.hpp Show resolved Hide resolved
src/core/kdtree.hpp Show resolved Hide resolved
src/town_cmd.cpp Outdated Show resolved Hide resolved
src/town_kdtree.h Outdated Show resolved Hide resolved
src/town_cmd.cpp Show resolved Hide resolved
src/station_cmd.cpp Outdated Show resolved Hide resolved
src/station_cmd.cpp Outdated Show resolved Hide resolved
src/station_cmd.cpp Show resolved Hide resolved
src/station_cmd.cpp Outdated Show resolved Hide resolved
src/station_kdtree.h Outdated Show resolved Hide resolved
src/viewport.cpp Show resolved Hide resolved
src/viewport.cpp Outdated Show resolved Hide resolved
src/station_cmd.cpp Outdated Show resolved Hide resolved
@nielsmh nielsmh merged commit e8d397e into OpenTTD:master Mar 9, 2019
@nielsmh nielsmh deleted the kdtree branch March 9, 2019 19:27
stormcone added a commit to stormcone/OpenTTD that referenced this pull request Jul 7, 2019
nielsmh pushed a commit that referenced this pull request Jul 22, 2019
douiwby pushed a commit to douiwby/OpenTTD that referenced this pull request Apr 16, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

4 participants