Рубрика «pathfinding»

Предисловие

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

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

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

Эта техника использована в игре 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 ставит особую задачу — генерировать и продвигать новые идеи.
Читать полностью »