Collision detection with QuadTree in 2D games
A quick primer on using QuadTrees as a broad-phase spatial partitioning strategy to reduce collision checks in 2D games, with references for deeper dives and implementations.
Collision detection is an essential part in game development, whose computations often involves inefficient complexity. Many algorithms have been introduced for optimisation. One of the algorithms that I found simple to adopt is QuadTree.
Introduction
A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The data associated with a leaf cell varies by application, but the leaf cell represents a “unit of interesting spatial information”.