Collision detection systems show up in all sorts of video games and simulations. But how do you actually build these systems? Turns out that the key ideas behind these systems show up all over a field of computer science called computer graphics.

We start off with the basics of animation and then branch off into ideas in discrete and continuous collision detection. We break them down in the context of some simple simulations of a small number of particles, but scaling up these simulations is another challenge entirely. We present big ideas in broad phase optimization schemes for speeding up collision detection including the sweep and prune algorithm, uniform grids, K-D trees, and bounding volume hierarchies.

0:00 Introduction
1:25 Intro to Animation
2:46 Discrete Collision Detection and Response
5:50 Implementation
6:50 Discrete Collision Detection Limitations
8:10 Continuous Collision Detection
11:42 Two Particle Simulations
13:13 Scaling Up Simulations
15:42 Sweep and Prune Algorithm
19:05 Uniform Grid Space Partitioning
20:43 KD Trees
23:51 Bounding Volume Hierarchies
27:12 Recap

Correction: At 9:02, the linear interpolation equations should be x(t) = t * x(1) + (1 - t) * x(0) and y(t) = t * y(1) + (1 - t) * y(0). All subsequent derivations have the x(0) switched with x(1). All y(0) should also be switched with y(1) for the same reason.

Post-correction 2: I ran the experiment with the naive solution of checking every pair of particles with an added inefficiency in rendering the animations so the comparison wasn't fair and that's why the number was so high. The actual speed up is still fairly significant, but not THAT significant.

Minor correction: p.vel is updated and used in the next line at 6:28, p.vel and p.pos should be updated simultaneously

This video is supported by a community of Patreons
Special Thanks to the following Patreons:
Burt Humburg
Justin Hiester
Michael Nawenstein
Richard Wells
Zac Landis

Support:   / reducible  
Twitter:   / reducible20  

This video wouldn't be possible without the open source library manim created by 3blue1brown: https://github.com/3b1b/manim

Here is link to the repository that contains the code used to generate the animations in this video: https://github.com/nipunramk/Reducible

2D Collision Response Vector Equation Derivation Walkthrough: https://www.vobarian.com/collisions/2...

Bounding Volume Hierarchy Traversal Algorithm for Broad Phase: https://thegeneralsolution.wordpress....

The ideas and presentation in this video were inspired by a culmination of resources -- here are some that I found particularly nice for further exploration:
https://www.toptal.com/game/video-gam...
Game Physics Engine Development by Ian Millington Ch. 12
https://github.com/mattleibow/jitterp...
http://www.mcihanozer.com/tips/comput...