roboforum.ru

Технический форум по робототехнике.

 

Принцип работы алгоритма поиска пути Астар (A*).

Автомат, адаптивный автомат ... разум

Принцип работы алгоритма поиска пути Астар (A*).

Сообщение setar » 26 окт 2004, 11:48

Принцип работы алгоритма поиска пути Астар (A*).

Автор: Cupper

Есть матрица узлов (сетка клеток), каждый узел имеет линки на своих соседей. Алгоритм оперирует двумя списками: сортированным (далее open), в котором хранятся узлы, линки которых еще не были обработаны (узлы сортируются по оценке расстояния до конечного узла от наиболее близкого), и не сортированный (далее close) с обработанными узлами. Принцип работы следующий:


1. Помещаем в open список стартовый узел.
2. Основной цикл (пока open список не пуст).
3. Берм из open списка верхний узел.
4. Если этот узел равен конечному, то строим путь и выходим из основного цикла.
5. Обрабатываем линки выбранного узла. Для каждого соседа:
- проверяем его на проходимость, для конкретного юнита, если непроходим, то, понятное дело, переходим к следующему соседу;
- вычисляем оценку пути от стартового узла через текущий до соседа;
- ищем соседа в open и close списках, если найден, то сравниваем его оценку пути от стартового узла с вычисленной, если его оценка лучше то идем к следующему соседу, в противном случае удаляем узел из соответствующего списка, пересчитываем оценку пути до конечного узла и помещаем этого соседа в open список, в соответствующее место;
6. Помещаем текущий узел в close список.
7. Переходим к п.3 (конец основного цикла).

Если путь найден, его можно обработать, сделать астаровский путь более плавным, если это нужно, конечно.

Самые тяжелые по быстродействию места в алгоритме - это поиск узла в списках. Если использовать стандартные списки из stl, то затраты составляют примерно 75%, от времени работы всего алгоритма, это верно для достаточно сложной карты и поиске пути на значительное расстояние. Вставка узла в open список примерно 15% и проверка проходимости (учитывая размеры юнита) - порядка 10%.

Способы оптимизации.

Использование хэш таблиц.

Самым быстрым поиском обладают хэш таблицы. Отсюда мое желание прикрутить их к алгоритму астара. К сожалению стандартные списки (stl) использовать с хэш таблицей не представляется возможным, поэтому придется написать свои.

Основная идея хранить в хэш таблице указатель на итератор списка.


Код: Выделить всёРазвернуть
const int c_HeapSizeForAstarList = 8192;

typedef struct AstarListIt
{
 int        idx;  // узел, в данном случае его индекс
 AstarListIt*  prev; // предыдущий итератор
 AstarListIt*  next; // следующий итератор
} AstarListIt;

class AstarList
{
public:
 AstarList()
 {
   iSize = 0;
   iHeap = 0;
   heap.push_back(new AstarListIt[c_HeapSizeForAstarList]);
   head = tail = heap[iHeap]; tail->prev = head;
 }
 ~AstarList()
 {
     clear();
   delete[] heap[0];
 }
 AstarListIt* begin() {return head;}  // получить головной итератор
 AstarListIt* end() {return tail;}    // получить хвостовой итератор
 AstarListIt* push_back(int& idx);    // добавить элемент в конец списка
 int  front(); // pop                  // взять элемент из головы списка
 void erase(AstarListIt* it);         // удалить итератор
 bool empty() { return tail == head; } // проверить пустой ли список
 AstarListIt* insert(AstarListIt* itNext, int idx); // вставить элемент
 void clear();                                      // очистить список

protected:
   void resize();                        // увеличить размер

 AstarListIt*        head;     // головной итератор (начало списка)
 AstarListIt*        tail;     // хвостовой итератор (конец списка)
 std::vector<AstarListIt*>  heap;     // куча зарезервированной памяти
 int              iSize;    // размер текущей кучи
 int              iHeap;    // индекс текущей кучи
};

class AstarHash
{
public:
 typedef struct PathHashTable{ // элемент таблицы
   AstarListIt*  it;       // указатель на итератор
   int        value;    // проверочное значение
   bool      closed;   // относится к закрытому или открытому списку
 } PathHashTable;

 PathHashTable*  Table;        // таблица
 int        Size;         // размер
 int        Power;        // кол-во идентификационных бит
 int        Mask;         // маска

 AstarHash(int power): Power(power), Size(1<<power)
 { Table = new PathHashTable[Size]; Clear(); }
 ~AstarHash(){delete [] Table;}
 void Clear() { ZeroMemory(Table, Size*sizeof(PathHashTable)); } // очистка
 void Add(int value, AstarListIt* it, bool closed);   // добавить элемент
 void Resize();                                       // увеличить размер
 AstarListIt* Find(int value, bool closed);        // найти элемент
 void Erase(int value);                            // удалить
 void Check();                                    // проверка (для отладки)
};

В итоге скорость увеличилась примерно в 15 раз.

smartLOD

Второй способ оптимизации - дополнительные линки, или, так называемый, "смартЛОД". Идея в том чтобы добавить в узел помимо основных линков к непосредственным соседям дополнительные. Если узел находится в некоторой свободной зоне, в которой отсутствуют препятствия, то из этого узла можно сделать линки до краев области. Размерами области можно варьировать, в зависимости от сложности карты. Например, для карт типа лабиринта, можно искать области в радиусе от 8 до 4 клеток. Эта оптимизация дала дополнительно к первой еще 10-15% прироста производительности.

Пример.

Простой пример функции поиска, используются следующие обозначения:
m_pCells - матрица узлов;
m_lOpen - сортированный список;
m_lClose - список обработанных;
m_pAstarHash - хэш таблица;
m_fMaxSmartArea - наибольшая область, использовавшаяся при построении смартЛОДа;

узел содержит следующую информацию:
m_pLinks[8] - основные линки;
m_pSmartLinks[8] - смартлинки;
m_fCost - оценка всего пути через узел;
m_fFromStart - оценка пути от старта до узла;
m_fToFinish - оценка пути от узла до финиша;
m_ParentIdx - индекс предыдущего узла для построения пути;

линки:
fCost - стоимость перехода от узла к узлу;
fLength - расстояние между узлами;
idxTo - индекс узла соединение, с которым линк описывает;
SmartSize - размер для смартЛОДа;


Код: Выделить всёРазвернуть
// поиск пути
bool FindPath(int idxFrom, int idxTo, float fUnitSize, int iUnitType)
{
 // лист узлов для найденого пути
 list<int> lPath;
 int idxCur = idxFrom;

   // вычислить и запомнить оценку расстояния до конечного узла
 m_pCells[idxCur].CalcCost(0, m_pCells[idxTo]);
   // пометить как начало цепочки, для последующего построения пути
 m_pCells[idxCur].m_ParentIdx = -1;

   // поместить начальный узел в сортированный список
 m_lOpen.push_back(idxCur);
   // добавить запись в хэш таблицу
 m_pAstarHash->Add(idxCur, m_lOpen.begin(), false);

   // получение текущего времени для последующей проверки на критическое время
 DWORD dwTime = timeGetTime();
 DWORD dwCriticalTime = 200;

   // начало главного цикла
 while(!m_lOpen.empty())
 {
     // получение текущего узла для обработки
   idxCur = m_lOpen.front();
       // удаление записи из хэш таблицы
   m_pAstarHash->Erase(idxCur);

       // проверка на достижение конечного узла
   if (idxCur == idxTo)
   {
           // построение пути с конца в начало
     for (int p = idxTo; p >= 0; p = m_pCells[p].m_ParentIdx)
       lPath.push_front(p);
     break;
   }
       // использовать смартЛОД, если до конечного узла достаточно большое
       // расстояние, больше чем максимальный размер области при
       // построении смарт линков
       bool useSmart = m_pCells[idxCur].m_fToFinish > m_fMaxSmartArea;
   int iSize;
       // обработка восьми соседей
   for (int iDir = 0; iDir < 8; iDir++)
   {
         // получить дистанцию до соседа, если нет смартлинков, то - 1
     if (useSmart)
       iSize = m_pCells[idxCur].m_pSmartLinks[iDir].SmartSize;
     else
       iSize = 1;
           // получить индекс соседа
     int idx = m_pCells.GetNeighborIdx(idxCur, iDir, iSize);
           // а есть ли сосед?
     if (idx < 0)
       continue;

           // расчет нового оценочного расстояния для текущего соседа
           // от стартового узла
     float fFromStart;
     if (useSmart)
       fFromStart = m_pCells[idxCur].m_fFromStart +
         m_pCells[idxCur].m_pSmartLinks[iDir].fCost;
     else
       fFromStart = m_pCells[idxCur].m_fFromStart +
         m_pCells[idxCur].m_pLinks[iDir].fCost;

           // поиск узла в списках при помощи хэш таблицы
     AstarListIt* pItO = m_pAstarHash->Find(idx, false);
     AstarListIt* pItC = m_pAstarHash->Find(idx, true);

           // если нашли то сравнить старое оценочное расстояние с новым
     if (pItO || pItC)
     {
       if (m_pCells[idx].m_fFromStart <= fFromStart)
         continue;

             // очистка списков и записей в хэш таблице
             if (pItC)
             {
                 m_lClose.erase(pItC);
                 m_pAstarHash->Erase(idx);
             }
             if (pItO)
             {
                 m_lOpen.erase(pItO);
                 m_pAstarHash->Erase(idx);
             }
     }
           else
           {
               // проверка узла на проходимость (занятость)
             if (CheckBusyWayable(idx, iUnitType, fUnitSize))
                 continue;
           }

           // обновление оценочного расстояния до конца пути
     m_pCells[idx].CalcCost(fFromStart, m_pCells[idxTo]);
     m_pCells[idx].m_ParentIdx = idxCur;

           // вставка узла в сортированный список
           AstarListIt* itOpen = m_lOpen.begin();
     for (; itOpen != m_lOpen.end(); itOpen = itOpen->next)
     {
       if ( m_pCells[itOpen->idx].m_fCost >= m_pCells[idx].m_fCost)
         break;
     }
     m_pAstarHash->Add(idx, m_lOpen.insert(itOpen, idx), false);
   }

       // поместить обработанный узел в close список
   m_pAstarHash->Add(idxCur, m_lClose.push_back(idxCur), true);

       // проверка времени (дабы пусть лучше путь не будет найден,
       // чем будет лаг из-за его поиска
   if (timeGetTime() - dwTime > dwCriticalTime)
     break;
 }
   // очистка списков и хэш таблицы
 m_lOpen.clear();
 m_lClose.clear();
 m_pAstarHash->Clear();

   // вызов функции сглаживания пути
 OptimizeWay(lPath, unitPath);

 // вернуть результат работы
 return !unitPath.m_lWayPoints.empty();
}

Принимаются предложения по оптимизации вставки элемента в сортированный список. После всех оптимизаций данная реализация вставки съедает порядка 30% времени поиска.

Сайт автора: http://ncdev.hostweb.ru/

Автор: Cupper
Вложения
20040117.h
Исходый код к статье:
(3.67 КиБ) Скачиваний: 336
Аватара пользователя
setar
Site Admin
 
Сообщения: 9230
Зарегистрирован: 04 окт 2004, 12:58
Откуда: St.Petersburg
Skype: taranenko.sergey
ФИО: Сергей Тараненко

Re: Принцип работы алгоритма поиска пути Астар (A*).

Сообщение =DeaD= » 26 окт 2004, 15:18

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

setar писал(а):Принцип работы алгоритма поиска пути Астар (A*).

Гм, это все-таки называется поиск в ширину по-научному, но видимо в среде разработчиков игра это называется А*-алгоритм :)

setar писал(а):Самые тяжелые по быстродействию места в алгоритме - это поиск узла в списках. Если использовать стандартные списки из stl, то затраты составляют примерно 75%, от времени работы всего алгоритма, это верно для достаточно сложной карты и поиске пути на значительное расстояние. Вставка узла в open список примерно 15% и проверка проходимости (учитывая размеры юнита) - порядка 10%.

Безумная проблема:
1. Непонятно почему нельзя если все узлы пронумерованы от 1 до N сделать массив размера N и в нем помечать - входит ли узел с данным номером в наш пресловутый CLOSE-список. При этом сам список можно не вести.
2. Непонятно какого лешего не хранят ссылки из некого доп. массива узлов размера N на элементы списка OPEN и обратно - делается за константу, а потом искать тоже за константу, а не за Log(N), как в хэше.

setar писал(а):Второй способ оптимизации - дополнительные линки, или, так называемый, "смартЛОД". Идея в том чтобы добавить в узел помимо основных линков к непосредственным соседям дополнительные. Если узел находится в некоторой свободной зоне, в которой отсутствуют препятствия, то из этого узла можно сделать линки до краев области. Размерами области можно варьировать, в зависимости от сложности карты. Например, для карт типа лабиринта, можно искать области в радиусе от 8 до 4 клеток. Эта оптимизация дала дополнительно к первой еще 10-15% прироста производительности.

Это уже оптимизация зависящая от вида карты, не имеющая ничего общего с универсальным алгоритмам. Комментировать не буду.

setar писал(а):Принимаются предложения по оптимизации вставки элемента в сортированный список. После всех оптимизаций данная реализация вставки съедает порядка 30% времени поиска.

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

В целом автору статьи рекомендуется пообщаться с "матерыми участниками АСМ-соревнований", подчерпнет много нового :) Там такие проблемы решаются регулярно и от них зависит решение задачи и вообще судьба команды игроков.

PS: А сайт автора мертвый уже.
Аватара пользователя
=DeaD=
 
Сообщения: 24053
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: Pascal / C++ / PHP / 1C
ФИО: Антон Ботов


Вернуться в Алгоритмы

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

Mail.ru counter