Асинхронный A*

1
Хочу представить общественности, в том числе и для критики, свой велосипед реализующий асинхронный поиск пути по алгоритму A*.

Path planning

Обычно для задачи поиска пути, я использовал найденный давным давно в интернете класс — http://snipplr.com/view/29715/astarmap-pathfinding-grid-use-with-astar-class/. Его минус — отжирание кучи времени от кадра в случае большой карты, для поиска.

Т.е. планирование пути — задача неслабо отжирающая ресурсы, в случае если карта маленькая, и одновременно планирует путь только 1 юнит, расчеты можно уместить в один кадр, без серьезной потери FPS. В случае если карта относительно большая или юнитов которые захотели куда-то переместиться несколько, то проседание FPS является неотъемлемым.

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

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

H = (|mtx - x| + |mty - y|) * 10;


Где mtx/mty — координаты цели.

Двумерный массив представлен в виде одномерного вектора, с доступом по координатам — map[x*mHeight + y], и реализован в классе Map2D. Класс PFSession — содержит необходимые данные для осуществления поисковой сессии, размазанной по времени. И класс PFMap — для работы со всем этим.

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

// Создаем карту заполненную пустыми клетками
var map:PFMap = new PFMap(100, 100);
// Значения для клеток меньшие 0 являются непроходимыми, 
//0 - идеально проходимая точка
//Все что выше нуля - вес клетки, который учитывается при построении пути (желательно делать кратным 10)
map.setCell(10, 10, -1);
map.setCell(10, 11, 10);

// Ищем путь от точки 0,0 до точки 99,99
// Возвращенный вектор содержит массивы с координатами вида [x,y], от следующей точки после начальной, до конечной
var path:Vector<Array> = map.findPath(0, 0, 99, 99);

// Асинхронное использование
stage.addEventListener(Event.ENTER_FRAME, function (e:Event):void {
    // Чтобы асинхронно использовать поиск, нам нужно каждый кадр просчитывать необходимое
    // количество итераций, оптимальное количество зависит от размеров карты и количества юнитов
    // Здесь мы каждый кадр просчитываем 50 итераций
    map.update(50);
});

// Асинхронные вызовы
map.findPathCallback(0, 0, 50, 50, function (path:Vector.<Array>):void {
    trace("Path founded!");
});

map.findPathCallback(0, 0, 40, 40, function (path:Vector.<Array>):void {
    trace("Path founded!");
});


В качестве первого места куда нужно заглянуть, это планировщик в PFMap.update, сейчас он до ужаса примитивный, но для большинства вещей его хватит за глаза.
При задании весов клеткам, необходимо учитывать, что G в данной реализации равно 10 (или 14, если движение по диагонали) + Вес.

Флешки: (колесико для зума, левая кнопка для перетаскивания)
Синхронный режим: 100х150, 100 юнитов — megaswf.com/serve/1098310
Асинхронный режим, те же параметры: megaswf.com/serve/1098309
(Чтобы рендер не тормозил, можно увести окошко с данными за границу, и фпс будет более соответствовать. Если у вас FPS одинаковый, то значит у вас компьютер много быстрее моей виртуальной машины :)).

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

Возможность хождения по диагонали включается в конструкторе PFSession.

Вот код: pathfinding.zip

Приветствую любую критику и указания на явные недостатки. Буду рад, если кому-то окажется полезным.
  • +12

Комментарии (7)

+1
Какие-то кривые пути он строит.
Даже на картинке в посте видно, что путь не оптимальный.
Для такого качества можно применять обычный обход по правилу левой руки.
Исходники не смотрел.
+2
Спасибо, ума не приложу как я этого бага на картинке не заметил. Сейчас все ок, исходники поправил.
0
имхо лучше не дробить процесс поиска пути, а разбить процесс поиска пути для нескольких человечков. Например в первом кадре ищем путь для первых пяти человечков, во втором кадре — для следующей пятёрки… и так далее.
0
Да, очереди это альтернативный вариант. Но если кадр уже нагружен игровой логикой/ai/рендером, и карта не 15х15 для тдшки, а побольше, то даже планирование для одного юнита может здорово его растянуть.
0
Вот еще какие фичи были бы полезными:
— учет «неожиданных» препятствий (кто-то встал на пути и т.п.)
— возможность задавать ограничение на используемую память для каждого моба
— возможность начала движения до завершения поиска пути (хотя может тут это есть, не нашел)
— учет движения в группе (во-первых чтобы иметь возможность шагнуть туда, где только что был другой моб, во-вторых чтобы искать путь целиком для всей группы).
— возможность движения под любым углом

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

— учет «неожиданных» препятствий (кто-то встал на пути и т.п.)

Это реализуется достаточно просто, либо перепланированием пути, если юнит во что-то уперся, либо ожиданием (если это был другой юнит, ждем пока он пройдет)

— возможность задавать ограничение на используемую память для каждого моба

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

— возможность начала движения до завершения поиска пути (хотя может тут это есть, не нашел)

В конце поста есть заметка о том, что можно двигать юнит по более простому алгоритму, пока путь будет не найден.

— возможность движения под любым углом

В тему сглаживания пути, как раз копаюсь :)
0
«Насколько мне видится, это невозможно организовать используя A*. Но если по памяти вопрос очень острый, и карты большие, то лучше использовать кластеризацию пространства, и тому подобные вещи»

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

«В конце поста есть заметка о том, что можно двигать юнит по более простому алгоритму, пока путь будет не найден.»

Да, но можно также воспользоваться промежуточными результатами A*.
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.