Collision Detection and How Effective They Are

Question

How exactly do you implement collision detection? What are the costs? Different platforms (c / C ++, java, cocoa / iphone, flash, directX) have different optimizations for calculating collisions. And finally, are there any libraries available for this, for me, or some that I can simply interpret for my platform of choice?

As I understand it, you will need to go through the collision map and find the area of ​​interest, and then match the input thing (for example, a sprite) with the type of pixel that is in the question area. I understand the most basic idea, but I do not understand the main implementation or even a higher level in this regard. It would seem that this type of detection, or any other, is very expensive. Tile map? Bit array? How are they created from the image (I would have guessed that loops and doing things)?

I ask this question to better understand the performance behind the scenes and to understand exactly what is happening. Links, links or examples would be very helpful. I know this question is a bit long, so any help or links would be very welcome. Thank you SO!

Answer 1

Check out this answer to my question regarding simple collision detection with a bounding box .

Collision detection is a huge topic, but there are primarily two areas. Wide phase and narrow phase detection. The wide phase is fast and dirty, if this goes away, you go on to narrow phase detection. The narrow phase, in turn, is more complex in depth. Even if collision detection is detected by large-scale detection, the object may not have collided with anything.

The key to being effective in games is not doing the job unless you need it. In other words, if you do not need to perform collision detection, do not. I mean, this is a game like GTA4. It will be crazy, plus the game will work as a slide show if you must check each object against each other in the world. Many methods can be used, but the best way is to limit the number of checks. Here the world is split using quad / oct / binary / trees or some other spatial indexing . This means that only objects nearby are scanned, and therefore the game will work much faster, since only possible objects for collisions are scanned.

"How are they created from the image (I would have guessed that the cycle and something to do)?

Yes and no. Pixel collision detection falls into narrow phase detection and is expensive. In most games, this is simply not necessary. Take a generic FPS. If you shoot an enemy between your legs, you say it is sometimes classified as a strike, it is not a perfect pixel, but it works quite well.

In 2D games, you know the size of the sprite, so any calculation will use a bounding volume. The same can be said of 3D games, except that this bounding volume is now in three dimensions. You can break down complex shapes / models down to further bounding volumes. This process is much, much faster than pixel checking. Sometimes, however, pixel detection is required. It all depends on the type of game.

As for the good links, I will point you to Gamedev.net . This is a great site to start with, covering a wide variety of topics. A good tutorial , showing you what additional concepts can be applied, is based on developing a game called N and N +. In conclusion, a game is an experience and an illusion. At any time, if game programmers can make a simplification to speed up development or a game, take it.