31 мая 2011 г.

Передвижение по точкам

Если у нас есть путь из одной точки в другую, который мы нашли с помощью алгоритма А-звездочка (смотрите в предыдущих статьях), то почему бы нам не реализовать перемещение по этому пути?

Чтобы найти путь, который прошел наш объект, нам надо умножить потраченное время на скорость объекта. Скорость объекта мы будем задавать сами, а время будем вычислять разницей времени между кадрами.

Получив пройденный путь, мы его будем вычитать из нашего общего пути. Таким образом, в конце наш путь будет состоять из одной точки, конечной, куда мы и должны были добраться. Плюсы этого метода:
  • первая точка будет являться положением объекта в пространстве;
  • пройденные точки будут удаляться
Для удобства я удалил ранее созданную структуру "MapPoint" и заменил её на vector2f. Чтобы использовать vector2f, потребуется подключить Configurable Math Library. Как видно из названия это двухмерный вектор, где каждый элемент имеет тип float.


Работу программы, которую мы создадим, можно посмотреть тут:


Давайте взглянем на наш класс, который сможет передвигаться.
class CPathUser
{
private:
// скорость
float m_Speed;
// вектор наших точек пути
std::vector< vector2f > m_Way;
public:
CPathUser(void);
~CPathUser(void);
// установка скорости
void SetSpeed(float Speed);
// прошли ли мы заданный путь
bool IsWayFinished();
// перемещение
void Move(int iDeltaMilliSeconds);
// возвращение позиции
vector2f GetPos();
// установка позиции
void SetPos(vector2f Pos);
// установка пути
bool SetWay(vector2f EndPos);
};
Предлагаю взглянуть на код примитивный функций, который я не буду комментировать - тут и так все ясно.
CPathUser::CPathUser()
{
m_Speed = 0;
}

CPathUser::~CPathUser()
{

}

void CPathUser::SetSpeed(float Speed)
{
m_Speed = Speed;
}

bool CPathUser::IsWayFinished()
{
if (m_Way.size() > 1)
return false;
return true;
}

void CPathUser::SetPos(vector2f Pos)
{
m_Way.clear();
m_Way.push_back(Pos);
}

vector2f CPathUser::GetPos()
{
return m_Way[0];
}
Рассмотрим детально нашу функцию передвижения.
void CPathUser::Move(int iDeltaMilliSeconds)
{
// если мы уже прошли путь выходим
if (IsWayFinished())
return;
// находим пройденный путь
float WayLen = iDeltaMilliSeconds * m_Speed;
// пока у нас есть точки, между которыми можно перемещаться
while(m_Way.size() > 1)
{
// находим вектор между двумя точками
vector2f vDir = m_Way[1] - m_Way[0];
// находим длину полученного вектора
float fLen = vDir.length();
// находим разницу длины между точками
// и длины пути, который мы успели пройти
float fDelta = fLen - WayLen;
// если разница отрицательная
if (fDelta <= 0)
{
// отнимаем от пройденной длины, длину между точками
WayLen = abs(fDelta);
// удаляем пройденную точку
m_Way.erase(m_Way.begin());
}
// если положительная
else
{
// так как мы где то между точками
// найдем наше местоположение
vector2f NewPos = m_Way[0] + vDir.normalize()*WayLen;
// сохраним его в первую точку пути
m_Way[0] = NewPos;
return;
}
}
}
Функция задания нового маршрута. Мы будем сохранять положение, в котором находимся, и потом его опять добавлять, так как при расчете нового пути, наша первая точка изменится на центр ближайшего квадрата. Поэтому нам ещё придется менять первую точку пути (которая потом окажется второй, при вставке сохраненной точки), чтобы бы мы правильно передвинулись в нужный центр квадрата.
bool CPathUser::SetWay(vector2f EndPos) 
{
// так как мы сейчас можем находиться между двумя
// точками, сохраним наше местоположение
vector2f PosNow = m_Way[0];
// рассчитываем новый путь
bool ValidWay = Pathfinding.GetWay(m_Way[0], EndPos, &m_Way);
// если путь не найден
if (!ValidWay)
{
// добавляем точку, в которой мы сейчас
// находимся, так как путь очищен
m_Way.push_back(PosNow);
return false;
}
// находим направление движения
vector2f Diff = m_Way[1] - m_Way[0];
if (Diff[0])
Diff[0] = Diff[0]/abs(Diff[0]);
if (Diff[1])
Diff[1] = Diff[1]/abs(Diff[1]);

// правим первую точку пути для правильного движения
m_Way[0]= m_Way[0]+Diff*20;

// вставляем сохраненную точку, где мы сейчас есть
m_Way.insert(m_Way.begin(), PosNow);
return true;
}


24 мая 2011 г.

Оптимизация найденного пути

В чем заключается оптимизация найденного пути? Все очень просто: мы должны убрать точки лежащие на одной прямой. Но у меня идея получше: в момент построения пути не будем добавлять лишние точки.
Для этого нам потребуется отредактировать нашу функцию "CPathfinding::GetWay".

Как мы узнаем, что точки лежат на одной прямой? Так как у нас все клетки карты хранятся в одномерном массиве и имеют свой уникальный номер, то просто давайте найдем разницу между номерами добавляемых в карту клеток. И если при следующем добавлении разница совпадает, то эту клетку мы добавлять не будем.

Итого, вот так выглядит наш кусок кода, который в конце ищет точки пути и добавляет его:

while (ID != iMasterID)
{
ID = iMasterID;
iMasterID = GetMasterID(ID);
PointOfWay.x = ID % WayMap->GetGridWidth()* WayMap->GetChunkSize();
PointOfWay.z = ID / WayMap->GetGridWidth()* WayMap->GetChunkSize();

int iDelta = abs(ID-iMasterID);
if (iDelta != iSaveDelta)
{
Way->insert(Way->begin(), PointOfWay);
iSaveDelta = iDelta;
}
}


Вот и все, теперь наш путь оптимизирован и не будет содержать лишних ненужных точек.

23 мая 2011 г.

Стоимость передвижения в A star

В прошлых примерах мы рассматривали только два типа проходимости, где можно пройти и где нельзя. Давайте исправим ситуацию и рассмотрим реализацию, когда каждая клетка имеет разную степень проходимости, или как ещё говорят имеют разный вес. Мы просто раздадим разным клеткам разный вес в зависимости от рельефа. Чем темнее у нас будет клетка, тем больше времени она будет отнимать у "путника", который будет по ней идти.

Как же это реализовать? А все очень и очень просто! В структуре CMapChunk (смотрите прошлые статьи) мы введем дополнительный параметр RankPassability, который будет хранить вес проходимости.

Я, например, заполнил так, что в середине карты у меня получилась синусоида, как будто тропа между холмами :)

Сейчас вы наверно подумали, опять будет куча расчетов и нудятины, а вот и ничего подобного!

Как один из вариантов: мы просто в оценке пути при расчете F (F это сумма G и H) умножаем его результат на вес клетки:

Chunk.F = (Chunk.H + Chunk.G) * WayMap->GetRankPass(Chunk.ID);

Если вам эта строка ни о чем не говорит, и вы не знаете что такое F, H и G, то вы не читали мои прошлые статьи. А зря :)

ДА! И это все :) Вот результат:

Но внезапно на нашем пути появилась китайская стена :)

Ну и последний пример:

Таким образом можно задать болота, реки, рельеф и другие типы местности на карте.


A star в картинках


В прошлой статье мы рассмотрели алгоритм поиска пути A star, как на теории, так и на практике. Но было бы не плохо ещё разобраться наглядно не используя ни формулы ни код.

Представим, что у нас есть карта 6 на 5 клеток, итого 30, и нам надо попасть из клетки с номером 6 в 22.

Зеленым квадратиком, я буду обозначать, что эта клетка находится в открытом списке.
Синим - в закрытом.

Я выбрал именно это расположение стартовой, конечной точек и преград, потому что мне показался этот случай интересным. Как мы видим мы сразу добавили нашу стартовую клетку в открытый список. Напомню, открытый список служит для хранения клеток, которые нужно проверить, закрытый хранит уже проверенные ячейки.

Давайте взглянем на то, как я буду записывать данные ячейки:

Напомню обозначения из прошлого урока:
  • ID - номер ячейки в сетке;
  • mID - её родитель;
  • G - стоимость передвижения из стартовой клетки к данной. В моем примере каждое передвижение по горизонтали и вертикале будет стоить 10 единиц, а по диагонали 14. Так вот G это сумма единиц пройденного расстояния от начала до конкретно рассматриваемой точки;
  • H - стоимость передвижения от данной клетки до конечной по методу Манхеттена (Manhattan method). Этот метод состоит в том что мы рассчитываем расстояние только по горизонтали и вертикали, игнорируя препятствия и диагональные перемещения.
  • F - сумма G и H;
Так как в открытом списке у нас лишь одна клетка 6, то мы берем её для анализа.

Мы добавили её проходимых соседей в открытый список, оценили их путь и нашу клетку отправили в закрытый список. Теперь нам надо выбрать клетку с наименьшим значением F (цифра верхнего левого уголка) для анализа. Так как мы начинали искать соседей слева направо, то первая клетка с наименьшим F у нас будет 12.

Опять у нас спорный момент между клетками 7 и 18, но 7 была добавлена раньше. Значит, ищем её соседей.

Клетка под номером 18 была добавлена раньше.

Уже видно два пути, которых наш алгоритм пытается сравнить и выявить наименьший. Хоть нам и ясно какой из них будет верным, продолжим наше наглядное исследование. Ищем соседей для клетки 8.

Следующая клетка, соседей которой мы будем оценивать, это клетка 19. И она будет последним анализируемым звеном в не самом коротком пути (но я вам этого не говорил).

В порядке очереди выбираем клетку 9.

На данном этапе, у нас появилась одна единственная клетка с наименьшим F, и она под номером 16.

Добавляя соседей для клетки 16, мы так же добавили нашу конечную точку, а значит, пора останавливать нашу рутинную процедуру :) Теперь нам надо найти по клеткам, находящимся в закрытом списке наш путь. Так как мы храним их номера родителей (master ID, правая верхняя цифра в квадратике), то двигаясь с конца по родительским клеткам дойдем до стартовой, это и будет наш путь.

Ну и вот так выглядит наш путь найденный алгоритмом A*.

Думаю теперь, когда мы "разжевали" алгоритм поиска пути A star (на теории, на картинках, на практике), недопонимания и вопросов не осталось ни у кого. Теперь мы легко можем найти кратчайший путь из одной точки в другу.


22 мая 2011 г.

Алгоритм поиска пути A*

В этой статье мы рассмотрим поиск пути. Говорят, что алгоритм 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;
Теперь становится ясно, что каждый раз, мы будем искать точку с наименьшем значением F.

Давайте же взглянем на объявление нашего класса:
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;
}
Путевая точка, находящаяся на пересечении. Этот вариант реализован в коде данной статьи.

Путевая точка, находящаяся в центре квадрата. Чтобы реализовать этот вариант, вам надо к каждой путевой точке добавить половину размера клетки карты по x и z. Именно этот вариант я буду использовать в дальнейшем.

Вот мы и заполнили вектор точками найденного пути. В общем все просто! А ещё говорят, что алгоритм поиска пути A* сложен для новичков. Стоит обратить внимание на то, что мы в наш путь добавляем все путевые точки подряд, что совсем не правильно. В дальнейшем мы рассмотрим способ добавления путевых точек, пропуская при этом лишние. А следующая статья будет посвящена опять таки алгоритму A star, но только уже в виде картинок, для полного понимания и закрепления наших знаний.


13 мая 2011 г.

Пространство поиска пути

Пространство поиска пути - это территория разделенная на части, где будет искаться путь из одной точки в другую.

Существует множество способов разделить пространство поиска пути. Это клетки, шестиугольники, путевые точки (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).


Рис.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;
}
}
}
}
Вот и все! Мы создали и разделили пространство поиска пути на клетки, по которым сможем искать путь. Так же реализовали "островную" систему, которая автоматически разделяет и делает слияние непроходимых зон на нашей карте. И теперь мы можем сразу определить до поиска пути: можно ли добраться из одной клетки в другую или нет?


12 мая 2011 г.

Искусственный интеллект


Рассмотрим в этой статье искусственный интеллект. Статья будет разбита на разделы, поэтому каждый сможет быстро найти то, что его интересует.
1. Искусственный интеллект и его понятие.
2. Главные проблемы.
3. Задачи.
4. Технологии создания.



1. Искусственный интеллект и его понятие.
Искусственный интеллект (ИИ, Artificial intelligence, AI) — набор программных методик, которые используются в компьютерных играх для создания иллюзии интеллекта в поведении персонажей, управляемых компьютером. Его применяют для контролирования неигровых персонажей (Non-player character, NPC).

Искусственный интеллект является не просто частью игры, а одним из самых главных её составляющих. Кто то может представить себе игру без врагов? С кем нам сражаться и воевать, если их не будет?

Даже тетрис становится интересней, если компьютер будет играть параллельно с нами в каком-нибудь уголку окна, ведь появляется дух соперничества. Но не только вражеские интеллектуалы доставляют радость в играх. К большому сожалению, не во всех играх разработчики на сторону игрока ставят дружественных объектов «с мозгами». Постоянно бегать/летать/скакать одному очень угнетает, а когда кто-то рядом уже не так страшно, да и намного интересней.



2. Главные проблемы
Многие наверно скажут, что главная проблема, это то, что искусственный интеллект никогда не заменит человека. А ведь в компьютерных играх этого совсем и не нужно. Кто захочет перестреливаться с вражеским юнитом в какой-нибудь FSP (First-person shooter) десятки минут? Для этого вполне подойдет игра по сети.
По мне, две главные проблемы это – «сверхглупые» и «сверхумные» враги. В первом случае игрок довольно быстро заскучает, во втором обидится, а это приведет к тому, что игра будет закрыта. А кому нравится проигрывать? Целью искусственного интеллекта является вовсе не обыгрывать игрока.

Супер пупер врага наверно легче написать, чем глупого, так как у них нет погрешности при стрельбе, он знает куда надо стрелять (чтобы сразу попасть в голову), он имеет данных больше чем игрок, поэтому его от них надо ограничить. Можно сделать проверку, которая скажет виден ли враг для нашего NPC или нет, можно сделать ему разброс при стрельбе, способов подпортить его читерские способности навалом.



3. Задачи
Теперь, когда мы знаем понятие искусственный интеллект и где он применяется, хотелось бы узнать его задачи. Пустышкам, наделенных "электронным мозгом", обычно приходится решать в ходе игры такие же задачи, что и игрокам. А значит, мы сами ставим им задачи и учим их самостоятельно с ними справляться. Примерами таких задач являются следующие категории:

  • Движение (нахождение пути, патрулирование, перемещение, преследование, уклонение и др.);
  • Атака (стрельба, перезарядка, бросок гранаты, установка мины и др.);
  • Взаимодействие с предметами (включить/выключить свет, пнуть предмет, попавшийся на пути, подобрать боеприпасы и др.);
  • Связь с другими NPC (переговоры по рации, включение сигнализации, запуск сигнальной ракеты и др.)
Полно других очень и очень даже интересных задач.



4. Технологии создания ИИ в играх
Теперь ознакомимся с некоторыми самыми популярными технологиями создания игрового ИИ.

Система, основанная на правилах (Rule Based Systems).

Она заключается в составлении узкой области поведения при каких либо условиях. Таким образом, частичка этой системы состоит из условия и действия, а при объединении этих частиц получается - автоматизированная система, основанная на правилах (проверках). Как только одно из условий этой цепи возвращает истину, выполняется его действие и выход из системы.

Пример вражеского патрулирующего NPC:

Если наши жизни < 20%, то убегаем.
Если враг в зоне нашей атаки, то атакуем.
Если мы видим врага, бежим к нему.
Если наши силы = 100%, патрулируем.
Стоим.


Как видно из примера, последнее действие не имеет условия. Достаточно примитивный и простой способ для организации ИИ в простых играх. При большом объеме поставленных задач для ИИ, этот способ крайне неэффективен.

Конечные автоматы (Finite State Machine).

Эта система, описывающая поведение объекта, используют заранее подготовленные состояния, выбирая нужное. Для удобства рассмотрим пример выше, у нас получатся следующие состояния: стоять, патрулировать, преследовать, атаковать, убегать. Мы находимся в том или ином состоянии до тех пор, пока не произойдет некое событие.

Например: в состоянии патрулирования, если мы увидели врага, мы переходим в состояние «атаковать», а в случае если устали, то в состояние «стоять».

Конечные автоматы бывают детерминированными и недетерминированными. Детерминированные это те конечные автоматы, переход состояний которых определен строго. Недетерминированные же имеют некую случайность. Скажем, мы можем и вовсе не входить в состояние убегать, а воевать до победного конца или смерти. А так же мы можем «случайно» не увидеть врага, которого бы увидели в детерминированном конечном автомате.

Нейронные сети (Neural Network).

Нейронные сети эмулируют нервные клетки живого организма. Эта технология состоит из двух этапов: обучение и использование. Сам по себе искусственный интеллект сложно отлаживать, а если он основан на технологиях нейронных сетей, то вообще пиши пропало. Сама система немного сложна и я с ней ещё не сталкивался, но посчитал нужным, хотя бы просто сказать о ней пару слов.