Skip to main content
gamedev.net
🔒 Locked

Data Structure for Physics System

Started by Palidine 3 replies 1.3k views
Original Post
Palidine
Palidine
Hey, I've been googling around the internets & searching on this site for a couple days now about this topic but haven't gotten near a comprehensive answer to the following question: For a physics system what is a good spatial data structure for your dynamic objects and how is it typically maintained? I've seen a lot about kd-trees or octtrees (I am familliar with both). However, would you completely rebuild the tree each frame with your dynamic objects (if so does this work because the savings on neighborhood queries are worth that cost)? Would you maintain it by removing and re-adding objects that have moved (if so how do you keep the tree balanced)? It seems like there are 2 challenges to overcome: 1) the cost of building a spatial data structure 2) the cost of doing efficient neighborhood queries to retrieve the group of objects with whom you must check collisions. 2 necessitates 1, so i guess I'm just wondering how you make 1 efficient. Obviously, these things are very game dependent (# of entities, etc). I'm just wondering what the most common approaches are. It would also be nice to be able to use the spatial data structure for rendering optimizations rather than requiring a separate one to be maintained for that purpose. Thanks -me
haphazardlynamed
haphazardlynamed
I like Portal Systems. (the low-level kind as seen in Descent, not the abstract ones used in say Halo for example)
Since the division of space is directly linked to the map complexity I'll just use the Sectors themselves for dynamic object partitioning.
Unlike a tree approach there is no rebalancing of the whole tree; when something moves we only check if it passed thru a portal in which case we have a direct pointer to it's new sector.
And of course the Portal System itself is great for the rendering culling...


oh, the cost of building the Sector/Portal arrangment is free of course, because you make that be a property of your map editor.
Palidine
Palidine
Quote:
Original post by haphazardlynamed
I like Portal Systems. (the low-level kind as seen in Descent, not the abstract ones used in say Halo for example)


In which case the "neighborhood" means all the dynamic objects in the test object's portal, yes? I'm not so familiar with portal systems, but i take it that this culls the number of possible objects per neighborhood down to a pretty reasonable number?

-me
haphazardlynamed
haphazardlynamed
We call them Sectors,
space is partiontioned into convex sectors, which are then linked to each other via Portals.
A sector is defined by its polygonal borders, which can either be impassable walls(of the map) or shared with an adjacent sector thus making them Portals.

That the sector be convex is not necesarially required in some engines... but it allows many optimizations in terms of collision checks with the walls as well as visibility determination
that is a tradeoff though, since requiring convexity means many more sectors are needed to represent map details

in general though, yeah, not very many objects co-exist in the same sector; since sector size tends to be the same order of magnitude as the map's complexity (wall segment sizes and whatnot)



P.S. note that this kind of system is almost exlusively for indoor mazelike environments. Like Doom and whatnot.

You said you're working on physics... which is probably ok, but if you're thinking of collisions between say 1000 bouncing balls in a playpen... this probaby is not ideal. There are algorithms for That kinda thing to be found in ... look into what molecular simulations for chemists use...i forget the name
Christer Ericson
Christer Ericson
Quote:
Original post by Palidine
I'm just wondering what the most common approaches are [for dynamic objects].
Entire books have been written on this topic, I believe. Three main choices: static spatial partitioning (grids, hierarchical grids, and (loose) octrees), dynamic spatial partitioning (sort and sweep), and dynamic tree hierarchies (often sphere or AABB trees, possibly lazily updated). They all have benefits and drawbacks and it really depends on your particulars which approach(es) would be best for you (such as what types of queries you need to support, how many objects, how they vary in size, how large the world is, etc). But just to suggest something, try hierarchical grids or possibly sort and sweep.

Quote:
It would also be nice to be able to use the spatial data structure for rendering optimizations rather than requiring a separate one to be maintained for that purpose.
This is often not a good idea, as it will typically save some memory but at the cost of slowing down both systems (in that a particular data structure may not support rendering and collision queries equally well; cache behavior will deteriorate when you're skipping irrelevant data looking only for data relevant to the one system; etc).

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.