Навмешы я и не делал никогда. Я просто обратил внимание, что навмешы делаются из этих же самых нодов. Путём аналитической склейки нодов в примитивы. Вот этот шаг я просто не стал выполнять. Потому что ноды оказалось дико удобно выключать перекрывающими объемами, что с навмешем уже не проделаешь. Да я же серию картинок приводил.
У нодов единственный минус - то что их много, а так они даже удобнее в работе.
SNMetamorph писал: Так ты в итоге от навмешей отказался в пользу обычных нодов? Не особо понимаю какой концепт на текущий момент времени.
Работа нодов большой плотности ничем не отличается от навмешей. Единственный минус это как говорил ДМ что нпц ходят как по рельсам, но это можно сгладить.
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
Такую штуку ещё нашел, но пока не выкурил как это работает.
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
Забавно. У меня изначально мысль работала как раз в направлении vector field pathfinding, я даже другие варианты и не рассматривал, мне этот казался самым очевидным. Собственно, именно его я сейчас и делаю.
Добавлено 05-02-2024 в 09:43:
Причём я вообще не штудировал никакой литературы на этот счёт, просто опирался на собственный опыт.
Дядя Миша писал: Забавно. У меня изначально мысль работала как раз в направлении vector field pathfinding, я даже другие варианты и не рассматривал, мне этот казался самым очевидным. Собственно, именно его я сейчас и делаю.
Расскажи хоть кратко как это устроено.
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
Досмотрел видео. Ну как обычно, начали за здравие. Какая нахрен карта градиентов в рантайме? А если у меня четыре миллиона нодов?
Нет, у меня иной принцип.
Добавлено 05-02-2024 в 09:53:
Я не планирую строить никакие карты градиентов. Поиск пути должен закончится быстрее, чем будет построена эта карта.
Добавлено 05-02-2024 в 11:13:
Итак, первые опыты. Когда я говорю "первые опыты", это означает, что создан механизм линковки нодов в AABB-дерево, создана пользовательская команда для построения пути из глаз игрока до точки прицела, создан механизм визуализации, которые показывает построенный нами путь, раскрашивая его градиентом от красного (начало) до зелёного (конец),
и написан простейший эвристический анализатор, задающий вектор пути для поиска без перебора. Посмотрим как это выглядит:
На последней картинке путь упирается в препятствие, не в силах его обогнть - алгоритм пока что такое не умеет.
Добавлено 05-02-2024 в 11:19:
Теперь, собственно, как это работает. У каждой ноды есть четыре соседа.
Они идут в строгом порядке, сосед с индексом 0 - это левая нода, сосед с индексом 1 - передняя, итогдалие. Т.е. по часовой стрелке.
Зная эту особенность, мы всегда можем вычесть позицию конечной ноды из текущей, нормализовать получившийся вектор и при помощи нехитрой функции, превратить направление в индекс ноды, которую нам следует выбрать. Именно поэтому путь сперва прямой, а затем начинает заворачивать. Я не берусь утверждать, что найденный путь является кратчайшим, но это не имеет никакого значения. Потому что живые существа далеко не всегда выбирают самый кратчайший путь.
Достаточно чтобы он был приемлимым.
Добавлено 05-02-2024 в 12:07:
То что приведено на рисунках выше - это просто прямой путь.
Если он упрётся в препятствие, то всё закончится. Добавим к алгоритму так же поиск ближайшего пути с учётом проверки на наличие уже пройденных нод. Ну чтобы путь случайно не закольцевался. Пусть лучше сфейлит.
Как видите - это вполне неплохо работает. Препятствия огибаются. На третьем скриншоте изображён фейл - я хотел попасть в самую дальнуюю комнатку, алгоритм упёрся в угол и всё закончилось. Чтобы избежать такого поведения, нам надо сохранять лишь часть нашего пути и делать бэкапы в спорных местах. Спорное место - это когда мы упёрлись в блокирующую ноду, очевидно. Учитывая организацию нод в пространстве - у нас есть фактически бинарный выбор. Мы можем попробовать обойти препятствие либо слева, либо справа.
Добавлено 05-02-2024 в 12:09:
Прикол в том, что в поиске пути при подобной организации нод есть всего-навсего четыре варианта действий:
1. прямой и тупой поиск.
2. огибание препятствия по вектору
3. огибание препятствия по отрицательному вектору
4. настолько сложная конфигурация лабиринта, что надо вообще идти назад.
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.
Дядя Миша
Я вот что подумал, а что если узкие проходы помечать как более приоритетные? Конечно в туннеле в 1 шаг делать это бессмысленно, но в твоём бы случае думаю это сильно помогло. Ведь даже человек бессознательно ищет как первую цель именно первый дверной проём. Что то в этом есть.
Ещё появилась такая мысля что для предрасчитаной статичной сетки можно и предрасчитать A*. Но это пока просто мысли, я ещё не обдумывал всё.
Дополню что можно сделать перебор по построению пути между комнатками, т.е. искать заранее не объект, а комнату относительно другой. А вот уже игрок будет искать ближайшее A* дерево т.к. ему ещё до начала поиска известно в какой комнате находится цель и в какой он сам.
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
FiEctro писал: Ещё появилась такая мысля что для предрасчитаной статичной сетки можно и предрасчитать A*
Градиенты можно посчитать. Чтобы алгоритм заведомо не лез в тупики.
Это неплохая оптимизация, но я пока что вожусь со своим велосипедом.
Цитата:
FiEctro писал: Я вот что подумал, а что если узкие проходы помечать как более приоритетные?
От узкого прохода до нашей цели может быть ещё сколько угодно нод.
Само хождение по нодам весьма быстрое, поэтому на данный момент я пока не вижу смысла оптимизировать этот момент. Ну разве что столкнёмся с ситуацией, когда кишка на полкарты ведет в заведомый тупик, но опять же - это надо профилировать.
То что на картинке - это ты для себя переоткрыл portal flow, да. Хорошая штука, но ей нужны навмешы, вместо нодов. А я уже говорил, что пока принял решение остановиться на нодах.
FiEctro писал: Конечно в туннеле в 1 шаг делать это бессмысленно
Кстати да, пришла такая мысля что в такой ситуации как опорные точки вместо проёмов можно использовать повороты туннеля (может даже выпуклые углы?). Попробуй лабиринт сделать классический. Интересно как у тебя будет работать.
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
Эта штука очень сильно зависит от начального и конечного направления.
Впрочем, если не искать путь сквозь всю карту, то она нормально справляется. Но мне не нравится, что есть заведомо фейловые кейсы, их не должно быть.
Добавлено 05-02-2024 в 22:57:
Цитата:
FiEctro писал: Попробуй лабиринт сделать классический.
Ну на скриншоте во вложении, что по твоему? Не классический лабиринт?
| IP: 
04-02-2024 13:57
