| netlib.narod.ru | < Назад | Оглавление | Далее > |
Теперь, продравшись через дебри теории, загрузите проект D3D_PathFinding и следуйте за мной. Проект содержит следующие файлы с исходным кодом: main.h, main.cpp, CPathFinder.h и CPathFinder.cpp. Наиболее важны два файла с именами CPathFinder. Они содержат код класса поиска пути.
Помимо поиска пути в программе нет ничего новаторского. Код выполняет обычную работу создавая окно и инициализируя графику. После загрузки изображений программа загружает карту, на которой будет выполняться поиск пути. Поиск выполняется после того, как пользователь щелкнет по расположенной на панели команд кнопке Go. Кроме того, пользователь может загружать другие карты, чтобы посмотреть как алгоритм поиска пути ведет себя в разных обстоятельствах.
На рис. 12.11 изображен ход выполнения кода поиска пути.
Рис. 12.11. Ход выполнения кода поиска пути в main.cpp
Обратите внимание, как функция vInitPathing() использует при вычислении пути объект класса CPathFinder. Кроме того, на рисунке изображена функция iGetMapCost(), которая вычисляет базовую стоимость для данного узла карты. Вот ее код:
int iGetMapCost(int iX, int iY)
{
// Узел непроходим, если находится вне горизонтальных границ карты
if(iX < 0 || iX >= g_iTilesWide)
return(-1);
// Узел непроходим, если находится вне вертикальных границ карты
if(iY < 0 || iY >= g_iTilesHigh)
return(-1);
// Узел непроходим, если номер блока карты отличается от 0
if(g_iTileMap[iX + (iY * g_iMapWidth)][1] != 0) {
return(-1);
}
// Для всех остальных случаев возвращаем стоимость блока
else {
return(g_iTileMap[iX + (iY * g_iMapWidth)][1]);
}
}
Функция получения стоимости узла карты принимает в параметрах пару координат и возвращает значение, зависящее от того, какой блок находится в точке с указанными координатами. Если точка с заданными координатами находится вне карты, функция возвращает –1. Если в указанной точке находится блок, через который нельзя пройти, функция также возвратит –1. И только когда точка с заданными координатами находится в пределах карты и через соответствующий блок можно передвигаться, функция вернет его стоимость.
Как я говорил раньше, функция vInitPathing() использует функцию получения стоимости узла карты при обращении к объекту поиска пути. Вот код функции инициализации пути:
void vInitPathing(void)
{
bool bRet;
int iTempX;
int iTempY;
int iDir;
// Начальная и конечная позиции на карте
int iNodeStartX;
int iNodeStartY;
int iNodeEndX;
int iNodeEndY;
// Таймеры
DWORD dwStartTime;
DWORD dwTotalTime;
// Объект класса пути
CPathFinder pathMyPath;
// Очистить карту со стрелками
// Она используется в дальнейшем для отображения пути
for(int i = 0; i < g_iMapWidth * g_iMapHeight; i++) {
g_iArrowMap[i] = -1;
}
// Ищем на карте исходный пункт
for(int y = 0; y < g_iMapHeight; y++) {
for(int x = 0; x < g_iMapWidth; x++) {
if(g_iTileMap[x + (y * g_iMapWidth)][0] == 19) {
g_iRabbitXPos = x;
g_iRabbitYPos = y;
// Сохраняем исходное состояние
iNodeStartX = g_iRabbitXPos;
iNodeStartY = g_iRabbitYPos;
break;
}
}
}
// Ищем на карте конечный пункт
for(y = 0; y < g_iMapHeight; y++) {
for(int x = 0; x < g_iMapWidth; x++) {
if(g_iTileMap[x + (y * g_iMapWidth)][0] == 20) {
iNodeEndX = x;
iNodeEndY = y;
break;
}
}
}
// Обновляем отображаемое сообщение
sprintf(g_szPathStatus, "CALCULATING PATH");
vRender();
// Задаем функцию получения стоимости
pathMyPath.vSetCostFunction(iGetMapCost);
// Запуск таймера
dwStartTime = timeGetTime();
// Задаем начальную и конечную позиции
pathMyPath.vSetStartState(iNodeStartX, iNodeStartY,
iNodeEndX, iNodeEndY);
// Ищем путь - максимальная длина 300 узлов
bRet = pathMyPath.bFindPath(300);
// Остановка таймера
dwTotalTime = timeGetTime() - dwStartTime;
// Выход в случае сбоя
if(!bRet) {
// Обновляем отображаемое сообщение
sprintf(g_szPathStatus,
"FAILED, OPEN = %d, CLOSED = %d, TIME = %ld",
pathMyPath.m_iActiveOpenNodes,
pathMyPath.m_iActiveClosedNodes,
dwTotalTime);
return;
}
else {
// Обновляем отображаемое сообщение
sprintf(g_szPathStatus,
"COMPLETE, OPEN = %d, CLOSED = %d, TIME = %ld",
pathMyPath.m_iActiveOpenNodes,
pathMyPath.m_iActiveClosedNodes,
dwTotalTime);
}
// Теперь следуем по пути
CPathNode *GoalNode = pathMyPath.m_CompletePath->m_Path[0];
int iTotalNodes = 0;
// Устанавливаем временную позицию,
// чтобы определить направление стрелки
iTempX = GoalNode->m_iX;
iTempY = GoalNode->m_iY;
// Старт из позиции 1, а не 0
iTotalNodes++;
GoalNode = pathMyPath.m_CompletePath->m_Path[iTotalNodes];
// Перебираем в цикле составляющие путь узлы
// Для каждого шага рисуем стрелку
while(iTotalNodes < pathMyPath.m_CompletePath->m_iNumNodes) {
// Определяем направление стрелки
iDir = vFindDirection(iTempX, iTempY,
GoalNode->m_iX, GoalNode->m_iY);
// Сохраняем стрелку в карте стрелок
g_iArrowMap[GoalNode->m_iX + (GoalNode->m_iY * g_iMapWidth)]
= iDir;
// Визуализируем сцену
vRender();
// Устанавливаем временную позицию,
// чтобы определить направление стрелки
iTempX = GoalNode->m_iX;
iTempY = GoalNode->m_iY;
// Увеличиваем счетчик узлов
iTotalNodes++;
// Получаем следующий узел
GoalNode =
pathMyPath.m_CompletePath->m_Path[iTotalNodes];
};
}
Гм-м — придется просмотреть весьма много кода. Я знаю, что код выглядит сложно, но большая его часть предназначена для отображения стрелок, представляющих найденный путь. В первой части кода определяется где на карте кролик находится сначала и где он должен оказаться в конце. Поскольку начало и конец пути представлены на карте специальными блоками, код просто ищет их и сохраняет координаты их местоположения.
После того, как начальная и конечная точки маршрута обнаружены код передает в класс поска пути указатель на функцию получения стоимости узла карты. Это делается для того, чтобы класс поиска пути знал как вычислить наилучший из возможных путей, основываясь на базовой стоимости блоков ландшафта. После того, как задана функция получения стоимости узла карты, код устанавливает начальный и конечный пункты маршрута в объекте поиска пути. Это действие сообщает объекту между какими двумя пунктами ему следует проложить маршрут.
Все самое интересное происходит когда программа вызывает принадлежащую объекту поиска пути функцию bFindPath(). Именно она выполняет работу по поиску наиболее эффективного пути на карте от начального до конечного пункта. Если путь найден, функция возвращает 1; если путь найти не удалось, функция возвращает 0.
Чтобы отобразить найденный путь на экране программа перебирает в цикле все входящие в путь узлы карты, начиная с первого, пока не доберется до цели. Проходя по пути она отображает стрелки, чтобы показать путь по которому кролик добирается от одного узла к другому. Направление вычисляется на основании данных о местоположении предыдущего узла пути относительно текущего. Здесь вступает в игру функция vFindDirection(). Она очень простая, поскольку лишь вычисляет какую именно стрелку необходимо отображать.
Я могу потратить 50 страниц на описание кода, но в классе CPathFinder есть только одна заслуживающая внимания функция. Это функция bFindPath(), которая выполняет всю работу по нахождению наиболее эффективного пути из одного пункта в другой. Взгляните на рис. 12.12, где изображено как работает эта функция.
Рис. 12.12. Ход выполнения функции bFindPath()
Код начинается с помещения стартового узла в закрытый список. Затем он ищет все открытые узлы, расположенные вокруг текущего узла (им является стартовый узел). После того, как найдены все открытые узлы, код поверяет есть ли среди них цель. Если да, то путь инвертируется и функция возвращает код успешного завершения. Если цель отсутствует в открытом списке, код ищет открытый узел с наименьшей стоимостью и добавляет его в закрытый список. Процесс повторяется и будет завершен если найден путь до цели, либо если в открытом списке не осталось узлов, либо если превышено максимальное количество узлов пути.
Функция поиска пути не самая сложная и не самая большая, но именно она координирует усилия по поиску пути. Остальные функции выполняют лишь вспомогательные роли и вы должны приспособить их к вашей программе.
| netlib.narod.ru | < Назад | Оглавление | Далее > |