Collisions in computer games

I have a general questions regarding techniques, or approaches used in computer games to detect particles (or objects collisions). Even in a smiple examples, like currently popular angry birds, how is it programmetically achieved that the game knows that an object hits another one and works out it trajectory, while this object can hit others etc. I presume it is not constantly checking states of ALL the objects in the game map...

Than开发者_运维问答ks for any hints/answers and sorry for a little dummy/general question.

Games like Angry Birds use a physics engine to move objects around and do collision detection. If you want to learn more about how physics engines work, a good place to start is by reading up on Box2D. I don't know what engine Angry Birds uses, but Box2D is widely used and open-source.

For simpler games however you probably don't need a physics engine, and so the collision detection is fairly simple to do and involves two parts:

First is determining which objects to test collision between. For many small games it is actually not a bad idea to test every single object against every other object. Although your question is leery of this brute-force approach, computers are very fast at routine math like that.

For larger scenes however you will want to cull out all the objects that are too far away from the player to matter. Basically you break up the scene into zones and then first test which zone the character is in, then test for collision with every object in that zone.

One technique for doing this is called "quadtree". Another technique you could use is Binary Space Partitioning. In both cases the scene is broken up into a lot of smaller pieces that you can use to organize the scene.

The second part is detecting the collision between two specific objects. The easiest way to do this is distance checks; just calculate how far apart the two objects are, and if they are close enough then they are colliding.

Almost as easy is to build a bounding box around the objects you want to test. It is pretty easy to check if two boxes are overlapping or not, just by comparing their coordinates.

Now bounding boxes are just rectangles; this approach could get more complex if the shapes you want to collide are represented by arbitrary polygons. Some basic knowledge of geometry is usually enough for this part, although full-featured physics engines can get into a lot more detail, telling you not just that a collision has happened, but exactly when and how it happened.

This is one of those hard to answer questions here, but here's a very basic example in 2D as a very basic example, in pseudo-code.

for-each sprite in scene:
  for-each othersprite in scene:
    if sprite is not othersprite & sprite.XY = othersprite.XY
       collision = true;
    else
       collision = false;

Hopefully that should be enough to get your thought muscles working!

Addendum: Other improvements would be to assume an area around the XY instead of a precise location, which then gives you a sort of support for sprites with large areas.

For 3D theory, I'll give you the article I read a while ago:

http://www.euclideanspace.com/threed/animation/collisiondetect/index.htm

num1's answer covers most of what I would say and so I voted it up. But there are a few modifications/additional points I would make:

1) Bounding boxes are actually the second easiest way to test collision. The easiest way is distance checks; just calculate how far apart the two objects are, and if they are close enough then they are colliding.

2) Another common way of organizing the scene in order to optimize collision tests (ie. an alternative to BSP) is quadtrees. In either case, basically you break up the scene into zones and then first test which zone the character is in, then test for collision with every object in that zone. That way if the level is huge you don't test against every single object in the level; you can cull out all the objects that are too far away from the player to matter.

3) I would emphasize more that Angry Birds uses a physics engine to handle its collisions. While distance checks and bounding boxes are fine for most 2D games, Angry Birds clearly did not use either of those simple methods and instead relied on collision detection from their physics engine. I don't know what physics engine is used in that game, but Box2D is widely used and open-source.