Frustum/view rectangle culling with quadtrees
Monkey Forums/Monkey Programming/Frustum/view rectangle culling with quadtrees
| ||
| Hello, Has anyone done anything like this for their Monkey game yet? I've been putting off doing this for a while, but for games with large levels, it may be unavoidable. I've been looking into culling of objects to reduce the number of polls I need to do for subobjects' AI inside a viewing rectangle by sorting the objects into a quadtree or some other sorted structure that I can traverse and exit early when the objects are outside the view rectangle. It seems that it would help for me to understand how to go about doing this if there was already a quadtree implementation for monkey in widespread use, but a cursory glance at the forums doesn't seem that anyone has made one that handles the specific situation I'm stuck with. Does anyone have any experience in this area? Specifically, I'm looking to partition a map based on rectangles in it, not points, specifically, so maybe quadtrees wouldn't be the perfect solution for this..... (Maybe some sort of R-Tree?!) |
| ||
| i'm in the process of making an Octree for miniB3D, but i've also made a primitive "grid-tree" for a tower defense game: simply dividing a map into a grid and managing the objects that go in and out of each area. it definitely helped with the firing AI. Box2D also uses some type of tree. for the Octree, i broke it into two classes: the main tree and the nodes. calls to the nodes are recursive which makes splitting/balancing easier. i can send you my in-progress Octree code, but there are still bugs in it. |
| ||
| I can wait! In the meantime, it's on my list of things to look into.... |
| ||
| By "view rectangle" are you referring to the camera view or some concept of AI entity view area? If you're just doing it for the camera then managing a space partition tree for moving objects may well be less efficient than doing the simple thing of testing each one that moves (or all if the camera moves) against the camera view area. If you have a load of static objects then a simple grid partition for those will likely get you where you need to be. If you are looking for something to enable testing against lots of AI awareness areas then Box2D has a pretty fancy spacial partitioning system that you can wire into that will give you what you need. Using that without also using it for collisions (not necessarily with physics responses) might be a bit of a waste though. |
   |