Алгоритм поиска пути в Unity [3]

Простая карта игровой локации

Доделал алгоритм формирования графа путей между укрытиями на игровой карте. Теперь нужно посмотреть его в действии. На картинке выше представлен примерный игровой уровень. Посмотрим, как отработает алгоритм на таком небольшом тестовом полигоне…

( Читать дальше )

Алгоритм поиска пути в Unity [2]

Оптимизация пути алгоритма A*

В предыдущем посте было показано, как устанавливаются связи между точками в прямой видимости, а также как отрабатывает алгоритм поиска пути A* для точек, между которыми нет прямой видимости.

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

Поиск пути в Unity [3]

Алгоритм поиска пути в Unity [1]

В посте про создание NPC в Unity я дал пару ссылок на уже готовые решения и представил примерный алгоритм поиска пути для самостоятельного создания основы AI для игрового бота (NPC). Сегодня поделюсь результатами, которые мне удалось реализовать в Unity.

Работа алгоритма поиска пути в Unity

( Читать дальше )

Создание NPC в Unity - Поиск пути

Практически в любой игре, кроме разве что головоломок или match 3, встречаются так называемые NPC (Non-Player Characters) — неигровые персонажи или попросту «боты». Поведением NPC или бота заведует ИИИ (игровой искусственные интеллект). И основная наиболее распространенная задача для ИИИ — поиск пути на игровой карте для перемещения ботов.

Для реализации поиска пути в Unity3D уже существует несколько готовых решений. Это Path от AngryAnt и A* Pathfinding Project от Aron Granberg. Первое можно использовать, если вас не смущает четырехсекундное лого автора в начале вашей игры. В противном случае нужно обращаться к разработчику за индивидуальными условиями лицензирования. Второе решение четко разграничивает бесплатную Lite и платную Pro версии.

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

( Читать дальше )