Ну чтож, вот руки наконец-то дошли до поиска путей. Собственно сам поиск - это реализация алгоритма A*. Тут вроде как иных вариантов попросту нет, по крайней мере на первый взгляд. Однако, кроме непосредственно поиска пути, нас интерисует ещё несколько вещей:
1. рассчёт сетки на статичной геометрии. Это я успешно проделал весной прошлого года, где-то тут в теме есть скриншоты. Теперь у нас есть сетка доступности в рамках статичной геометрии. Хорошо, но это только половина дела.
2. блокировка сетки с учётом подвижной геометрии. К подвижной геометрии мы можем отнести все лифты, двери, вагончики, а так же других монстров и игрока.
И вот какие у нас тут есть варианты? Я к примеру не знаю как это устроено в Юнити\Унреале, но руководствуясь здравым смыслом и тем фактом, что ни в одной игре ни один монстр не добирается до конечной точки мгновенно (тогда бы его было проще туда телепортировать, а поиск пути был бы вообще не нужен), можно наметить два сценария:
1. Сперва делается поиск по статичной геометрии, а поправки на динамическую вносятся на каждом шагу, который сделал монстр.
2. Динамическая геометрия может вносить изменения в статичную сетку.
Я склоняюсь ко второму подходу, но с элементами первого. Если мы к примеру выбрали первый вариант, он нам рассчитал доступность пути, монстр по нему побежал и тут внезапно оказалось, что на пути есть закрытая дверь. И монстр будет в нее безнадёжно долбиться, прямо как в халфе. Кому такое интересно видеть? Во втором варианте идея в том, что ячейки навигационной сетки линкуются в тоже самое AABB-дерево, что и физические объекты. Поскольку это делается каждый кадр и обязательно для физики (чтобы искать объекты), нам даже не придётся перестраивать архитектуру всего этого дела. Только лишь определить какие именно объекты нам надо указать в качестве фундаментальных блокираторов пути. А дальше их линковка в сетку автоматически пометит те или иные ячейки как недоступные и A* будет это учитывать. Что немаловажно - мы например можем исключить из блокираторов двери, которые монстр в состоянии открыть самостоятельно - для него они будут прозрачными.
Единственный минус такого подхода - мы не сможем фильтровать объекты на уровне разных монстров. Ну типа один может открывать все двери, а другой - только определённые. Хотя и это можно решить, например заведя маску блокировки. Ну пока что не требуется. Обычно идёт разграничение на скриптовые двери и двери, которые могут открыть все.
А игроку построение пути не нужно.
Что же касается элементов второго подхода, то на мой взгляд блокировать сетку перемещением тех же NPC смысла не имеет. Пока наш монстр добежит, там уже 10 раз всё поменяется. Поэтому огибание локальных препятствий (в виде ббокса монстров) можно оставить классическим - т.е. так, как его реализовал Кармак - через рандом и сохранение общего направления пути. Потому что обогнуть таким образом ббокс получится, а вот найти более сложный путь - уже нет.
Собственно, именно поэтому монстры в кваке такие тупые.
Плюс в том, что проверка локальных перемещений больше не требует тяжёлой трассировки уровня, т.к. мы движемся по предрассчитаному пути, который гарантировано проходим.
Собственно пример того, как закрытие двери обновляет навигационную сетку:
Это всё делается на самом низком уровне, поэтому мы не зависим от логики самих дверей или лифтов. Дверь может остановиться в любом положении и в сетке будет доступен именно проход по ширине щели.
Ну и ещё об одном моменте хочу сказать. Если бы я смержил эти ноды в меш, то уже не смог бы проделать эту фишку. Так что пожалуй пока остановлюсь на дискретных нодах.
Добавлено 03-02-2024 в 14:52:
Поговорим об общей философии поиска пути. Учитывая что практически всегда используется A* либо его модификации, для увеличения скорости работы. Алгоритм находит кратчайший путь между двумя точками.
В переводе с человеческого на машинный это означает:
1. Найти все возможные пути из точки А в точку Б
2. Выбрать самый короткий из них
Оптимизация предполагает, что мы не будем трассировать все пути, а осуществлять непрерывную коррекцию дистанции прямо в процессе поиска, т.е. кол-во шагов сокращается. Всё это довольно долго.
Я смотрю на это дело следующим образом. Нахождение пути используется только и исключительно монстрами, которые в игре призваны имитировать живые существа, либо человекоподобных роботов. И те и другие могут ошибаться, как ошибается в реальной жизни и сам человек. Т.е. когда маршрут очевиден - человек разумеется выбирает кратчайший путь.
Если маршрут неочевиден, может быть выбран и не самый оптимальный путь.
Для игры это некритично. Ну сделает монстр десяток лишних шагов, так что же с того? Наоборот подобное поведение придаст ему больше человечности, он не будет ломиться каждый раз по одному и тому же пути.
Таким образом мы приходим к простой мысли: для большинства случаев нам вовсе необязательно искать все доступные пути и затем выбирать наилучший. Будет вполне достаточно найти из приемлимых. Это куда проще и быстрее. Мы можем использовать тот же самый алгоритм, который использует квейк для поиска пути - выбор одного из четырёх направлений + рандом. Вот только от квейка, который каждую ячейку долго и муторно тестирует на предмет заполненности геометрией, наличия обрывов, уступов, возможности сделать шаг вверх\вниз или скажем наличие водной преграды, в моём алгоритме ничего этого не понадобится - т.к. ячейки уже заранее предрассчитаны и если между ними есть связь, значит шаг возможен. Проложение пути осуществляется по кратчайшему расстоянию между точками. У каждой ноды - четыре соседа.
Значит аппроксимация для углов, отличных от 90 градусов - просто чередование смены направлений. Сперва влево, потом вправо.
Можно и локальный рандом подмешать, он погоды не сделает. Монстр не обязан бегать как по рельсам. Я помню как в P2 меня покоробило, что солдаты бегут по нодам именно как по рельсам, несмотря на все триангуляции. Но зато математически всё чётко - не придерёшься.
Опять же режим поиска может настраиваться при помощи флагов, например. Помоему такой фишки ещё нигде не было.
Дядя Миша
У меня такой вопрос с которым я сам столкнулся. Вот если сам игрок и монстры будут являться преградой для А* то как поступать? Ну ладно упростим, игрока игнорируем его обходить не будем. Но что делать с монстрами? Они могут окружить игрока и тогда поиск пути к игроку будет невозможен. И тут я столкнулся с такой проблемой что вот именно в таком конкретном случае дерево начинает беспомощно разростаться в надежде найти нужный путь, и следовательно тормозить.
Цитата:
Дядя Миша писал: Я склоняюсь ко второму подходу, но с элементами первого. Если мы к примеру выбрали первый вариант, он нам рассчитал доступность пути, монстр по нему побежал и тут внезапно оказалось, что на пути есть закрытая дверь.
Я тоже думал об этом, не придумал ничего более умного чем просто изредка например 1 раз в секунду прокидывать трассу между нодами. Наверное это не очень хорошая идея с т.з. производительности, но зато гарантировано определит всякие тонкие двери и мелкие препятствия лежащие за пределами точности сетки.
Цитата:
Дядя Миша писал: Я помню как в P2 меня покоробило, что солдаты бегут по нодам именно как по рельсам, несмотря на все триангуляции. Но зато математически всё чётко - не придерёшься.
Мы боролись с этим так - по нодам как по рельсам двигается невидимый объект, а за ним просто как в точку бежит монстр на небольшом расстоянии. Это выглядит более естественно.
И ещё такой вопрос, что насчёт нодов для летающих и плавающих монстров (как глючный ихтиозавр из хл1 и верталёт)? Как они работают?
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
FiEctro писал: Вот если сам игрок и монстры будут являться преградой для А* то как поступать?
Да так же, как Кармак поступал. Очень тупой способ, но для локальных препятствий в виде коробки прекрасно работающий.
Допустим монстр идёт в заданном направлении. Упёрся в игрока. Выбрал путь влево или вправо. Сделал шаг. Затем попытался вернуться к заданному направлению - не прокатило. Сделал ещё шаг в обходном (выбранном изначально). Опять попытался вернуться - о, теперь путь свободен.
Плавно возвращаемся к заданному направлению под углом. Человек и в жизни бы сделал точно так же. Вот пояснительную картинку приложил.
Цитата:
FiEctro писал: дерево начинает беспомощно разростаться в надежде найти нужный путь, и следовательно тормозить.
И это тоже проблема, совершенно верно.
Цитата:
FiEctro писал: просто изредка например 1 раз в секунду прокидывать трассу между нодами
Не надо "Изредка". Надо всё чётко привязывать к событиям. Что за мода такая - изредка. Изредка можно запускать разве что сборщик мусора, да и то...
Добавлено 03-02-2024 в 17:14:
Цитата:
FiEctro писал: мелкие препятствия лежащие за пределами точности сетки.
Не знаю что у тебя там за сетка такая, но в NT подобное невозможно просто по определению. Т.к. каждая нода имеет объем, равный размеру хулла монстра. И любое препятствие имеет объем. И ноды стоят вплотную друг к другу. Как там может что-то протиснуться?
На визуализацию не смотри, я их нарочно немного уменьшил, чёб в глазах не рябило. В реальности они впритык стоят.
Дядя Миша писал: Не надо "Изредка". Надо всё чётко привязывать к событиям. Что за мода такая - изредка. Изредка можно запускать разве что сборщик мусора, да и то...
Ну теперь то я всё понял как ты оптимизируешь. Я то всё в реальном времени обсчитываю и пути, и занятость нод и т.д. понятно почему у тебя оно не тормозит.
Цитата:
Дядя Миша писал: И это тоже проблема, совершенно верно.
Но я даже пока не знаю как решать её. Пока что просто прерываю если циклов получается очень много. При обычных ситуациях такого практически никогда не бывает.
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
Дядя Миша писал: Что же касается элементов второго подхода, то на мой взгляд блокировать сетку перемещением тех же NPC смысла не имеет. Пока наш монстр добежит, там уже 10 раз всё поменяется.
Хороший монстр должен пытаться предсказать поведение других монстров как в непосредственной близости от себя так и чуть подальше по направлению своего движения. Как минимум через экстраполяцию их текущего движения на несколько сотен юнитов вперёд.
Цитата:
Дядя Миша писал: Алгоритм находит кратчайший путь между двумя точками.
Сделай чтобы путь по возможности оставлял зазор в 1 ячейку от каждой стенки. И от других монстров и игрока. И чтобы монстров как бы немного заносило при обходе препятствий, ну типа скругленный путь. Потому что даже собака не будет идти и обтирать боком стену и никто не хочет на повороте внезапно столкнуться нос к носу с врагом или даже с коллегой идущим из-за угла. Тем более в ситуациях вроде каскадного резонанса.
Дядя Миша писал: Не знаю что у тебя там за сетка такая, но в NT подобное невозможно просто по определению. Т.к. каждая нода имеет объем, равный размеру хулла монстра. И любое препятствие имеет объем. И ноды стоят вплотную друг к другу. Как там может что-то протиснуться?
В целом тоже верно если оно всё содержимое коробки апроксимирует до её размера. Но коробки очень тормозные, у меня сферы, а сферы могут страдать фигнёй, хотя я этого не замечал, но боюсь что что то оно может пропускать.
Цитата:
Crystallize писал: Сделай чтобы путь по возможности оставлял зазор в 1 ячейку от каждой стенки. И чтобы монстров как бы немного заносило при обходе препятствий, ну типа скругленный путь. Потому что даже собака не будет идти и обтирать боком стену и никто не хочет на повороте внезапно столкнуться нос к носу с врагом или даже с коллегой идущим из-за угла. Тем более в ситуациях вроде каскадного резонанса.
Ну да, в Юнити есть такая штука для навмеша типа отступы от стенок делать. А то любят они пушками сквозь двери светить.
Добавлено 03-02-2024 в 18:22:
Цитата:
Crystallize писал: Хороший монстр должен пытаться предсказать поведение других монстров как в непосредственной близости от себя так и чуть подальше по направлению своего движения. Как минимум через экстраполяцию их текущего движения на несколько сотен юнитов вперёд.
Проблема этих предсказаний в их производительности. А* работает хорошо когда гарантировано у тебя есть свободный путь, но вот если его нет надо уже городить какие то костыли. Если каждый монстр будет чекать всех остальных это может привести ещё к большим затупам среди них.
Добавлено 03-02-2024 в 18:29:
Цитата:
Дядя Миша писал: Да так же, как Кармак поступал. Очень тупой способ, но для локальных препятствий в виде коробки прекрасно работающий.
Допустим монстр идёт в заданном направлении. Упёрся в игрока. Выбрал путь влево или вправо. Сделал шаг. Затем попытался вернуться к заданному направлению - не прокатило. Сделал ещё шаг в обходном (выбранном изначально). Опять попытался вернуться - о, теперь путь свободен.
Плавно возвращаемся к заданному направлению под углом. Человек и в жизни бы сделал точно так же. Вот пояснительную картинку приложил.
Ты не понял. Вот игрок занимает 1 клетку. 8 клеток вокруг него это монстры его со всех сторон окружили. Монстр где то снаружи уже не сможет построить к игроку путь, т.к. монстры которые окружили игрока являются преградой. A* не имеет решения. Если таких монстров много, каждый начинает нищадно дудосить дерево приводя к тормозам.
MMM
MPM<-----------M(A*)
MMM
И везде где я встречал говорится именно о случаях где путь есть. Но вот случаи что делать если пути нет, они замалчивают. Я пытаюсь строить путь до первой преграды, что и приводит к вышеупомянутым проблемам.
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
FiEctro писал: Ну да, в Юнити есть такая штука для навмеша типа отступы от стенок делать. А то любят они пушками сквозь двери светить.
Для случая с пушками в Сорсе году в 2015 выпускали хак для рендера. Но вообще вплотную не прижиматься никуда всем телом это просто инстинкт живого существа.
Цитата:
FiEctro писал: Проблема этих предсказаний в их производительности. А* работает хорошо когда гарантировано у тебя есть свободный путь, но вот если его нет надо уже городить какие то костыли. Если каждый монстр будет чекать всех остальных это может привести ещё к большим затупам среди них.
Когда у тебя 3000 энтитей и каждая чекает все остальные то да. В остальных случаях не должно быть проблем.
Crystallize писал: Для случая с пушками в Сорсе году в 2015 выпускали хак для рендера. Но вообще вплотную не прижиматься никуда всем телом это просто инстинкт живого существа.
Я говорю про пушки у монстров в руках.
Цитата:
Crystallize писал: Когда у тебя 3000 энтитей и каждая чекает все остальные то да.
3000 энтитей это крайне мало в современных движках. Но конкретно 3000 монстров с А* врядли кто то будет ставить в одном месте.
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
Crystallize писал: Хороший монстр должен пытаться предсказать поведение других монстров как в непосредственной близости от себя
Вообще-то когда толпа - все друг-другу мешают. Ничего предсказать невозможно.
Цитата:
FiEctro писал: Но коробки очень тормозные, у меня сферы
Как у тебя коробки тормозные ума не приложу. Ты что каждый кадр проверяешь миллион коробок?
Цитата:
FiEctro писал: Монстр где то снаружи уже не сможет построить к игроку путь, т.к. монстры которые окружили игрока являются преградой. A* не имеет решения.
Я же сказал, что монстров в качестве блокировщиков пути можно включать по желанию. Я это выключил. Т.е. построитель пути монстров не видит и не учитывает. Потому что пока тот для кого строился путь добежит - там уже 10 раз всё поменяется. К тому же если, это союзник и он увидит монстров - он переключится в режим боя. А там глядишь и путь освободится.
FiEctro писал: 3000 энтитей это крайне мало в современных движках.
В новых думах запрещают ставить на карту больше 12 кажется монстров в одном зале.
Цитата:
FiEctro писал: Я говорю про пушки у монстров в руках.
Ну я понял.
Добавлено 03-02-2024 в 22:49:
Цитата:
Дядя Миша писал: Вообще-то когда толпа - все друг-другу мешают. Ничего предсказать невозможно.
Толпа это крайний случай. Но когда два монстра сближаются под некоторым углом то они должны суметь разойтись ещё на некотором расстоянии, без необходимости одного уткнуться носом в бок другому. Один из них должен либо ускориться и пробежать наперерез, либо пройти за спиной.
Дядя Миша писал: Я же сказал, что монстров в качестве блокировщиков пути можно включать по желанию. Я это выключил. Т.е. построитель пути монстров не видит и не учитывает. Потому что пока тот для кого строился путь добежит - там уже 10 раз всё поменяется. К тому же если, это союзник и он увидит монстров - он переключится в режим боя. А там глядишь и путь освободится.
Так, а если не выключать? Как это можно оптимизировать?
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
Дядя Миша писал: А зачем им сближаться? Если на локации толпа и все настроены враждебно, игрок в последнюю очередь будет рассматривать как они друг-друга обходят.
Это может влиять на геймплей. Пока монстр тупит он легкая мишень для игрока. В той же кудваке была фича когда энфорсер мог добежать до кнопки и включить сирену после чего взрывались ящики и прилетали враждебные дроны.
Но я имел в виду скорее кейс когда ученые ходят по скриптовым путям. Да и в хл2 людей бесило когда напарники блокировали собой проходы.
Как правило при большом количестве мобов проблема в том что они сбиваются в длинную очередь и плетутся паровозиком за игроком.
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
30-01-2024 10:04
В остальных случаях не должно быть проблем.
