HLFX.Ru Forum Страницы (255): « Первая ... « 230 231 232 233 [234] 235 236 237 238 » ... Последняя »
Показать все 3825 сообщений этой темы на одной странице

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)

Отправлено Дядя Миша 04-02-2024 в 13:57:

Цитата:
FiEctro писал:
Так, а если не выключать?

Тогда будет логическое противоречие.

У A* как я понял главная проблема в том, что он в принципе не допускает возможности фейла. Тогда как в играх это сплошь и рядом.

__________________
My Projects: download page

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

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'

Отправлено SNMetamorph 05-02-2024 в 00:36:

Так ты в итоге от навмешей отказался в пользу обычных нодов? Не особо понимаю какой концепт на текущий момент времени.

__________________
Мой сайт
Xash3D Modding Discord

Отправлено Дядя Миша 05-02-2024 в 05:38:

Навмешы я и не делал никогда. Я просто обратил внимание, что навмешы делаются из этих же самых нодов. Путём аналитической склейки нодов в примитивы. Вот этот шаг я просто не стал выполнять. Потому что ноды оказалось дико удобно выключать перекрывающими объемами, что с навмешем уже не проделаешь. Да я же серию картинок приводил.
У нодов единственный минус - то что их много, а так они даже удобнее в работе.

__________________
My Projects: download page

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

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'

Отправлено FiEctro 05-02-2024 в 06:06:

Цитата:
Дядя Миша писал:
У A* как я понял главная проблема в том, что он в принципе не допускает возможности фейла. Тогда как в играх это сплошь и рядом.


Да в этом и проблема. Его начинает раздувать на всё свободное пространство.
Кстати ты так и не рассказал что там за кластеры у тебя.

Кстати помимо A* можешь чекнуть ещё следующие методы:

Dijkstra's Algorithm (Алгоритм Дейкстры)
Breadth-First Search (Поиск в ширину)
Probabilistic Roadmaps (PRM)
Visibility Graphs (Граф видимости)
Cell Decomposition

Цитата:
SNMetamorph писал:
Так ты в итоге от навмешей отказался в пользу обычных нодов? Не особо понимаю какой концепт на текущий момент времени.


Работа нодов большой плотности ничем не отличается от навмешей. Единственный минус это как говорил ДМ что нпц ходят как по рельсам, но это можно сгладить.

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

Отправлено Дядя Миша 05-02-2024 в 06:26:

Цитата:
FiEctro писал:
Кстати ты так и не рассказал что там за кластеры у тебя.

Да это я так неудачно выразился штоле, а ты прям зацепился за это слово.

__________________
My Projects: download page

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

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'

Отправлено FiEctro 05-02-2024 в 06:39:



Такую штуку ещё нашел, но пока не выкурил как это работает.

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

Отправлено Дядя Миша 05-02-2024 в 06:43:

Забавно. У меня изначально мысль работала как раз в направлении vector field pathfinding, я даже другие варианты и не рассматривал, мне этот казался самым очевидным. Собственно, именно его я сейчас и делаю.

Добавлено 05-02-2024 в 09:43:

Причём я вообще не штудировал никакой литературы на этот счёт, просто опирался на собственный опыт.

__________________
My Projects: download page

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

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'

Отправлено FiEctro 05-02-2024 в 06:45:

Цитата:
Дядя Миша писал:
Забавно. У меня изначально мысль работала как раз в направлении vector field pathfinding, я даже другие варианты и не рассматривал, мне этот казался самым очевидным. Собственно, именно его я сейчас и делаю.


Расскажи хоть кратко как это устроено.

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

Отправлено Дядя Миша 05-02-2024 в 09:09:

Досмотрел видео. Ну как обычно, начали за здравие. Какая нахрен карта градиентов в рантайме? А если у меня четыре миллиона нодов?
Нет, у меня иной принцип.

Добавлено 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. настолько сложная конфигурация лабиринта, что надо вообще идти назад.

__________________
My Projects: download page

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

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'

Отправлено (_-=ZhekA=-_) 05-02-2024 в 09:12:

Цитата:
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.

http://button.moddb.com/download/medium/125531.png

Отправлено FiEctro 05-02-2024 в 10:58:

Дядя Миша
Я вот что подумал, а что если узкие проходы помечать как более приоритетные? Конечно в туннеле в 1 шаг делать это бессмысленно, но в твоём бы случае думаю это сильно помогло. Ведь даже человек бессознательно ищет как первую цель именно первый дверной проём. Что то в этом есть.

Ещё появилась такая мысля что для предрасчитаной статичной сетки можно и предрасчитать A*. Но это пока просто мысли, я ещё не обдумывал всё.


Дополню что можно сделать перебор по построению пути между комнатками, т.е. искать заранее не объект, а комнату относительно другой. А вот уже игрок будет искать ближайшее A* дерево т.к. ему ещё до начала поиска известно в какой комнате находится цель и в какой он сам.

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

Отправлено Дядя Миша 05-02-2024 в 12:15:

Цитата:
FiEctro писал:
Ещё появилась такая мысля что для предрасчитаной статичной сетки можно и предрасчитать A*

Градиенты можно посчитать. Чтобы алгоритм заведомо не лез в тупики.
Это неплохая оптимизация, но я пока что вожусь со своим велосипедом.

Цитата:
FiEctro писал:
Я вот что подумал, а что если узкие проходы помечать как более приоритетные?

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

То что на картинке - это ты для себя переоткрыл portal flow, да. Хорошая штука, но ей нужны навмешы, вместо нодов. А я уже говорил, что пока принял решение остановиться на нодах.

__________________
My Projects: download page

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

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'

Отправлено Дядя Миша 05-02-2024 в 16:32:

Ну, собственно. Впрочем, он частенько фейлит.
Буду думать.

Добавлено 05-02-2024 в 19:32:

Тест на реальных уровнях:

__________________
My Projects: download page

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

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'

Отправлено FiEctro 05-02-2024 в 19:54:

По скриншотам вроде всё ок?

Цитата:
FiEctro писал:
Конечно в туннеле в 1 шаг делать это бессмысленно


Кстати да, пришла такая мысля что в такой ситуации как опорные точки вместо проёмов можно использовать повороты туннеля (может даже выпуклые углы?). Попробуй лабиринт сделать классический. Интересно как у тебя будет работать.

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

Отправлено Дядя Миша 05-02-2024 в 19:57:

Цитата:
FiEctro писал:
По скриншотам вроде всё ок?

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

Добавлено 05-02-2024 в 22:57:

Цитата:
FiEctro писал:
Попробуй лабиринт сделать классический.

Ну на скриншоте во вложении, что по твоему? Не классический лабиринт?

__________________
My Projects: download page

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

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'
Временная зона GMT. Текущее время 02:03. Страницы (255): « Первая ... « 230 231 232 233 [234] 235 236 237 238 » ... Последняя »
Показать все 3825 сообщений этой темы на одной странице

На основе vBulletin версии 2.3.0
Авторское право © Jelsoft Enterprises Limited 2000 - 2002.
Дизайн и программирование: Crystice Softworks © 2005 - 2024