| Вопрос: Алгоритм А* | Добавлено: 19.08.06 11:27 |
Автор вопроса:  AgentFire | ICQ: 192496851 |
| Как действует алгоритм А*, является ли он самым быстрым из всех, ищущих путь от заданных начала и конца и если нет, то какой самый быстрый и правильный? |
| Ответы | Всего ответов: 1 |
|
Номер ответа: 1 Автор ответа:  ChemistN1 Вопросов: 7 Ответов: 43 |
Web-сайт: Профиль | | #1 | Добавлено: 26.08.06 11:35 |
|
Принцип работы алгоритма поиска пути Астар (A*).
Есть матрица узлов (сетка клеток), каждый узел имеет линки на своих соседей. Алгоритм оперирует двумя списками: сортированным (далее 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); // получение текущего времени для последующей проверки на критическое время  WORD dwTime = timeGetTime();
WORD 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(); } |
||
Страница: 1 |