Кстати да у нод на выпуклых углах интересная особенность что они всегда друг друга видят (за исключением карты коробки где все углы вогнутые), но там и препятствий нет). По ним реально пути можно строить. Странно что нигде об этом не упоминается, это в разы бы уменьшило количество необходимых нод если речь идёт именно о простом поиске пути.
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
Самое любопытное то, что AStar без проблем его пройдет, а мой алгоритм скорее всего нет. Но в реальных играх такие лабиринты и не встречаются.
Цитата:
FiEctro писал: Кстати да у нод на выпуклых углах интересная особенность что они всегда друг друга видят (за исключением карты коробки где все углы вогнутые), но там и препятствий нет).
Картинку нарисуй штоле.
Добавлено 05-02-2024 в 23:26:
Я тут поизучал имплементации AStar и обратил внимание на примечательный факт. Запуск алгоритма начинается с перемещения всех узлов в локальный массив. И потом они из него перетекают в другой массив.
Вот сейчас у меня на баллотах 4.5 миллиона нод и я буду их в какой-то массив пихать. Делать мне нечего.
Вот. Имеются ввиду ноды на выпуклых углах геометрии. Остальные игнорируются.
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
Ещё проще - ноды, где кол-во связей менее четырёх.
Да, ты прав, что-то в этом есть. Я подумаю над этим.
Можно замутить локальную трассировку между такими нодами.
Добавлено 06-02-2024 в 00:11:
A* почти во всех движках запускается в фоне, никто не может гарантировать что путь будет рассчитан за приемлимое время.
Мда.
Добавлено 06-02-2024 в 00:14:
А ведь действительно. Зачем мне бегать по этим нодам, я если я могу замутить в пространстве нод трассировку, как будто бы это не ноды, а реальная геометрия.
Скажем стрельнул по направлению к цели - ага, фейл, значит, стреляем между корнерами. Ну посмотрим. Идея интересная.
Ещё такая мысля что монстр может искать только самую дальнюю ноду в прямой его видимости в 2д пространстве. Дабы не ходить и облизывать каждый угол на пути к очевидной цели.
Цитата:
Дядя Миша писал: Ещё проще - ноды, где кол-во связей менее четырёх.
Так у стены тоже меньше 4 связей.
Добавлено 06-02-2024 в 08:56:
Цитата:
Дядя Миша писал: Скажем стрельнул по направлению к цели - ага,
Ещё можно стрелять толщиной с бокс монстра. Ведь таракан например может пролезть там где не пролезет гаргантьюа. Промежуточные ноды могут хранить информацию о высоте потолка, и может даже проверять её, вдруг там сверху дверь опускается?
Добавлено 06-02-2024 в 09:23:
И ещё такой вопрос, как строятся ноды в таких случаях? Т.е. когда у нас есть место куда гарантировано попадает нода, но её позиция не совпадает с общей сеткой?
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
Дядя Миша писал: Зачем мне бегать по этим нодам, я если я могу замутить в пространстве нод трассировку, как будто бы это не ноды, а реальная геометрия.
Дело не в трассировке, а в том что ноды на углах видят друг друга всегда, это довольно забавная особенность геометрии используются много где. Но вот в поиске пути не встречал, наверняка наверное уже кто то догадался, но найти похожую реализацию пока не удалось.
Цитата:
Дядя Миша писал: Ты сейчас очень сильно удивишься, но нода и так уже толщиной с ббокс монстра.
Так это для каждого монстра тогда отдельную сетку строить. Жирно.
Цитата:
Дядя Миша писал: Не делать таких узких коридоров, очевидно же.
Так такой же коридор удовлетворяет проходимости ббокса, но соосность нод всё ломает.
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
Поизучал вчера навмешы в юнити и UE3. Ну что сказать. У меня сложилось впечатление, что навмешы начали использовать вот как раз в силу невозможности оптимизации AStar. При этом огребли проблем, например с расстановкой обстаклей, которые теперь в этих мешах должны выгрызать дыры (ну а как ещё?). Да и сам факт, что пространство больше не квантизировано, мешает сохранять какую-то дополнительную информацию. Ну скажем я бы мог в нодах на берегу водоёма установить подсказку - форсирование водной преграды. С навмешами, понятно, такое уже не прокатит.
Добавлено 06-02-2024 в 09:34:
Цитата:
FiEctro писал: а в том что ноды на углах видят друг друга всегда, это довольно забавная особенность геометрии используются много где
Поздравляю, у тебя появилось базовое понимание конвексной геометрии.
Цитата:
FiEctro писал: Так это для каждого монстра тогда отдельную сетку строить. Жирно.
Ну а что делать? Не для каждого конечно. Ну вот в халфе были клипхуллы - три штуки. Хватало.
Цитата:
FiEctro писал: Так такой же коридор удовлетворяет проходимости ббокса, но соосность нод всё ломает.
Дядя Миша писал: Что ты сделаешь с регулярной сеткой?
Локальные сетки. Например если в геометрию влазит нода но она не соосна с регулярной сеткой, можно создать для неё отдельную группу с оффсетом.
Цитата:
Дядя Миша писал: Поздравляю, у тебя появилось базовое понимание конвексной геометрии.
Да это понятно, я же сразу писал что углы конвексные. Просто я не знал что так пути искать можно.
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
FiEctro писал: Локальные сетки. Например если в геометрию влазит нода но она не соосна с регулярной сеткой, можно создать для неё отдельную группу с оффсетом.
Да, давай усложняй, чтобы каждый запрос на генерацию пути обрабатывался минимум 10 секунд.
Цитата:
Crystallize писал: Юзеры скосят калидор и когда монстр откажется идти, решат что это глюк движка.
Вообще-то сетка визуализируется.
Добавлено 06-02-2024 в 11:45:
Можно попробовать ещё вот какую штуку. Сделать из карты нодов - двухмерное BSP-дерево и портализовать его. Тогда, соответственно поиск пути сведётся к Portal Flow. Правда репортализацию придётся выполнять каждый раз при обновлении обстаклей, что не слишком хорошо.
Дядя Миша писал: Да, давай усложняй, чтобы каждый запрос на генерацию пути обрабатывался минимум 10 секунд.
Какая разница если сетки собираются в оффлайне? А в игре они уже единым массивом. Это только вопрос расстановки нод.
Пришла такая мысля что ноды например можно расставлять по нормали от стены. Тогда они будут учитывать повороты корридоров. Однако это уже конечно не регулярная сетка, и в местах стыков соседей надо определять несколько иначе.
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
Потестировал свою конструкцию в сталкере. Ну в принципе норм.
Скорость рассчёта весьма быстрая, если речь только о поиске пути при наличии визуального контакта, то мой алгоритм почти всегда справляется.
Если же речь о том, чтобы монстр честно прорвался с одного края карты на другой, пока его никто не видит - то увы. Скорее всего сфейлит.
Но скажем поиск пути, когда враг забежал за угол или за два угла - вот это всегда работает чётко. А ведь именно это в играх и бесит больше всего.
Игрок за угол забежал - монстры его потеряли. Так быть точно не должно.
Добавлено 06-02-2024 в 14:09:
Постепенно приходит понимание, что алгоритм полного и честного поиска пути через перебор всех существующих ячеек на данный момент мне просто-напросто не нужен. В первой-второй кваке монстры вообще искали игрока тыкаясь в примерном направлении, куда он убежал и останавливаясь на каждом шагу. И ничего, игроки им эту тупость вполне прощали.
Моя реализация позволяет успешно огибать не слишком сложные препятствия, вплоть до поиска пути с одного этажа на другой.
Зато скорость поиска такого пути - мгновенная. Ну почти.
Так что я буду оттачивать и отлаживать свой алгоритм.
Дядя Миша
А как кстати боты в той же кваке третьей путь ищут? Там они довольно бодро бегают и не спотыкаются.
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
Так я же объяснял - через портализацию. Это спайка технологий трёхмерного навмеша, фиксированных хуллов и portal flow. Впрочем с обстаклями там дело обстоит так же как грустно как и с классическими навмешами. Но для кваки некритично, там из обстаклей только двери, которые может открыть любой бот или игрок.
Добавлено 06-02-2024 в 16:23:
Я ведь поначалу и сам хотел сделать нечто подобное, но оно не подружится с полигональной геометрией. Хотя я честно три недели копал в этом направлении.
| IP: 
05-02-2024 20:06
