Datastructe for dynamic objects in engine

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.

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*

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

Hi!

Thanks for your answer! This sounds like a good idea and i will try to implement this now.

thank you!

b