Sign in to follow this  
earl

2D pixel quadtree for collision detection?

Recommended Posts

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!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
I havn't read the full thread, so this may have been mentioned, just a quick idea. After creating the terrain could you not partition it into cells of a grid. When an explosion occurs it will be quick and easy to locate all cells within the radius of the explosion, you could then take the contents of these cells and make them into one large image, apply the terrain damage andthe devide it back up again placing the parts back into the cells, this will handle an explosion radius. If there is only one cell present then you can simply blow the chunk out of that cell, since the long blowtorch like weapon will simply be a series of smaller circles cutting out of the terrain the worst case scenario for it would be 4 cells being cut into during a frame, which providing you choose a smart cellsize, really shouldnt hurt you that badly.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this