A-tit indd

эффективный поиск объектов в опре-
деленном месте или рядом с ним
. Когда позиция объ-
екта меняется, 
обновите пространственную структу-
ру данных
так, чтобы она могла продолжить выполнять 
свои функции.
Когда использовать
Это распространенный паттерн для хранения как живых 
движущихся объектов, так и для статичных декораций 
и геометрии мира. Сложные игры обычно используют 
несколько пространственных разбиений для различных 
видов содержимого.
Двоичный поиск имеет 
сложность 
O(
log
 n)
, 
означающую, что слож-
ность поиска юнита 
снижается с 
O(n
2
)
до 
O(n
log
 n)
. Примене-
ние 
голубиной сорти-
ровки (pigeonhole sort
, он 
же
 поиск со списком)
по-
зволило бы снизить 
сложность до 
O(n)
.

---

410
Пространственное разбиение (Spatial Partition) — 
Паттерны программирования игр
Базовые требования для использования паттерна —
наличие набора объектов с определенной позицией 
и достаточное количество запросов о местоположении, 
влияющее на производительность.
Имейте в виду
Пространственное разбиение существует для того, что-
бы снизить сложность операций 
O(n)
или 
O(n
2
)
. Чем 
больше
у вас объектов, тем ценнее становится данный 
паттерн. И наоборот, если 
n
достаточно мало, то его 
применение не стоит затраченных усилий.
Поскольку данный паттерн подразумевает организа-
цию объектов в соответствии с позицией, объекты, 
ме-
няющие
свою позицию, сложнее обрабатывать. Вам при-
дется заново организовывать структуру данных, чтобы 
отследить изменение положения объекта, а это добавля-
ет сложности 
и
расходует такты процессора. Убедитесь 
в оправданности затрат.
Пространственное разбиение использует дополни-
тельную память для хранения структуры данных. Как 
и многие другие паттерны оптимизации, данный ме-
няет память на скорость. Если в памяти вы ограничены 
больше, чем в частоте процессора, то можете даже про-
играть.
Пример кода
Суть паттернов в том, что они могут 
изменяться
: каждая 
реализация будет немного отличаться от других, и про-
странственное разбиение не исключение. Хотя в отли-
чие от других паттернов вариации данного хорошо задо-
кументированы. Академики любят публиковать статьи, 
доказывающие прирост производительности. Так как 
меня волнует только сама идея паттерна, я покажу вам 
простейшее пространственное разбиение: 
фиксирован-
ная сетка
.
Представьте хеш-
таблицу, где ключи хе-
шированных объектов 
могут изменяться не-
предсказуемо, и вы 
сразу почувствуете всю 
боль ситуации.
В последней части этой 
главы приведены другие 
наиболее распростра-
ненные в играх примеры 
пространственного 
разбиения.

---