Brute Force vs Quad Tree: A Deep Dive into Collision Detection Algorithms

Introduction

When developing games, physics simulations, or any interactive application with moving objects, collision detection becomes a critical performance bottleneck. The question "are any of these objects touching?" seems simple, but as your object count grows from dozens to thousands, the naive approach quickly becomes a performance nightmare.

In this article, we'll explore two fundamental approaches to collision detection: the straightforward Brute Force method and the sophisticated Quad Tree algorithm. We'll dive deep into how each works, analyze their time and space complexity, and understand why one can handle 10,000 and more objects smoothly while the other struggles with just a few hundred.

The Collision Detection Challenge

Before diving into algorithms, let's understand the problem. Given N objects in 2D space, we need to determine which pairs are colliding. The brute force approach asks: "Should I check every object against every other object?" The quad tree approach asks: "How can I avoid checking objects that are nowhere near each other?"

This fundamental difference in thinking leads to dramatically different performance characteristics.

Brute Force Collision Detection

How It Works

The brute force approach is conceptually simple: compare every object with every other object exactly once.

class BruteForceCollisionDetector {
  detectCollisions(objects: GameObject[]): CollisionPair[] {
    const collisions: CollisionPair[] = [];

    for (let i = 0; i < objects.length; i++) {
      for (let j = i + 1; j < objects.length; j++) {
        if (this.checkCollision(objects[i], objects[j])) {
          collisions.push({
            objectA: objects[i],
            objectB: objects[j]
          });
        }
      }
    }

    return collisions;
  }

  private checkCollision(a: GameObject, b: GameObject): boolean {
    const dx = a.x - b.x;
    const dy = a.y - b.y;
    const distance = Math.sqrt(dx * dx + dy * dy);
    return distance < (a.radius + b.radius);
  }
}

Visual Understanding

Imagine 5 objects labeled A, B, C, D, E:

Comparisons made:
A vs [B, C, D, E] → 4 checks
B vs [C, D, E]    → 3 checks  
C vs [D, E]       → 2 checks
D vs [E]          → 1 check
Total: 10 checks for 5 objects

The pattern is clear: for N objects, we need N×(N-1)/2 collision checks.

Complete Implementation

class BruteForceCollisionSystem {
  private objects: GameObject[];
  private collisionCount: number = 0;

  constructor(objects: GameObject[]) {
    this.objects = objects;
  }

  update(): void {
    const startTime = performance.now();
    this.collisionCount = 0;

    for (let i = 0; i < this.objects.length; i++) {
      for (let j = i + 1; j < this.objects.length; j++) {
        this.collisionCount++;

        if (this.sphereCollision(this.objects[i], this.objects[j])) {
          this.handleCollision(this.objects[i], this.objects[j]);
        }
      }
    }

    const endTime = performance.now();
    console.log(`Brute Force: ${this.collisionCount} checks in ${endTime - startTime}ms`);
  }

  private sphereCollision(a: GameObject, b: GameObject): boolean {
    const dx = a.position.x - b.position.x;
    const dy = a.position.y - b.position.y;
    const distanceSquared = dx * dx + dy * dy;
    const radiusSum = a.radius + b.radius;
    return distanceSquared < radiusSum * radiusSum; // Avoid expensive sqrt
  }

  private handleCollision(a: GameObject, b: GameObject): void {
    // Simple collision response - reverse velocities
    const tempVelX = a.velocity.x;
    const tempVelY = a.velocity.y;

    a.velocity.x = b.velocity.x;
    a.velocity.y = b.velocity.y;
    b.velocity.x = tempVelX;
    b.velocity.y = tempVelY;
  }

  getCollisionCount(): number {
    return this.collisionCount;
  }
}

Time and Space Complexity Analysis

Time Complexity: O(n²)

• Outer loop runs n times

• Inner loop runs (n-1), (n-2), ..., 1 times

• Total iterations: n×(n-1)/2 = O(n²)

• Each collision check is O(1)

• Overall: O(n²)

Space Complexity: O(1)

• No additional data structures needed

• Only temporary variables for calculations

• Memory usage independent of input size

• Overall: O(1) auxiliary space

Performance Scaling

Let's see how brute force performs with different object counts:

ObjectsCollision ChecksExpected Time (60 FPS)1045< 0.001ms501,2250.02ms1004,9500.08ms500124,7502ms1,000499,5008ms5,00012,497,500200ms10,00049,995,000800ms

At 10,000 objects, brute force takes 800ms per frame - that's less than 2 FPS!

Quad Tree Collision Detection

What is a Quad Tree?

A quad tree is a hierarchical data structure that recursively subdivides 2D space into four quadrants. Each node represents a rectangular region and can contain objects or child nodes.

Quad Tree Structure

Root Node (entire world)
├── NW Quadrant
│   ├── NW.NW (further subdivided if needed)
│   ├── NW.NE
│   ├── NW.SW
│   └── NW.SE
├── NE Quadrant
├── SW Quadrant
└── SE Quadrant

Implementation: Boundary Class

First, we need to define boundaries for our quad tree regions. This class represents a rectangular region in 2D space:

import { createVector2D } from '../lib/physics';
import Vector from '../physics/vector';

/**
 * Represents a rectangular boundary in 2D space
 * Used to define regions in the quad tree structure
 */
export class Boundary {
  pos: Vector;      // Center position of the boundary
  width: number;    // Half-width of the boundary
  height: number;   // Half-height of the boundary

  /**
   * Creates a new boundary
   * @param x - Center X coordinate
   * @param y - Center Y coordinate  
   * @param w - Half-width (distance from center to edge)
   * @param h - Half-height (distance from center to edge)
   */
  constructor(x: number, y: number, w: number, h: number) {
    this.pos = createVector2D(x, y);
    this.width = w;
    this.height = h;
  }

  /**
   * Checks if a point is contained within this boundary
   * @param point - Vector representing the point to test
   * @returns true if point is inside the boundary
   */
  contains(point: Vector): boolean {
    return (
      point.x >= this.pos.x - this.width &&
      point.x <= this.pos.x + this.width &&
      point.y >= this.pos.y - this.height &&
      point.y <= this.pos.y + this.height
    );
  }

  /**
   * Checks if this boundary intersects with another boundary
   * Used for spatial queries to determine if we should search a region
   * @param range - Another boundary to test intersection with
   * @returns true if boundaries overlap
   */
  intersects(range: Boundary): boolean {
    return (
      range.pos.x - range.width < this.pos.x + this.width &&
      range.pos.x + range.width > this.pos.x - this.width &&
      range.pos.y + range.height > this.pos.y - this.height &&
      range.pos.y - range.height < this.pos.y + this.height
    );
  }
}

Implementation: Quad Tree Class

Now let's implement the quad tree using your actual code structure:

import { CavnasAPI } from '../canvas';
import { SphereCollider } from '../physics/spherecollider';

/**
 * QuadTree implementation for spatial partitioning in 2D space
 * Recursively subdivides space into four quadrants to optimize collision detection
 */
export class QTree {
  bound: Boundary;                    // The spatial boundary this node represents
  points: SphereCollider[];          // Objects contained in this node
  isSubdivided: boolean;             // Whether this node has been subdivided
  tr: QTree | undefined;             // Top-right child quadrant
  tl: QTree | undefined;             // Top-left child quadrant  
  br: QTree | undefined;             // Bottom-right child quadrant
  bl: QTree | undefined;             // Bottom-left child quadrant
  n: number;                         // Capacity - max objects before subdivision

  /**
   * Creates a new quad tree node
   * @param bound - The spatial boundary this node covers
   * @param cap - Maximum number of objects before subdivision (typically 4-8)
   */
  constructor(bound: Boundary, cap: number) {
    this.bound = bound;
    this.n = cap;
    this.tl = undefined;
    this.tr = undefined; 
    this.bl = undefined;
    this.br = undefined;
    this.isSubdivided = false;
    this.points = [];
  }

  /**
   * Subdivides this node into four child quadrants
   * Called when the node exceeds its capacity
   */
  subdivide(): void {
    const x = this.bound.pos.x;
    const y = this.bound.pos.y;
    const w = this.bound.width;
    const h = this.bound.height;

    // Create four child boundaries by dividing current boundary
    const ne = new Boundary(x + w / 2, y - h / 2, w / 2, h / 2); // Northeast
    const nw = new Boundary(x - w / 2, y - h / 2, w / 2, h / 2); // Northwest  
    const sw = new Boundary(x - w / 2, y + h / 2, w / 2, h / 2); // Southwest
    const se = new Boundary(x + w / 2, y + h / 2, w / 2, h / 2); // Southeast

    // Create child quad trees for each quadrant
    this.tr = new QTree(ne, this.n);
    this.tl = new QTree(nw, this.n);
    this.bl = new QTree(sw, this.n);
    this.br = new QTree(se, this.n);

    this.isSubdivided = true;
  }

  /**
   * Inserts a sphere collider into the appropriate position in the quad tree
   * @param point - The sphere collider to insert
   */
  insert(point: SphereCollider): void {
    // Check if the point is within this node's boundary
    if (!this.bound.contains(point.userData.pos)) {
      return; // Point is outside this boundary, can't insert here
    }

    // If we have space and haven't subdivided, store the point here
    if (this.points.length < this.n) {
      this.points.push(point);
    } else {
      // Node is at capacity, need to subdivide
      if (!this.isSubdivided) {
        this.subdivide();
      }

      // Try to insert into each child quadrant
      // Note: Only one will actually accept it based on position
      this.tl?.insert(point);
      this.tr?.insert(point);
      this.bl?.insert(point);
      this.br?.insert(point);
    }
  }

  /**
   * Draws the quad tree boundaries for visualization
   * Useful for debugging and understanding the spatial partitioning
   * @param cP - Canvas API for drawing
   */
  draw(cP: CavnasAPI): void {
    // Draw this node's boundary
    cP.rect(
      this.bound.pos.x,
      this.bound.pos.y,
      this.bound.width * 2,  // Full width (width is half-width)
      this.bound.height * 2, // Full height (height is half-height)
      {
        fill: 'rgba(0,0,0,0)',  // Transparent fill
        stroke: 'white',        // White border to show boundaries
      }
    );

    // Recursively draw child boundaries if subdivided
    if (this.isSubdivided) {
      this.bl?.draw(cP);
      this.br?.draw(cP);
      this.tl?.draw(cP);
      this.tr?.draw(cP);
    }
  }

  /**
   * Queries the quad tree for all objects within a given range
   * This is the key optimization - only returns objects in nearby regions
   * @param range - The boundary to search within
   * @param found - Array to collect found objects (passed by reference)
   */
  query(range: Boundary, found: SphereCollider[]): void {
    // Only search this node if the query range intersects with our boundary
    if (this.bound.intersects(range)) {
      // Check all points stored in this node
      for (let p of this.points) {
        if (range.contains(p.userData.pos)) {
          found.push(p);
        }
      }

      // If subdivided, recursively search child nodes
      if (this.isSubdivided) {
        this.tl?.query(range, found);
        this.tr?.query(range, found);
        this.bl?.query(range, found);
        this.br?.query(range, found);
      }
    }
  }
}

Implementation: Quad Tree Collision System

Now let's implement the collision system using your quad tree structure:

import { CavnasAPI } from '../canvas';
import { SphereCollider } from '../physics/spherecollider';
import { Boundary, QTree } from '../collisions/quadtree';

/**
 * Collision detection system using quad tree spatial partitioning
 * Dramatically reduces collision checks compared to brute force approach
 */
class QuadTreeCollisionSystem {
  private quadTree: QTree;
  private worldBounds: Boundary;
  private colliders: SphereCollider[];
  private collisionCount: number = 0;

  constructor(worldBounds: Boundary, colliders: SphereCollider[]) {
    this.worldBounds = worldBounds;
    this.colliders = colliders;
    this.quadTree = new QTree(worldBounds, 4); // Capacity of 4 objects per node
  }

  /**
   * Main update loop - rebuilds quad tree and detects collisions
   * Called every frame for dynamic objects
   */
  update(): void {
    const startTime = performance.now();
    this.collisionCount = 0;

    // Rebuild quad tree each frame (necessary for moving objects)
    // Note: For static objects, you could optimize by not rebuilding
    this.quadTree = new QTree(this.worldBounds, 4);

    // Insert all colliders into the fresh quad tree
    for (const collider of this.colliders) {
      this.quadTree.insert(collider);
    }

    // Perform collision detection using spatial queries
    this.detectCollisions();

    const endTime = performance.now();
    console.log(`Quad Tree: ${this.collisionCount} checks in ${(endTime - startTime).toFixed(2)}ms`);
  }

  /**
   * Detects collisions by querying nearby objects for each collider
   * This is where the O(n log n) complexity comes from
   */
  private detectCollisions(): void {
    for (const collider of this.colliders) {
      this.checkColliderAgainstNearby(collider);
    }
  }

  /**
   * Checks one collider against all nearby colliders using spatial query
   * @param collider - The collider to check
   */
  private checkColliderAgainstNearby(collider: SphereCollider): void {
    // Create a query range around the collider
    // Range size should be at least 2x the collider radius to catch all potential collisions
    const queryRange = new Boundary(
      collider.userData.pos.x,
      collider.userData.pos.y,
      collider.size, // Using collider size as the query radius
      collider.size
    );

    // Query the quad tree for nearby objects
    const nearbyColliders: SphereCollider[] = [];
    this.quadTree.query(queryRange, nearbyColliders);

    // Check collisions only with nearby objects
    for (const nearbyCollider of nearbyColliders) {
      if (nearbyCollider !== collider) { // Don't check against self
        this.collisionCount++;

        if (this.checkSphereCollision(collider, nearbyCollider)) {
          this.handleCollision(collider, nearbyCollider);
        }
      }
    }
  }

  /**
   * Checks if two sphere colliders are intersecting
   * @param a - First sphere collider
   * @param b - Second sphere collider
   * @returns true if spheres are colliding
   */
  private checkSphereCollision(a: SphereCollider, b: SphereCollider): boolean {
    const dx = a.userData.pos.x - b.userData.pos.x;
    const dy = a.userData.pos.y - b.userData.pos.y;
    const distanceSquared = dx * dx + dy * dy;
    const radiusSum = a.size + b.size;

    // Use squared distance to avoid expensive sqrt calculation
    return distanceSquared < (radiusSum * radiusSum);
  }

  /**
   * Handles collision between two objects
   * @param a - First colliding object
   * @param b - Second colliding object
   */
  private handleCollision(a: SphereCollider, b: SphereCollider): void {
    // Simple collision response - reverse velocities
    // In a real game, you might want more sophisticated physics
    const tempVelX = a.userData.vel.x;
    const tempVelY = a.userData.vel.y;

    a.userData.vel.x = b.userData.vel.x;
    a.userData.vel.y = b.userData.vel.y;
    b.userData.vel.x = tempVelX;
    b.userData.vel.y = tempVelY;
  }

  /**
   * Returns the number of collision checks performed in the last update
   * Useful for performance comparison with brute force
   */
  getCollisionCount(): number {
    return this.collisionCount;
  }

  /**
   * Returns the current quad tree for visualization or debugging
   */
  getQuadTree(): QTree {
    return this.quadTree;
  }

  /**
   * Draws the quad tree structure for debugging
   * @param canvas - Canvas API for drawing
   */
  drawQuadTree(canvas: CavnasAPI): void {
    this.quadTree.draw(canvas);
  }
}

How Quad Tree Collision Detection Works

1. Build Phase: Insert all objects into the quad tree

2. Query Phase: For each object, query the quad tree for nearby objects

3. Check Phase: Only check collisions between objects in the same spatial region

Visual Example

World divided into regions:
┌─────────┬─────────┐
│   NW    │   NE    │
│  [A]    │  [C,D]  │
├─────────┼─────────┤
│   SW    │   SE    │
│  [B]    │   [E]   │
└─────────┴─────────┘

Collision checks:
- A only checks against objects in NW region (none)
- B only checks against objects in SW region (none)  
- C checks against D (both in NE)
- D checks against C (both in NE)
- E only checks against objects in SE region (none)

Total: 2 collision checks instead of 10!

Time and Space Complexity Analysis

Time Complexity: O(n log n) average, O(n²) worst case

Insertion Phase:

• Each object insertion: O(log n) average (tree height)

• Total insertions: n objects

• Insertion total: O(n log n)

Query Phase:

• Each query: O(log n) average to traverse tree

• Objects returned per query: O(k) where k is objects in region

• Total queries: n objects

• Query total: O(n log n + nk)

Overall Time Complexity:

• Average case: O(n log n) when objects are well-distributed

• Worst case: O(n²) when all objects are in the same region

Space Complexity: O(n)

• Quad tree nodes: O(n) in worst case (one object per leaf)

• Object storage: Each object stored once

• Overall: O(n) auxiliary space

Performance Scaling Comparison

ObjectsBrute Force ChecksQuad Tree Checks (avg)Improvement1004,950~40012x faster1,000499,500~4,000125x faster5,00012,497,500~20,000625x faster10,00049,995,000~40,0001,250x faster

Detailed Complexity Comparison

Brute Force Analysis

Time Complexity Breakdown:

for i = 0 to n-1:           // n iterations
  for j = i+1 to n-1:       // (n-1) + (n-2) + ... + 1 = n(n-1)/2
    checkCollision(i, j)    // O(1) operation

Total: n × (n-1) / 2 = O(n²)

Space Complexity Breakdown:

• No additional data structures

• Only local variables

• Space: O(1)

Quad Tree Analysis

Time Complexity Breakdown:

Building Phase:

for each object:              // n iterations
  insert into quad tree       // O(log n) average, O(n) worst case

Average: O(n log n)
Worst: O(n²) when tree degenerates

Query Phase:

for each object:              // n iterations
  query nearby objects        // O(log n) tree traversal + O(k) objects returned
  check collisions            // O(k) collision checks

k = average objects per region
Average: O(n log n + nk) = O(n log n) when k is small
Worst: O(n²) when k approaches n

Space Complexity Breakdown:

• Tree nodes: Each subdivision creates 4 children

• Maximum depth: O(log n) for balanced tree

• Maximum nodes: O(n) when fully subdivided

• Space: O(n)

Practical Performance Considerations

When Quad Tree Performs Well

• Objects are spatially distributed

• World size is reasonable relative to object size

• Objects move at moderate speeds

• Object density varies across regions

When Quad Tree Struggles

• All objects clustered in one area (degrades to O(n²))

• Objects much larger than quad tree cells

• Very sparse object distribution

• Extremely fast-moving objects

Optimization Strategies

1. Dynamic Capacity Adjustment:

class AdaptiveQuadTree extends QuadTree {
  constructor(boundary: Boundary, totalObjects: number) {
    // Adjust capacity based on total object count
    const optimalCapacity = Math.max(4, Math.sqrt(totalObjects) / 4);
    super(boundary, Math.floor(optimalCapacity));
  }
}

2. Depth Limiting:

class DepthLimitedQuadTree extends QuadTree {
  private maxDepth: number;
  private currentDepth: number;

  constructor(boundary: Boundary, capacity: number, maxDepth: number = 8) {
    super(boundary, capacity);
    this.maxDepth = maxDepth;
    this.currentDepth = 0;
  }

  private subdivide(): void {
    if (this.currentDepth >= this.maxDepth) {
      return; // Don't subdivide further
    }
    // ... rest of subdivision logic
    this.currentDepth++;
  }
}

3. Hybrid Approach:

class HybridCollisionSystem {
  detectCollisions(objects: GameObject[]): void {
    if (objects.length < 100) {
      // Use brute force for small counts
      this.bruteForceDetection(objects);
    } else {
      // Use quad tree for large counts
      this.quadTreeDetection(objects);
    }
  }
}

Real-World Implementation Example

To demonstrate these collision detection algorithms in practice, I've developed an interactive simulation that showcases both brute force and quad tree approaches with real-time performance comparisons. The complete implementation is available as an open-source project with comprehensive documentation and configurable parameters.

Repository Access The full source code can be found at:
🔗 https://github.com/shoebilyas123/overshadowed/

Local Setup Instructions To run the simulation on your local development environment:

bash

pnpm install && pnpm dev

Configuration Options The simulation includes a customizable gameConfig file that allows you to experiment with various parameters including object count, world dimensions, collision detection methods, and performance visualization settings. These configurations enable you to observe firsthand how different scenarios impact the algorithmic performance characteristics discussed in this article.

Conclusion

The difference between brute force and quad tree collision detection is dramatic:

Brute Force Summary

• Time Complexity: O(n²) - always

• Space Complexity: O(1) - minimal memory

• Performance: Terrible with large object counts

• Use Case: Small numbers of objects (< 100)

Quad Tree Summary

• Time Complexity: O(n log n) average, O(n²) worst case

• Space Complexity: O(n) - additional memory for tree

• Performance: Excellent with spatial distribution

• Use Case: Large numbers of objects with spatial locality

Key Takeaways

1. Scale Matters: Brute force is fine for dozens of objects but catastrophic for thousands

2. Spatial Distribution Helps: Quad trees work best when objects are spread out

3. Memory vs Performance: Quad trees use more memory but provide massive performance gains

4. Algorithm Choice is Critical: The right algorithm can mean the difference between 1 FPS and 60 FPS

For any serious collision detection with more than a few hundred objects, quad trees (or similar spatial partitioning) aren't just an optimization - they're a necessity. The mathematical difference between O(n²) and O(n log n) becomes a practical difference between unusable and smooth performance.

Understanding these algorithms and their complexity helps you make informed decisions about collision detection in your projects, whether you're building a simple game or a complex physics simulation.

Tags

#CollisionDetection #GameDev #Algorithms #QuadTree #Performance #DataStructures #TimeComplexity