До сих пор мы говорили о передвижении игрока, взаимодействующего с некими плоскостями (горизонтальными, вертикальными, наклонными). Чтобы продвинуться дальше, нам нужно рассмотреть суть этого взаимодействия, причём как со стороны карты, так и со стороны игрового движка. В этой статье мы обсудим основные понятия, касающиеся устройства карты. При создании тестовых карт я буду использовать только самые базовые функции редактора карт J.A.C.K., так что пользователи Valve Hammer Editor разницы почти не заметят.



При создании карты маппер с помощью инструмента Block Creation Tool последовательно добавляет блоки-параллелепипеды, которые при необходимости обрезает, растягивает и симметрично отражает. При этом какие бы комбинации этих преобразований не применялись, блок остаётся выпуклым многогранником. Для него в маппинге существует специальный термин браш (англ. brush). За счёт увеличения числа граней мапперы могут создавать из набора брашей формы, которые для игрока выглядят как цилиндрические или шарообразные, но на самом деле всё ещё являются многогранниками.

Вместе браши образуют собой модель (англ. model). Геометрию модели можно задать с помощью ограничивающих её плоскостей. Эти плоскости можно упорядочить в единую структуру в виде двоичного (бинарного) дерева. Именно это дереро и является основой *.bsp файла карты. Собственно, само расширение bsp означает binary space partitioning, то есть двоичное разбиение пространства. Давайте посмотрим, что из себя представляет это самое дерево на примере простейшей тестовой карты.

Редактор J.A.C.K., в котором я создал новую карту, по умолчанию помещает нас внутри пустой комнаты, сложенной из шести блоков-параллелепипедов. Возле одной из стен я разместил ещё один блок и скомпилировал карту, назвав её hull_1model:


Файл карты hull_1model.bsp состоит из секций (англ. lump), каждая из которых содержит информацию определённого вида (формат всех секций можно посмотреть здесь). Я извлёк из файла только интересующие нас секции и записал их в удобоваримом виде в файл hull_1model.txt (все файлы по карте можно скачать здесь). Из секции LUMP_MODELS мы можем понять, что все браши карты объединены в одну модель, для которой указаны крайние точки fMins и fMaxs, ограничивающие нашу комнату:

Model #0: fMins -288.000000 -288.000000 -32.000000 fMaxs 288.000000 288.000000 192.000000 iHeadnodes 0 0 10 20

Также здесь указаны индексы iHeadnodes, первый из которых задаёт начало (верхушку) двоичного дерева. Этой верхушкой является узел (англ. node) #0 в секции LUMP_NODES:

Node #0: plane 0 childnodes 1 -1
Node #1: plane 1 childnodes -1 2
Node #2: plane 2 childnodes 3 -1
Node #3: plane 3 childnodes -1 4
Node #4: plane 4 childnodes 5 6
Node #5: plane 5 childnodes -1 -2
Node #6: plane 6 childnodes 7 -1
Node #7: plane 7 childnodes -3 8
Node #8: plane 8 childnodes -4 9
Node #9: plane 9 childnodes 10 -6
Node #10: plane 10 childnodes -1 -5

Секция содержит всего 11 узлов-плоскостей: пол, потолок и 4 стены комнаты, а также 5 плоскостей, ограничивающих блок возле стены (компилятор карты не стал включать плоскости снаружи комнаты, поскольку их мы не увидим). Узлу Node #0 соответствует плоскость Plane #0, которую мы находим в LUMP_PLANES:

Plane #0: flNormal 0.000000 0.000000 1.000000 flDist 0.000000

Плоскость задаётся уравнением flNormal[0] * x + flNormal[1] * y + flNormal[2] * z = flDist. В нашем случае нормаль flNormal направлена вверх по оси +Z и имеет нулевое смещение по Z. Другими словами, это плоскость пола комнаты. В соответствии с принципом bsp пространство мысленно делится на то, что находится под этой плоскостью (отрицательное направление нормали), и то, что находится над ней (положительное направление нормали). Далее для правого дочернего узла нужно выбрать одну из плоскостей под полом, а для левого одну из плоскостей над ним. Поскольку других плоскостей под полом нет, в правый дочерний узел дерева записывается отрицательный индекс, и далее эта ветвь не развивается. В качества левого узла Node #1 компилятор выбрал плоскость Plane #1:

Plane #1: flNormal 0.000000 0.000000 1.000000 flDist 160.000000

Это плоскость потолка, причём нормаль также направлена в +Z, так что на этот раз уже левый дочерний узел стал отрицательным, а в качестве правого узла Node #2 выбрана плоскость Plane #2. Остальная часть дерева строится аналогично. При этом на узле Node #4 мы попадаем в ситуацию, когда по обе стороны его плоскости есть другая плоскость, а на узле Node #5 наоборот, по обе стороны ничего нет. Получившееся дерево выглядит следующим образом:


Отрицательные индексы дочерних узлов на самом деле тоже несут в себе полезную информацию. Если взять побитовую инверсию такого индекса, то получится индекс элемента из секции LUMP_LEAVES. К примеру, для узла Node #5 инверсия дочерних узлов -1 и -2 даст 0 и 1 соответственно. Ищем Leaf #0 и Leaf #1 в LUMP_LEAVES:

Leaf #0: iContents -2
Leaf #1: iContents -1
Leaf #2: iContents -1
Leaf #3: iContents -1
Leaf #4: iContents -1
Leaf #5: iContents -1

На странице с описанием формата (или прямо в исходниках компилятора) находим:

#define CONTENTS_EMPTY -1
#define CONTENTS_SOLID -2
#define CONTENTS_WATER -3
#define CONTENTS_SLIME -4
#define CONTENTS_LAVA -5
#define CONTENTS_SKY -6
#define CONTENTS_ORIGIN -7

Получаем, что левый дочерний узел соответствует CONTENTS_SOLID, то есть там находится твёрдая стена, с коротой игрок будет взаимодействовать, а правый узел соответствует CONTENTS_EMPTY, то есть в другой половине пространства (внутри комнаты) ничего нет, там игрок перемещается свободно.



Ещё одним важным понятием в маппинге является entity (в переводе с англ. "сущность"). Концептуально это объект, обладающий некоторыми свойствами. Если мы найдём в hull_1model.txt секцию LUMP_ENTITIES, то увидим там три entity разных классов: worldspawn содержит название комплилятора и свойства, являющиеся общими для всей карты; info_player_start и light - это так называемые точечные entity, задающие место респавна игрока и расположение источника освещения с помощью свойства "origin". В редакторе карт worldspawn явно не видно, но в bsp эта entity присутствует всегда. Две другие entity J.A.C.K. мне добавил сам в момент создания проекта с картой.

Entity бывают не только точечные, но и брашевые, то есть состоящие из одного или нескольких брашей. Создам ещё одну тестовую карту hull_2models, которая будет отличаться от первой карты только тем, что блок возле стены я превращу в entity класса func_wall (скачать файлы карты можно здесь). C виду карта выглядит точно так же, однако если открыть hull_2models.txt, в который я выгрузил информацию о секциях, то мы сразу же заметим, что моделей стало две:

Model #0: fMins -288.000000 -288.000000 -32.000000 fMaxs 288.000000 288.000000 192.000000 iHeadnodes 0 0 6 12
Model #1: fMins 80.000000 -64.000000 0.000000 fMaxs 240.000000 64.000000 48.000000 iHeadnodes 6 18 24 30

В то же время в секции LUMP_ENTITIES появилась ещё одна entity func_wall, в одном из полей которой указано "model" "*1", то есть компилятор при обработке брашевой entity выделил относящийся к ней браш в отдельную модель Model #1, дабы было понятно, к чему именно должны применяться свойства func_wall. Поскольку блок возле стены стал самостоятельным объектом, он теперь задаётся не 5 плоскостями, а всеми 6, так что узлов в секции LUMP_NODES стало на один больше. Верхушкой двоичного дерева для Model #0 по-прежнему является Node #0, а для Model #1 первый индекс iHeadnodes указывает нам на Node #6:


Таким образом, каждая новая entity будет являться с точки зрения компилятора отдельной независимой моделью со своим двоичным деревом.



Двоичное дерево из секции LUMP_NODES описывает геометрию карты, однако для передвижения игрока не используется. У iHeadnodes помимо первого индекса есть ещё три, каждый из которых указывает на начало своего двоичного дерева в секции LUMP_CLIPNODES (будем называть их clip-деревьями, а дерево из LUMP_NODES основным деревом). Эти clip-деревья получаются из основного сдвигом всех образующих плоскостей в сторону пустоты на половину размеров модельки. Например, для стоящего игрока стены сдвинутся внутрь комнаты на 16 юнитов, потолок опустится на 36, а пол поднимется на 36 юнитов. Блок возле стены соответственно станет больше, зазор между ним и стеной фактически пропадёт. Зачем же нужна такая тесная комната?

Когда мы говорили о перемещении игрока в предыдущих статьях, мы представляли его себе как оболочку (англ. hull) в виде параллелепипеда высотой 72 (в приседе 36) и шириной в 32 юнита по каждой оси, который независимо от направления взгляда всегда сохранял свою ориентацию. На самом деле эта "неповоротливость" оболочки связана с тем, что для движка CS игрок на самом деле представляет собой точку, которая перемещается между плоскостями, отстоящими от брашей на половину размеров параллелепипеда.

Из трёх clip-деревьев секции LUMP_CLIPNODES первое нужно для стоячей модельки игрока, второе для некоего объекта размерами 64x64x64 (нас оно интересовать не будет), а третье для сидячей модельки игрока. Узлы таких деревьев мы будем называть clip-нодами (англ. clipnode). Вообще говоря, количество clip-нодов в этих деревьях может отличаться от количества узлов в основном дереве. Например, если покрыть часть брашей карты текстурой CLIP, сделав их так называемыми clip-брашами, их плоскости не будут участвовать в формировании основного дерева, и потому основное дерево будет иметь меньше узлов, а в игре эти браши окажутся невидимыми. При этом на clip-ноды это не повлияет, и передвижению игрока невидимые браши будут препятствовать точно так же, как и видимые (кстати говоря, знакомый всем noclip по сути переводит игрока в режим, в коротом clip-ноды игнорируются). Другим отличием clip-нодов является наличие всего двух отрицательных значений индексов: -1 указывает на пространство снаружи блока и -2 указывает на его внутренности. Для обработки движения игрока этого достаточно.



Напоследок посмотрим на список всех секций *.bsp файла, дабы получить более цельную картину:

LUMP_ENTITIES - список entity и их свойств
LUMP_MODELS - модели (брашевые entity ссылаются на модели с помощью ключа "model")
LUMP_NODES - узлы основного двоичного дерева, соответствующие плоскостям брашей
LUMP_LEAVES - узлы основного двоичного дерева, описывающие содержимое пространства и соответствующие граням брашей
LUMP_CLIPNODES - clip-ноды двоичных деревьев для обработки столкновений
LUMP_PLANES - плоскости брашей
LUMP_FACES - грани брашей
LUMP_EDGES - рёбра брашей (стороны граней), заданные двумя вершинами
LUMP_VERTICES - вершины брашей
LUMP_SURFEDGES - индексы рёбер, с помощью которых рёбра ставятся в соответствие граням, их содержащим
LUMP_MARKSURFACES - индексы граней, с помощью которых грани ставятся в соответствие узлам из LUMP_LEAVES
LUMP_TEXTURES - текстуры
LUMP_TEXINFO - координаты и индексы текстур, с помощью которых текстуры ставятся в соответствие граням
LUMP_LIGHTING - данные об освещении карты
LUMP_VISIBILITY - данные, позволяющие исключать из рендера области, заведомо не попадающие в поле зрения игрока

Все секции находятся в тесной связи между собой и ссылаются друг на друга (за исключением, разве что, visibility):



Мы продолжим рассматривать особенности компиляторов карт и то, как игровой движок работает с clip-нодами, в следующих статьях.