Collision detection is an essential part in game development, whose computions often involves inefficient complexity. Many algorithms have been introduced for optimisation. One of the algorithms that I found simple to adopt is QuadTree.


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”.