# Broad Phase Collision Detection Using Spatial Partitioning

12/27/12

Collision detection is an ongoing source of research and constant optimization in game development. It can be a source of exuberance or nearly infinite frustration. Rolling your own is typically the best way to make sure your game is never finished! However, knowing what an engine does internally to make your life easier is extremely beneficial to you as a developer. In addition to increasing your knowledge and understanding, it also helps you appreciate the hard work wrought by the giants whose shoulders you’re standing on.

This article focuses on two approaches to broad phase detection of collisions. The first is a brute force method that, while simple, quickly becomes wildly inefficient at typical game entity counts. The second is a form of spatial partitioning called a spatial grid. It is relatively simple, yet handles large numbers of game entities efficiently.

Collision detection is usually performed in two phases: broad phase and narrrow phase.

Broad phase detection is typically a computationally low cost operation that quickly answers the question, “Which objects have a strong possibility of colliding?” Approaches include Sweep and Prune, and Spatial Partitioning.

Narrow phase is the fine grained, “What part of object A colided with object B?” step. It is typically computationally intense, and thus cannot be performed on every pair of objects in the time between game updates (e.g. the next drawn frame). Examples of narrow phase techniques are the Hyperplane Separation Theorem (also known as the Separating Axis Theorem) 1, Pixel Perfect Collision Detection 2, and Swept Tests.

Collision Detection vs Collision Response

There are two phases when attempting to update a game world: detection of the collision, followed by the response, or the result of that collision (e.g. two balls bounce off of each other). This article will focus exclusively on the detection of a collision, not the response.

Our World and Demos

The same basic setup will be used for each example of collision detection. We have a global namespace, ro (which is also the name of the basic engine), which will contain the following components:

• ro.World: responsible for adding entities, stepping/updating, and tying everything together.
• ro.Entity: a single “thing” that will exist in our game. It has basic properties, like position, size, acceleration, and more.
• ro.Screen: responsible for providing a drawing context and drawing management. Simple boxes are all that will be needed to be drawn, but separating out drawing state from the state of the world itself is good practice.
• ro.math: some common math utilities, like line intersection.
• ro.ov3: vector operations for generic objects with x/y properties
• ro.coltech: Short for “collision technique”, this object will hold the constructors for our collision detection interface.

Each demo will be using squares, and this is by no accident; most engines use a concept known as an Axis-Aligned Bounding Box (AABB) to simplify and speed up broad phase detection. An AABB is a rectangular approximation for the position and amount of space an entity occupies, and can be used in both 2D and 3D. In this article’s 2D demos, an AABB will be defined by two points: a minimum and maximum. Together, these can be used to extrapolate the remaining two points, but this is usually not necessary. Axis-aligned implies that the sides of the box are parallel to the major axes of the coordinate system, which in the demos are positive X moving right across the screen, and positive Y moving down the screen.

JSFiddle will be used to sandbox the demos. This means that the following will be valid for each demo:

 Variable Path Instance Type Description bng Object A namespace for our demo instances bng.world ro.World Global reference to the world bng.world.screen ro.Screen Global reference to the screen (canvas and canvas 2D context) ov3 Object References ro.ov3, for vector operations

The world also uses the following order for each step of the simulation:

• Clear the screen
• Call World.draw
• Accelerate all entities, update their AABBs
• Call the collision system’s update method
• Call the collision system’s queryForCollisionPairs method
• Call the user-defined handleCollisions
• Apply inertia to all entities 3, update their AABBs
• Call the user-defined update

All demos can be stopped/paused and started by mouseover/mouseout.

Let’s get started!

Approach #1: Brute Force

In nearly any collision detection scheme, every object must be tested or touched by code at least once. The most simple form is called a brute force test, where every object is uniquely tested (no duplication of tests) for collision with every other object. For games with very few objects, this is more than likely the fastest and simplest method. However, the computational complexity of this method increases quadratically for every object you add:

• #### Web Development Newsletter Signup

Invalid email
You have successfuly registered to our newsletter.
•
•
• ## HTML5 ebook

HTML5 is the new standard that is expected to take over the Web. New versions of browsers are already starting to support the advanced features. Learn why HTML5 is important and discover how to use start using it today.