HLFX.Ru Forum (https://hlfx.ru/forum/index.php)
- Наши проекты (https://hlfx.ru/forum/forumdisplay.php?forumid=1)
-- XashNT: блог разработчика (https://hlfx.ru/forum/showthread.php?threadid=5297)

То была просто тестовая карта из PrimeXT, я проверял как модельки превращаются в браши. Ну вот на этом тестовом домике - отлично превращаются.

__________________
My Projects: download page

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

Ну чтож, вот руки наконец-то дошли до поиска путей. Собственно сам поиск - это реализация алгоритма A*. Тут вроде как иных вариантов попросту нет, по крайней мере на первый взгляд. Однако, кроме непосредственно поиска пути, нас интерисует ещё несколько вещей:

1. рассчёт сетки на статичной геометрии. Это я успешно проделал весной прошлого года, где-то тут в теме есть скриншоты. Теперь у нас есть сетка доступности в рамках статичной геометрии. Хорошо, но это только половина дела.
2. блокировка сетки с учётом подвижной геометрии. К подвижной геометрии мы можем отнести все лифты, двери, вагончики, а так же других монстров и игрока.
И вот какие у нас тут есть варианты? Я к примеру не знаю как это устроено в Юнити\Унреале, но руководствуясь здравым смыслом и тем фактом, что ни в одной игре ни один монстр не добирается до конечной точки мгновенно (тогда бы его было проще туда телепортировать, а поиск пути был бы вообще не нужен), можно наметить два сценария:
1. Сперва делается поиск по статичной геометрии, а поправки на динамическую вносятся на каждом шагу, который сделал монстр.
2. Динамическая геометрия может вносить изменения в статичную сетку.

Я склоняюсь ко второму подходу, но с элементами первого. Если мы к примеру выбрали первый вариант, он нам рассчитал доступность пути, монстр по нему побежал и тут внезапно оказалось, что на пути есть закрытая дверь. И монстр будет в нее безнадёжно долбиться, прямо как в халфе. Кому такое интересно видеть? Во втором варианте идея в том, что ячейки навигационной сетки линкуются в тоже самое AABB-дерево, что и физические объекты. Поскольку это делается каждый кадр и обязательно для физики (чтобы искать объекты), нам даже не придётся перестраивать архитектуру всего этого дела. Только лишь определить какие именно объекты нам надо указать в качестве фундаментальных блокираторов пути. А дальше их линковка в сетку автоматически пометит те или иные ячейки как недоступные и A* будет это учитывать. Что немаловажно - мы например можем исключить из блокираторов двери, которые монстр в состоянии открыть самостоятельно - для него они будут прозрачными.
Единственный минус такого подхода - мы не сможем фильтровать объекты на уровне разных монстров. Ну типа один может открывать все двери, а другой - только определённые. Хотя и это можно решить, например заведя маску блокировки. Ну пока что не требуется. Обычно идёт разграничение на скриптовые двери и двери, которые могут открыть все.
А игроку построение пути не нужно.
Что же касается элементов второго подхода, то на мой взгляд блокировать сетку перемещением тех же NPC смысла не имеет. Пока наш монстр добежит, там уже 10 раз всё поменяется. Поэтому огибание локальных препятствий (в виде ббокса монстров) можно оставить классическим - т.е. так, как его реализовал Кармак - через рандом и сохранение общего направления пути. Потому что обогнуть таким образом ббокс получится, а вот найти более сложный путь - уже нет.
Собственно, именно поэтому монстры в кваке такие тупые.
Плюс в том, что проверка локальных перемещений больше не требует тяжёлой трассировки уровня, т.к. мы движемся по предрассчитаному пути, который гарантировано проходим.

Собственно пример того, как закрытие двери обновляет навигационную сетку:


Это всё делается на самом низком уровне, поэтому мы не зависим от логики самих дверей или лифтов. Дверь может остановиться в любом положении и в сетке будет доступен именно проход по ширине щели.

Ну и ещё об одном моменте хочу сказать. Если бы я смержил эти ноды в меш, то уже не смог бы проделать эту фишку. Так что пожалуй пока остановлюсь на дискретных нодах.

Добавлено 03-02-2024 в 14:52:

Поговорим об общей философии поиска пути. Учитывая что практически всегда используется A* либо его модификации, для увеличения скорости работы. Алгоритм находит кратчайший путь между двумя точками.
В переводе с человеческого на машинный это означает:
1. Найти все возможные пути из точки А в точку Б
2. Выбрать самый короткий из них
Оптимизация предполагает, что мы не будем трассировать все пути, а осуществлять непрерывную коррекцию дистанции прямо в процессе поиска, т.е. кол-во шагов сокращается. Всё это довольно долго.

Я смотрю на это дело следующим образом. Нахождение пути используется только и исключительно монстрами, которые в игре призваны имитировать живые существа, либо человекоподобных роботов. И те и другие могут ошибаться, как ошибается в реальной жизни и сам человек. Т.е. когда маршрут очевиден - человек разумеется выбирает кратчайший путь.
Если маршрут неочевиден, может быть выбран и не самый оптимальный путь.
Для игры это некритично. Ну сделает монстр десяток лишних шагов, так что же с того? Наоборот подобное поведение придаст ему больше человечности, он не будет ломиться каждый раз по одному и тому же пути.
Таким образом мы приходим к простой мысли: для большинства случаев нам вовсе необязательно искать все доступные пути и затем выбирать наилучший. Будет вполне достаточно найти из приемлимых. Это куда проще и быстрее. Мы можем использовать тот же самый алгоритм, который использует квейк для поиска пути - выбор одного из четырёх направлений + рандом. Вот только от квейка, который каждую ячейку долго и муторно тестирует на предмет заполненности геометрией, наличия обрывов, уступов, возможности сделать шаг вверх\вниз или скажем наличие водной преграды, в моём алгоритме ничего этого не понадобится - т.к. ячейки уже заранее предрассчитаны и если между ними есть связь, значит шаг возможен. Проложение пути осуществляется по кратчайшему расстоянию между точками. У каждой ноды - четыре соседа.
Значит аппроксимация для углов, отличных от 90 градусов - просто чередование смены направлений. Сперва влево, потом вправо.
Можно и локальный рандом подмешать, он погоды не сделает. Монстр не обязан бегать как по рельсам. Я помню как в P2 меня покоробило, что солдаты бегут по нодам именно как по рельсам, несмотря на все триангуляции. Но зато математически всё чётко - не придерёшься.
Опять же режим поиска может настраиваться при помощи флагов, например. Помоему такой фишки ещё нигде не было.

__________________
My Projects: download page

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

Дядя Миша
У меня такой вопрос с которым я сам столкнулся. Вот если сам игрок и монстры будут являться преградой для А* то как поступать? Ну ладно упростим, игрока игнорируем его обходить не будем. Но что делать с монстрами? Они могут окружить игрока и тогда поиск пути к игроку будет невозможен. И тут я столкнулся с такой проблемой что вот именно в таком конкретном случае дерево начинает беспомощно разростаться в надежде найти нужный путь, и следовательно тормозить.

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

__________________
My Projects: download page

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

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

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

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

__________________
My Projects: download page

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

__________________
My Projects: download page

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

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

Как правило при большом количестве мобов проблема в том что они сбиваются в длинную очередь и плетутся паровозиком за игроком.

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