A-tit indd

424
Пространственное разбиение (Spatial Partition) — 
Паттерны программирования игр
Рис. 20.6.
Каждая ячейка, которая содержит 
более двух юнитов, рекурсивно разбивается
• Объекты могут добавляться постепенно
. Добав-
ление нового объекта означает поиск нужного 
квадрата и добавление в него. Если при этом ко-
личество элементов выходит за верхнюю границу, 
область разделяется. Все объекты в квадрате поме-
щаются в новые квадраты меньшего размера. Ко-
нечно, требуется приложить небольшие усилия, 
но их количество 
фиксировано
: количество объ-
ектов, которые надо переместить, всегда меньше, 
чем максимально разрешенное количество объек-
тов. Добавление нового элемента никогда не вызо-
вет более одного нового разделения.
Удаление объектов так же просто. Вы удаляете 
объект, и если общее количество элементов роди-
тельского квадрата меньше максимально допусти-
мого, то вы можете объединить его в один.
• Объекты могут перемещаться быстро
. Это непре-
менно следует из вышесказанного. «Перемещение» 
фактически является просто добавлением и удале-
нием, а оба действия можно выполнить достаточно 
быстро в квадродереве.
• Разбиение сбалансированно
. Поскольку любой ква-
драт будет содержать меньшее количество объек-
тов, чем какой-то определенный максимум, даже 
когда объекты сосредоточены в одном месте, у вас 
не будет ни единой области с огромным количе-
ством элементов в ней.

---

Паттерны программирования игр
— Паттерны оптимизации
425
 Хранятся ли объекты только в областях разбиения?
Вы можете рассматривать пространственное разбиение 
как место обитания объектов вашей игры, ну или про-
сто в качестве второго кэша, где вы можете быстро их 
находить и при этом иметь другой набор, в котором они 
просто перечислены.