Collision detection for beginners (with code examples)

Inspiration

This resource is heavily inspired by Jeff Thompson’s Collision Detection. I have worked with it on my own projects for several years now, and it helped me implement my own collision detection: every 2D algorithm in this book has been used in Hallify, my venue booking platform.

Introduction

Collision detection answers one question: do two shapes share at least one point? A program can’t answer that by looking. To a program, a ball and a wall are just numbers. Analytic geometry is the part of maths that turns shapes into numbers and equations, so the question becomes arithmetic that takes a computer a handful of operations.

This is a small book. Each chapter builds on the one before it: coordinates first, then distances, then shapes as equations, and every idea ends in a collision test with a demo you can play with. Part I works in the plane (2D), and Part II takes the same ideas into space (3D).

If you’re only after the code, jump to all the functions of Part I.

Prerequisites

Basic understanding of any programming language of your choice. Every example comes in TypeScript, JavaScript and Python: pick one with the tabs above any code block, and the whole book switches with it. I explain the core concepts as well, so you’ll have no trouble rewriting the examples in any other language. You will need to know how functions work and some basic data types. If you understand the following example, you’re good to go!

function greet(name: string): string {
	return `Hello ${name}!`;
}

function greet(name) {
	return `Hello ${name}!`;
}

def greet(name: str) -> str:
    return f"Hello {name}!"

Time and space complexity

Every function in this book comes with its time and space complexity, in big-O notation. Time complexity says how the number of steps grows as the input grows, and space complexity how much extra memory a function needs on top of its input.

$O(1)$ means it doesn’t grow at all: comparing two circles takes the same handful of steps however big they are, or however far apart. The polygon chapters count vertices: with $n$ of them, $O(n)$ grows in step with $n$, and $O(n^2)$ with its square, so twice the vertices means four times the work.