BSP-дерево и индексация объектов игрового уровня

Кубическое BSP-дерево в Unity

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

За примерами далеко ходить не надо — в бесплатной версии Unity нету встроенного механизма Occlusion Culling (автоматического отсечения перекрытых объектов). Если вы создаете город, и камера смотрит на какой-либо квартал, то рендерится будут не только ближайшие дома, но и дома, расположенные за ними, даже если они полностью закрыты близлежащими строениями. Владельцам Unity Pro беспокоиться на этот счет не стоит, но не у каждого есть лишняя пара тысяч долларов на лицензию. Использование же BSP-дерева позволит самостоятельно реализовать механизм Occlusion Culling и сэкономить немалые деньги :)

Но, как я уже писал ранее, применение BSP-дерева не ограничивается реализацией алгоритма Occlusion Culling и быстрым поиском столкновений между объектами. В частности, без индексации игрового пространства невозможна программная генерация уровней. Да и вообще, трудно блуждать в потемках без карты :)


( Читать дальше )

Поиск в BSP-дереве: поиск соседей

BSP-ячейка с соседямиВ последнее время очень часто ловлю себя на мысли: «А ведь я это уже когда-то делал!» Начинаешь рыться в исходниках предыдущих проектов, но тщетно! Напишу-ко я сюда :)

Продолжая тему применения BSP-деревьев, хочу рассказать немного о поиске пути в BSP-дереве. В том виде, в котором оно сейчас (каждый элемент содержит массив вложенных элементов), его применение для поиска путей является трудоемким: для каждой следующей точки при построении варианта пути придется делать новый поиск от самого корня дерева, чтобы проверить, есть ли рядом точка.

Поиск соседей в BSP-дереве
Гораздо оптимальнее было бы хранить для каждой точки ссылки на своих соседей. Тогда нам не придется каждый раз для соседней точки начинать поиск сначала. Но что делать с объемом выделяемой памяти? Неужели придется для каждого соседа отводить по целому 32-х разрядному числу? Если учесть, что у каждой ячейки в пространстве может быть 26 соседей, то размер дерева вырастет на ужасающую величину!

Нет! Мы так делать не будем, потому что нам поможет справиться с задачей бинарная упаковка. Далее немного исходников на ActionScript 3. Да, я занимаюсь прототипированием работы BSP-дерева на Flash-е :) Очень, кстати, удобно и наглядно получается.


( Читать дальше )