NavMeshSurface и Алгортим поиска пути А*

Добрый день! Я новичок в Unity и я решил запрограммировать игрового бота для выполнения рада задач, и начал с реализации алгоритма поиска пути А*. Я хотел сделать все своими руками, не используя NavMeshAgent. Алгоритм написал, но он не учитывает объекты на карте, которые могут образовать препятствия на пути у бота. Я нашел такую штуку, как NavMeshSurface которая строит сетку путей, по которым может перемещаться бот, проблема в том, что нормально ее использовать может только NavMeshAgent (можно буквально в паре строк кода реализовать перемещение из точки А в точку Б), а как использовать построенную сетку для своего алгоритма я не знаю. Я пытался нагуглить подробности о NavMeshSurface, но так и не монял, можно ли сторонним скриптом использовать данные сгенерированные NavMeshSurface.
Можно ли вообще пользоваться сеткой путей (извиняюсь, если использую неправилные термины)? Или это привилегия NavMeshAgent?

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

0

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

1

Есть несколько алгоритмов поиска путей по графам, которые имеют общий принцип и представляют собой дополненную версию предыдущего алгоритма. По порядку это идёт примерно так:

1) Жадный алгоритм (ищет самое выгодное локальное решение задачи на данной итерации - в случае поиска по графам - ближайшую на данный момент вершину. Как недостаток - почти любое препятствие, которое представляет собой угол ловит путь в себя и алгоритм не работает). Делается это так: смотришь все клетки, через которые можно пройти и в каждой новой клетке ищешь клетку ближайшую к цели.

2) Поиск в ширину и алгоритмы Дейкстры - разницы в них я не вспомню, но она не очень большая. Они оба обходят любые препятствия, но тратят много ресурсов на больших картах. Суть алгоритмов: составляешь два массива - те, узлы, где можно пройти и те, которые уже пройдены. добавляешь стартовую точку в массив доступных. Далее, на каждой итерации выбираешь точку из массива, все точки, в которые из неё можно прийти добавляешь в доступные, а саму точку удаляешь из доступных и добавляешь в пройденные. Далее, как только при проверке на попалась точка старта - мы строим жадным алгоритмом из неё путь в начальную точку, проходя по массиву рассмотренных точке.

3) А* уже очень удобный и интересный алгоритм: Работает как и предыдуще алгоритмы, только при проверке из массива выбираются точки, которые удовлетворяют некой функции, которая называется эвристической (в широком смысле - это функция, которая позволяет отбросить заведомо ложные решения и их не рассматривать), в случае поиска пути простейшего, мы просто в первую очередь рассматриваем точки, которые лежат ближе к цели, а потом уже рассматриваем остальные, если путь не был найден.

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

0

Steroid да, о таком варианте я слышал, но тут действительно стрелять рейкастами будет топорно. NavMesh не буду использовать, тк хочу попробовать сделать свою реализацию, и вопрос в том, придется ли мне писать свой скрипт определения препятствий или можно как-то использовать NavMeshSurface
DarkPtect про эти алгоритмы я знаю, у меня в проекте уже реализован А* алгоритм, но весь расчет пути идет по transform.position точек в пространстве, но при этом он, пока, не видит препятствия.

Добавлено через 1 минуту
т.е. алгоритм находит путь от А до Б и строит маршрут, но при этом он игнорирует любые объекты на карте

0

Сообщение от justnomad алгоритм находит путь от А до Б и строит маршрут, но при этом он игнорирует любые объекты на карте

значит надо добавить проверку есть ли между А и Б чтото если есть то туда не идет

0