0
\$\begingroup\$

I've created a top-down shooter with multiple objects such as enemy AI (tanks), walls, power-ups etc.

At first I was able to create about 300 AI units which aims to move the player character, checks for collision and shoot a bullet. This bullet also checks for collision on each frame until it encounters an intersection to be destroyed.

I wasn't long after I encountered massive performance issues. I immediately identified that the main performance drop was caused by the collision detection.

Each object's bounds is represented by a rectangle. If this rectangle intersects with any other rectangle the collision event is raised.

I'm currently unsuccessful in deciding what to do to reduce performance, but still maintain all the characters' capabilities. I want to check if the player or AI will collide with any object before it moves to the given location. I also want to check when the bullet collides with any other object.

I'm currently flagging all my objects by using different interfaces. I then created a Dictionary>> (GroupedObjects) Dictionary that filters the objects into different flags where the first type represents the interfaces the object inherited and the second type identifies the object's type. For e.g. I check only the Hostile tanks of type AITank for collision with the bullet. GroupObjects[Hostile][AITank].

I've read that I need to create trees where collision is only checked with all the objects in the current tree.

After a few benchmarks I identified that checking collision between 1 million rectangles uses 38ms on the CPU and checking the distance from a fixed point to 1 million other points take 136ms.

QUESTION

  1. With the benchmarks above in mind, how would I group objects by their range (for e.g. within the screen size) if calculating the distance takes more processing than checking the intersection with a rectangle representing the screen?

  2. What will be the most efficient way to check for collision between objects, meaning the player checks for collision AND the AI tank checks for collision since both of them can't move through the walls? Keep in mind that the AI isn't static and moves on each frame. Also, object A checks for collision between itself and object B and object B checks for collision between itself and object A.

  3. I created an object called CollisionMap that contains points, that represent collision, generated by an image with a specified colour as collision. These points need to be updated every time an object moves and an other object needs to check for collision with this object's CollisionMap (that can contain hundreds of points). I've created this CollisionMap to represent shapes that isn't rectangular or circular so that colliding object will treat each intersection according the shape of the shape. Does this sound possible to process if you have hundreds of objects with hundreds of points representing collision?

I'm new to game dev and I have no idea on what's the most efficient way to check for collision between multiple objects. And for all the algorithms (AABB, Rays) I've seen: it's only for one object or it's still too inefficient...

P.S. I know I typed allot, but I'm trying to explain my problem so that I don't get referenced back to sources I already examined and show what I've tried.

Thanks in advance!

\$\endgroup\$
1
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$
    – user1430
    Oct 9, 2016 at 1:46

2 Answers 2

1
\$\begingroup\$

Implementing a Quadtree

The following was converted to C# from a Java tutorial by Steven Lambert, Quick Tip: Use Quad Trees to Detect Collisions in 2D Space.

A quadtree starts as a single node. Objects added to the quadtree are added to the single node.

When more objects are added to the quadtree, it will eventually split into four subnodes. Each object will then be put into one of these subnodes according to where it lies in the 2D space. Any object that cannot fully fit inside a node’s boundary will be placed in the parent node.

enter image description here

Each subnode can continue subdividing as more objects are added.

enter image description here

We’ll start off by creating the main Quadtree class.

public class Quadtree {

  private int MAX_OBJECTS = 10;
  private int MAX_LEVELS = 5;

  private int level;
  private List<myGameObject> objects; //convert to your object type
  private Rectangle bounds;
  private Quadtree[] nodes;

 /*
  * Constructor
  */
  public Quadtree(int pLevel, Rectangle pBounds) {
   level = pLevel;
   objects = new List<myGameObject>;
   bounds = pBounds;
   nodes = new Quadtree[4];
  }
}

The Quadtree class is straightforward. MAX_OBJECTS defines how many objects a node can hold before it splits and MAX_LEVELS defines the deepest level subnode. Level is the current node level (0 being the topmost node), bounds represents the 2D space that the node occupies, and nodes are the four subnodes.

In this example, the objects the quadtree will hold are Rectangles, but for your own quadtree it can be whatever you want.

Next, we’ll implement the five methods of a quadtree: clear, split, getIndex, insert, and retrieve.

/*
 * Clears the quadtree
 */
 public void Clear() {
   objects.Clear();

   for (int i = 0; i < nodes.Count; i++) {
     if (nodes[i] != null) {
       nodes[i].Clear();
       nodes[i] = null;
     }
   }
 }

The clear method clears the quadtree by recursively clearing all objects from all nodes.

/*
 * Splits the node into 4 subnodes
 */
 private void Split() {
   int subWidth = (int)(bounds.Width / 2);
   int subHeight = (int)(bounds.Height / 2);
   int x = (int)bounds.X;
   int y = (int)bounds.Y;

   nodes[0] = new Quadtree(level+1, new Rectangle(x + subWidth, y, subWidth, subHeight));
   nodes[1] = new Quadtree(level+1, new Rectangle(x, y, subWidth, subHeight));
   nodes[2] = new Quadtree(level+1, new Rectangle(x, y + subHeight, subWidth, subHeight));
   nodes[3] = new Quadtree(level+1, new Rectangle(x + subWidth, y + subHeight, subWidth, subHeight));
 }

The split method splits the node into four subnodes by dividing the node into four equal parts and initializing the four subnodes with the new bounds.

    /*
     * Determine which node the object belongs to. -1 means
     * object cannot completely fit within a child node and is part
     * of the parent node
     */
  private int GetIndex(Rectangle pRect) {
   int index = -1;
   double verticalMidpoint = bounds.X + (bounds.Width / 2);
   double horizontalMidpoint = bounds.Y + (bounds.Height / 2);

   // Object can completely fit within the top quadrants
   boolean topQuadrant = (pRect.Y < horizontalMidpoint && pRect.Y + pRect.Height < horizontalMidpoint);
   // Object can completely fit within the bottom quadrants
   boolean bottomQuadrant = (pRect.Y > horizontalMidpoint);

   // Object can completely fit within the left quadrants
   if (pRect.X < verticalMidpoint && pRect.X + pRect.Width < verticalMidpoint) {
      if (topQuadrant) {
        index = 1;
      }
      else if (bottomQuadrant) {
        index = 2;
      }
    }
    // Object can completely fit within the right quadrants
    else if (pRect.X > verticalMidpoint) {
     if (topQuadrant) {
       index = 0;
     }
     else if (bottomQuadrant) {
       index = 3;
     }
   }

   return index;
 }

The getIndex method is a helper function of the quadtree. It determines where an object belongs in the quadtree by determining which node the object can fit into.

    public void insert(Rectangle pRect) {
       if (nodes[0] != null) {
         int index = getIndex(pRect);

         if (index != -1) {
           nodes[index].Insert(pRect);

           return;
         }
        }

       objects.Add(pRect);

       if (objects.Count > MAX_OBJECTS && level < MAX_LEVELS) {
          if (nodes[0] == null) { 
             Split(); 
          }

         int i = 0;
         while (i < objects.Count) {
           int index = GetIndex(objects[i]);
           if (index != -1) {
             nodes[index].Insert(objects.Remove(i));
           }
           else {
             i++;
           }
         }
       }
    }

The insert method is where everything comes together. The method first determines whether the node has any child nodes and tries to add the object there. If there are no child nodes or the object doesn’t fit in a child node, it adds the object to the parent node.

Once the object is added, it determines whether the node needs to split by checking if the current number of objects exceeds the max allowed objects. Splitting will cause the node to insert any object that can fit in a child node to be added to the child node; otherwise the object will stay in the parent node.

/*
 * Return all objects that could collide with the given object (recursive)
 */
 public List<myGameObject> Retrieve(List<myGameObject> returnObjects, Rectangle pRect) {
   int index = GetIndex(pRect);
   if (index != -1 && nodes[0] != null) {
     nodes[index].Retrieve(returnObjects, pRect);
   }

   returnObjects.AddRange(objects);

   return returnObjects;
 }

The final method of the quadtree is the retrieve method. It returns all objects in all nodes that the given object could potentially collide with. This method is what helps to reduce the number of pairs to check collision against.

Using This for 2D Collision Detection

Now that we have a fully functional quadtree, it’s time to use it to help reduce the checks needed for collision detection.

In a typical game, you’ll start by creating the quadtree and passing the bounds of the screen.

Quadtree quad = new Quadtree(0, new Rectangle(0,0,600,600));

At every frame, you’ll insert all objects into the quadtree by first clearing the quadtree then using the insert method for every object.

quad.Clear();
for (int i = 0; i < allObjects.Count; i++) {
  quad.Insert(allObjects[i]);
}

Once all objects have been inserted, you’ll go through each object and retrieve a list of objects it could possibly collide with. You'll then check for collisions between each object in the list and the initial object, using a collision detection algorithm.

List<myGameObject> returnObjects = new List<myGameObject>();
for (int i = 0; i < allObjects.Count; i++) {
  returnObjects.clear();
  quad.Retrieve(returnObjects, objects[i]);

  for (int x = 0; x < returnObjects.Count; x++) {
    // Run collision detection algorithm between objects
    // i.e. your Rectangle.IntersectsWith(x)
  }
}
Note: Collision detection algorithms are beyond the scope of this tutorial. See this article for an example.

Conclusion

Collision detection can be an expensive operation and can slow down the performance of your game. Quadtrees are one way you can help speed up collision detection and keep your game running at top speeds.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks Jonathan. But do you know how I can implement this solution in 3D space? Because screen size will be replaced with an area around the character and an entity's depth should also be taken into account. \$\endgroup\$ Nov 5, 2016 at 15:10
  • \$\begingroup\$ Is it really important to clear the nodes each frame. Can't I just update the node the entity is in when the entity is moved or so? \$\endgroup\$ Nov 5, 2016 at 15:18
0
\$\begingroup\$

enter image description here

On creation, each wall should be assigned to a region (maybe an array or list or chunk). These sections are part of the world map as opposed to being part of the camera.

As each moving object (tanks and bullets) moves, they should each determine which region they are in. There are many ways to do this and lots of room for optimization... but don't get focused on that too early, just get the system working first.

When each moving object knows what region it is in, now do your collision check against all the objects (moving and stationary) in that region as well as the neighboring regions.

For example, tank 1 knows it is in region 134 (how it knows this will depend on your design... maybe it's camera position plus tank position or maybe your tanks have real world coordinates), and knowing that, it then checks for collision against walls in and tanks in regions 133, 134, 135, 212, 211, 210, and the 3 regions north as well. No need to check 213's walls and tank 4, or the hundreds of other regions' tanks and walls and bullets. Tweak and optimize region sizes and even regions within regions until your performance goals are met.

That's the idea. The specifics will depend on your particular case and since I don't know c# or whatever it was you said you are using I can't offer any specific help anyway.

\$\endgroup\$
6
  • \$\begingroup\$ Thanks for your answer. By creating small regions, I don't have to check collision between allot of objects. Since most objects constantly move, they need be sorted into a list representing their region. If I use a list, I constantly need to remove the object that changed region the the list representing it's new region. Or I could increase the region size to reduce the interval of changing regions. What do you recommend I use to represent region? It doesn't help I loop through all 3000 objects to see in what region they are and creating a new list for each region is not very efficient? \$\endgroup\$ Oct 8, 2016 at 13:36
  • \$\begingroup\$ This is essentially a quad tree. Tracking which object is in which quadrant is important, and usually not expensive. \$\endgroup\$
    – ashes999
    Oct 8, 2016 at 16:44
  • \$\begingroup\$ @ashes999 can you give some input on the way to do that? I'd think pushing and popping an array. \$\endgroup\$
    – Neal Davis
    Oct 8, 2016 at 16:46
  • \$\begingroup\$ @NealDavis I built something similar in Monogame with Lists of stuff, pretty much as described here. Works pretty well. \$\endgroup\$
    – ashes999
    Oct 9, 2016 at 0:52
  • 1
    \$\begingroup\$ @RudiJansenvanVuuren that depends on your architecture. I had an explicit QuadTree class that had references to regions and sprites, and per update call, checked all objects per-quadrant for intersections. \$\endgroup\$
    – ashes999
    Oct 10, 2016 at 23:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .