Sign in to follow this  

Distinct quadtrees for static and moving objects

This topic is 483 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am currently implementing a quadtree (in TypeScript) for a game prototype.

 

In order to optimize performances, a little bit, instead of managing just one quadtree for all game objects, I am wondering if it would be speed-wise to separate static objects (like walls) from movings objects (like characters).

 

This way, the static layer shall never be updated (cleared and populated) each frame which may save some CPU cycles.

 

Obviously, in order to check collision, we will have to retrieve objects from both the static and the moving objects layers.

 

What do you think about this idea? Is it relevant?

 

Share this post


Link to post
Share on other sites

There are data structures that are optimized for "build-once read-many". So there is definitely some value in separating out static objects from movable ones. You wouldn't use the same data structure for both, though. There are a lot of data structures out there that are optimized for different situations, so choose the right one for each case if you need optimization.

 

That said... if you keep your code well designed, it should be easy to swap out implementations later after you have everything built so you can test real world situations and find the data structure that works best for you.

Share this post


Link to post
Share on other sites

I used to have an octree which tried to keep cells "hot" on the cache by putting in a short delay before removing a cell. The idea was that if someone shoots a machine gun with lots of little, fast moving bullets, it would be a waste of memory to delete and recreate the cells. It worked, but the implementation was messy and probably caused more overhead costs than savings. Back then, I didn't even take careful measurements of my timings, so it was impossible to know if I made an improvement or a regression.

 

If you really want to make a distinction between static objects and movable objects, you could just create two quad trees. One is for static objects and almost never changes, and the other is for moveable objects, which have to check against other moveable objects and against static objects.

Share this post


Link to post
Share on other sites

There are data structures that are optimized for "build-once read-many". So there is definitely some value in separating out static objects from movable ones. You wouldn't use the same data structure for both, though. There are a lot of data structures out there that are optimized for different situations, so choose the right one for each case if you need optimization.

 

That said... if you keep your code well designed, it should be easy to swap out implementations later after you have everything built so you can test real world situations and find the data structure that works best for you.

Would you have some suggestions about data structures that could be more suitable than quadtrees for static objects?

Edited by yahiko00

Share this post


Link to post
Share on other sites

You can use a static AABB tree if you need fast ray or AABB queries. It is possible to store the nodes in an array to improve cache performance when traversing it. I use this for generating mesh contacts in my physics engine, but I'm pretty sure it is suitable for graphics (e.g. culling) as well. 

Share this post


Link to post
Share on other sites

It depends on several implementation details that involves memory management, data structures, and heuristics.

 

You can achieve O(1) insertion with a Quadtree if you implement the optimizations described by L. Spiro in this post (originally described in GPG 4 IIRC):

 

http://lspiroengine.com/?p=530

 

but I can't talk more about this because I never needed to implement such data structure.

 

As for AABB trees, one detail is the way the nodes are  stored in the memory. For both static and dynamic tree is possible to store their nodes in an array in an attempt to decrease memory access time when traversing the tree. For an array-based static tree the insertion is simple. But for an array-based dynamic tree the operations are not so trivial. A free list of nodes needs to be maintained in the tree for quick node allocation when inserting a new leaf. It is also recommended to inflate the node's AABB by some units such that becomes possible not re-inserting the node into the tree in a future time, when updating the AABB. For example, that could be done by checking if the new AABB is still contained in the old AABB. Another optimization is to predictively extend the new AABB by some units in the direction of motion of the object associated with the node.

 

Here is an example implementation if you need help implementing the dynamic tree with the optmizations/heuristics I've mentioned above:

 

https://github.com/erincatto/Box2D/blob/master/Box2D/Box2D/Collision/b2DynamicTree.cpp

 

Here are some nice slides by Erwin 

 

https://bullet.googlecode.com/files/GDC10_Coumans_Erwin_Contact.pdf

Edited by Irlan Robson

Share this post


Link to post
Share on other sites
For moving objects collision detection is always my key.

As other posters have said. It's down to what your world is.

For me in my game I'm using voxelised space to register and deregister my moving objects. It's actually just a reference count at the moment. But what it does is allow for quick eliminiation 99% of the time. From there even if i do a horrible list search for collisions then it's only on objects that have collided with something or close to.

I think your quad tree is a good idea. That's if your world is operating in 2d space. You could align your quad tree to sectors of voxel space and you could then quickly test for more detailed collisions. Be aware though. In voxelspace i test the neighbor for possible collisions. And on edge cases you might need to visit another node in the quadtree.

Youre doing the right thing anyway by minimising your potential collision sets. Have a look around at combining different ones if they can rapidly shrink your sets.

Share this post


Link to post
Share on other sites

While you're looking at other data structures you should take a look at loose quad/octree's.  I've forgotten much of what I had read about them but you might find them useful.

 

edit - This is what I had originally read in regards to loose octrees/quadtrees.  http://www.tulrich.com/geekstuff/partitioning.html

Edited by Infinisearch

Share this post


Link to post
Share on other sites

I am currently finishing to implement a small prototype, and fix some bugs.

After that, I plan to run a first benchmark between a simple quadtree with all game objects and a quadtree with two layers, one for static objects and another for moving objects.

I will publish my results here of course.

Then, I will try to implement some other structures to compare their performance with quadtrees.

Share this post


Link to post
Share on other sites

This topic is 483 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this