HLFX.Ru Forum Страницы (255): « Первая ... « 231 232 233 234 [235] 236 237 238 239 » ... Последняя »
Показать все 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)

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

Цитата:
Дядя Миша писал:
Ну на скриншоте во вложении, что по твоему? Не классический лабиринт?


Вот классический лабиринт:
https://cs12.pikabu.ru/post_img/201...38147937444.jpg

Цитата:
FiEctro писал:
(может даже выпуклые углы?)


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

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

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

Цитата:
FiEctro писал:
Вот классический лабиринт:

Самое любопытное то, что AStar без проблем его пройдет, а мой алгоритм скорее всего нет. Но в реальных играх такие лабиринты и не встречаются.

Цитата:
FiEctro писал:
Кстати да у нод на выпуклых углах интересная особенность что они всегда друг друга видят (за исключением карты коробки где все углы вогнутые), но там и препятствий нет).

Картинку нарисуй штоле.

Добавлено 05-02-2024 в 23:26:

Я тут поизучал имплементации AStar и обратил внимание на примечательный факт. Запуск алгоритма начинается с перемещения всех узлов в локальный массив. И потом они из него перетекают в другой массив.
Вот сейчас у меня на баллотах 4.5 миллиона нод и я буду их в какой-то массив пихать. Делать мне нечего.

__________________
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 в 20:40:

Цитата:
Дядя Миша писал:
Картинку нарисуй штоле.


Вот. Имеются ввиду ноды на выпуклых углах геометрии. Остальные игнорируются.

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

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

Ещё проще - ноды, где кол-во связей менее четырёх.
Да, ты прав, что-то в этом есть. Я подумаю над этим.

Можно замутить локальную трассировку между такими нодами.

Добавлено 06-02-2024 в 00:11:

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

Добавлено 06-02-2024 в 00:14:

А ведь действительно. Зачем мне бегать по этим нодам, я если я могу замутить в пространстве нод трассировку, как будто бы это не ноды, а реальная геометрия.
Скажем стрельнул по направлению к цели - ага, фейл, значит, стреляем между корнерами. Ну посмотрим. Идея интересная.

__________________
My Projects: download page

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

Цитата:

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

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

Ещё такая мысля что монстр может искать только самую дальнюю ноду в прямой его видимости в 2д пространстве. Дабы не ходить и облизывать каждый угол на пути к очевидной цели.

Цитата:
Дядя Миша писал:
Ещё проще - ноды, где кол-во связей менее четырёх.


Так у стены тоже меньше 4 связей.

Добавлено 06-02-2024 в 08:56:

Цитата:
Дядя Миша писал:
Скажем стрельнул по направлению к цели - ага,


Ещё можно стрелять толщиной с бокс монстра. Ведь таракан например может пролезть там где не пролезет гаргантьюа. Промежуточные ноды могут хранить информацию о высоте потолка, и может даже проверять её, вдруг там сверху дверь опускается?

Добавлено 06-02-2024 в 09:23:

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

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

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

Цитата:
FiEctro писал:
Так у стены тоже меньше 4 связей.

всё что меньше четырёх связей - это какие-то препятсвия\проёмы.
И оно требует проверки.

Цитата:
FiEctro писал:
Ещё можно стрелять толщиной с бокс монстра

Ты сейчас очень сильно удивишься, но нода и так уже толщиной с ббокс монстра.

Цитата:
FiEctro писал:
вдруг там сверху дверь опускается

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

Добавлено 06-02-2024 в 09:25:

Цитата:
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 06-02-2024 в 06:25:

Цитата:
Дядя Миша писал:
Зачем мне бегать по этим нодам, я если я могу замутить в пространстве нод трассировку, как будто бы это не ноды, а реальная геометрия.


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

Цитата:
Дядя Миша писал:
Ты сейчас очень сильно удивишься, но нода и так уже толщиной с ббокс монстра.


Так это для каждого монстра тогда отдельную сетку строить. Жирно.

Цитата:
Дядя Миша писал:
Не делать таких узких коридоров, очевидно же.


Так такой же коридор удовлетворяет проходимости ббокса, но соосность нод всё ломает.

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

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

Поизучал вчера навмешы в юнити и UE3. Ну что сказать. У меня сложилось впечатление, что навмешы начали использовать вот как раз в силу невозможности оптимизации AStar. При этом огребли проблем, например с расстановкой обстаклей, которые теперь в этих мешах должны выгрызать дыры (ну а как ещё?). Да и сам факт, что пространство больше не квантизировано, мешает сохранять какую-то дополнительную информацию. Ну скажем я бы мог в нодах на берегу водоёма установить подсказку - форсирование водной преграды. С навмешами, понятно, такое уже не прокатит.

Добавлено 06-02-2024 в 09:34:

Цитата:
FiEctro писал:
а в том что ноды на углах видят друг друга всегда, это довольно забавная особенность геометрии используются много где

Поздравляю, у тебя появилось базовое понимание конвексной геометрии.

Цитата:
FiEctro писал:
Так это для каждого монстра тогда отдельную сетку строить. Жирно.

Ну а что делать? Не для каждого конечно. Ну вот в халфе были клипхуллы - три штуки. Хватало.

Цитата:
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 06-02-2024 в 06:36:

Цитата:
Дядя Миша писал:
Что ты сделаешь с регулярной сеткой?


Локальные сетки. Например если в геометрию влазит нода но она не соосна с регулярной сеткой, можно создать для неё отдельную группу с оффсетом.

Цитата:
Дядя Миша писал:
Поздравляю, у тебя появилось базовое понимание конвексной геометрии.


Да это понятно, я же сразу писал что углы конвексные. Просто я не знал что так пути искать можно.

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

Отправлено Crystallize 06-02-2024 в 07:06:

Цитата:
Дядя Миша писал:
Не делать таких узких коридоров, очевидно же.

Юзеры скосят калидор и когда монстр откажется идти, решат что это глюк движка.

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

Цитата:
FiEctro писал:
Локальные сетки. Например если в геометрию влазит нода но она не соосна с регулярной сеткой, можно создать для неё отдельную группу с оффсетом.

Да, давай усложняй, чтобы каждый запрос на генерацию пути обрабатывался минимум 10 секунд.

Цитата:
Crystallize писал:
Юзеры скосят калидор и когда монстр откажется идти, решат что это глюк движка.

Вообще-то сетка визуализируется.

Добавлено 06-02-2024 в 11:45:

Можно попробовать ещё вот какую штуку. Сделать из карты нодов - двухмерное BSP-дерево и портализовать его. Тогда, соответственно поиск пути сведётся к 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'

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

Цитата:
Дядя Миша писал:
Да, давай усложняй, чтобы каждый запрос на генерацию пути обрабатывался минимум 10 секунд.


Какая разница если сетки собираются в оффлайне? А в игре они уже единым массивом. Это только вопрос расстановки нод.

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



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

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

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

Но скажем поиск пути, когда враг забежал за угол или за два угла - вот это всегда работает чётко. А ведь именно это в играх и бесит больше всего.
Игрок за угол забежал - монстры его потеряли. Так быть точно не должно.

Добавлено 06-02-2024 в 14:09:

Постепенно приходит понимание, что алгоритм полного и честного поиска пути через перебор всех существующих ячеек на данный момент мне просто-напросто не нужен. В первой-второй кваке монстры вообще искали игрока тыкаясь в примерном направлении, куда он убежал и останавливаясь на каждом шагу. И ничего, игроки им эту тупость вполне прощали.
Моя реализация позволяет успешно огибать не слишком сложные препятствия, вплоть до поиска пути с одного этажа на другой.
Зато скорость поиска такого пути - мгновенная. Ну почти.
Так что я буду оттачивать и отлаживать свой алгоритм.

Добавлено 06-02-2024 в 15:33:

__________________
My Projects: download page

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

Цитата:

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

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

Дядя Миша
А как кстати боты в той же кваке третьей путь ищут? Там они довольно бодро бегают и не спотыкаются.

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

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

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

Добавлено 06-02-2024 в 16:23:

Я ведь поначалу и сам хотел сделать нечто подобное, но оно не подружится с полигональной геометрией. Хотя я честно три недели копал в этом направлении.

__________________
My Projects: download page

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

Цитата:

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

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