Sign in to follow this  

Datastructe for dynamic objects in engine

This topic is 4392 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

Hi, what datastructures can you recommend to store dynamic objects in a 3d scene ? We are using a BSP Tree to store static geometry, now we need to store the dynamic objects too (enemies, projectils, chairs, etc..) thanks

Share this post


Link to post
Share on other sites
There is a list of free libraries in a stick on the Alternative Game Libraries forum on this site. Overall I think the type of library you are looking for would be called a game engine.

Hehe, oops, wrong thread. Not sure how that happened.

Share this post


Link to post
Share on other sites
nobody with an idea ?

I will try to explain my problem again. We have implemented a little gameengine witch is able to render quake style bsp levels with pvs. As far as i know, bsp is only efficient if you store static data in it. Otherwise i would have to recompute the bsp tree if the position of an object changed. And that will mostlikely result in a drastic framerate drop.
What are efficient ways to store dynamic objects in a 3d game ?

thanks for your time,
b


*edit: found my old account data*

Share this post


Link to post
Share on other sites
Hi!

Yes, it is true that adding and maintaining dynamic actor geometry in the BSP would be very inefficient and for this reason I don't think anyone wants to do it that way.

You're saying your engine is Quake-style engine using a BSP as a spatial index data structure. In this case, you're probably storing your level polygons in the leaf nodes of the BSP. Due to the properties of the BSP tree each leaf is guaranteed to be a convex volume limited by the polygons stored in the leaf. Let's refer to this volume as a "cell" for now.

The simplest options are:
1. Maintain a linked list of dynamic objects occupying a cell (leaf node)
2. Maintain a linked list of dynamic objects per "room". Each "cell" then contains a reference to a "room" to which it belongs.

After this you might consider indexing your dynamic actors with a separate data structure per "room" or have a global data structure. Suitable data structures include a regular grid, kD tree, octree, quadtree etc. Whether separate indexing is needed at all depends on the number of actors, the size of the world etc.

I hope this is worth a penny. :)

-- Jani

Share this post


Link to post
Share on other sites

This topic is 4392 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