__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
Итак товарищи, я финализировал свой авторский алгоритм поиска пути.
При его разработке я сделал целую кучу допущений и активно опирался на уже имеющееся у меня представление навигационной сетки.
Допущения были следующие:
1. В подавляющем большинстве случаев монстру не надо прокладывать кратчайший маршрут через полкарты. Обычно это или маршрут по прямой, или маршрут буквой Г, если враг успел укрыться за углом. Нахождение подобного маршрута может быть решено крайне быстро.
2. В некоторых случаях, например если мы хотим попасть в какую-то точку сквозь узкий проём, допустимо реверсивное построение маршрута, в случае если прямой путь зафейлился.
3. Лучше просто зафейлить построение маршрута, чем пытаться найти путь, который возможно вообще не существует. При этом мы не должны привязываться ни к каким магическим константам или радиусам, в которых этот путь ищется. Иными словами фейл проблемного пути должен завершиться так же быстро, как и поиск существующего.
4. Пусть маршрут будет не слишком коротким, главное чтобы он построился быстро.
Исходя из этого я разработал алгоритм, основанный на движении по заданному направлению, сходимости и отскоке от препятствий, с вариативностью. Суть алгоритма сводится к следующему:
Каждую итерацию мы выбираем ноду, согласно направлению между текущей и финальной. Из четырёх нод мы можем выбрать только три.
Первой будет выбрана самая предпочтительная, затем - менее предпочтительная, затем самая нежелательная. Таким образом на каждом шаге у нас может образоваться три ноды. Первая нода используется в поиске текущего пути, вторая и третья (если они выбраны) добавляются к уже пройденному пути (текущий путь + вторая нода) и (текущий путь + третья нода), которые помещаются в массив частичных путей. Изначально частичный путь состоит всего лишь из одной ноды - стартовой. Ну и в процессе построения первого пути достраиваются остальные частичные пути. Дальше начинается самое интересное:
Если самый первый путь успешно достроился, то функция завершает свою работу и возвращает этот самый первый путь. Если же нет, то функция в цикле пытается достроить остальные частичные пути (попутно порождая новые на каждой потенциальной развилке). Вы конечно можете задаться вопросом, что подобное порождение всё новых и новых частичных путей никогда не закончится и всё это зависнет в бесконечном цикле. Да, но нет. Ведь мы с момента построения самого первого частичного пути помечаем ноды, в которых мы уже побывали, как бы ограничивая пространство. Таким образом, путь ведущий в никуда уже заведомо отсечён чем-то вроде виртуальной секущей плоскости (в роли которой выступает сам наш путь, завершившийся фейлом). Из-за этой любопытной особенности у алгоритма есть сходимость - только один путь из всех закончится успехом, остальные упруться в препятствия. Зная эту особенность нам нет нужды проверять абсолютно все частичные пути - первый, достигший конечной точки и будет валидным маршрутом. Этот момент ценен в качестве оптимизации. т.к. потенциально алгоритм может наплодить до десятка тысяч незаконченных путей, но если уже самый первый путь достигнет финальной точки, то нам уже нет нужды их проверять - мы справились. Так же в коде присутствует специальный лукап, чтобы строящийся путь не упёрся в препятствие уже на следующем шаге, что потенциально может привести не то чтобы к быстрому фейлу, а к весьма замысловатой и нереалистичной траектории маршрута, которая будет похожа на слишком длинную змейку, которая огибает сама себя.
Эта же штука сглаживает обход препятствий и ускоряет поиск маршрута.
Однако для сложных маршрутов она наоборот сама по себе является проблемой. К примеру с этой включённой эвристикой невозможен проход сложного лабиринта, или поиск пути буквой U, когда финальная точка находится сзади начальной, а начальная - соответственно в нише, выход из которой противоположен направлению между стартовой и конечной точкой. Поэтому я сделал данную эвристику отключаемой со стороны пользователя. Таким образом есть флаг глубокого поиск пути, который используется для скриптовых сцен, например, если монстру надо прорваться сквозь всю карту. Если же он просто следует за врагом, то выставлять этот флаг не надо - время поиска значительно ускориться.
Теперь мне надо финализировать отладочный режим поиска пути, чтобы провести углублённое юнит-тестирование и по его окончании, я выложу разные интересные скриншоты и комментарии. Повторюсь, главное свойство моего алгоритма - это поиск, на который требуется не более 0.001 секунды (или меньше). Вне зависимости от кол-ва нод на карте.
Всё же кажется что конвексный поиск который мы придумали был бы быстрее разрастающихся нод. Ну ладно, возможно такая реализация будет тоже хорошо работать, но конечно излишнее разрастание дерева это большой минус A* и причина тормозов. В конвексном поиске такого жесткого брутфорса уже не будет.
Надо будет уже у себя тогда поэкспериментировать.
Цитата:
Дядя Миша писал: Вы конечно можете задаться вопросом, что подобное порождение всё новых и новых частичных путей никогда не закончится и всё это зависнет в бесконечном цикле. Да, но нет. Ведь мы с момента построения самого первого частичного пути помечаем ноды, в которых мы уже побывали, как бы ограничивая пространство. Таким образом, путь ведущий в никуда уже заведомо отсечён чем-то вроде виртуальной секущей плоскости (в роли которой выступает сам наш путь, завершившийся фейлом).
А если мы тут впервые?
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
В режиме глубокого поиска мой алгоритм фейлит только в случае если пути действительно не существует. По крайней мере с обратной ситуацией я ещё не столкнулся. Но надо ещё на болотах рассчитать ноды для полноценного теста. Там их как раз 4.5 миллиона, вот и посмотрим.
Добавлено 08-02-2024 в 14:54:
Предварительные выводы:
1. Пока что подтверждается факт, что поиск со включённым режимом глубокого исследования никогда не фейлит.
2. В режиме глубокого исследования путь зачастую может выглядеть... странно. См аттач. В режиме быстрого поиска эвристика предотвращает появление подобных загогулин, но и вероятность фейла в случае сложного пути - кратно выше.
3. Производительность алгоритма прибита гвоздями к порядку следования нод и как следствие - к вектору направления поиска. Иными словами, поиск с севера на юг гораздо быстрее, чем поиск с востока на запад. Ну это к примеру, поскольку там целый ряд факторов. Заметным это становится тогда, когда мы выбираем сложный случай и сперва нацеливаем конечную точку в одну сторону (например на юго-запад), а потом на второй попытке целимся на северо-восток. Стартовая точка в обоих случаях остаётся идентичной.
И вот в одном случае у нас скорость работы может быть порядка 0.0005, а в другом - 0.27 секунды. Почему так происходит тоже понятно - алгоритм генерирует порядка десяти тысяч недостроенных путей и чем раньше он найдет правильный - тем быстрее завершится поиск. В первом случае валидный путь находится ближе к началу, во втором - ближе к концу, отсюда и такая чудовищная разница в скорости поиска. Однако всё вышесказанное относится только к предельным, максимально сложным случаям. Данные что я приводил выше не придуманы мной от балды, а получены на тестировании сталкеровской карты testers_mp_rostok.
Там, как вы знаете, по центру уровня стоит такой пятиэтажный недострой. Чем не лабиринт? И вот значит я тестировал выход с пятого этажа на один из краёв карты. И именно так и были получены эти значения. Впрочем подобный поиск пути в бою не нужен, только для скриптовых персонажей. Так что некритично. Важен сам факт, что по крайней мере пока доказать возможность фейла глубокого поиска мне не удалось, следовательно алгоритм работает правильно. В случае же типового поиска когда конечная и начальна точка лежат плюс-минус на одной плоскости (пусть даже и с препятствиями), поиск пути завершается примерно за 0.001 секунду, назависимо от направления поиска. Это глубокий. Обычный завершится ещё быстрее, хотя при таких значения это уже не имеет особого значения. Опять-таки сам факт, что поиск может сфейлить можно использовать для эмуляции умных и глупых монстров, например.
Дядя Миша писал: 2. В режиме глубокого исследования путь зачастую может выглядеть... странно. См аттач. В режиме быстрого поиска эвристика предотвращает появление подобных загогулин, но и вероятность фейла в случае сложного пути - кратно выше.
где аттач
Цитата:
Дядя Миша писал: Первой будет выбрана самая предпочтительная, затем - менее предпочтительная, затем самая нежелательная.
Надо найти ноды у стенок и запретить им быть предпочтительными.
О, круть.
Ну и на краях обрывов тоже неплохо бы им понизить приоритет.
Вообще задача борьбы с такими змейками перекликается с твоим советом мне про умную камеру от третьего лица. У тебя он строит буквы S а у меня игрок может пробежать кружком или ещё как и камера давай лети всё это за ним. Но у тебя это в сетку организовано. Получается лучше строить весь путь одним кадром и потом перебирать весь путь и смотреть какая самая дальняя нода доступна напрямую.
Странно, похоже на баг, А* не должен так работать.
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
Так это и не A*
Я ведь целую простыню накатал выше, что алгоритм мой собственный.
Да, он иногда выделывает затейливые вензеля, но в целом они предиктабельные.
Добавлено 08-02-2024 в 19:37:
Собственно, я что хотел сказать-то. Путь всё равно надо триангулировать, это касается результатов работы любого алгоритма.
Так вот срезать результаты этих вензелей - куда проще и практически ничего не стоит. Но это я как-нибудь потом, попозже сделаю.
Добавлено 08-02-2024 в 19:39:
Собственно результаты. Сложно сделать кадр так, чтобы в него одновременно попало и время работы графопостроителя и полный маршрут.
ZGreen
Так, а оригинальный сталкер разве меньше фпс даёт?
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
Дядя Миша писал: Так это и не A*
Я ведь целую простыню накатал выше, что алгоритм мой собственный.
Да, он иногда выделывает затейливые вензеля, но в целом они предиктабельные.
Хм, тогда хорошо. Интересно теперь проверить когда монстров будет ну хотя бы такое же количество как на картах в сталкере. Но в целом я согласен с тобой что строить пути прямо сквозь всю карту глупо с точки зрения гейм дизайна т.к. все монстры сразу сбегутся на игрока, а остальная карта будет пустой.
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
__________________
У котёнка мокрый нос и гладенькая шерсть, у него забавный хвост и быстрых лапок шесть. Две задних, две средних и две передних лапы, такая многоножка получилася у папы.
Он ученый — папа мой — зверушек изучает, гуляет по помойкам, ловит крыс и чаек. Две крысы белокрылые и чайки две унылые покрытые пупырчатою кожей лягушат без пёрышек тоскуют и ускакать спешат.
А ещё есть муравей большой размером с гуся он пугает всех зверей, и я его боюся, когда он ковыляет на лапках на своих.
И в двери ударяет, и начинает стих: Я — муравей, воды налей! Не меньше ведра, напиться мне пора!
| IP: 
07-02-2024 11:02
