A-tit indd

Паттерны программирования игр
— Паттерны оптимизации
423
производительность: если в каждой области нахо-
дится одинаковое количество объектов, вы можете 
не сомневаться, что все запросы будут обрабаты-
ваться одинаковое количество времени. Если вам 
нужно поддерживать постоянную скорость смены 
кадров, стабильность может стать важнее, чем про-
изводительность.
• Выгоднее разбивать весь набор объектов за раз
. 
Если набор объектов влияет на то, где расположе-
ны границы, то намного лучше иметь полную кар-
тину набора до его разбиения. Вот почему такой 
тип разбиения чаще используется для статической 
геометрии, которая остается постоянной на протя-
жении игры.
• Если разбиение не зависит от объектов, а 
иерар-
хия
 зависит
Одно пространственное разбиение заслуживает осо-
бого внимания, поскольку включает в себя все луч-
шее от обоих, фиксированного и адаптируемого, раз-
биений: деревья квадрантов. Квадродерево начинает 
с того, что воспринимает все пространство как еди-
ную область. Если количество объектов в области 
превосходит определенное значение, оно разбива-
ется на четыре более мелкие области. 
Границы
обла-
стей фиксированы: они всегда разделяют простран-
ство ровно пополам.
Затем для каждой из четырех областей мы проде-
лываем то же самое, рекурсивно, пока в каждом ква-
драте не останется небольшое количество объектов. 
Так как мы рекурсивно разбиваем только квадраты, 
в которых много объектов, данное разбиение адап-
тируется к набору объектов, но области не 
сдвига-
ются
.
Вы можете увидеть разбиение в действии на сле-
дующем рисунке, слева направо (рис. 20.6).
Квадродерево разби-
вает двухмерное 
пространство. Его трех-
мерный аналог — 
окта-
дерево
, оно берет объ-
емное пространство 
и разбивает его на 
кубы
. 
Если не принимать 
во внимание дополни-
тельное измерение, оно 
работает точно так же, 
как и его плоский род-
ственник.

---