Рубрика «поиск пути» - 2

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

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

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

Алгоритмы поиска пути — неотъемлемая часть разработки игр. А также различных систем навигации, ориентации и много чего ещё. Но мы сосредоточимся на именно игровой индустрии и алгоритмах, которые в ней применяются.

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

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

Pathfinding: До одури простая реализация алгоритма воронки (Funnel Algorithm) - 1

Алгоритм воронки — это простой алгоритм поиска наипростейшего пути, проходящего через «порталы». Наиболее подробное описание можно найти по ссылке Efficient Triangulation-Based Pathfinding (2)
Здесь же этот алгоритм будет реализован до одури просто. Вместо использования очередей и прочих очешуительных вещей, наша простейшая реализация перезапускает цикл каждый раз, когда обнаруживает очередной угол. Это значит, что некоторые порталы будут опрашиваться таки чаще, чем должны были бы, тем не менее, делая реализацию всяко проще.
Читать полностью »

Все ошибки по данной статье присылайте, пожалуйста, в личные сообщения.
Алгоритмы интеллектуальной автогенерации уровней в iOS игре - 1
Я люблю смотреть на звездное небо и размышлять о далеких мирах, но факт бесконечности вселенной с трудом укладывается в моей голове. Согласно теории большого взрыва, наша вселенная непрерывно расширяется и охлаждается из сингулярного состояния, но давайте предположим, что наша бесконечная вселенная постоянно генерируется по определенным правилам, и количество этих правил ограниченно. Можно допустить, что наша вселенная уже сгенерировалась, то есть для каждой точки бесконечной вселенной уже была произведена генерация по конечному числу правил (генерация была произведена бесконечное количество раз), в итоге мы имеем бесконечную сгенерированную вселенную.

Вернемся к нашей задаче, нам нужно интеллектуально генерировать карты для IPhone/IPad игры типа «Марио», для начала мы рассмотрим генерацию карты в пределах поля 128х128 кубов.
Читать полностью »

Приветствую всех читателей. Сегодня попробую продолжить серию достаточно редких статей, посвящённым естественным алгоритмам. В частности, эта статья будет посвящена модификации муравьиного алгоритма, известной как Max-Min Ant System (MMAS). Я расскажу об отличиях от классического муравьиного алгоритма и о причинах внесения таких модификаций. Подробности под катом.
Читать полностью »

Привет, меня зовут Дмитрий, программист из Snowforged Entertainment. Я только что закончил рефакторинг компонента движения кораблей для проекта Starfall Tactics — тактической игры в реальном времени, в которой игроки могут собрать свой собственный космический флот и повести его в бой. Компонент движения переписывался уже три раза, от релиза до начала разработки альфа версии. Было собрано множество граблей, как архитектурных, так и сетевых. Постараюсь подбить весь этот опыт и рассказать вам о: Navigation Volume, Movement component, AIController, Pawn.
Читать полностью »

Алгоритмы поиска путей на JavaScript

Поиск оптимального маршрута юнита к цели на неизвестной карте — одна из самых сложных задач при разработке игры. К счастью, существует некоторое количество алгоритмов, которые решают эту задачу. Есть и отличная библиотека PathFinding.js с поддержкой 11 таких алгоритмов.
Читать полностью »

Маскируем класс под граф Boost. Часть 3: Находим путь
Пролог: Концепции Boost
Часть 1: Подключение ассоциированных типов без вмешательства в интерфейс исходного класса
Часть 2: Завершаем реализацию поддержки концепций

В прошлых статьях цикла описывался процесс адаптации класса клеточного игрового поля под концепции графов boost. Сейчас рассмотрим собственно то, ради чего все затевалось — поиск пути на клеточном поле. Реализация поиска boost позволяет достаточно тонко настраивать алгоритм, в этой статье будет приведет только один пример такой параметризации — возможность задавать различную длину ребер графа.
Читать полностью »

Маскируем класс под граф Boost. Часть 2: Завершаем реализацию поддержки концепций
Пролог: Концепции Boost
Часть 1: Подключение ассоциированных типов без вмешательства в интерфейс исходного класса

Кратко напомню задачу. Есть двумерное игровое поле из клеток, часть из которых свободна, а часть занята. Требуется найти путь по свободным клеткам из одной позиции поля в другую. Алгоритм поиска пути реализован в Boost. Но он требует, чтобы наше поле подходило под определение графа. Точнее класс должен удовлетворять двум концепциям — boost::VertexListGraph и boost:: IncidenceGraph. При этом интерфейс игрового поля менять не хочется — для всего остального проекта это не граф и графом никогда не станет.

В прошлой части было рассмотрено подключение внешних ассоциированных типов, необходимых для интерпретации класса как boost-графа. Конечно, одних типов недостаточно. Также требуется реализовать несколько функций с заданной сигнатурой и итераторов, с помощью которых библиотека сможет манипулировать игровым полем как графом.
Читать полностью »

Маскируем класс под граф Boost. Часть 1: Не трогаем интерфейс
Потребовалось недавно алгоритм поиска пути для нашей игры переделать. Прошлый был полностью самописный — шаг в сторону, и все плохо… Захотелось взять готовый из хорошего источника. Тут-то и вспомнилось, что в boost есть функциональность для работы с графами. К сожалению подход, «найди функцию, вызови — и все заработает» не состоялся. Упор в библиотеке сделан на максимальную гибкость использования, что негативно сказалось на простоте. В то же время и ничего смертельного — все лучше, чем с нуля делать (и потом исправлять). С другими библиотеками тоже связываться желания не было, в то время как boost в проекте используется давно…
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js