Обычно для задачи поиска пути, я использовал найденный давным давно в интернете класс – http://snipplr.com/view/29715/astarmap-pathfinding-grid-use-with-astar-class/. С задачей он справлялся отлично, но имел один сильный минус, а именно – при поиске длинного пути на достаточно большой карте, он отъедал от кадра кучу времени. Если же этих поисков было несколько, то несмотря на высокий средний фпс, дергания убивали все затеи.
Посидев, и разобравшись с алгоритмом, хочу представить свою версию реализации A* с возможностью асинхронной работы. Т.е. вы можете оставить заявку на поиск, и через несколько кадров/секунд, когда поиск будет закончен, вам в коллбэк прилетит результат. В качестве бонуса, данная реализация вышла быстрее представленного класса по ссылке в 2-7 раз, в зависимости от условий. Алгоритмических оптимизаций никаких не применялось, и если необходимо, их можно будет легко навернуть на то что есть, и заменить эвристическую функцию, сейчас это:
H = (|mtx - x| + |mty - y|) * 10;
Двумерный массив представлен в виде одномерного вектора, с доступом по координатам – 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 юнитов – http://megaswf.com/serve/1098310
Асинхронный режим, те же параметры: http://megaswf.com/serve/1098309
Как видно – минус асинхронного режима, что при сохранении фпс, много юнитов очень долго ждут пока их путь будет найден. Эта проблема решается нахождением золотой середины для аргумента update, и применением дополнительного поведения. Например – юнит запросил планирование пути, а в этот момент идет к цели по прямой, либо с простым алгоритмом обхода, как только путь будет найден, корректирует свой на более правильный.
Возможность хождения по диагонали включается в конструкторе PFSession.
Вот код: http://blog.poppergames.com/wp-content/uploads/2011/04/pathfinding.zip
Ошибки, улучшения, слова “так пишут только му**ки”, можно писать на мыло, или в комменты.
