0
\$\begingroup\$

I figured this is would be the correct place to ask the following ...

1) How would I go about making multiple object collision detection (Bullets For Example)?

2) How would I make it efficient enough so that I can have many objects be able to detect collision of other objects.

The only idea I currently have is for each bullet to iterate through the other game objects and check collision individually. But that could/would have a terrible impact on time, considering that there can be many objects in the scene. I have also considered multi threading, but I really don't know how to apply it in game programming. Any Suggestions?

\$\endgroup\$
1
\$\begingroup\$

My approach is to throw everything into a quadtree, update the items inside the quadtree as they move, and then each object checks the objects returned by the quadtree. The advantage of a quadtree in general is that it reduces the number of collision checks required by dividing the playarea into smaller chunks, hence quickly ruling out entities that are far away.

Your collision loop could look something like this:

for (Entity* entity : entities)
{
    std::vector<Entity*> collisions = quadTree.Get(entity->Bounding);
    for (Entity* collision : collisions)
    {
        // Handle collisions per-entity.
    }
}

With the help of the quadtree, it shouldn't be a problem to iterate over some stuff multiple times.

Quadtree isn't a must, basically any way to do spatial hashing will probably suffice.

\$\endgroup\$
  • \$\begingroup\$ +1 for noticing that quadtree is not a must. For a beginner just a simple grid spatial partition would be enough, quadtrees are strong but they can hurt if you have constantly changing dynamic objects. \$\endgroup\$ – Pins Nov 1 '17 at 17:44
1
\$\begingroup\$

The problem you describe is solved by what is largely known as Broadphase collision detection.

Your basic problem is this:

If you have 1000 objects in your scene that all need collision checks, then using a pure brute force attack, you need to perform one million checks. And it gets exponentially worse, the more objects you add. In CS terms, this is known as an intractable problem, with O(n^2) complexity.

So, how do we solve this problem? We introduce a way of reducing the number of collision checks which are performed each update. We do this by eliminating objects which cannot possibly collide by means of very cheap tests (usually circle/circle, or AABB/AABB tests).

How those tests are run is a matter of debate, but there are several options, each with strengths and weaknesses:

  1. Quad/octree spatial partition trees
  2. Binary space partition trees (BSP)
  3. Spatial grid
  4. Sweep and prune.

The list is not exhaustive, but is a good starting point.

Quad/Octrees partition space recursively, and statically, and are very good at handling many static objects, but are poor at dealing with moving objects which have to be removed and reinserted into the structure.

BSP trees are also recursive, but require reconstruction when dealing with moving objects.

Both resursive options are at their best performance when the scene they model is static, quadtrees especially so, as their "collision" test is actually logical rather than mathematical, i.e. if two objects share a tree node, then they are close, and therefore worth the cost of further testing in your narrowphase.

Spatial grids are the most simple, conceptually, and basically divide up your game world into equal sized "cells". They can handle moving objects pretty well, but need to be updated each frame, i.e, the position of each object needs to be tested against the boundary of the cell it's currently in, and potentially moved to a new cell. Again, when collecting potential collisions, if two objects occupy the same cell, you test them further.

Sweep and prune is a different beast entirely, and is very good at handling moving objects.

The basic idea is that you have two/three sorted lists of "end points" which represent the min/max extents of each object on a given axis (X/Y/Z). These end points contain an id for the object that "owns" it. The lists are sorted every frame, and because they are unlikely to from one frame to the next, sorting is fast.

To build up pairs of potential collisions, there must be logical id overlaps. ie if you move through the list two at a time, and the two ids don't match, you cache the pair. If the pair exists in all lists, then it needs further narrow phase testing.

This is a very broad overview of common solutions, so I would recommend analysing your game to see which one suits your needs, and then researching it.

It is, however, worth noting, that in many case, a combination of these approaches can sometimes be beneficial.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.