Пространственное разбиение
Деление пространства на области, чтобы запрос просматривал только ближайшие объекты, а не все подряд.
Проверять каждый объект против каждого — это O(n²): для десяти объектов нормально, для десяти тысяч разорительно. Пространственное разбиение индексирует объекты по их положению, так что запрос столкновения или видимости затрагивает только ячейки рядом с интересующей точкой.
Структуры различаются способом разреза: равномерная сетка делит пространство на одинаковые ячейки, квадродерево и октодерево рекурсивно дробят его там, где объекты скапливаются, BSP-дерево режет произвольными плоскостями. Все они обменивают память и стоимость обновления на куда более дешёвые запросы и стоят за широкой фазой (broad phase) обнаружения столкновений и отсечением по пирамиде видимости.