游戏中如何实现自动寻路？A*算法斜线版本与DEBUG功能详解
最编程
2024-02-01 12:13:47
...
一、简述以及地图
- G 表示从起点移动到网格上指定方格的移动距离 (暂时不考虑沿斜向移动，只考虑上下左右移动)。
- H 表示从指定的方格移动到终点的预计移动距离，只计算直线距离，走直角篇走的是直角路线。
- 令 F = G + H ，F 即表示从起点经过此点预计到终点的总移动距离接下来我们从起点开始，按照以下寻路步骤，直至找到目标。
- 从起点开始, 把它作为待处理的方格存入一个预测可达的节点列表，简称 openList, 即把起点放入“预测可达节点列表”， 可达节点列表 openList 就是一个等待检查方格的列表。
- 寻找 openList 中 F 值最小的点 min（一开始只有起点）周围可以到达的方格（可到达的意思是其不是障碍物，也不存 在关闭列表中的方格,即不是已走过的方格）。计算 min 周围可到达的方格的 F 值。将还没在 openList 中点放入其中, 并 设置它们的"父方格"为点 min,表示他们的上一步是经过 min 到达的。如果 min 下一步某个可到达的方格已经在 openList 列表那么并且经 min 点它的 F 值更优,则修改 F 值并把其"父方格"设为点 min。
- 把 2 中的点 min 从"开启列表"中删除并存入"关闭列表"closeList 中, closeList 中存放的都是不需要再次检查的方格。如 果 2 中点 min 不是终点并且开启列表的数量大于零，那么继续从第 2 步开始。如果是终点执行第 4 步，如果 openList 列 表数量为零，那么就是找不到有效路径。
- 如果第 3 步中 min 是终点，则结束查找，直接追溯父节点到起点的路径即为所选路径
案例地图说明：
起点：5.2
终点：5.10
障碍：*红色坐标
二、示例代码：
代码中带有 DEBUG 打印，开关在 Astar.h 的宏定义中
main.cpp
1 #include "Astar.h" 2 #include <list> 3 #include <iostream> 4 #include <windows.h> 5 6 7 using namespace std; 8 9 //定义地图数组,二维数组在内存顺序存储的 10 int map[13][13] = { 11 { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 12 { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 13 { 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 }, 14 { 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 }, 15 { 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 }, 16 { 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 }, 17 { 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 }, 18 { 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 }, 19 { 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 }, 20 { 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 }, 21 { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 22 { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 23 { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } 24 }; 25 26 void AStarTest() 27 { 28 InitAstarMaze(&map[0][0], 13, 13); 29 30 //设置起始和结束点 31 Point* start = AllocPoint(5, 2); 32 Point* end = AllocPoint(5, 10); 33 34 //A*算法找寻路径 35 list<Point*> path = GetPath(start, end); 36 cout << "\n寻路结果:" << endl; 37 38 for(list<Point*>::const_iterator iter = path.begin(); iter != path.end(); iter++) 39 { 40 cout << '(' << (*iter)->x << ',' << (*iter)->y << ')' << endl; 41 Sleep(10); 42 } 43 44 ClearAstarMaze(); 45 } 46 47 int main(void) 48 { 49 AStarTest(); 50 system("pause"); 51 return 0; 52 }
Astar.h
1 #pragma once 2 3 #include <list> 4 5 #define DEBUG 1 //打印 DEBUG 6 7 const int kCost1 = 10; //直移一格消耗 8 const int kCost2 = 14; //斜移一格消耗 9 10 typedef struct _Point 11 { 12 int x, y; //点坐标，这里为了方便按照 C++的数组来计算，x 代表横排，y 代表竖列 13 int F, G, H; //F=G+H 14 struct _Point* parent; //parent 的坐标 15 }Point; 16 17 /*分配一个节点(格子)*/ 18 Point* AllocPoint(int x, int y); 19 20 /*初始化地图*/ 21 void InitAstarMaze(int* _maze, int _lines, int _colums); 22 23 /*通过 A* 算法寻找路径*/ 24 std::list<Point*> GetPath(Point* startPoint, Point* endPoint); 25 26 /*清理资源，结束后必须调用*/ 27 void ClearAstarMaze();
Astar.cpp
1 #include <math.h> 2 #include "Astar.h" 3 #include <iostream> 4 #include <vector> 5 6 static int* maze; //迷宫对应的二维数组，使用一级指针表示 7 static int lines; //二维数组对应的行数 8 static int cols; //二维数组对应的列数 9 static std::list<Point*> openList; //开放列表 10 static std::list<Point*> closeList; //关闭列表 11 12 /*搜索从起点到终点的最佳路径*/ 13 static Point* findPath(Point* startPoint, Point* endPoint); 14 15 /*从开启列表中返回 F 值最小的节点*/ 16 static Point* getLeastFpoint(); 17 18 /*获取当前点周围可达的节点*/ 19 static std::vector<Point*> getSurroundPoints(const Point* point); 20 21 /*判断某点是否可以用于下一步判断 */ 22 static bool isCanreach(const Point* point, const Point* targetNode); 23 24 /*判断开放/关闭列表中是否包含某点*/ 25 static Point* isInList(const std::list<Point*>& list, const Point* point); 26 27 //计算 FGH 值 28 static int calcG(Point* temp_start, Point* point); 29 static int calcH(Point* point, Point* end); 30 static int calcF(Point* point); 31 32 /*分配一个节点(格子)*/ 33 Point* AllocPoint(int x, int y) 34 { 35 Point* temp = new Point; 36 memset(temp, 0, sizeof(Point)); //C语法 初始值清零 37 temp->x = x; 38 temp->y = y; 39 return temp; 40 } 41 42 /*初始化 A*搜索的地图*/ 43 void InitAstarMaze(int* _maze, int _lines, int _colums) 44 { 45 maze = _maze; 46 lines = _lines; 47 cols = _colums; 48 } 49 50 /*通过 A* 算法寻找路径*/ 51 std::list<Point*> GetPath(Point* startPoint, Point* endPoint) 52 { 53 Point* result = findPath(startPoint, endPoint); 54 std::list<Point*> path; 55 56 //返回路径，如果没找到路径，返回空链表 57 while(result) 58 { 59 path.push_front(result); 60 result = result->parent; 61 } 62 return path; 63 } 64 65 /*搜索从起点到终点的最佳路径*/ 66 static Point* findPath(Point* startPoint, Point* endPoint) 67 { 68 openList.push_back(AllocPoint(startPoint->x, startPoint->y)); //置入起点,拷贝开辟一个节点，内外隔离 69 70 71 while(!openList.empty()) 72 { 73 //第一步，从开放列表中取最小 F 的节点 74 Point* minNodeF = getLeastFpoint(); //找到 F 值最小的点 75 76 if(DEBUG) 77 { 78 int i = 1; 79 for(std::list<Point*>::const_iterator iter = openList.begin(); iter != openList.end(); iter++) 80 { 81 std::cout << "开放链表第" << i++ << "个节点为: " << (*iter)->x << "," << (*iter)->y << " F值为：" << (*iter)->F; 82 if ((*iter)->parent != NULL) 83 { 84 std::cout << " --->父节点为：" << (*iter)->parent->x << "," << (*iter)->parent->y << std::endl; 85 } 86 else 87 { 88 std::cout << std::endl; 89 } 90 } 91 std::cout << "===================================" << std::endl; 92 std::cout << "从开放列表中取最小 F 的节点为：" << minNodeF->x << "." << minNodeF->y << std::endl; 93 std::cout << "=============================================" << std::endl; 94 } 95 96 //第二步，把当前节点放到关闭列表中 97 openList.remove(minNodeF); 98 if(DEBUG) 99 { 100 std::cout << "开放链表移除、关闭链表增加节点为: " << minNodeF->x << "," << minNodeF->y << " F值为：" << minNodeF->F << std::endl; 101 std::cout << "=======================================================" << std::endl; 102 } 103 closeList.push_back(minNodeF); 104 if(DEBUG) 105 { 106 int i = 1; 107 for(std::list<Point*>::const_iterator iter = closeList.begin(); iter != closeList.end(); iter++) 108 { 109 std::cout << "关闭链表第" << i++ << "个节点为: " << (*iter)->x << "," << (*iter)->y << " F值为：" << (*iter)->F; 110 if ((*iter)->parent != NULL) 111 { 112 std::cout << " --->父节点为：" << (*iter)->parent->x << "," << (*iter)->parent->y << std::endl; 113 } 114 else 115 { 116 std::cout << std::endl; 117 } 118 } 119 std::cout << "===========================================================\n\n" << std::endl; 120 } 121 122 //第三步，找到当前节点周围可达的节点，并计算 F 值 123 std::vector<Point*> surroundPoints = getSurroundPoints(minNodeF); 124 for(std::vector<Point*>::const_iterator iter = surroundPoints.begin(); iter != surroundPoints.end(); iter++) 125 { 126 //周围可到达点 127 Point* targetNode = *iter; 128 129 /*对某一个格子，如果它不在开放列表中，设置当前格为其父节点，计算 F G H, 并加入到开启列表。否则重新计算G值*/ 130 Point* exist = isInList(openList, targetNode); 131 if(!exist) 132 { 133 targetNode->parent = minNodeF; 134 targetNode->G = calcG(minNodeF, targetNode); 135 targetNode->H = calcH(targetNode, endPoint); 136 targetNode->F = calcF(targetNode); 137 openList.push_back(targetNode); 138 } 139 else 140 { 141 if (DEBUG) 142 { 143 std::cout << ">>" << exist->x << "," << exist->y << " 在开放链表 跳过<<" << std::endl; 144 } 145 //int tempG = calcG(minNodeF, targetNode); 146 //if (tempG < targetNode->G) 147 //{ 148 // exist->parent = minNodeF; 149 // exist->G = tempG; 150 // exist->F = calcF(targetNode); 151 //} 152 //delete targetNode; 153 } 154 } 155 surroundPoints.clear(); 156 Point* resPoint = isInList(openList, endPoint); 157 if(resPoint) 158 { 159 if (DEBUG) 160 { 161 std::cout << "开放链表中找到了结束节点: " << resPoint->x << "," << resPoint->y; 162 if (resPoint->parent != NULL) 163 { 164 std::cout << " --->父节点为：" << resPoint->parent->x << "," << resPoint->parent->y << std::endl; 165 } 166 else 167 { 168 std::cout << std::endl; 169 } 170 } 171 return resPoint; 172 } 173 } 174 return NULL; 175 } 176 177 /*从开启列表中返回 F 值最小的节点*/ 178 static Point* getLeastFpoint() 179 { 180 if(!openList.empty()) 181 { 182 Point* resPoint = openList.front(); 183 184 for(std::list<Point*>::const_iterator itor = openList.begin(); itor != openList.end(); itor++) 185 { 186 if((*itor)->F < resPoint->F) 187 { 188 resPoint = *itor; 189 } 190 } 191 return resPoint; 192 } 193 return NULL; 194 } 195 196 /*获取当前点周围可达的节点*/ 197 static std::vector<Point*> getSurroundPoints(const Point* point) 198 { 199 std::vector<Point*> surroundPoints; 200 for(int x = point->x - 1; x <= point->x + 1; x++) 201 { 202 for(int y = point->y - 1; y <= point->y + 1; y++) 203 { 204 Point* temp = AllocPoint(x, y); 205 if (DEBUG) 206 { 207 std::cout << " 判断周围坐标点: " << temp->x << "," << temp->y << std::endl; 208 } 209 if(isCanreach(point, temp)) 210 { 211 surroundPoints.push_back(temp); 212 } 213 else 214 { 215 delete temp; 216 } 217 } 218 } 219 if (DEBUG) 220 { 221 std::cout << "minNodeF周围点收集判断完毕" << std::endl; 222 } 223 224 return surroundPoints; 225 } 226 227 /*判断某点是否可以用于下一步判断 */ 228 static bool isCanreach(const Point* point, const Point* targetNode) 229 { 230 if(targetNode->x<0 231 || targetNode->x>(lines - 1) 232 || targetNode->y<0 233 || targetNode->y>(cols - 1) 234 || maze[targetNode->x * cols + targetNode->y] == 1 //为 1 的障碍物判断 235 || maze[targetNode->x * cols + targetNode->y] == 2 //为 2 的障碍物判断 236 || (targetNode->x == point->x && targetNode->y == point->y) 237 || isInList(closeList, targetNode)) 238 { 239上一篇： C++打造简易版24点游戏
下一篇： 玩转24点！用Java来实现