Сканер карты для AStar 3D

[Кирпи4]

Вобщем, столкнулся с такой проблемой, как автоматизация процесса создания вейпоинтов для Астара (использую его в движке как поиск пути до игрока или какой - либо другой точки). Много идей перебрал, но ни одна не спасает. Есть ли идеи, форумчане?

[Gector]

Сообщение от Кирпи4

Вобщем, столкнулся с такой проблемой, как автоматизация процесса создания вейпоинтов для Астара (использую его в движке как поиск пути до игрока или какой - либо другой точки). Много идей перебрал, но ни одна не спасает. Есть ли идеи, форумчане?

Если для стратегии:
Создать в максе карту и разделить ее на чилды. Их всего три- проходимый, непроходимый, вода(проходимый для одного типа юнитов). Сканирование проводится пиком сверху. При сканировании проверяется принадлежность каждой клетки(имя пикнутого меша). Таким образом получаем карту проходимости.
Если для стрелялки (или другой игры с закрытыми пространствами):
Создаешь модели узлов и линков сетки в максе. Узлы и линки - разные меши с разными именами. Пересечение проверяется с помощью meshesintersect. Во время скана проверяется пересечение узлов и линков после чего меши сетки удаляются.

[moka]

Второй вариант, чего-то ты замудрил. Это Waypoint'ы. Отлично подходит для indoor пространств, без большого наличия динамичных объектов.

А вот даже для стратегий, я бы пересмотрел, есть не мало весьма мощных подходов, используя коллизии отрезков. Если корректно реализовать, можно сделать весьма мощный и шустрый поиск пути в сложных уровнях..

[Gector]

Сообщение от MoKa

Второй вариант, чего-то ты замудрил. Это Waypoint'ы.

Это вейпойнты для ленивых))). Извращение конечно, но если не принципиально то можно и так.

А вот даже для стратегий, я бы пересмотрел, есть не мало весьма мощных подходов, используя коллизии отрезков. Если корректно реализовать, можно сделать весьма мощный и шустрый поиск пути в сложных уровнях..

Не совсем понял о чем ты.

[moka]

Астар, волновой, и подобные алгоритмы, используют сетку, где мир делиться на сетку, и весьма ограничен по размерам - больще сетка, больше искать нада. Можно конечно заюзать octree подход для более огромных миров, но снова, это весьма грубо.

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

С правильным подходом, можно реализовать весьма сложный и мощный поиск пути на такой основе..
Всё что нужно, это карта препядствий - отрезки.

[Кирпи4]

По поводу Астара должен с тобой несогласиться. 3D-версия астара юзает пивоты, которые надо коннектить спец. командой. Так что я думаю можно просто сделать небольшую прогу, где нужно пройти по уровню и самому всё расставить. Имхо, ручная расстановка по-моему всегда вздует автоматику. А с 3DS не работал, слишком он заумный и на вес тяжелый + нигде не могу найти крякнутую версию.

[moka]

Ээээ...

3D-версия астара юзает пивоты, которые надо коннектить спец. командой. Так что я думаю можно просто сделать небольшую прогу, где нужно пройти по уровню и самому всё расставить.

Это не Астар, а Waypoint'ы. Астар - это название алгоритма, а не сама суть поиска пути.

Имхо, ручная расстановка по-моему всегда вздует автоматику.

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

Учит мат. часть..

[Кирпи4]

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

[moka]

Ну если понимаешь разницу между алгоритмами, то тут можно понять не затрудняясь.

В Астаре, ты гуляешь по массиву, и вся логика отталкивается от этого.

А вот с вэйпоинтами, ты гуляешь по вп (вэйпоинтам) и от них к подсоединёным (каждый вп имеет 1 или более ссылки на другие вп). И нужно учитывать дистанцию каждой вариации пути, и далее сверять их, т.к. вариаций может быть много. Более детализированный путь может иметь 10 точек, а менее детализированный 5 и быть длиннее. Поэтому нада учитывать общую длину пути и в итоге выбирать по ней.
Это подобно волновому алгоритму, только используются именно точки, а не массив.

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

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

Я предлагаю, совсем другой подход.
Что является главным фактором поиска пути? Препятствия. Тут Астар или Волновой алгоритмы молодцы. Но учитывая детализацию и сам уровень, опять, сильно не замудришь, плюс подходит лишь для узкого круга жанров и т.п.
Если взять уровень, и описать его отрезками. Вот стоит у нас стена - это один отрезок. Чтобы её обойти, нужно провезти отрезок через неё, если пересекаются, провезти два к одному углу стены, и второй к другому от точки старта, при этом снова делать эту же проверку (это уже два пути развивается + возможные ещё перемещение), и так проводить от концов путей до точки назначения пока не достигнет.
Это динамическая генерация пути, основываясь лишь уровню. Не важно где находишься, не важно куда идёшь. Таким образом уровень может быть Очень сложный. Также можно учитывать любую динамику, и делать "локальные" вычисления рассчитанного пути, если на отрезок попадает динамический объект, или где-то изменился уровень, это всё можно пересчитать, т.к. есть путь.

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

[Кирпи4]

Ну смотри короч. Игра TPS, иговой интеллект уже написан (кстати планирую его в общее пользование выложить), а стены - больное место ИИ Вот я и планирую всякие тактики. Счас попробую реализовать твой алгоритм, но мне кажется хрен я его напишу...

[moka]

Начни с простого - обход одного отрезка. Сложнее будет когда отрезки соединены.