Автор: 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% времени поиска.
Сайт автора:
Автор: Cupper
