В этой статье мы рассмотрим поиск пути. Говорят, что алгоритм A* (или А звездочка, или A star) сложен для новичков, ну что ж, пусть так говорят :)
Давайте же на теории пройдемся по этапам поиска пути по алгоритму A*, а потом закрепим это на практике.
У нас будет два списка, которые будут хранить номера клеток. В первом будут клетки, которые нужно проверить, во втором - клетки, которые уже проверены. Первый список обычно называют "открытый", второй - "закрытый".
- Мы добавляем стартовую точку в наш открытый список.
- Находим точку с наименьшим оцененным путем в открытом списке (как будем оценивать, написано ниже) и ищем для неё проходимых соседей. Найденные новые точки мы оцениваем путь и добавляем их в открытый список. А исследуемую точку мы удаляем из открытого списка и добавляем в закрытый, чтобы больше её не проверять.
- Повторяем предыдущий пункт до тех пор, пока не найдем конечную точку (а не найти мы её не сможем из-за "островного" разделения закрытых друг от друга зон, которое мы рассмотрели в прошлой статье).
- По закрытому списку строим наш путь.
Работу программы, которую мы создадим, можно посмотреть тут:
Для начала немного подправим класс "CWayMap", который мы рассмотрели в прошлом уроке.
class CWayMap
{
private:
...
public:
...
// эту функцию мы просто перенесли из private в public
bool CheckDiagonals(int iNeighborX, int iNeighborZ, int iMasterX, int iMasterZ);
// функция, возвращает true если из одной точки можно пройти в другую
bool IsCanWay(int iStartID, int iEndID);
// возвращаем ширину сетки
int GetGridWidth() {return m_iGridWidth;}
// возвращаем размер ячейки сетки
int GetChunkSize() {return m_iChunkSize;}
};
Тут вроде ничего серьезного кроме "IsCanWay", но комментарии в коде дают нам понять, что можно смело двигать дальше, не тратя времени на ерунду.
bool CWayMap::IsCanWay(int iStartID, int iEndID)
{
// не равны ли начальная и конечная точки пути
if (iStartID == iEndID)
return false;
// проверяем, сможем туда попасть или нет, за счет разделения зон
if (m_Grid[iStartID].Passability != m_Grid[iEndID].Passability)
return false;
// проверив одну из точек, мы сразу отсекаем случаи:
// конечная точка - препятствие
// начальная точка - препятствие
if (!m_Grid[iEndID].Passability)
return false;
return true;
}
Я ещё ввел структуру "MapPoint", она будет хранить позиции ячеек сетки в экранных координатах, но можно обойтись и без неё.
struct MapPoint
{
int x;
int z;
};
Так же у нас появится ещё одна структура "WayChunk". Она пригодится для оценки пути определенной клетки. Давайте взглянем на неё:
struct WayChunk
{
int ID;
int MasterID;
int G;
int H;
int F;
};
- ID - номер ячейки в сетке;
- MasterID - её родитель;
- G - стоимость передвижения из стартовой клетки к данной. В моем примере каждое передвижение по горизонтали и вертикале будет стоить 10 единиц, а по диагонали 14. Так вот, G -это сумма единиц пройденного расстояния от начала до конкретно рассматриваемой точки;
- H - стоимость передвижения от данной клетки до конечной по методу Манхеттена (Manhattan method). Этот метод состоит в том, что мы рассчитываем расстояние только по горизонтали и вертикали, игнорируя препятствия и диагональные перемещения.
- F - сумма G и H;
Давайте же взглянем на объявление нашего класса:
class CPathfinding
{
private:
// стоимость передвижения по горизонтали и вертикали
#define WeightLine 10
// стоимость передвижения по диагонали
#define WeightDiag 14
// возможные результаты
enum
{
SEARTH_COMPLETED = -1,
NOT_FIND_END = -2,
FIND_END = -3
};
// наша карта
CWayMap* WayMap;
// Список, который надо проверить
std::vector < WayChunk > m_aOpenList;
// Проверенный список
std::vector < WayChunk > m_aCloseList;
// точка, до куда мы должны найти путь
int iEndX;
int iEndZ;
// возвращает клетку с наименьшим F
int GetMinWayChunk();
// проверяем клетку, ищем её соседей
bool DoSearchStep(int iChunkNum);
// поиск в открытом списке
int FindInOpenList(int iChunkID);
// поиск в закрытом списке
int FindInCloseList(int iChunkID);
// возвращаем мастер клетку по ID
int GetMasterID(int iChunkID);
public:
CPathfinding(int iWidth, int iHeight, int iSize);
~CPathfinding(void);
void DrawGrid(HDC dc);
// наша функция, которой мы будем пользоваться
bool GetWay(MapPoint From, MapPoint To, std::vector< MapPoint >* Way);
};
Не стоит пугаться, здесь большинство функций работают с нашими списками, и ничего сложного в них нет. Я даже не буду их комментировать, просто пробежимся по ним, но только после конструктора и деструктора :)
CPathfinding::CPathfinding(int iWidth, int iHeight, int iSize)
{
WayMap = NULL;
// создаем нашу карту
WayMap = new CWayMap(iWidth, iHeight, iSize);
}
CPathfinding::~CPathfinding(void)
{
SafeDelete(WayMap);
}
// ищем в закрытом списке клетку по ID
// и возвращаем его мастера
int CPathfinding::GetMasterID(int iChunkID)
{
for (unsigned int i=0; i < m_aCloseList.size(); i++)
{
if (m_aCloseList[i].ID == iChunkID)
return m_aCloseList[i].MasterID;
}
return -1;
}
// есть ли в закрытом списке клетка с указанным ID
int CPathfinding::FindInCloseList(int iChunkID)
{
for (unsigned int i=0; i < m_aCloseList.size(); i++)
{
if (iChunkID == m_aCloseList[i].ID)
return i;
}
return -1;
}
// есть ли в открытом списке клетка с указанным ID
int CPathfinding::FindInOpenList(int iChunkID)
{
for (unsigned int i=0; i < m_aOpenList.size(); i++)
{
if (iChunkID == m_aOpenList[i].ID)
return i;
}
return -1;
}
Функция "GetMinWayChunk" ищет в открытом списке клетку с наименьшим F для её дальнейшего анализа (возвращает порядковый номер открытого списка!).
int CPathfinding::GetMinWayChunk()
{
// если открытый список пуст, то мы не нашли путь
if (!m_aOpenList.size())
return NOT_FIND_END;
// ищем в открытом списке клетки с наименьшим F
int iMinWay = m_aOpenList[0].F;
int ID = 0;
for (unsigned int i=0; i < m_aOpenList.size(); i++)
{
if (m_aOpenList[i].F < iMinWay)
{
iMinWay = m_aOpenList[i].F;
ID = i;
}
}
// если H этой клетки не 0, то это не конец пути
if (m_aOpenList[ID].H != 0)
return ID;
else
{
// иначе добавляем конечную точку и сообщаем об этом
m_aCloseList.push_back(m_aOpenList[ID]);
return FIND_END;
}
}
"DoSearchStep" получает номер элемента открытого списка, из которого определяет ID клетки, для которой будем искать проходимых соседей. Каждого "хорошего" мы добавляем в открытый список, оценивая его путь. В конце анализирующую клетку, с которой работали, удаляем из открытого списка и добавляем в закрытый.
bool CPathfinding::DoSearchStep(int iChunkNum)
{
// Родительский ID, для которого ищем соседей
int iMasterID = m_aOpenList[iChunkNum].ID;
// вычисляем по номеру ячейки ширину и высоту в сетке
int iMasterX = iMasterID % WayMap->GetGridWidth();
int iMasterZ = iMasterID / WayMap->GetGridWidth();
// проходимся по всем соседям
for (int i = -1; i <= 1; i++)
{
for (int j = -1; j <= 1; j++)
{
// если это и есть ячейка, соседей которых мы ищем, то пропускаем
if (!j && !i)
continue;
int iNeighborX = iMasterX+i;
int iNeighborZ = iMasterZ+j;
// проверка на диапазон и проходимость клетки
if (WayMap->CheckPassability(iNeighborX, iNeighborZ))
{
// если он является диагональным, то можно ли
// пройти в него не срезав углы
if (WayMap->CheckDiagonals(iNeighborX, iNeighborZ, iMasterX, iMasterZ))
{
// по ширине и высоте находим номер соседа в сетке
int iNeighborID = WayMap->GetIDByPos(iNeighborX, iNeighborZ);
// если клетка проверялась, пропускаем
if (FindInCloseList(iNeighborID) > -1)
continue;
// начинаем оценивать путь этой точки
WayChunk Chunk;
// устанавливаем ID клетки
Chunk.ID = iNeighborID;
// устанавливаем родителя клетки
Chunk.MasterID = iMasterID;
// стоимость передвижения Манхеттена
Chunk.H = (abs(iNeighborX - iEndX) + abs(iNeighborZ - iEndZ)) * 10;
// рассчитываем длину пути от начальной точки до нынешней
int iDiffX = abs(iMasterX - iNeighborX);
int iDiffZ = abs(iMasterZ - iNeighborZ);
int iDiag = min(iDiffX, iDiffZ);
int iDirect = max(iDiffX, iDiffZ) - min(iDiffX, iDiffZ);
Chunk.G = iDiag*WeightDiag + iDirect*WeightLine + m_aOpenList[iChunkNum].G;
// вычисляем наш F
Chunk.F = Chunk.H + Chunk.G;
// есть ли наша клетка в открытом списке
int iNumChunk = FindInOpenList(Chunk.ID);
if (iNumChunk == -1)
// если нет, то добавлем
m_aOpenList.push_back(Chunk);
else
{
// если есть, то не короче ли наши новые расчеты
if (m_aOpenList[iNumChunk].G > Chunk.G)
m_aOpenList[iNumChunk] = Chunk;
}
}
}
}
}
// после того как с нашей точкой мы поработали, пора её перенести в другой список
m_aCloseList.push_back(m_aOpenList[iChunkNum]);
m_aOpenList.erase(m_aOpenList.begin() + iChunkNum);
return true;
}
Ну и последняя функция, которая собирает все части пазла. В неё мы передаем начальную точку, конечную и указатель на вектор, который мы наполним точками найденного пути. Мы будем анализировать каждый раз клетку с наименьшим F, пока не добавим конечную точку в открытый список. Далее мы будем следовать с конца через мастер точки, добавляя их в путь, до тех пор, пока не дойдем до стартовой точки. Это и будет наш путь.
bool CPathfinding::GetWay(MapPoint From, MapPoint To, std::vector< MapPoint >* Way)
{
// очищаем вектор, который мы передали в функцию, вдруг он не пустой
Way->clear();
// переводим стартовую точку в координаты сетки
int iStartX = From.x/WayMap->GetChunkSize();
int iStartZ = From.z/WayMap->GetChunkSize();
// проверяем, есть ли такая точка на карте
if (!WayMap->CheckRange(iStartX, iStartZ))
return false;
// переводим конечную точку в координаты сетки
iEndX = To.x/WayMap->GetChunkSize();
iEndZ = To.z/WayMap->GetChunkSize();
// проверяем, есть ли такая точка на карте
if (!WayMap->CheckRange(iEndX, iEndZ))
return false;
// находим их ID
int iIDFromChunk = WayMap->GetIDByPos(iStartX, iStartZ);
int iIDToChunk = WayMap->GetIDByPos(iEndX, iEndZ);
// если туда добраться нельзя, возвращаем false
if (!WayMap->IsCanWay(iIDFromChunk, iIDToChunk))
return false;
// добавляем в открытый список стартовую точку
WayChunk Chunk;
Chunk.ID = iIDFromChunk;
Chunk.MasterID = iIDFromChunk;
Chunk.G = 0;
Chunk.H = (abs(iStartX - iEndX)+abs(iStartZ - iEndZ))*WeightLine;
Chunk.F = Chunk.G + Chunk.H;
m_aOpenList.push_back(Chunk);
// находим номер элемента, у которого минимальный F
int iNumInOpenList = GetMinWayChunk();
// до тех пор пока поиск не завершится, делаем анализ клетки с минимальным F
// а после опять ищем новую клетку с минимальным F
for (; iNumInOpenLis > SEARTH_COMPLETED; iNumInOpenLis = GetMinWayChunk())
{
DoSearchStep(iNumInOpenLis);
}
bool bDone = false;
// если конечная точка найдена
if (iNumInOpenLis == FIND_END)
{
// добавляем конечную точку в наш вектор пути
MapPoint PointOfWay;
PointOfWay.x = iEndX * WayMap->GetChunkSize();
PointOfWay.z = iEndZ * WayMap->GetChunkSize();
int ID = -1;
int iMasterID = WayMap->GetIDByPos(iEndX, iEndZ);
// до тех пор пока мы в обратном порядке на найдем стартовую точку
// через мастер точки движемся с конца в начало, добавляя путь в вектор
while (ID != iMasterID)
{
ID = iMasterID;
iMasterID = GetMasterID(ID);
PointOfWay.x = ID % WayMap->GetGridWidth()* WayMap->GetChunkSize();
PointOfWay.z = ID / WayMap->GetGridWidth()* WayMap->GetChunkSize();
Way->push_back(PointOfWay);
}
bDone = true;
}
// очищаем наши открытый и закрытый списки
m_aCloseList.clear();
m_aOpenList.clear();
return bDone;
}
Вот мы и заполнили вектор точками найденного пути. В общем все просто! А ещё говорят, что алгоритм поиска пути A* сложен для новичков. Стоит обратить внимание на то, что мы в наш путь добавляем все путевые точки подряд, что совсем не правильно. В дальнейшем мы рассмотрим способ добавления путевых точек, пропуская при этом лишние. А следующая статья будет посвящена опять таки алгоритму A star, но только уже в виде картинок, для полного понимания и закрепления наших знаний.
3 коммент.:
статья была обновлена
Добрый день!
А можно где-нибудь скачать готовые исходники программы ?
Делаю курсовую на эту тему, хотелось бы пошагово изучить программу.
К сожалению исходников не осталось, только тот код, что присутствует тут, но надо учитывать что этот код я писал, когда опыта в программировании было очень мало. По большей части я пытался преподнести теорию, а код как вариант реализации.
Отправить комментарий