Improve object-object collision performance

[raymoo]

Currently entity-entity collision checking is quadratic in the number of entities, because getObjectsInsideRadius goes through every entity and checks if it's in the zone. It would allow more colliding entities to be active on the server.

I don't know if this is the current bottleneck for entities, but supposing you had 2^16 entities active, you would need to do 2^16 * 2^16 = 2^32 (about 4 billion) bounds checks.

A quadtree typically has O(nlogn) asymptotic performance, which for 2^16 entities would be on the order of 2^16 * 16 = 2^20 = about a million "somethings". This isn't directly comparable, but clearly the quadtree would have to have much, much worse constant factors to be worse than the current solution at 2^16 entities. Finding at what count it becomes more efficient would require benchmarking.

EDIT: By O(nlogn) I mean when using it to check collisions between all objects.
EDIT2: And by quadtree I mean octree of course

[raymoo]

Another option for Minetest is spatial hashing. It would fit well with the theme of cubes.

[raymoo]

Yet another option would be sweep and prune. Probably this or spatial hashing would be a better choice than octrees due to implementation simplicity and lower constant factors.

[rubenwardy]

you had 2^16 entities active, you would need to do 2^16 * 2^16 = 2^32 (about 4 billion) bounds checks.

surely get objects in range works using the lovely static spatial partition we have, ie: the map block system, so you'd need to to have 2^16 chunks loaded in the r/16 mapblocks around the position

[raymoo]

@rubenwardy No:

minetest/src/serverenvironment.cpp

Line 955 in 5a3b8e3

void ServerEnvironment::getObjectsInsideRadius(std::vector<u16> &objects, v3f pos,

If we use spatial cells for collisions then I think that mapblocks would be too coarse; I think 4x4x4 cells would be better since most colliding entities are 1x1x1 or 1x2x1.

[numberZero]

May that be reason for servers to become unresponsive when there are many items dropped? (Items don’t seem to merge as usual if dropped in inactive mapblocks, thus the amount may become rather large in such case)

[raymoo]

@numberZero Possibly, I think even though they might not be colliding, they still contribute to the cost of getObjectsInsideRadius.

[rubenwardy]

PR merged #6587

[raymoo]

Should probably be reopened since #7539 reverted the PR.

[raymoo]

Suggested benchmarks:

• Lots of reasonably small objects densely spaced (item entity size?)
• Lots of reasonably small objects sparsely spaced
• Lots of reasonably large objects densely spaced (largest common collide-able entity I can think of is the helicopter mod one)
• Lots of reasonably large objects sparsely spaced
• Mixed sizes, dense and sparse

Also I think that the cell size for hashing should be 2 or 4 nodes long on each edge, if using spatial hashing. That would be large enough for the largest common case, which is players and mobs. I don't think the performance for tiny objects is crucial since most tiny entities do not collide with other entities.

EDIT: Sorry, just saw that I already posted that earlier

[sorcerykid]

I definitely hope there can be more investigation into spatial partitioning, as in my view the current method of iterating over all LuaEntitySAOs just isn't reasonable. I'd even be happy with a half-baked solution using mapblocks for starters, as the cell sizes can always be tweaked later. In my experience there are rarely more than 20 or 30 physical entities in a mapblock at any one time. So even with 16^3 cell sizes, that's still going to eliminate the vast majority of extraneous iterations. And suffice it to say, just about anything would better than the current implementation.

[sfan5]

Partitioning isn't so much the problem.
The big question is how to handle moving objects in a nice way? Every object can move to a different partition at every step and I don't think you want to reorganize the partitions at every step...

[numberZero]

I don't think you want to reorganize the partitions at every step...

That may be the way to go actually... it’s relatively easy, not bug-prone, and may still give a reasonable performance boost with large number of entities.

…

On 11.05.2020 22:02, sfan5 wrote: Partitioning isn't so much the problem. The big question is how to handle moving objects in a nice way? Every object can move to a different partition at every step and I don't think you want to reorganize the partitions at every step... — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#6453 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABYDCMTOOCJAQ6JUFXJXEGTRRBDU3ANCNFSM4D4ADALA>.

[sorcerykid]

I admit I have very little knowledge of how spatial partitioning algorithms work. But I mean if I were to implement something rudimentary in Lua as a proof of concept, I would simply check the position of of the entity during each server step, and and see if the object moved into a different cell (based on the hashed mapblock position). If so I'd remove the object reference from the original cell and add it into the correct cell.

Using this method means that checking for collisions should at most require scanning 27 total cells, most of which probably wouldn't have any physical objects in them. You could probably even add some further optimization by checking how far the base position is from the center of its parent cell, and reducing the neighbor checks even more if the collision box is sufficiently small.

on_activate(self, staticdata, dtime, id)
        self.id = id
        self.mapblock_hash = get_mapblock_hash(self:get_pos())
end,

on_deactivate(self, id)
        spatial_cells[self.mapblock_hash][self.id] = nil
end,

on_step(dtime, pos)
        local cur_mapblock_hash = get_mapblock_hash(pos)

        if self.mapblock_hash ~= cur_mapblock_hash then
                spatial_cells[self.mapblock_hash][self.id] = nil
                spatial_cells[cur_mapblock_hash][self.id] = self.object
                self.mapblock_hash = cur_mapblock_hash
        end
end,

Unless I'm missing something, it doesn't seem as if it should be much more complex than something like this (albeit adapted for CPP, of course).

[TheTermos]

There's a dedicated data structure in the standard lib for that kind of thing, std::unordered_map iirc.

A while ago I tried to emulate a slow server by releasing hundreds of moving entities at once, I failed because server step duration wasn't noticeably affected, so this change while technically justified may not provide as much benefit as hoped.

[sorcerykid]

According to #9403, the get_objects_in_radius() function certainly appears to be a frequent bottleneck on live servers with itemframes. I'm not sure what your test conditions were, but I'm inclined to believe that there can be a noticeable a performance hit due to fact that function iterates blindly over all active objects in the server environment.

[lhofhansl]

A simple idea to half the load is to consider each pair of entities only once, instead of twice. I.e. now we loop over each object and then lookup each other object, so any pair of objects is considered twice.

Logically that is easy, the code would need to be refactored a lot! :(

[raymoo]

@TheTermos How would you suggest unordered_map be used there? There is no guarantee that locations in the same grid cell would be mapped to the same hash value, which is required by spatial hashing. In fact, not matching up is almost guaranteed to happen in practice, because unordered_map is designed to avoid hash collisions.

[TheTermos]

There is no guarantee that locations in the same grid cell would be mapped to the same hash value, which is required by spatial hashing.

The idea was to partition the space, and then partition ID would be the key, so get_objects_within_radius would access only objects contained in specific partitions instead of the whole thing.
Then moving objects would be responsible for managing their place in the structure whenever they'd cross a partition boundary.
Imo it's best not to worry about the underlying hash implementation if not necessary.

I should rather have said unordered_multimap because that one allows for key duplicates.

[numberZero]

get_objects_within_radius is not for object-object collisions AFAIK. It gets objects whose logical position is within given radius. Not sure where is it used... in ABMs? (to compute the obscure additional parameters that are virtually never used)

But for the actual collisions, collision boxes are used. They can be arbitrary (axis aligned, actually), so that one needs to hash a box and not a point. That’s possible but requires thinking. My attempt was unsuccessful (#6587, reverted).

[raymoo]

@TheTermos I see now, thanks for the explanation. It turns out I didn't really read sorcerykid's post very well either, because I was imagining a typical spatial hashing implementation with a fixed-size table, but that's not what was in that post. I guess compared to a fixed-size table this way saves memory and asymptotic behavior if there are a lot of grid cells that would be matched to the same spot in the table, but has worse constant factors.

@numberZero It's used here as a broadphase for collision (

minetest/src/collision.cpp

Line 408 in 0fc51db

s_env->getObjectsInsideRadius(s_objects, *pos_f, distance, include_obj_cb);

), though not really a good one for reasons mentioned earlier. I think it could even miss colliding objects if the other object was big enough.

[raymoo]

Also something to note, currently any accelerating structure would need to be updated incrementally because entity movement is resolved sequentially, so each entity when moving needs to have updated results from all the previous entities moving that step. An alternative strategy that would allow rebuilding the structure each step would be to move all entities without collision with other entities, and then push intersecting pairs away from each other until they aren't colliding. This allows either keeping a structure incrementally or just building it before doing the intersection checks. Changing it like this is likely to make collision results a little worse in corner cases, like if two entities move into intersection, but there's not enough room in the terrain to push them away from each other. I believe this is how most game physics engines work though, allowing objects to penetrate and then resolving collisions.

[ExeVirus]

So I've done a decent amount of thinking on this subject when Rubenwardy brought it up about 2 years ago to me in a chat.

Long Explaination of my proposed solution with code snippets

Currently the max world size is 60000x60000x60000, which is easy for non-programmers, but bad for a spatial dataset. In our case, it would be better to treat max world size as 65536x65536x65536 (2^16), which allows MUCH better partitioning that can speed up calculations significantly.

First off, we have to understand the implications of a spatial dataset based merely on mapblocks alone. We firstly need to have a datastructure that is loaded at server startup for each possible mapblock (no dynamic generation for this structure) to have fast access times. This datastructure would just be a 3 dimensional array, with size 4096x4096x4096. Even if this array is just a bunch of 64 bit pointers, that's still 8 bytes * 4096 *4096 * 4096 = 512 Gigabytes.

That obviously is not going to fly. So instead we need a multi-layer approach. I.e. a multi-dimensional array of multidimensional arrays. But the lower multidimensional array is not allocated until it's needed. This also helps with processing, as any NULL large chunk of area obviously has no entities in it.

I propose a two layer system:

// Mapblock in this case represents a vector/list of entity pointers contained in the actual mapblock,
// not an actual mapblock pointer

//Lower layer (pointers to mapblocks)
typedef mapblock*[32][32][32] BottomLayer;

//Upper Layer (pointers to BottomLayers)
typedef BottomLayer*[128][128][128] TopLayer;

//Only actually create one TopLayer at startup, and initialize BottomLayers as needed:
TopLayer StartUp; 

In this case, the startup spatial map is only 16 MB of RAM (much better),
and when we allocate the BottomLayers, each is only 256 KB.

Finally, the underlying "mapblock" vectors would be allocated as needed.

Why not more layers? Extra complexity for little memory benefit. AND it starts to hurt update performance.

"Update performance?"

Well, when I say update performance, I mean that each entity has to place itself in the right bucket.

So if player1 joins the game at 0,0,0, we must find the correponding TopLayer, which can be had easily with some math:
0,0,0 is actually (30912/16/32),(30912/16/32),(30912/16/32) in our map (beacuse −30912=0 in this case). Or 60,60,60. We would check if
this TopLayer[60][60][60] is NULL, which it would be, at startup of any world, every time. Because this map is not saved between
shutdowns or restarts, just like active objects are erased when a mapblock is unloaded (unless you save them, different story).

So we would allocate a new BottomLayer for our TopLayer:

TopLayer[60][60][60] = new BottomLayer; //That was easy!

Now, we get our actual mapblock for this player, so we can add their pointer to it. (30912/16)-60*32 = 12. Meaning we would be in
the [12][12][12] mapblock of our Bottom layer. So we check if it's null (it will be here), and create a mapblock vector/list, and add
ourselves to it:

auto localBottom = TopLayer[60][60][60];
auto localMapBlock = localBottom[12][12][12];
if(localMapBlock != nullptr) {
    localMapBlock = new std::list<entity*>(8); //size 4-16 is reasonable here in my mind
}
localMapBlock.push_back(&Player1); //Done, now there's a player there!
Player1.noteCurrentMapblock(topLayerX * 32 + BottomLayerX, etc, etc); //for updating when we leave

Then, every update step for that players' position on the server will require you to check if you have left your previous mapblock,
remove yourself from it, add yourself to your new mapblock, and noteCurrentMapblock() on the entity. If you haven't changed mapblocks, no update required. Based on my earlier comments, if we had more
layers than just Top and Bottom, then we would have to start updating more layers as we move around across borders.

These would be the same steps for any given entity.

The key helpful factor here is the active mapblocks help inform us. When a mapblock is unloaded,
we know we can just delete and set null the underlying mapblock in this map.

How does all this help with performance?

When it comes time to do GetObjectsInRadius() or GetObjectsInRectangle() or GetObjectsInRayCast(), we can operate
on these layers rather than using linear search on every object in the server. (yes GetObjectsInRayCast doesn't exist, but it could now without performance death)

For example, if player1 wants to check for entities within a range of 16, we only need to check 8 mapblocks surrounding our own.
And likely 4 or more will be empty. And the ones that aren't will only have like a total of 15 entities, rather than the sometimes 500-10,000
you can have on larger servers total at once.

Raycast checks could actually be faster in some cases, as we are only looking for the first hit and likely have a max range of view distances in the ~300 max. If we were looking, say straight backward at 0,0,0, we would only check 13 mapblocks backward, check each one at a time, and then one TopLayer back (since we went from [12][12][12] to [12][12][0] in our current TopLayer). So we would check topLayer[60][60][59]. And could very well find it empty. In which case we did 14 checks to look through 300 distance. Of course, this assumes no terrain collisions, but even that can be included and optimized for (as hitting terrain could stop the search early, XRAY mode optional of course)

Can we use it for entity-entity collisions?

Yes, these help with entity-entity collisions, as we are able to narrow down our search to our own mapblock or at least nearby ones.
Just keep in mind we use a 1.5 meter tolerance on our current collision.cpp code, so sometimes you might not have a collision box that goes outside your mapblock, but someone else might.

[ExeVirus]

Note, this is compatible with incremental updates, and would be the default method I would personally implement this. Entity should update themselves in the map at the end of their global physics step.

[sfan5]

Before any spatially indexed implementation is added the engine needs some way to track movement of objects, on_step is an obvious way to track changes but objects can be moved at any point during a server step, not just inside on_step.

I'm not sure how this would be best done. Changing ServerActiveObject::setPos is an obvious solution, but objects shouldn't need to be aware of what they are contained in (or should they?), but delegating responsibility to the caller sucks too.
I guess ServerActiveObject could easily call a function in ServerEnvironment which then does whatever is needed.

Also, we shouldn't reinvent the wheel. SpatialIndex is already (optionally) used for AreaStores and provides the primitives we need.
I implemented a PoC of that here: https://github.com/sfan5/minetest/tree/spatialent
(problem described above: notice how SpatialImpl caches the previous object positions on its own, this shouldn't be necessary)

[ExeVirus]

Necessary, no. But more efficient. Without caching your previous bin, you have to recalculate every object's latest bin every position update, or find the bin the player is currently in through search. We'd have to do a quick search nearby. Teleporting obviously would mess with it, and may require essentially linear search speeds to update the index.

I don't think you can get away from a serverActiveObject maintaining a pointer/hash/value to the bin/position it was previously contained in.

[sfan5]

I wasn't saying that you don't have to cache the previous position, just that the active object manager shouldn't have responsibility to do this.