Sign in to follow this  
seifist

Collision Detection Idea (from a newbie)

Recommended Posts

seifist    100
I am new to game development, I come from a primarily web based software development background, so forgive me if this question belongs in the "For Beginners" section.

I have been working on developing a simple 2d game engine (or library, whatever you want to call it) and I have a question about collision detection.

I have built in the basic three types of collision detection so far: Object-to-object bounding-box, Object-to-object reduced bounding-box and Object-to-Point pixel-level. I want to give myself the option to choose on the object level, at the "level" level and/or at the game level which one to use, for scalability, flexibility, whatever...

I am finding though, for non-rectangular polygons (namely vector objects or oddly shaped sprite objects), pixel by pixel is too taxing on resources (for the environment I am using), and reduced bounding-box doesn't work as well as I'd like. I am working on another option for collision detection, that would essentially sit between reduced bounding-box and pixel-level I am calling "grid-level" detection.

In this option, the plane would be broken up into a grid that has larger squares (10 X 10 to 100 X 100 pixels). It would essentially function like pixel level detection, but with "bigger pixels". The plane would have a two dimensional array of which grid squares were occupied and before an object tried to move into a new set of grid squares it would check to make sure they were occupied. The size of the squares within this grid would be scalable, and you would be able to fine tune it to get a balance of accuracy and resource optimization. Bigger grid squares would require less resources but also be less accurate, and visa versa.

Forgive me if "grid squares" isn't the proper term, I was in the military and anytime I think of grids I automatically go to my military terminology.

Also, please excuse me if this is obviously a bad idea, or has been done before. I am modeling the classes and methods now, and will start coding soon, I just thought I get some expert advice. So far, this is the only part of the engine I am putting in that doesn't come from a concept I have read about or studied.

Share this post


Link to post
Share on other sites
KulSeran    3267
You are looking for "Spatial Partitioning" and "Broad-phase Collision Detection".

Spatial Partitioning involves grids, trees, and graphs. The objective is to split up the space into small areas where you can quickly locate possible nearby objects. For a 2d world you'd use a 2d grid. If the colliders are sparsely populating the space, a hash-space or Quadtree would be a good choice. Hash Spaces use a hash function to map many 2d coordinates to a small number of hash buckets. Quadtrees are tree data structures that represent space being recursively divided into 4 smaller zones. You can sparsely populate your quad tree, by only creating the child nodes that you need.

Broad-phase collision usually uses algorithms like sweep-and-prune to generate lists of possibly colliding pairs of objects. Anything that can't possibly collide is quickly thrown out, and you end up with a small list of pairs. You then do whatever narrow-phase collision you need to determine if the pair represents a real collision or a false positive.

Checkout something like Box2D to take care of some of this for you.

Share this post


Link to post
Share on other sites
seifist    100
Thank you very much KulSeran, this is exactly what I was looking for.

I had a sneaking suspicion there was already something out there that met my needs, I'm glad I checked before I started "reinventing the wheel".

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