FiEctro писал: Что такое Иерархический поиск А* (на 38 секунде)?
Я ещё не впилился в эту тему - занимаюсь совершенно другими вещами.
Но беглый осмотр алгоритма A* как бы подсказывает, что он дико медленный. Кармак, к слову юзал portal flow для навигации. Изящно, элегантно, но к сожалению с полигональной геометрией не подружишь.
Да и оно точно так же требует замкнутого уровня для правильной работы.
Зато скоро нахождения пути чуть ли не нулевая.
Помнишь как быстро строился путь к дырке на карте?
Цитата:
FiEctro писал: Так это всю карту перебрать надо?
Нет, зачем всю карту? Просто помечать только те ноды, которые перескаются.
Цитата:
FiEctro писал: по карте постоянно что то да перемещается
Единственное что постоянно перемещается по карте - это игрок. Всё остальное по ситуации.
Дядя Миша писал: Да и оно точно так же требует замкнутого уровня для правильной работы.
Цитата:
Дядя Миша писал: Помнишь как быстро строился путь к дырке на карте?
Сам себе противоречишь. Какой же уровень замкнутый если там дырка?
Цитата:
Дядя Миша писал: Кармак, к слову юзал portal flow для навигации. Изящно, элегантно,
Тут конечно не поспоришь. Но навигация в кваке работает у монстров мягко говоря не очень. Они тупят порой когда у них игрок в прямой видимости. Например в этом месте:
И валве всеравно пришлось расставлять ноды вручную.
Цитата:
Дядя Миша писал: Но беглый осмотр алгоритма A* как бы подсказывает, что он дико медленный.
Ну может для компов времен первой кваки да, медленный, НО сейчас я бы сказал что как минимум в моём случае перебор пересечений (как в твоём случае коробок) отжирает куда больше ресурсов. И я не очень понимаю как это правильно оптимизировать.
Ну тоесть у нас есть цикл который спавнит несколькр десятков тысяч нод, и каждый такт (или с таймером) проверяет пересекается какая то из нод или нет. Это уже жирно. Потом нам надо записать это в массив всё это для того чтобы скормить это A*.
Это тоже жирно. Если мы будем как ты пишешь перебирать заранее этот массив чтобы определить что перезаписалось а что нет, это ещё хуже.
Объясни мне пожалуйста как кухарке, пошагово, как правильно организовать этот момент?
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
FiEctro писал: Сам себе противоречишь. Какой же уровень замкнутый если там дырка?
Я про сам принцип поиска. Если бы в уровне была дырка, монстр бы искал кратчайший путь через внешний лиф и вываливался бы на ружу. Ну или просто долбился бы в эту щель.
Цитата:
FiEctro писал: Но навигация в кваке работает у монстров мягко говоря не очень
Так это появилось только у ботов третьей кваки. Но ты прав, механизм существовал уже для ботов первой, написанный на QC.
Цитата:
FiEctro писал: перебор пересечений (как в твоём случае коробок) отжирает куда больше ресурсов.
А зачем перебирать пересечения? В идеале тебе надо найти кластер и там проверить ну штук 10 нод. А ты штожы - все перебираешь?
Цитата:
FiEctro писал: Ну тоесть у нас есть цикл который спавнит несколькр десятков тысяч нод
Нет, это предрассчитанные ноды, как лайтмапа. Геометрия-то не меняется.
Дядя Миша писал: А зачем перебирать пересечения? В идеале тебе надо найти кластер и там проверить ну штук 10 нод. А ты штожы - все перебираешь?
Что то не сходится, у тебя в пределах видимости на скриншоте куда больше 10 нод. Помню была карта с амбаром, так там вообще их тысячи.
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
Ну у тебя скриншот был там дом похожий на амбар в середине поля стоял. Уже не помню где он был. Искать не стал.
Цитата:
Дядя Миша писал: Я и говорю - нод на карте миллионы могут быть. Ты что, собрался каждый кадр все ноды проверять на пересечение?
Ну в пределах видимости хотя бы, но это тоже не мало. А какой путь искать в пределах 10 нод? Это несколько метров вокруг игрока.
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
FiEctro писал: Ну в пределах видимости хотя бы, но это тоже не мало. А какой путь искать в пределах 10 нод? Это несколько метров вокруг игрока.
Я ничего не говорил про пределы видимости вокруг игрока.
Я говорил что ноды должны быть помещены в какие-то кластеры для быстрого поиска текущей. Ну вот как к примеру узнать, на какой именно ноде стоит монстр? Для простоты предположим что ноды несолидные и используются только для построения пути.
Дядя Миша писал: Я говорил что ноды должны быть помещены в какие-то кластеры для быстрого поиска текущей. Ну вот как к примеру узнать, на какой именно ноде стоит монстр? Для простоты предположим что ноды несолидные и используются только для построения пути.
Ну опять же, игрок и монстр находятся в разных кластерах, как они увидят друг друга и построют путь?
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
Ты неверно интерпретируешь слово кластеры. Это просто ускоряющая структура типа того же AABB-дерева для быстрого поиска конкретной ноды в трёхмерном пространстве. Только и всего.
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
Дядя Миша писал: FiEctro когда займусь навигацией всё расскажу и покажу.
Так ты же уже делал навигацию на картах сталкера или просто тогда не доделал?!
__________________
Kiss my ass if you don't like my Ford!
------------------------------------------ Game Area51 Update 1
First Person Shooter Released Jul 24, 2017
The game is a 3d shooter with the elements of the quest.
Crystallize писал: grass demo наверное, где многослойный ландшафт и озеро.
Да вроде там пол ровный был, ещё на крыше дома ноды были.
Цитата:
Дядя Миша писал: FiEctro когда займусь навигацией всё расскажу и покажу.
К тому времени я сам уже разберусь.
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
| IP: 
29-01-2024 11:59
