Равномерная сетка
Пространственное разбиение: пространство делят на одинаковые ячейки и раскладывают по ним объекты, так что проверки столкновений идут только с соседями по ячейке.
Каждый объект помещается в ячейку или ячейки, которые он перекрывает, и запросу о столкновении или соседях достаточно заглянуть в свою ячейку и смежные, а не во всю сцену. Когда объекты схожи по размеру и распределены равномерно, и вставка, и поиск в среднем занимают O(1), структура дружелюбна к кэшу и легко распараллеливается — поэтому она частый broad phase в 2D-физике и в boids.
Слабое место — «чайник в стадионе»: мало объектов или сильно различающиеся размеры либо тратят ячейки впустую, либо переполняют их. Тогда лучше справляются пространственное хеширование, иерархические сетки или адаптивные деревья вроде квадродеревьев и октодеревьев.