HLFX.Ru Forum (https://hlfx.ru/forum/index.php)
- Volatile Engine (https://hlfx.ru/forum/forumdisplay.php?forumid=3)
-- Area Awareness System (https://hlfx.ru/forum/showthread.php?threadid=5275)

Area Awareness System

Я решил создать эту тему по нескольким причинам. Во-первых, мне давно интересна эта сложная тема, и я решил всё как следует систематизировать в своей голове, а нет лучшего способа систематизировать, чем проговорить вслух и записать. Во-вторых, знание это, на мой взгляд, довольно ценное, и им стоит поделиться с народом, к тому же мне не попадалось хороших статей по этой теме на русском языке. Ну и в-третьих, вы лучше узнаете движок Volatile и в дальнейшем, возможно, когда (если?) он будет выпущен как отдельный продукт, вероятно, захотите им воспользоваться. В общем, это будет что-то вроде цикла статей по устройству Area Awareness System (AAS), системы навигации, впервые представленной в Quake III, и в дальнейшем широко использовавшейся в продуктах id (как в мультиплеере для ботов, так и в сингле для монстров, например, в RTCW). Пост будет постепенно обновляться, хотя вероятно, не слишком часто, т.к. с ботами я разбираюсь в свободное от остальных задач Volatile/Perilous Warp время, ибо мультиплеер в первоначальном релизе не планируется.

Если кому-то тема покажется интересной - поставьте ей, пожалуйста, пять звёзд (в правом нижнем углу страницы). Так мне будет проще понять размер аудитории, ведь не все любят писать комментарии. Но вообще, комментарии, замечания и предложения приветствуются!


Введение

Каждый, кто хотя бы немного рисовал уровни для Quake III, помнит, что расставлять вейпоинты (waypoints) на них не нужно, но при этом боты довольно бодро бегают по оригинальным уровням, пользуются прыгалками, лифтами и телепортами, и на удивление склонны проникать в труднодоступные места за красной бронёй или рейлганом. При этом рано или поздно начинающий левел-дизайнер сталкивается с тем, что на его карте боты бегать отказываются наотрез. Так он впервые знакомится с магическими файликами с расширением "aas", и с системой AAS в целом. Ну как - знакомится? Он узнаёт, что это файлы навигации для ботов, что их нужно компилировать специальной программой, и что при компиляции тоже может вылезти "LEAK LEAK LEAK". Давайте попробуем разобраться, что это за зверь такой - AAS, и чем он отличается от классических вейпоинтов.

Немного о вейпоинтах

Как мы понимаем, у ботов нет глаз, и оценить старания левел-дизайнера они не могут. Если их поместить на уровень, они будут тыкаться, как слепые котята, во все стены, и в целом будут оживляться лишь когда игрок попадёт в их угол обзора (тут всё просто - атака на поражение). Для борьбы с этим фатальным недостатком были придуманы специальные штуки - вейпоинты. Расставляя их на уровне, мы вообще говоря расставляем вершины графа, а рёбра его просчитываются автоматически следующим образом. Если от вейпоинта А бот может пройти к вейпоинту Б, что создаётся ребро, если же не может - то не создаётся. Разумеется, этот граф должен учитывать различные хуллы игрока (как минимум стоящего и присевшего). Тогда мы можем легко рассчитать путь для бота на игровом уровне из одной точки в другую: нужно взять два ближайших к ним вейпоинта и найти в графе путь между ними, не обязательно прямой. Зная, что путь осуществим, бот может начать свой нелёгкий путь по этим вейпоинтам, и в конце концов, при удачном стечении обстоятельств и временах года, доберётся до своей цели. Подобный способ навигации используется не только для ботов в HL/CS, но и для монстров в сингле халфы. Да, это тот самый Node Graph, а вейпоинты - это энтити info_node.

У такого подхода есть как минимум две сложности. Во-первых, наш мир изменчив: там где раньше торговали морковкой с шести соток, возвели высоток с парковками для шестисотых. Иными словами, однажды посчитанный путь может стать непроходимым, если туда, скажем, приедет func_train. Для борьбы с этой проблемой можно периодически перепроверять путь впереди себя, и в случае возникновения сложностей пометить его как временно непроходимый и найти другой. К тому же бот, в отличие от игрока, имеет прямой доступ к свойствам энтитей, и может легко разобраться, как быстро поезд оттуда уедет (и подождать), или же он, подобно крейсеру Аврора, встал там на вечную стоянку. Вторая сложность - это то, что качество графа напрямую зависит от удачной расстановки вейпоинтов. Если доверить эту работу мапперу - всё будет прекрасно, но потребует большого количества времени, и как минимум понимания общих принципов навигации ботов. Если же делать это автоматически - то неизбежны ошибки, и как следствие, проблемы навигации в отдельных зонах уровня. В Node Graph проблема решается первым способом - ноды расставляет левел-дизайнер. К чему это привело, мы с вами знаем - интернет переполнен фантазиями на тему, как правильно расставлять info_node, но монстры по-прежнему застревают за поворотом и скорбно провожают взглядом счастливчика-игрока, который к нодам не привязан и может идти, куда хочет. Боты обычно используют подход с автоматической расстановкой нодов. Например, у популярного CS-бота PoD-bot есть специальный режим, включая который, вейпоинты будут автоматически появляться там, где находится игрок, через заданные интервалы. Игрок бегает по карте в обычном режиме, забирается во всякие места, и в итоге через какое-то время у нас есть файл навигации. Разработчик Parabot пошёл дальше. Он справедливо рассудил, что "считать должен компьютер", и доверил расстановку вейпоинтов самим ботам. Да, поначалу они тычутся во все стены, но тем не менее, бегая вдоль стенок, им удаётся перемещаться между зонами, и они тут же сохраняют новоприобретённое Знание в виде нодов. Такая автоматическая расстановка требует чуть больше времени, т.к. ботам нужно значительно больше времени на случайные поиски, в то время как игрок бегает по карте целенаправленно, но тем не менее она вполне работоспособна.

А есть ли альтернативы?

Но, как говорила дочь офицера, не всё так однозначно. Есть ещё одна сложность, о которой разработчики навигации для монстров и ботов вспоминать не любят. Дело в том, что невозможность пройти от нода А к ноду Б ещё не означает, что у игрока нет возможности туда попасть. Например, можно прыгнуть, или сделать longjump, а то и вообще рокетджамп (в халфе - гаусс-джамп). А в опфоре ещё можно воспользоваться верёвкой, как следует на ней раскачаться, и... как тебе такое, Илон Маск? Для этого граф нодов нужно дополнять дополнительными маршрутами с разными способами их преодоления, а их расчёт может быть невероятно сложным. Судите сами: если на пути от А к Б у нас есть яма, барьер и резервуар с водой, нам нужно просчитать, можно ли яму перепрыгнуть, и если да - то можно ли перепрыгнуть барьер, и есть да - то можно ли переплыть резервуар. А если барьер перепрыгнуть можно только ровно в одном месте, как мы его найдём? А если в резервуаре кислота? А если у нас есть к ней неуязвимость (как у буллсквида)? "Данунафиг", подумали разработчики халфовского ИИ, и в итоге наши любимые халфовские монстры не заморачиваются такими мелочами и пытаются идти исключительно напролом. Вальвовцы честно пытались проблему решить и ввели такое понятие, как "hint node" - это специальный вейпоинт, который трактуется ИИ как требующий особого действия - например, того же прыжка. Но система эта в итоге так и не была доделана. Разработчики ботов, впрочем, это реализовали - можно ставить ноды, указывающие на начало и конец лестниц, на хорошие кемперские позиции и т.п. Но качественно делать это в автоматическом режиме по-прежнему невозможно.

Непорядок, подумал товарищ van Waveren, он же MrElusive, к тому времени уже имевший солидный опыт написания ботов для Quake и Quake II, а тут весьма удачно нанятый Кармаком, чтобы сделать качественных ботов для нового проекта Id - Quake III. Поговорив с командой, он понял, что ни один левел-дизайнер не горит желанием расставлять хинт-ноды - да чего там, вообще любые ноды. "Считать должен компьютер", помните? И MrElusive пришёл к очевидному выводу: ежели ноды никто не хочет расставлять, то от них нужно отказаться вообще. Это звучит на первый взгляд дико - откуда же боты будут брать информацию о путях на геометрически сложном уровне? Ответ такой: эта информация будет заботливо создаваться для них специальным компилятором, который потратит достаточно времени на геометрический анализ, просчитает все мыслимые варианты и подготовит идеальный граф навигации. Так появилась система осведомлённости об окружающей среде, или AAS. Благодаря ей боты в Quake III умели бегать, прыгать, плавать, пользоваться grapple и даже делать рокетджампы в труднодоступные места, и всё это аж в 1999 году! Система оказалась настолько удачной, что в дальнейшем использовалась и в Doom III, и в Quake IV, и подозреваю, что во всех дальнейших проектах id. А с открытием исходного кода idTech3 она, вернее, её первоначальная реализация, стала доступна широким народным массам.

Мы с вами вместе подробно теоретически проанализируем эту систему, разберём все тонкости, а затем, вооружившись Знанием, создадим свою собственную AAS-систему для мультиплеера Perilous Warp, исправленную и дополненную. Мы не будем брать код напрямую из Quake III, который, к слову, довольно тяжело читать - мы напишем качественный код сами, опираясь на идеи и алгоритмы MrElusive. А кто-то из вас, возможно, захочет внедрить систему AAS в халфу заместо Node Graph, чтобы вправить монстрам мозги... Не переключайтесь!

Браши и энтити - строительный материал AAS

Итак, как я уже писал - система AAS представляет собой результат геометрического анализа уровня. В комментариях упомянули навигационный меш - да, можно сказать, что AAS представляет собой частный случай навмеша, который создаётся компилятором без участия левел-дизайнера (ну, почти). Мир в представлении AAS поделён на зоны (area), каждая из которых обладает очень важным свойством - выпуклостью. Иными словами, зона представляет собой выпуклый многогранник. Почему это так важно, спросите вы? Да потому, что внутри одной зоны бот может беспрепятственно пройти из одной точки в другую, мы можем быть в этом уверены на сто процентов, даже пожалуй на все 146%. Именно зоны, а не вейпоинты, являются вершинами графа в AAS, и после того, как мы нарубим наш мир на зоны с соблюдением условия выпуклости, нам останется лишь определить, между какими зонами и как именно бот может перемещаться (на самом деле, есть и ещё одно, второе условие для зон, но о нём мы поговорим позже, когда будем обсуждать гравитационное разбиение).

Чтобы нарезать мир на зоны и определить способы перемещений между ними, нам нужна определённая информация: энтити и браши. Из свойств энтитей нам нужна информация об оригинах и углах, чтобы правильно размещать связанные с ними браши, а также скриптовая энтити-специфичная информация, например, скорость движения двери или поезда. Браши, в свою очередь, задают геометрию мира, с которой взаимодействует игрок. Таким образом, для построения AAS нам нужно сначала подготовить входные данные для алгоритма: энтити и браши. Если с энтитями всё более-менее понятно (в каждом BSP файле есть лумп энтитей, который нужно просто загрузить и распарсить на keyvalues), то с брашами всё несколько сложнее. Т.к. колоизация в Quake III (а также в Quake II и Volatile) осуществляется именно с брашами, то они в некотором смысле сохранены в BSP-файле, и их можно оттуда загрузить. В Quake и Half-Life колоизация выполняется не по брашам, а по дереву клипнодов, так что сначала придётся восстановить оригинальные браши. Если имеется исходник карты - можно воспользоваться им и прочитать браши из мап-файла. В противном случае нужно написать алгоритм декомпиляции карты. Желающие могут утащить его из исходников bspc, который умеет не только генерировать AAS, но и декомпилировать BSP-файлы, и именно по описанной причине.

Хорошо, когда ты большой и сильный бугай: искупался, лёг на травку и кубай. Но внимательный читатель спросит - как же быть с патчами, и особенно модельками с полигональной колоизацией? Ответ напрашивается сам собой: нужно создать для них браши. Именно так поступает компилятор q3map2, когда строит колоизацию с misc_model, и именно так поступает bspc, когда создаёт браши для патчей. Можно даже заморочиться и конвертировать замкнутые выпуклые патчи в цельные браши, но авторы bspc заморачиваться не стали и создают по одному брашу на патчевый полигон. Выглядит это довольно стрёмно: цилиндр превращается большое количество пересекающихся брашей. Но с точки зрения алгоритма построения AAS всё вполне ok, вот разве что зон такие браши наплодят довольно много. Поэтому левел-дизайнеру дали способ, скажем так, задавать особую колоизацию для ботов, намного проще, чем полигональная, ведь в отличие от игрока, бот не будет жаловаться, что вокруг красивой круглой колонны не удаётся плавно скользить. Но об этом мы поговорим чуть позже.

Но вернёмся к движку Volatile. В его BSP-формате уровней, помимо брашей, присутствуют так называемые "clipmodels". Это небольшие бинарные деревца полигональной колоизации, которые создаёт компилятор VMap для патчей и моделей. Узлы этих деревьев, "clipfaces", чем-то напоминают браши, и могут быть в них легко сконвертированы. Поэтому для Volatile никакой специальной обработки патчей, как в Quake III, не требуется, и лумп сурфасов можно вообще не загружать.

Таким образом, подготовительный этап построения AAS выглядит так:

LoadBSPFile();

ParseEntitiesFromEntityLump();

CreateBrushesFromBrushesAndBrushsidesLumps();

CreateBrushesFromClipmodelsLump();

1

float BrushSideDistanceFromAABB( const float *normal, const float *mins, const float *maxs )

2

{

3

  float dir[3];

4

  for ( size_t i = 0; i < 3; ++i ) {

5

    if ( normal[i] > 0.0001 )

6

      dir[i] = mins[i];

7

    else if ( normal[i] < -0.0001 )

8

      dir[i] = maxs[i];

9

    else

10

      dir[i] = 0;

11

  }

12

  return -DotProduct( dir, normal );

13

}

14

// ...

15

side->plane.dist += BrushSideDistanceFromAABB( side->plane.normal, aabb_mins, aabb_maxs );

__________________

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

Ух ты, наконец-то действительно интересная тема

Давно интересовала эта тема. Gladiator бот также существует под Q2. Gladiator бот под HL - это мечта!

__________________

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

Дядя Миша
Как минимум впервые за долгое время

А в чём принципиальное отличие? Будет ли раставлять вейпоинты бот или компилятор, какая разница?

__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!

FiEctro
Вопрос из разряда "Какова ката выбы выбрали?"
Правильный ответ - "неко кова", потому что нет там, в AAS, неко ких вейпоинтов. Это и есть принципиальное отличие.

__________________

Это же то же самое, что и navmesh?

ncuxonaT
Это не "то же самое, что и навмеш". Это один из вариантов реализации навмеша. Реализации могут быть любыми, нас - интересует та, что хорошо ложится на брашево-энтитиевую архитектуру.

__________________

__________________
Ты топчешь мир своими ботинками,
Не замечая куда наступаешь,
А время от тебя уходит цветными картинками,
Но ты даже этого не понимаешь.

Компрометирую данные своей учётной записи.
ЛОГИН: Ghoul [BB]
ПАРОЛЬ: paladin_solo

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

Дядя Миша
Вейпоинты тоже может дизайнер создавать, што ж теперь?
Но мы с вами знаем, что дизайнеры не хотят создавать никакие навмеши и вейпоинты. Дизайнеры хотят фыр-фыр-фыр.

__________________