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