Slightly more advanced collision detection (with graphics)

[The_Mezentine]

Okay, so this is definitely more of an advice seeking thread then a specific question. I'm working with the basic collision detection functions laid out here which work great for the actual "detection" part of collision detection. The problem I'm working on is this:
If two sprites partially overlap, then the collision detection returns true. If it returns true then I want to move one of the sprites (designated "mobile") until they no longer overlap. That way you get true edge-to-edge collision.
 (The reason I want this is that I don't want high-velocity objects getting "trapped" several pixels into the object they collide with)

I've been trying to think through a few ways to do this. The best I've come up with is to look at the intersection rectangle of the two objects and use its shape to determine the direction of the offset movement.
For example, if an intersection box has a greater height then it has width and the position value of the mobile object is to the left of the stationary object then the mobile should be offset left by a value equal to the intersection box's width.


This works, but I feel that its reliance on bounding boxes is going to bite me in the ass if I try to work with more complicated geometry, or with sprites who's images feature large concavities. Another issue is that for it to be compatible with a pixel perfect test I would have to draw all objects twice: once before collision test, and once after offset (since the pixel perfect test relies on alpha values)
So I'm curious to here the thoughts of anyone who wants to contribute.

[lolz123]

Most games that do not use a physics library use bounding boxes for collision detection or other simple constructs such as circles and points. Per pixel collision detection can be very taxing on the system and is not used often. If you really need to test against complex shapes, I recommend using a library like Box2D (http://box2d.org/). This is a physics library, but if physics are not desired then you can just use the collision module. I have used Box2D in some of my projects, it is very easy to use. With it, you can use any convex polygon or circle for collision detection. Concave shapes are not supported to my knowledge, but you can just use multiple shapes to achieve the same effect. Also, it is a pretty fast library; it uses a spatial partitioning system (I believe it is a KD-Tree) which is much faster then checking every shape to every shape individually.

[The_Mezentine]

Also, it is a pretty fast library; it uses a spatial partitioning system (I believe it is a KD-Tree) which is much faster then checking every shape to every shape individually.

I've never understood how spatial partitioning works. Say you're a programmer and you have 20 objects on screen. How do you have those objects stored? Individually? I keep them all in a vector. How does spatial partitioning speeding that up? Won't you have to examine each object for its co-ordinate values, so you're still cycling through the objects even if you aren't colliding with each one?

I mean I get that examining co-ordinate values is faster then running collision detection, I just had my own system in place that further sorted the vector on initialization into smaller groups based on proximity (I call it "chunking", think Minecraft) and then only cycled through the chunk in which the mobile sprite was positioned.

[lolz123]

Spatial partitioning allows one to skip checking certain objects entirely, since they are grouped in such a way that the algorithm can simply skip the group. In the game I am currently developing, I created a Quad Tree to sort all of my lights and shadow casters in such away that I can easily detect which lights are visible and which hulls its perimeter can reach using some region queries.

The Quad Tree works by grouping objects into groups which are in turn grouped as well, where every group has 1 parent group and 4 child groups.

For more information, read here:

http://en.wikipedia.org/wiki/Quadtree

The example shows it storing points, but you can store anything you want.

The KD-Tree that Box2D uses works differently from the Quad Tree, it turns the game world into a sort of 2D binary search tree. It has advantages and disadvantages over a quad tree, it is faster for region queries but can be slower if re-balancing is required often (the entities in the game work move around allot).

For more on that, go here:

http://en.wikipedia.org/wiki/Kd-tree

Other methods exist too, such as BSP Trees, Octrees (3D quad tree, Minecraft uses it to store chunks), Bins, R-Trees, etc. All have advantages and disadvantages.

Unless you want to ignore parts of your game world completely if too far away (e.g. Minecraft), you will still have to perform some logic on all entities, but at least you do not have to render them all and do note have to do things like collision checks on them all (trees speed it up by only testing against other objects in the vicinity, not all other objects).

[Haikarainen]

You're making it more complex than it have to be. Remember we have a lot of more processing power to spare since the 90's, dont be shy to actually use it.

I also thought about doing something like that, for box->pixelperfect-sprite collision, and i ended up with just checking if they collide like this:

Code: [Select]

while(DoesCollide){
move+= 0.1f;
}

This works out just fine, no lag or anything. Use this in realtime on a platformer with gravity as well, and the DoesCollide actually check for pixelperfect collision on every while-iteration. Runs really smooth!

I put it to 0.1f since i use floating point positions, and that seemed to cut it perfectly.