Рубрика «pathfinding»

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

Ситуация еще больше осложняется, если рядом нет никаких крупных достопримечательностей, о которых все знают и которые можно было бы включить в свой маршрут после короткого поиска в интернете. Что делать если вы застряли в каком-нибудь Купчино, про которое вы только и слышали, что там лучше не застревать? Приходится идти по навигатору, надеясь, что на пути встретится что-то интересное. Однако популярные навигаторы учитывают лишь расстояние и время в пути, но не принимают во внимание интересность маршрута. Мне попадались еще проекты, пытающиеся учитывать удобство пешего маршрута (ведущие в обход шумных магистралей), но хочется же пройти не только комфортно, но и увидеть какие-нибудь красоты.

Гуляем по городу с умом: как я делал сервис для построения интересных пешеходных маршрутов - 1

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

Описание алгоритма и примеры работы под катом, ссылка в конце.Читать полностью »

image

Следование по пути и управление движением

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

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

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

Технические требования

Необходима версия Unity 2017, установленная в системе с Windows 7 SP1+, 8, 10 или с Mac OS X 10.9+. Код из данной статьи не будет работать на Windows XP и Vista, а серверные версии Windows и OS X не тестировались.

Файлы кода для этого поста можно найти на GitHub.

Чтобы изучить код в действии, посмотрите это видео.
Читать полностью »

Предисловие

Если вы создаёте игру-платформер в стиле «беги и прыгай», то, возможно, уже задумывались о добавлении в неё ИИ. Он может управлять противниками, объектами, которые игрок должен преследовать, и так далее… И слишком часто ради простоты программист реализации отказывается от умного ИИ, что в результате приводит к тому, что ИИ не может справиться с хитрыми прыжками, особо умным игроком или движущимися объектами уровня.

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

Мы рассмотрим основную идею и создадим полную реализацию. Более сложные случаи, в том числе подвижные платформы/разрушаемые стены, мы рассмотрим в другой статье.

Эта техника использована в игре Nomera, см. на www.dotstarmoney.com или в Twitter.

e3iKSJ7.png

Прежде чем начать, проверьте, возможно, вы удастся реализовать более простой алгоритм, соответствующий упрощённой геометрии карты. Например, если коллизии в уровнях распознаются по сетке квадратов (как в большинстве 2D-игр). В таких случаях можно реализовать надёжный поиск путей ИИ с помощью более простых техник. Мой метод в основном подойдёт тем, кто хочет более «человечного» поведения ИИ.
Читать полностью »

Привет, Друзья!

Я написал библиотеку поисков путей на произвольных графах, и хотел бы поделиться ей с вами: http://github.com/anvaka/ngraph.path

Пример использования на огромном графе:

Поиграться с демо можно здесь: https://anvaka.github.io/ngraph.path.demo/

В библиотеке используется мало-известный вариант A* поиска, который называется NBA*. Это двунаправленный поиск, с расслабленными требованиями к функции-эвристике, и очень агрессивным критерием завершения. Не смотря на свою малоизвестность у алгоритма отличная скорость сходимости к оптимальному решению.

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

Читать полностью »

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

В играх жанра Tower Defense (TD) множество врагов стремится добраться в одну точку. Во многих играх TD существует заранее заданный путь или несколько путей. В некоторых, в том числе в классической Desktop Tower Defense можно размещать башни в произвольных местах, и они становятся препятствиями, влияющими на пути врагов. Запустите демо и нажимайте на карту, чтобы возводить или убирать стены:

Читать полностью »

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

image

Читать полностью »

Поиск пути через NavMesh на ActionScript – CrossBridge порт Recast Navigation

В этой статье я расскажу об опыте переноса C++ кода на ActionScript с помощью FlasCC компилятора и покажу, как с его помощью мне удалось портировать довольно большой объем полезного кода, решающего задачу поиска пути. В конце будет демо и ссылка на репозиторий с кодом. А пока пара слов о том, с чего вообще все началось.
Читать полностью »

Вперед к новым вершинам незнания
За время своей деятельности Intel сгенерировала и воплотила в жизнь огромное количество инновационных замыслов, начиная с пионерских технологий в процессорах и памяти 60-х – 70-х годов и заканчивая перспективными разработками сегодняшнего дня. Ключ к этим достижениям – мощная и бережно лелеемая внутри компании культура выдвижения и восприятия новых идей. Под катом – сокращенный перевод интервью со старшим архитектором подразделения Intel Software and Services Group Ylian Saint-Hilaire о нелегкой, но увлекательной жизни разработчиков-первопроходцев, перед которыми Intel ставит особую задачу — генерировать и продвигать новые идеи.
Читать полностью »