Моя основная задача - это построение самого навмеша. Может показаться, что это просто полигоны, но в действительности он состоит из сотен тысяч квадратиков, размером точно с хулл игрока\монстра. При сохранении в карту я просто эти квадратики объединяю обратно, т.к. для визуализации это не нужно. А как он будет представлен в итоге, я ещё не решил.
Дядя Миша писал: размером точно с хулл игрока\монстра.
Кстати это тоже проблема, я так понимаю нужно ещё хранить размеры хулла который может туда влезть.
__________________ Иван Топорышкин пошел на охоту,
С ним пудель пошел, перепрыгнув забор,
Иван, как бревно провалился в болото,
А пудель в реке утонул, как топор.
Сейчас самое главное - построить непрерывный меш, чтобы монстр мог везде ходить. А способов его оптимизации много и они особой проблемы не представляют. Сложность же заключается в том, что навмеш генерируется из произвольной геометрии. Из брашей было бы не в пример проще.
Дядя Миша писал: Сложность же заключается в том, что навмеш генерируется из произвольной геометрии.
Так это вроде просто нужно сделать копию геометрии с нужными нормалями и обрезать лишнее?
__________________ Иван Топорышкин пошел на охоту,
С ним пудель пошел, перепрыгнув забор,
Иван, как бревно провалился в болото,
А пудель в реке утонул, как топор.
крайне желательно нарезать эту геометрию на квадратные патчи. Каждый патч по размеру хулла монстра, чтобы можно было точно проверить куда он может шагать.
Подведу некоторые промежуточные итоги. Всё нижесказанное я пишу исходя из главных допущений при построении ai-карты - никаких ручных правок, мы хотим чтобы компилятор нам самостоятельно всё посчитал. Мы же к примеру лайтмапу не дорисовываем, если компилятор ошибся. Так оно и здесь должно быть. Да, задачка не слишком простая, но решаемая.
1. В сталкере (впрочем как и практически везде) не было нормальной трассы по форме объекта и тем более трассы произвольной формой объекта, а не только bbox. Последний там как-раз бы, но не использовался. Видимо применение bbox test в сочетании с регулярной сеткой приводило к большому кол-ву мёртвых зон. Поэтому там трасса только точечная используется. Что приводит к необходимости ручного редактирования всего этого дела.
2. AAS для уровней из произвольной геометрии не годится. Максимум уровень первой-второй кваки (он собственно для них и делался, а потом его кое-как натянули на Q3 и D3). Там приходится слишком многое окружать специальными брашами, чтобы монстр не попал в плохие места. К тому же там AI очень сильно завязан на предрассчёты и специальные контентсы.
На полигональных уровнях всё это нормально работать не будет. Ну или будет очень-очень долго считаться и не факт, что коллизия получится нормальной для всех случаев. Мелкие полигоны, сами знаете, провоцируют щели и прочие ошибки точности.
3. Навмешы подошли бы лучше, но у них есть проблема. Ступеньки! В идеале навмеш должен быть непрерывным, чтобы монстр мог бежать придерживаясь его внутреннего объема. Ступенька - это разрыв в навмеше. Ладно, если бы все лестницы были прямые, то можно было бы аппроксимировать их пологим подъемом. На практике лестницы бывают и витые и с разным шагом ступенек. То есть тут какая-то ручная правка всё равно потребуется. Ручная правка означает, что навмеш частично приходит из исходника. Это ничем не лучше клипбрашей, которыми в халфе обстраивают модели, иммитируя коллизию. Модель поменялась, клипбраш остался прежний, коллизия не совпадает. В Метро Эксодус был забавный ляп, ну все наверное помнят - на карте "Поволжье" бандюки бегали по воздуху. Вот как раз геометрия поменялась, а навмеш старый остался. Не вариант.
4. Остаются только ноды-точки. У каждой точки должна быть связь с другой точкой. И у каждой связи должна быть специальная подсказка для кода WalkMove или чего-то подобного. А именно - что представляет собою следующая нода. Ну навскидку как это могло бы выглядеть:
0. move stop - стена
1. move normal - обычный шаг
2. move step up - ступенька вверх
3. move step down - ступенька вниз
4. move fall - падение с высоты (обратная связь разорвана и покажет move stop)
5. jump to water - следующий шаг приведёт к падению в воду
6. jump from water - следующий шаг это waterjump
Возможно ещё какие-то ситуации упустил, но в целом примерно так.
И подобные подсказки избавляют нас от кучи лишних проверок на самом деле. AI надо будет лишь убедиться, что путь не перекрыт каким-то динамическим объектом. Локальные сетки так же могут присутствовать на моделях, встроенных в карту. Чтобы монстр, например мог ходить по вагончику поезда или чему-то подобному.
Ну и самое любопытное - в эти сетки можно инжектировать позиции точечных энтить и отсекать все те части, которые оказались недосягаемыми, подобно тому, как портализация убирает все внешние части геометрии.
Единственный момент - построение оптимального графа сквозь путешествие через пол-карты может быть не столь быстрым, однако это не критично, поскольку монстры так далеко не заглядывают. Обычно это в случае получения нового задания - например пробежать по скрипту в указанную точку или найти укрытие. А в обычных состояниях они довольствуются локальным шагом на размер хулла и эта сетка идеально поможет им ориентироваться в пространстве.
ЗЫ. я тут уже три версии построения навигации опробовал. Напоминает разработку лайтмаппера, тот тоже менялся раз 15, пока я не нащупал наиболее оптимальный путь. Впрочем и с компилятором уровней было так же и с разработкой собственного языка.
Идеи для построения путей навигации неожиданно нашли применение в лайтмаппере. У меня там оставалась одна нерешённая проблема с генерацией патчей для радиосити. И вот я внезапно додумался как решить её красиво и эффективно. И удивился, почему эта идея мне раньше не приходила в голову. Поясню в чём была проблема:
Когда у нас брашевая геометрия, обработанная CSG, лайтмаппер работает в идеальных условиях. Когда у нас произвольная полигональная геометрия, условия уже далеко не такие идеальные. К тому же с модельной геометрией делать как правило ничего нельзя. Сквозь CSG её не пропустишь, рубить нежелательно. К тому же там много кривых поверхностей. Наложить лайтмапу в таких условиях проблематично но вполне реально. А вот нарубить эти поверхности на регулярную симметричную сетку уже гораздо труднее. Раньше я действовал просто - пытался объединить все треугольники лежащие на одной плоскости, а затем рубил геометрию на квадарты-патчи с заданным шагом. Процентов 40 патчей при этом оставалось состоять из двух-трёх кусков. А каждый патч генерирует собственные трансферы и потребление памяти растёт экспоненциально.
И тут мне в голову пришла здравая мысль - надо попытаться смержить уже нарубленные патчи! Зная длину ребра довольно просто проверить две ситуации:
1. В результате объединения получился квадратный патч с нужной стороной ребра
2. В результате объединения получился еще не квадратный патч, но аксиальные стороны ребра у него подходящие и он скоро будет достроен до квадрата. Чтобы объединение происходило веселее, я поместил кусочки патчей в AABB-дерево. В данном случае дерево использовалось не для поиска. а для сортировки. На каждой ноде скопились именно те кусочки, которые и надо было объединить. Мне осталось линейно пробежаться по нодам (ну или обработать каждую ноду в отдельном потоке) и доклеить разобранные патчи. Экономия в результате оптимизации составила до 40%! Второй позитивный момент заключался в том, что раньше я выбрасывал сверхмалые патчи, из-за чего потенциально менялась общая яркость светопереноса и приходилось нормализовывать излучающий свет. Сейчас я ничего не выбрасываю, поскольку велик шанс, что эти мелкие кусочки в процессе склейки достроятся до квадратного патча. Получился стабильный и прозрачный алгоритм, который в любых условиях должен хорошо себя проявить.
Чтож, возвращаюсь к генерации навигационных путей. Поскольку нодов адски много надо разработать эффективный дисковый формат для их хранения. Подобный формат предполагает различные допущения.
Я выбрал следующие:
Максимальный размер уровня, который может быть покрыт нодами +\-98304 юнита. Т.е. квадрат ~2.4 километра.
Минимальный размер хулла (по любому измерению) составляет 24 юнита.
Это с запасом, т.к. в халфе например минимальный размер хулла - 36 юнитов (+\- 16). Меньше делать смысла нет, да и этот хулл, как вы понимаете, смогут использовать все, кто меньше по размерам. Уж если персонаж проходит, то и тараканы, мышы, крысы тоже пролезут. Вероятно понадобится еще один хулл - для больших персонажей. Сама система предусматривает наличие нескольких Ai-хуллов для каждой модели уровня. По аналогии с клипнодами.
И точно так же некоторых хуллов может и не быть вовсе.
Ну прикольно хардкодить хулл для каждого персонажа прямо в карту. Может тогда всё же воксельную сетку сделать лучше?
__________________ Иван Топорышкин пошел на охоту,
С ним пудель пошел, перепрыгнув забор,
Иван, как бревно провалился в болото,
А пудель в реке утонул, как топор.
FiEctro а ты думаешь в других играх оно не так? В сталкере размер патча точно так же означает приблизительный хулл монстра. Только он там вообще один и если монстры крупные. то начинаются проблемы. Поэтому крупные монстры в основном в подземельях тусуются, где проходы широкие.
Добавлено 28-03-2023 в 15:07:
Исходя из накопленной информации, обычно нужно не более двух хуллов на уровень: хулл персонажа-хумана и хулл крупного монстра.
Кстати в халфе тот факт, что мелкая живность боится яркого света - не случаен. Потому что они в качестве навигации как раз и используют яркость света и стремятся найти тёмный угол. Они же не по нодам бегают.
Это просто кто-то очень удачно предложил и оно совпало с реальным поведением.
Добавлено 28-03-2023 в 15:08:
Цитата:
FiEctro писал: воксельную сетку
Гы-гы. А у воксельной сетки размер ячейки чем определяться будет? Правильно - тем же самым размером хулла %)
Согласно новой концепции, вот такая вот сетка из нодов у меня получилась.
Пустые места - это те, где ноды создать по каким-то причинам не удалось, учитывая, что изначально они генерятся из реальной геометрии, а геометрия может быть порезана как угодно. Но ничего страшного. В дальнейшем я полагаю эти точки можно будет восстановить. У нас же сетка!
А зная шаг и уклон, можно попробовать экстраполировать недостающие ячейки. Я долго с этим маялся и в конечном итоге пришёл к выводу, что экстраполяция в данном случае будет надёжнее, чем собирать их из осколков реальной геометрии (с учётом того, что я и так это делаю).
| IP: 
24-03-2023 06:20
