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

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



Обычно для задачи поиска пути, я использовал найденный давным давно в интернете класс — 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

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