Для разработки небольшой компьютерной игры зачастую применяются базовые алгоритмы поиска пути (алгоритм Дейкстры, А*), которых вполне достаточно для игрового поля не слишком больших размеров. Однако как же решить задачу о поиске пути на громадных игровых пространствах в играх жанра RTS или RPG? Ведь в виду значительного потребления памяти и ресурсов процессора базовые алгоритмы не подходят. О решении этой проблемы (а также нескольких других) и пойдет речь дальше в статье.
Читать полностью »
Рубрика «поиск пути» - 3
Иерархический поиск пути
2013-01-22 в 19:08, admin, рубрики: game development, HPA*, rpg, RTS, алгоритм, Алгоритмы, поиск пути, Программирование, метки: HPA*, rpg, RTS, алгоритм, поиск путиАлгоритм поиска пути — на раз, два, три!
2012-12-23 в 20:42, admin, рубрики: Алгоритмы, Песочница, поиск пути, метки: поиск пути Поиск пути — это алгоритм, осуществляющий прокладку маршрута из точки 1 в точку 2, в обход препятствий.
Чаще всего находит применение в играх жанра стратегии и у военных роботов, для поиска пути к врагу.
На сегодня обладает неимоверной известностью алгоритм астар, иногда пишут как А*. Но на хабре была обнаружена статья рассказывающая о новом, революционном алгоритме «прыгающих точек», на английском выглядит так «Jump Point Search».
Введение
Эта статья направлена на тех, кто вообще никак не понимает данный алгоритм, но хочет его понять снова и снова.
Прочитав эту статью, вы сразу все поймете и сможете на любом языке объяснить его любому желающему.
И главное не забывайте, для закрепления материала, рекомендую рассказать о принципе работы этого хитрого алгоритма кому нибудь еще.
Представляю, что у меня есть некий полигон, с ячейками. Уважаемые читатели, смотрите на рисунок ниже. В нем вы должны увидеть зеленый кубик, а справа о него обнаружите красный кубик. Так вот, зеленый квадратик — начало пути нашего героя, красный квадратик — место где сидит дракон. Наш герой просто обязан найти путь к дракону и вальнуть его.
Поиск пути: алгоритм для новичков
2012-11-20 в 8:06, admin, рубрики: javascript, jquery, алгоритм, логика, поиск пути, метки: javascript, jquery, алгоритм, логика, поиск путиПоиск пути — неотъемлемая часть игр, встречающаяся в большинстве современных игровых жанров. Наиболее часто задача поиска пути возникает в стратегиях, в которых игрок дает команды игровым юнитам двигаться через область карты, которая содержит препятствия. Игры постоянно усложняются, а поиск пути эволюционирует и развивается вместе с ними.
Алгоритмы поиска пути не всегда эффективны, но их изучение помогает понять, как решаются различные проблемы, одной из которых является обход препятствий.
Наиболее простым, но достаточно известным и популярным алгоритмом поиска пути является алгоритм Астар (или A*), данная статья основана на данном алгоритме и содержит реализацию на JavaScript.
Читать полностью »