A-tit indd

422
Пространственное разбиение (Spatial Partition) — 
Паттерны программирования игр
Они все помещались бы в одной ячейке, а наш код сно-
ва вернулся бы к сложности 
O(n
2
)
, от которой мы как раз 
пытаемся избавиться.
• Если разбиение не зависит от объектов
• Объекты могут добавляться постепенно
. Доба-
вить объект — значит найти подходящую ему часть 
и поместить его туда, так что вы можете это делать 
без потерь производительности.
• Объекты могут быть быстро перемещены
. При 
фиксированном разбиении перемещение юнита 
означает удаление его из одного списка и помеще-
ние в другой. Если границы разбиения меняются 
сами в зависимости от объектов, то перемещение 
объекта может спровоцировать движение границ, 
что в свою очередь иногда приводит к необходимо-
сти перемещать другие объекты в различные части.
• Разбиение может быть несбалансированным
. Ко-
нечно, недостаток такой жесткости в том, что вы 
теряете контроль над частями, которые в итоге по-
лучаются. Если объекты сконцентрированы вместе, 
вы получаете более низкую производительность 
и напрасно потраченную память на пустые области.
• Если разбиение адаптируется под набор объектов
Специальные разбиения типа двоичного разбиения 
пространства (BSP) или k-мерных деревьев разделя-
ют пространство рекурсивно, так что все части со-
держат примерно одинаковое количество объектов. 
От вас требуется посчитать, сколько объектов нахо-
дится с каждой стороны при выборе границы разбие-
ния. Иерархия ограничивающего объема — другой 
вид пространственного разбиения, который позволя-
ет оптимизировать разбиение в зависимости от спе-
цифики набора объектов мира.
• Вы можете быть уверены в сбалансированности ча-
стей
. Это дает не только хорошую, но и 
стабильную 
Это прямой аналог от-
сортированным бинар-
ным деревьям поиска 
вроде красно-черного 
дерева или АВЛ-дерева 
(AVL tree): когда вы до-
бавляете новый эле-
мент, в итоге может ока-
заться, что дерево надо 
заново отсортировать 
и перемешать кучу его 
узлов.

---