Пространство поиска пути - это территория разделенная на части, где будет искаться путь из одной точки в другую.
Существует множество способов разделить пространство поиска пути. Это клетки, шестиугольники, путевые точки (waypoints) и полигонная сетка (navigation mesh). Для простоты я буду использовать клетки.
Мы создадим пространство поиска пути в виде прямоугольника и разделим его на квадратики (такой квадрат называют ещё - chunk), но это задача легкая, поэтому усложним её. Так как в дальнейшем мы будем рассматривать алгоритм поиска пути A* (A star), хотелось бы отметить главный из его недостатков. Он состоит в том, что для нахождения пути к недоступному участку, алгоритм будет искать путь на всей карте, потратив много времени. Этого можно избежать, если разделить карту на закрытые участки (недоступные друг для друга). Об этом мы и поговорим.
Итого наша задача не только создать "карту" пути, но и сделать так, чтобы она делилась на зоны ("острова").
Как вы заметили по видео, если был изменен цвет в какой то области, то там происходила проверка либо на существование отделенных друг от друга зон, либо на их слияние.
Давайте пройдемся по этапам нашего алгоритма:
- Указываем номер области, для которой нужно сделать проверку.
- Ищем элемент карты, совпадающий с указанным номером, и добавляем его в массив для обработки. Этот квадрат будет являться частью новой зоны.
- Берем первый элемент из массива клеток, которые нам нужно проверить, и ищем для него проходимых соседей, которые будут добавляться в тот же массив. После чего элементу, который мы проанализировали, мы присваиваем новый номер зоны и удаляем его. Этот этап мы повторяем до тех пор, пока наш массив не станет пустым.
- Повторяем пункт №2 до тех пор, пока совпадений по заданному номеру области не будет обнаружено.
Пора переходить к практике. Создадим класс поиска пути с именем «CWayMap», который потом будет использоваться и для алгоритма А* (A star).
class CWayMap
{
private:
// структура, которая будет являться каждой ячейкой сетки
struct CMapChunk
{
// проходимость
int Passability;
};
// тип переменной для проходимости, означающий что нужна проверка
#define NO_INIT -1
// освобождение памяти
#define SafeDelete(b) if (b) { delete b; b = NULL;}
// cетка, которая состоит из наших клеток
CMapChunk * m_Grid;
// ширина сетки
int m_iGridWidth;
// высота сетки
int m_iGridHeight;
// размер чанка (клетки)
int m_iChunkSize;
// счетчик зон
int m_iCountZone;
// разделение клеток с определенным типом проходимости на зоны
void SplitZones(int iPassabilityType);
// создание зоны
void CreateZone(int iChunkID, int NewZone);
// проверки на воможность перемещения по диагонали
bool CheckDiagonals(int iNeighborX, int iNeighborZ, int iMasterX, int iMasterZ);
public:
CWayMap(int iWidth, int iHeight, int iSize);
~CWayMap(void);
// проверка существует ли клетка с указанной шириной и высотой в сетке
bool CheckRange(int iChunkX, int iChunkZ);
// смена значения проходимости клетки
void ChangePassability(int x, int z);
// возвращаем ID клетки по его ширине и высоте
int GetIDByPos(int iChunkX, int iChunkZ);
// проверка на диапазон и проходимость клетки
bool CheckPassability(int iChunkX, int iChunkZ);
};
Passability у нас будет отвечать за проходимость каждой ячейки сетки. Так же ячейку сетки я буду называть – клетка и чанк. Таким образом, сравнив значение Passability стартовой и конечной точки пути, можно будет сразу узнать – можно туда попасть или нет. А если оно равно нулю, то эта зона не проходима, таким образом можно легко это будет проверить:
Если (Passability) То можем_пройти;Начнем с конструктора:
CWayMap::CWayMap(int iWidth, int iHeight, int iSize)
{
// запоминаем размер ячейки
m_iChunkSize = iSize;
// вычисляем кол-во ячеек в ширину
m_iGridWidth = iWidth/iSize;
// вычисляем кол-во ячеек в высоту
m_iGridHeight = iHeight/iSize;
m_Grid = NULL;
// создаем нашу сетку с нужным кол-ом ячеек
m_Grid = new CMapChunk[m_iGridWidth*m_iGridHeight];
// проходимся по всем ячейкам и выставляем им одну зону
for (int x = 0; x < m_iGridWidth*m_iGridHeight; x++)
{
m_Grid[x].Passability = NO_INIT;
}
// у нас пока 0 зон, указываем это
int m_iCountZone = 0;
// делим нашу сетку на зоны, если они есть
SplitZones(NO_INIT);
}
Тут все просто… мы передаем в функцию размеры нашей игровой карты и размер ячейки, на которые будет разбита эта карта. Разбиваем карту, сохраняем нужные нам параметры и присваиваем каждой созданной ячейке значение NO_INIT. Указываем, что у нас на данный момент нет зон, и используем функцию «SplitZones», которая проверяет клетки с типом проходимости NO_INIT и разделяет их на зоны, если они есть, но об этом позже.
В деструкторе освобождаем память, которую выделяли для нашей сетки.
CWayMap::~CWayMap(void)
{
// освобождение памяти
SafeDelete(m_Grid);
}
Функция «CheckRange» проверяет, существует ли указанная ячейка в диапазоне нашей сетки, это понадобится при поиске соседей у клетки. Ведь на границе карты у нашей клетки может отсутствовать несколько соседей.
bool CWayMap::CheckRange(int iChunkX, int iChunkZ)
{
// если ширина ячейки меньше 0 или больше ширины сетки, возвращаем false,
// с высотой так же.
if ( iChunkX < 0 || iChunkZ < 0 || iChunkX > m_iGridWidth-1 || iChunkZ > m_iGridHeight-1)
return false;
return true;
}
Функция «GetIDByPos» возвращает номер клетки по высоте и ширине сетки.
int CWayMap::GetIDByPos(int iChunkX, int iChunkZ)
{
return iChunkZ*m_iGridWidth + iChunkX;
}
«CheckDiagonals» проверяет, является ли найденный сосед (клетка находящаяся рядом с исследуемой) «мастер» клетки диагональным, и если да, то можно ли туда переместиться, не срезав углы недоступных клеток. В моем примере я решил не допускать срезы углов (рис.1).
В эту функцию мы передаем «координаты» соседа и его хозяина.
bool CWayMap::CheckDiagonals(int iNeighborX, int iNeighborZ, int iMasterX, int iMasterZ)
{
// вычисяем разницу в ширине между соседем и «хозяином»
int iDiffX = iNeighborX - iMasterX;
// вычисяем разницу в высоте между соседем и «хозяином»
int iDiffZ = iNeighborZ - iMasterZ;
// если сосед является диагональным
if (iDiffX && iDiffZ)
{
// находим первого соседа для соседа соприкасающимся с «хозяином»
int iContact1X = iMasterX + iDiffX;
int iContact1Y = iMasterZ;
// если найденный сосед не проходимый, возвращаем false
if (!m_Grid[GetIDByPos(iContact1X, iContact1Y)].Passability)
return false;
// находим второго соседа для соседа соприкасающимся с «хозяином»
int iContact2X = iMasterX;
int iContact2Y = iMasterZ + iDiffZ;
// если найденный сосед не проходимый, возвращаем false
if (!m_Grid[GetIDByPos(iContact2X, iContact2Y)].Passability)
return false;
}
// в противном случае сосед «мастера» проходимый
return true;
}
«CheckPassability» проверяет, существует ли такой чанк в диапазоне нашей сетки и если существует, то является ли он проходимым.
bool CWayMap::CheckPassability(int iChunkX, int iChunkZ)
{
// если сосед существует в нашем диапазоне
if (CheckRange(iChunkX, iChunkZ))
{
// если этот сосед ещё не проверялся и является проходимым
if (m_Grid[GetIDByPos(iChunkX, iChunkZ)].Passability)
return true;
}
return false;
}
«CreateZone» это функция непосредственного создания зоны. В неё мы передаем номер клетки, с которой начнется исследование по определению закрытой зоны, а так же новый номер зоны, который мы будем присваивать.
void CWayMap::CreateZone(int iIDChunk, int iNewZone)
{
// вектор номеров ячеек, для которых надо найти всех соседей
std::vector aListForCheck;
// добавляем туда номер ячейки из параметра функции
aListForCheck.push_back(iIDChunk);
// до тех пор пока наш вектор не пуст
while(aListForCheck.size() != 0)
{
// вычисляем по номеру ячейки его ширину и высоту в сетке
int iChunkX = aListForCheck[0] % m_iGridWidth;
int iChunkZ = aListForCheck[0] / m_iGridWidth;
// проходимся по всем соседям
for (int i = -1; i <= 1; i++)
{
for (int j = -1; j <= 1; j++)
{
int iNeighborX = iChunkX+i;
int iNeighborZ = iChunkZ+j;
// проверка на диапазон и проходимость клетки
if (CheckPassability(iNeighborX, iNeighborZ))
{
// по его ширине и высоте находим номер в сетке
int iNeighborID = GetIDByPos(iNeighborX, iNeighborZ);
if (m_Grid[iNeighborID].Passability != iNewZone)
{
// если он является диагональным, то можно ли
// пройти в него не срезав углы
if (CheckDiagonals(iNeighborX, iNeighborZ, iChunkX, iChunkZ))
{
// устанавливаем ему новую зону
m_Grid[iNeighborID].Passability = iNewZone;
// добавляем его в вектор, для поиска его соседей
aListForCheck.push_back(iNeighborID);
}
}
}
}
}
// удаляем из вектора проверенную ячейку
aListForCheck.erase(aListForCheck.begin());
}
}
Суть такова: мы добавляем номер ячейки в вектор, в котором каждый элемент проверяется на возможных проходимых соседей, которые тоже потом добавляются в вектор. И так до тех пор, пока количество элементов в векторе не будет равно нулю. А это значит, что функция будет искать всех соседей и метить их до тех пор, пока мы не найдем закрытую зону.
Ну и вот наша главная функция «SplitZones», которая использовалась в конструкторе:
void CWayMap::SplitZones(int iPassabilityType)
{
// пробегаемся по всем ячейкам сетки
for (int x = 0; x < m_iGridWidth*m_iGridHeight; x++)
{
// если это та зона, которую нужно проверить
if (m_Grid[x].Passability == iPassabilityType)
{
// увеличиваем наши зоны
if (++m_iCountZone > INT_MAX -1)
// ошибка, счетчик переполнится и будет баг
showerror("ошибка, счетчик переполнится и будет баг");
// создаем новую зону
CreateZone(x, m_iCountZone);
}
}
}
Наверно уже понятно как она работает. Мы указываем номер зоны, который надо проверить (в конструкторе это NO_INIT), при первом поиске элемента с нужной зоной, функция «CreateZone» находит всех её соседей... потом соседей соседей… и так далее, присваивая им новое значение зоны… Но если мы потом опять в цикле встретим указанный номер зоны для проверки, то эта зона отделена от первой и проделываем для неё тоже самое. Ну и так далее пока не найдем все отделенные друг от друга зоны.
Как же быть, если произошли изменения на карте? Я сделал так:
- если ячейка изменилась на непроходимую, то проверяю, сколько у неё таких же непроходимых соседей, если больше 1 (не включая её саму), то делаю проверку на разделение той зоны, в которой появилась новая «стенка».
- если же «стенка» наоборот убралась, я устанавливаю новую зону всем её уникальным по зонам соседям, и делаю проверку этой новой общей зоны.
void CWayMap::SetPassability(int x, int z)Вот и все! Мы создали и разделили пространство поиска пути на клетки, по которым сможем искать путь. Так же реализовали "островную" систему, которая автоматически разделяет и делает слияние непроходимых зон на нашей карте. И теперь мы можем сразу определить до поиска пути: можно ли добраться из одной клетки в другую или нет?
{
// x и z это оконные координаты клика мыши, по ним находим ширину и высоту
// в сетке ячейки на которую тыкнули
int iChunkX = int(x)/m_iChunkSize;
int iChunkZ = int(z)/m_iChunkSize;
// по ширине и высоте ячейки находим её номер в сетке
int iChunkID = GetIDByPos(iChunkX, iChunkZ);
// запоминаем значение проходимости, так как мы его изменим
int iChangePassability = m_Grid[iChunkID].Passability;
// если мы убираем препятствие
if (!iChangePassability)
{
// указываем что нужна проверка
iChangePassability = NO_INIT;
m_Grid[iChunkID].Passability = NO_INIT;
}
else
// меняем на непроходимую
m_Grid[iChunkID].Passability = 0;
// вектор зон, которые возможно соединятся
std::vector< int > aZoneForSplit;
// кол-во найденных непроходимых соседей
int iCountBlock = 0;
// пробегаемся по соседям
for (int i = -1; i <= 1; i++)
{
for (int j = -1; j <= 1; j++)
{
// если это и есть ячейка, соседей которых мы ищем, то пропускаем
if (!j && !i)
continue;
int iNeighborX = iChunkX+i;
int iNeighborZ = iChunkZ+j;
// по ширине и высоте находим номер в сетке
int iNeighborID = GetIDByPos(iNeighborX, iNeighborZ);
// проверка на диапазон и проходимость клетки
if (CheckPassability(iNeighborX, iNeighborZ))
{
// если по клику мыши мы убрали «стену»
if (iChangePassability == NO_INIT)
{
// уникальна ли зона
bool bNewSplitZone = true;
for (unsigned int i = 0; i < aZoneForSplit.size(); i++ )
{
// если зона уже есть в списке, то она не уникальна
if (aZoneForSplit[i] == m_Grid[iNeighborID].Passability)
bNewSplitZone = false;
}
// если зона уникальная, то добавляем
if (bNewSplitZone)
aZoneForSplit.push_back(m_Grid[iNeighborID].Passability);
// меняем цвет зоны, где убрали стенку, на цвет соседа
m_Grid[iChunkID].Passability = m_Grid[iNeighborID].Passability;
}
}
// иначе увеличиваем счетчик «плохих» соседей
else
iCountBlock++;
// если найденных непроходимых соседей больше 1
if (iCountBlock > 1)
{
// если по клику мыши мы убрали «стену»
if (iChangePassability == NO_INIT)
{
// пробегаемся по всем ячейкам и из всех зон в aZoneForSpli
// делаем одну общую
for (int x=0; x < (m_iGridWidth * m_iGridHeight); x++)
{
for (unsigned int i = 0; i < aZoneForSplit.size(); i++ )
{
if (aZoneForSplit[i] == m_Grid[x].Passability)
{
m_Grid[x].Passability = NO_INIT;
break;
}
}
}
}
// перепроверяем и делим зону, если это требуется
SplitZones(iChangePassability);
return;
}
}
}
}
4 коммент.:
дикий фейковый код, куча логических ошибок, начиная от утечки памяти, и заканчивая неправильным определением проходимости по диагонали
1) укажите хоть одну утечку памяти в этом коде
2) неправильное определение проходимости по диагонали (не срезая при этом углы) показал бы тест
3) код из статьи доводит до читателя идею, никто не заставляет его использовать в своих проектах, всегда можно написать лучше и самим (без логических ошибок)
Утечка - delete для массивов должен быть delete []
недавно глянул свой код и ужаснулся)) как будет время поправлю
Отправить комментарий