Chapter 6. 2D Optimizations

Now that we know how to check for collisions between 2D primitives, it's time to start thinking about performance. Checking for collisions between a few objects is trivial. However, when it comes to checking for collisions between hundreds, or even thousands of objects, that's going to be tricky. With so many objects, performance really starts to matter. In this chapter, we will cover topics to improve performance when checking for collisions between objects. Specifically, we will cover:

• Containing circle

• Containing rectangle

• Simple and complex shapes

• Quad tree

• Broad phase collisions

Introduction

Optimizing 2D collisions is not a trivial task. There are several strategies for improving the speed of complex collision detection. However, none of the available strategies are perfect. You have to understand the pros and cons of each strategy for your game to be able to decide on the best strategy for handling and optimizing collisions.

Containing circle

One of the necessities for performing real-time collision detection is to simplify a given shape. For this reason, we need to make a function that, given a set of points, will return a circle containing all the points. This simplified bounding circle can then be used to approximate a collision area:

Getting ready

In order to avoid adding a dependency to std::vector in Geometry2D.h, we will implement this new function using an array. The ContainingCircle function will take two arguments, one is a Point2D array, and the other deals with the number of elements in the array. The ContainingCircle function will return a bounding circle that encapsulates all of the points.

How to do it…

Follow these steps to implement a function that will build a bounding circle from a set of points:

1. Declare the ContainingCircle function in Geometry2D.h:

   Circle ContainingCircle(Point2D* pArray, int arrayCount);

2. Implement ContainingCircle in Geometry2D.cpp:

   Circle ContainingCircle(Point2D* pArray, int...

Containing rectangle

A containing rectangle is very similar to a containing circle. We will find the minimum non-oriented rectangle that contains a set of points. Depending on the shape being contained, a rectangle might be a tighter fit than a circle:

Getting ready

The ContainingRectangle function is going to be very similar to the ContainingCircle function. Just like ContainingCircle, this function will take an array of points, and a count of the number of points in the array. Given this set of input points, ContainingRectangle will return the minimum non-oriented rectangle that encompasses every point.

How to do it…

Follow these steps to create a function that will create a bounding rectangle from a set of points:

1. Declare the ContainingRectangle function in Geometry2D.h:

   Rectangle2D ContainingRectangle(Point2D* pointArray, 
      int arrayCount);

2. Implement the ContainingRectangle function in Geometry2D.cpp:

   Rectangle2D ContainingRectangle(Point2D* pointArray, 
      int arrayCount) {
      vec2 min =...

Simple and complex shapes

Sometimes a containing circle or a containing rectangle alone is not accurate enough for collision detection. When this happens we can use several simple shapes to approximate a complex shape:

Getting ready

We are going to create a new structure called BoundingShape. This new structure will hold an array of circles and an array of rectangles. It's assumed that the structure does not own the memory it is referencing. We can implement several primitive tests by looping through all the primitives that BoundingShape contains.

How to do it…

Follow these steps to create a class which represents a complex shape. A complex shape is made out of many simple shapes:

1. Declare the BoundingShape primitive in Geometry2D.h:

   typedef struct BoundingShape {
      int numCircles;
      Circle* circles;
      int numRectangles;
      Rectangle2D* rectangles;
   
      inline BoundingShape() :
         numCircles(0), circles(0),
         numRectangles(0), rectangles(0) { }
   };

2. Define a new PointInShape function in Geometry2D...

Quad tree

A quad tree recursively subdivides a game world into smaller and smaller sections. It's called a quad tree because each non-leaf node is divided into four smaller nodes. Usually, quad trees are dynamic, meaning they rearrange at runtime. Every node has a maximum number of children, if the number of objects in a node exceeds this, the node is split:

To build a quad tree we must start with a root node. This root node encompasses all of the objects in a given scene. If the root node contains more than some arbitrary number of game objects, it subdivides into four new leaf nodes. The same splitting process is recursively applied to each child. This leaves us with the edge case where some children are just too big. What happens if two objects happen to overlap at a point? No matter how far we subdivide, they will never separate:

To avoid this Infinite Subdivision, we can assign a maximum depth to the quad tree. But there are other edge cases to consider as well. What happens when an object...

Broad phase collisions

Simple video games might have hundreds or thousands of objects. More complicated games might even have millions. Testing collisions between all of these objects will quickly become computationally expensive. This is why we need broad phase collisions. Broad phase collisions are not accurate, they let us know if two objects are too far apart to touch.

For example, let us assume we have two rectangles. We could contain both rectangles in circles. If the resulting circles are not touching, there is no reason to check whether the rectangles are colliding or not. In this scenario we do not have to do complex intersection testing because we first test simple objects.

Getting ready

The QuadTree class that we have built is ideal for broad phase collision detection. It segments world space so that objects which are far apart don't need to be tested against each other. In this section, I'm going to demonstrate how the quad tree can be used in a real world situation using some pseudo...