Ход выполнения кода поиска пути в 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(). Она очень простая, поскольку лишь вычисляет какую именно стрелку необходимо отображать.



- Начало - - Назад - - Вперед -