Как пространственное разбиение ускоряет поиск соседей в игровом мире

В стратегии реального времени число попарных проверок растёт как квадрат числа юнитов. Пространственное разбиение хранит объекты с учётом координат, поэтому движок ищет соседей в нужной области, а не на всём поле.

Простейший вариант: наложить на поле фиксированную сетку и хранить в каждой ячейке связный список юнитов. Обработчик ближнего боя сравнивает только юнитов внутри ячейки. Когда юнит переходит в другую ячейку, структуру нужно обновить; это расходует процессорное время, а служебные данные занимают память.

Оптимизация оправдана при множестве объектов и частых запросах по координатам. При малом числе объектов расходы могут не окупиться. Код на C++ и разбор компромиссов собраны в главе Game Programming Patterns.