Hi all, I'm looking at creating a 2D game that combines a fully destructible pixel map terrain, with geometric primitives (as opposed to sprites). I'm intending to build this game for hand held devices, so performance is critical. I'm expecting probably no more than 50 active objects on the entire map at any one time. I'm well aware of standard approaches to collision detection, but they all seem to fall into 2 categories. Those being ALL geometry, or ALL pixel based. I could either go the obvious route and do a pixel look-up on the outline of my geometry, or a more reliable method by rasterizing the entire geometry and then speeding up the check via bitmasking. OR, I could go with something more complex and turn the terrain into a quadtree, where a parent cell is recursively subdivided until all contained pixels are of the same type (i.e. All solid). This saves a lot of memory for areas on the map that are largely solid. I like the idea of a quadtree, because it would enable me to do sweep tests on all my geometry and avoid missing collisions with narrow bits of terrain. There are however a couple of issues I can see with this method, and I would like some suggestions about the best way to approach them. 1) Update performance on the quadtree - If terrain is added or removed, what would be the fastest way to rebuild the quadtree? Would this be unbearably slow? 2) Finding the normal of collision (for accurate response) - With typical pixel maps, I guess you just search the border pixels in the vicinity and go from there, but a quad tree would either require a second collision query of the area surrounding the contact point, or some smart traversal of the tree until the surrounding pixels had been found (any ideas how?). I'd love to hear any thoughts you may have about this technique. Is it more trouble than it's worth? Would rasterizing some/all of my geometry be the better approach? Are there any other approaches I haven't thought of? Apologies for a very long first post!

Anyone?

Was my description clear?

Can't you just use something geometric like a quad tree in a first broad detection of a small set of your smaller objects that could collide, and then do things the pixel way ?

As for rebuilding the tree, you're not forced to do it every frame, but only when destruction occurs. You're maybe also not forced to rebuild the whole tree, but only the part containing objects that changes.

Sorry if I missed the point.

I essentially already have which collision between objects and tiles (64x64 pixels) can occur for free (as tiles can be looked up by index from an objects min/max positions), and I don't create empty tiles, so only have to perform slow pixel checks for tiles that actually have a chance of colliding. Also, I think resorting to pixel checks after an initial quadtree check would prevent me from doing sweep tests, so tunneling would still be an issue.

Regarding rebuilding the quadtree, if for instance a weapon is digging through the terrain, it would require partial rebuilding every frame for however long the weapon is active. Therefore I'd need to handle this worst case scenario with no major slowdown.

I'm starting to think I'll just have to implement the quadtree approach and do some real benchmarks to see if it'll perform fast enough for my needs.

I'm still a little fuzzy on how to do the insertion & deletion of pixels into the tree, as well as doing the collision normal calculation. So if anyone has any thoughts, pseudo code or reference material they'd like to share, I'm all ears!

Thanks for the help so far.