Problems with OctTree Design
Author
I''m working on a space sim, similar to Tie Fighter, but have run into some problems. Hopefully someone hear can give me some advice.
My original idea was to create an octree where the leaves are sectors, which is a cubic area. It would contain a linked list of GameObjects. This would be fine, except I wasn''t sure what to do if GameObjects were in multiple sectors.
My next idea was to have the sector store a linked list of triangles, and each triable object has a pointer to it''s corresponding GameObject. However, I''m not sure how to handle when triangles are in multiple sectors. Any advice?
Thanks.
-Nick
Why not have a linked list of pointers to game objects per octree node... If an objects overlaps, what you should do depends on the wider design of the system. you may wish to only include the object in the node it is mostly in. This makes scenegraph design easier, but means that you may have to introduce otherwise avoidable calculations in collision detection checks (check in adjacent ocTree nodes as well as the one the object resides within). If you decide to repeat the object.. then this has implications in your scenegraph design (ie you don''t want to render it twice). If you have some form of render manager, then this isn''t an issue... but otherwise you might need some special flag to make sure it only gets rendered once. This scheme however means you can be sure that only objects within that octree node can collide with you... but similarly, you might be in two node, so again.. there are design issues. I wonder how important having a fine octree structure in a space sim is however. A simple distance squared test is VERY cheap, and provides exremely cheap rejection for collision and culling tests. Octrees seem more useful when the object density is going to be much higher.
one of my top 3 games is TieFighter!!
(I am assuming you mean the Dos version, right after Xwing??)..
Man, I think I will install that guy tonight!! Anyone have dos 6.22??
I wish you the best nickwinters!
(I am assuming you mean the Dos version, right after Xwing??)..
Man, I think I will install that guy tonight!! Anyone have dos 6.22??
I wish you the best nickwinters!
You may want to look into AABB trees instead, since they are likely to be far more effective for a game as sparse as a space sim.
for scattered objects, a sweep and prune seems a good solution. basically, it involves sorting objects on 2 or 3 axes using their bounding box, and testing intervals overlap. that should give a (2n) solution (for 2-axis sweep and prune).
but if you have 50 or so objects, a distance calculations seems fair. But as soon as those Tie let rip, then the amount of objects to test can rise quite significantly (laser beams, missiles).
With any partitioning algo (sweep and prune, radius checks, trees), because laser beams aren''t tested against each other, you might want two systems working concurrently, one for the bullets, one for the ships. So you test one (laser beams) against the other (ships), and one oagainst itself (ship against ships).
but if you have 50 or so objects, a distance calculations seems fair. But as soon as those Tie let rip, then the amount of objects to test can rise quite significantly (laser beams, missiles).
With any partitioning algo (sweep and prune, radius checks, trees), because laser beams aren''t tested against each other, you might want two systems working concurrently, one for the bullets, one for the ships. So you test one (laser beams) against the other (ships), and one oagainst itself (ship against ships).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
