-
Notifications
You must be signed in to change notification settings - Fork 2k
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
Add spatial index for objects #14631
base: master
Are you sure you want to change the base?
Conversation
I think this will need comprehensive tests for how the spatial index and object lifecycle interact. (basically the check list I had in that issue) |
How does this relate to #14643? Do they solve the same problem? Are they complementary? |
They solve the same problem in different ways. I am not yet sure which way is better. Some thoughts:
|
appgurueu is correct on many fronts here. To clarify on the two drawbacks mentioned, I have two pending solutions for the subjects:
I have implemented exactly the recommended solution here: check the number of buckets we are about to iterate over and compare against the total number of entities. If there more mapblocks, I fallback to linear iteration over all entities for now, until the algorithm is more optimized.
Except where all entities in the entire server are in a single mapblock, this solution will still help, just not tremendously. In this case, only one or two mapblocks will need to be checked (worst case 8 on a corner), ignoring all the other entities on the server. I am have been debating allowing the data structure use a non-hardcoded bucket size, so that buckets can be of size 16x16x16 or 1x1x1, 64x64x64, etc. Then we could expose it as a setting for servers/games to tweak for their needs.
And yes, both algorithms can be improved. I'm looking to give mine another 2 or 3x improvement for large range queries by using the regularity of the boxes to check for whole rows/columns of mapblocks, rather than each individual mapblock or entity inside a given mapblock. This will only apply for range queries that are at least 2 mapblocks in dimension or larger, however. I'm looking to improve this specifically to help with connected client object updates, which we currently rely on large getObjectsInRadius queries for. My Recommendation:Once we are done with optimizations over the next days/weeks, we can do side by side comparisons and let the numbers decide for us. If they're comparable, Core Devs can make that call. These structures are certainly exclusive: i.e. we should choose one not both. |
84bcdd9
to
fb5d3bd
Compare
946a55b
to
953f2d1
Compare
What's needed to make progress on this one (or #14643)? |
Mostly we need solid, repeatable, verifiable, and somewhat diverse test
methods, to prove to ourselves these implementations are flawless, and to
have a very good benchmark to say which we choose.
There are small scale tests we can set up easily, but the most important is
one that is pseudorandom, that adds, removes, and moves entities, starting
with 100, up to about 2-3K, and back down.
We would do both in radius and in box checks during this time (say every 20
frames or something), and I'd want to see identical results between master
and these branches before saying merge. We haven't really tested all the
cases of entities being added and removed during iteration in real time and
need to be confident in the solution.
I think it would take maybe 3-5 hours to get those tests written, and I
would have them done probably within a week or two.
After we verify they are safe implementations, it should be very easy to
compare performance and consider code maintenance at that point to decide
the better solution.
Really don't want to over engineer, or bike shed, but hey as long as a core
dev doesn't have to do it... Shrug
…On Mon, Jun 3, 2024, 12:36 PM lhofhansl ***@***.***> wrote:
What's needed to make progress on this one (or #14643
<#14643>)?
I tried both out on a busy world and it all seems to work. (In my scenario
I did not see any performance improvements - many object in a single blocks
- but all continued to work fine)
—
Reply to this email directly, view it on GitHub
<#14631 (comment)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/AKT7N2WUEVIM7BTOEKYFALDZFSLRFAVCNFSM6AAAAABHPG5SFWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDCNBVGY3DANRRGY>
.
You are receiving this because you commented.Message ID:
***@***.***>
|
953f2d1
to
743199f
Compare
Optimizes range queries for objects in order to resolve #14613.
The spatial index is a dynamic forest of static k-d-trees, as outlined in my comment.
To do
This PR is WIP; the TODOs are in-source and might not be exhaustive.
How to test
There is a randomized unit test which tests this against a naive implementation. I also recommend playing e.g. Shadow Forest or other games with entities to give this some "field testing".
The benchmarks added by sfan show the following range query speedups on my setup:
Data
old
new