Метка «поиск пути»

в 11:20, , рубрики: astar, boost, boost.graph, c++, graph_traits, граф, кратчайший путь, поиск пути, Программирование, метки: , , , , , ,

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

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

в 22:34, , рубрики: astar, boost, boost.graph, c++, graph_traits, граф, кратчайший путь, поиск пути, Программирование, метки: , , , , , ,

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

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

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

в 9:27, , рубрики: astar, boost, boost.graph, c++, graph_traits, граф, кратчайший путь, поиск пути, Программирование, метки: , , , , , ,

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

в 19:08, , рубрики: game development, HPA*, rpg, RTS, алгоритм, Алгоритмы, поиск пути, Программирование, метки: , , , ,

Иерархический поиск пути
Для разработки небольшой компьютерной игры зачастую применяются базовые алгоритмы поиска пути (алгоритм Дейкстры, А*), которых вполне достаточно для игрового поля не слишком больших размеров. Однако как же решить задачу о поиске пути на громадных игровых пространствах в играх жанра RTS или RPG? Ведь в виду значительного потребления памяти и ресурсов процессора базовые алгоритмы не подходят. О решении этой проблемы (а также нескольких других) и пойдет речь дальше в статье.
Читать полностью »

в 20:42, , рубрики: Алгоритмы, Песочница, поиск пути, метки:

Поиск пути — это алгоритм, осуществляющий прокладку маршрута из точки 1 в точку 2, в обход препятствий.
Чаще всего находит применение в играх жанра стратегии и у военных роботов, для поиска пути к врагу.

На сегодня обладает неимоверной известностью алгоритм астар, иногда пишут как А*. Но на хабре была обнаружена статья рассказывающая о новом, революционном алгоритме «прыгающих точек», на английском выглядит так «Jump Point Search».

http://angors.ru/_ph/1/2/435973493.jpg

Введение

Эта статья направлена на тех, кто вообще никак не понимает данный алгоритм, но хочет его понять снова и снова.

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

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

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

в 8:06, , рубрики: javascript, jquery, алгоритм, логика, поиск пути, метки: , , , ,

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

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

Наиболее простым, но достаточно известным и популярным алгоритмом поиска пути является алгоритм Астар (или A*), данная статья основана на данном алгоритме и содержит реализацию на JavaScript.
Поиск пути: алгоритм для новичков
Читать полностью »

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js