A-tit indd

Паттерны программирования игр
— Паттерны оптимизации
407
Пространственное 
разбиение 
(Spatial Partition)
«Позволяет эффективно находить/располагать 
объекты, храня их в структуре данных, организо-
ванной на основе их позиций».
Мотивация
Игры позволяют нам окунуться в другие миры, но обыч-
но эти самые миры не особо отличаются от нашего соб-
ственного. В них действуют те же самые законы физики, 
например. Вот почему они могут казаться реальными, 
хотя созданы из кучки битов и пикселей.
Часть фальшивой реальности, на которой мы оста-
новимся, —
положение
. У игровых миров есть чувство 
пространства
, и объекты находятся где-то в простран-
стве. Это декларируется множеством способов. Очевид-
ный — в физическом движке. Объекты движутся, стал-
киваются и взаимодействуют. Но есть и другие способы. 
Аудиодвижок может принимать во внимание, откуда 
относительно игрока исходит звук, и отдаленные звуки 
воспроизводить тише. Онлайн-чат может быть ограни-
чен только близко находящимися игроками.
Значит, игровому движку постоянно надо отвечать 
на вопрос: «Какие объекты находятся близко?» И если 
ответ на вопрос приходится искать достаточно много 
раз за кадр, то нагрузка на процессор может стать весь-
ма серьезной.
Глава 20

---

408
Пространственное разбиение (Spatial Partition) — 
Паттерны программирования игр
Боевые юниты на поле боя
Допустим, мы создаем стратегию реального времени. 
Противоборствующие армии с тысячами боевых юни-
тов столкнутся на поле боя. Воинам надо знать, на кого 
направить свои острые мечи. Самый тривиальный спо-
соб — рассмотреть каждую пару воинов в отдельности 
и проверить, насколько они близко друг к другу:
void handleMelee(Unit* units[], int numUnits)
{
for (int a = 0; a < numUnits -
1; a++)
{
for (int b = a + 1; b < numUnits; b++)
{
if (units[a]->position() ==
units[b]->position())
{
handleAttack(units[a], units[b]);
}
}
}
}
У нас получился весьма сомнительный вложенный 
цикл двух уровней, и в каждом мы проходим через всех 
воинов на поле боя. То есть количество попарных срав-
нений, которое нам надо выполнить, равняется 
квадра-
ту
изначального числа воинов. Каждый новый добав-
ленный воин также должен подвергнуться сравнению 
со 
всеми
уже существующими. И при большом количе-
стве боевых единиц это быстро выйдет из-под нашего 
контроля.