This describes a 2D broad-phase collision detection algorithm that runs in O(n) time where n is the number of entities. It easily extends to 3D. It holds no state except entity bounding box calculated during the previous frame in order to prevent phasing. The algorithm performs 4 steps every frame: Rectangle Creation, Rectangle Sorting, Chunk Creation, and Collision Detection.
- point = a point in 2D space
- path = an open set of linearly connected points
- polygon = a closed set of linearly connected points
- entity = a point or path or polygon
- space = the 2D space formed by two spatial dimensions
- spacetime = the 3D space formed by two spatial dimensions and a time dimension