A-tit indd

420
Пространственное разбиение (Spatial Partition) — 
Паттерны программирования игр
Хотя есть и другой частный случай, который стоит рас-
смотреть. Выше мы предполагали, что максимальная даль-
ность атаки меньше размера ячейки. Но если у нас будут 
маленькие ячейки и большие радиусы поражения, то нам 
придется искать в нескольких рядах соседних ячеек.
Архитектурные решения
Существует довольно короткий список хорошо опреде-
ленных структур данных для пространственного раз-
биения. Можно было просто перечислить их, однако 
я попытался организовать их по важнейшим характери-
стикам. Я очень надеюсь, что, когда вы познакомитесь 
с деревом квадрантов (иначе квадродерево, quadtree) 
и бинарным разбиением пространства (binary space 
partitions — BSP), вы поймете, 
почему
и 
как
они рабо-
тают и почему стоит выбрать именно одно, а не другое.
Разделение иерархическое или плоское?
Наш пример с сеткой разделял пространство на единый 
плоский набор ячеек. Иерархическое разбиение, напро-
тив, делит пространство всего на пару областей. Если 
одна из областей все еще содержит слишком много объ-
ектов, она подразделяется еще. Процесс продолжается 
рекурсивно, пока в каждой области не останется объек-
тов меньше, чем определенный максимум.
 
• Если разбиение плоское
• Это прощ
е. С плоскими структурами проще рабо-
тать и проще реализовывать.
• Количество использованной памяти постоянно
. 
Так как добавление новых объектов не требует со-
здания новых частей, количество памяти, исполь-
зуемой в пространственном разбиении, фиксиро-
вано и определено заранее.
• Его проще обновлять, если объекты изменяют свою 
позицию
. Когда объект движется, структура данных 
должна обновляться, чтобы соответствовать его 
Обычно они разбива-
ются на два, четыре или 
восемь — прекрасные 
круглые числа для про-
граммиста.
Опять и снова повто-
рюсь: всегда выбирайте 
наболее простой вари-
ант. Большинство про-
граммистов сражаются 
с излишней сложно-
стью.

---