idea建设完整的网站,东营运政信息网官网查询,h5科技 网站,苏州网站建立公司在游戏当中#xff0c;经常需要找一个点到其它点的路径。在之前的一篇博文(地图编辑器开发#xff08;三#xff09;)中也有使用到到A寻路。我们期望能找到最短的路径#xff0c;同时也需要考虑到查找路径的时间消耗。游戏中的地图可以图的数据结构来表示#xff0c;然后使…在游戏当中经常需要找一个点到其它点的路径。在之前的一篇博文(地图编辑器开发三)中也有使用到到A寻路。我们期望能找到最短的路径同时也需要考虑到查找路径的时间消耗。游戏中的地图可以图的数据结构来表示然后使用图的搜索算法来搜索最短路径。在图的搜索算法中使用最为广泛的的是A寻路算法它是对图广度优先搜索的优化图广度优先搜索又是一种图的遍历万丈高楼平地起我们先从基础数据结构的遍历讲起到广度优先遍历最后拓展到A*寻路算法。
一 遍历
遍历Traversal是指沿着某条搜索路线依次对多元素集合中的每个元素均做且仅做一次访问。根据遍历代码的实现方式可以分为两种迭代遍历和递归遍历。
1.1 线性表的遍历
对于最简单的数据结构线性表比如数组、链表等其遍历方式的实现通常使用的是迭代遍历递归遍历用的比较少。在遍历的过程中根据元素的访问顺序又可以分为前序遍历和后续遍历利用后续遍历可以实现逆序访问效果。线性表几种遍历方式的核心代码如下
// 数组迭代遍历
void traverse(vectorint arr) {for (int i 0; i arr.size(); i) {// 迭代访问 arr[i]}
}// 链表迭代遍历
void traverse(ListNode* head) {for (ListNode* p head; p ! nullptr; p p-neighbor) {// 迭代访问 p - val}
}// 递归遍历数组
void traverse(vectorint arr, int i) {//前序访问 arr[i]traverse(arr, i 1);//后序访问 arr[i]
}// 递归遍历单链表
void traverse(ListNode* head) {//前序访问 head - valtraverse(head - neighbor);//后序访问 head - val
}1.2 二叉树的遍历
相对于线性表而言二叉树多了一个后继节点结构复杂了一点。对于非线性表的遍历通过是使用递归的方式实现。
1.2.1 二叉树的深度优先
因为二叉树有两个后继节点便有三个访问位置多出了一个中序访问位置。二叉树的深度优先遍历通常都是使用递归实现代码清晰容易理解当然也可以使用迭代实现不过迭代实现的代码比较长且难以写出像递归那样风格统一的代码。迭代遍历的过程就是利用栈来模拟递归调用过程因为栈是后进先出因此入栈的顺序于访问的顺序相仿。下面这种二叉树迭代遍历的写法是目前能收集到风格比较统一的非递归实现方式它巧妙地使用了一个空节点作为是否访问过的标记。两种迭代方式实现的核心代码如下
// 递归实现
void traverse(TreeNode* root) {// 前序访问 root-valtraverse(root-left);// 中序访问 root-valtraverse(root-right);// 后序访问 root-val
}// 迭代实现
vectorint traverse(TreeNode* root) {vectorint result;stackTreeNode* st;if (root) st.push(root);while (!st.empty()) {TreeNode* node st.top();st.pop();if (node) { // 入栈节点顺序于访问顺序相反// 前序遍历中左右if (node-right) st.push(node-right); // 右if (node-left) st.push(node-left); // 左st.push(node); // 中st.push(nullptr); // 空路过但未访问加入空节点做为标记// 中序遍历左中右if (node-right) st.push(node-right); // 右st.push(node); // 中st.push(nullptr); // 空if (node-left) st.push(node-left); // 左// 后序遍历左右中st.push(node); // 中st.push(nullptr); // 空if (node-right) st.push(node-right); // 右if (node-left) st.push(node-left); // 左} else { // 出栈只在出栈时加入到返回值node st.top();st.pop();result.push_back(node-val);}}return result;
}1.2.2 二叉树的广度优先
因为二叉树有两个后继节点除了像深度优先遍历那样从跟节点一直访问到叶子节点外多出一种访问路线即广度优先它先访问二叉树同一深度的所有节点然后访问下一深度的所有节点。二叉树的广度优先也叫二叉树的层次遍历通常都是使用队列来实现。
// 迭代实现 - BFS
void traverse(TreeNode* root) {if (!root) return;queueTreeNode* q;q.push(root);// 从上到下遍历二叉树的每一层int depth 0;while (!q.empty()) {depth;int breadth q.size();// 从左到右遍历每一层的每个节点for (int i 0; i breadth; i) {TreeNode* cur q.front();q.pop();// 访问 cur - val// 将下一层节点放入队列if (cur-left) q.push(cur-left);if (cur-right) q.push(cur-right);}}
}// 递归实现 - BFS:利用递归访问每一层的节点
vectorvectorint res;
void traverse(queueTreeNode* curLevelNodes) {if (curLevelNodes.empty()) {return;}vectorint nodeValues;queueTreeNode* neighborLevelNodes;while (!curLevelNodes.empty()) {// 取出当前层的节点TreeNode* node curLevelNodes.front();curLevelNodes.pop();nodeValues.push_back(node-val);// 将下一层的节点加入队列if (node-left) neighborLevelNodes.push(node-left);if (node-right) neighborLevelNodes.push(node-right);}// 记录当前层的节点值取得自上而下的遍历结果res.push_back(nodeValues);traverse(neighborLevelNodes);
}1.3 多叉树的遍历
多叉树是在二叉树的基础上多出1~N个后续节点。节点变多后中序难以定义所以多叉树没有了中序遍历只有前序遍历和后续遍历。对照二叉树的遍历方式可以得出多叉树的遍历核心代码如下
// 迭代实现 - DFS
void traverse(TreeNode* root) {// 前序访问 root-valfor (TreeNode* child : root-children)traverse(child);// 后序访问 root-val
}// 迭代实现 - BFS
void traverse(TreeNode* root) {if (!root) return;queueTreeNode* q;q.push(root);int depth 0;while (!q.empty()) {depth;int breadth q.size();for (int i 0; i breadth; i) {TreeNode* cur q.front();q.pop();// 访问 cur - valfor (auto child : cur-children) {q.push(child);}}}
}1.4 图的遍历
多叉树后续节点有0N个但前驱节点最多只有一个。图的结构是在多叉树的基础上新增了前驱节点的数量也可以有0N个这也导致了图中可能有环的村在所以在图的遍历过程中需要一个 visited 数组来记录节点是否被访问过防止节点被多次访问避免死循环的出现。图通常是用迭代遍历两种遍历方式的核心代码如下
// 图的广度优先
void traverse(Node* root) {if (!root) return;queueTreeNode* q;q.push(root);int depth 0;while (!q.empty()) {depth;int breadth q.size();for (int i 0; i breadth; i) {Node* cur q.front();q.pop();// 访问 cur - valfor (auto child : cur-neighbors) {if (!visited[child]) q.push(child);}}}
}// 图的深度优先
vectorbool visited; // 记录被遍历过的节点
vectorbool onPath; // 记录从起点到当前节点的路径
void traverse(Graph graph, Node s) {if (visited[s]) return;// 经过节点 s标记为已遍历visited[s] true;// 做选择标记节点 s 在路径上onPath[s] true;for (Node neighbor : graph.neighbors(s)) {traverse(graph, neighbor);}// 撤销选择节点 s 离开路径onPath[s] false;
}以上就是基础数据结构遍历的全部内容从至多只有一个前驱和后继节点的线性表开始到有多个后继节点的树再到有多个前驱节点的图。接下来基于图的遍历开始讨论寻路算法。
二 寻路算法
2.1 地图的表示
在学习一个算法时要做的第一件事是要理解数据弄清楚它的输入是什么、输出是什么 输入图搜索算法包括A*都是用“图”作为输入图是由一组点及其之间连接的边组成除此之外算法不知道任何其它内容诸如地图上是室内或是室外、是房间或者门廊、或者面积多大等它知道的唯一内容就是图。无论地图上的内容是什么样只要图是一致的对算法来说就没有任何区别。 输出寻路算法找到的路径是由图中的顶点和边组成。边是抽象的数学概念寻路算法只会告诉你从哪个点移动到哪个点但不会关注如何移动。记住算法不知道任何的房间或门它只知道图。我们必须自己决定算法返回的边表示的是什么意思是从一个网格移动到另一个网格还是从一个点直线走到另一个点或是开一个门或是游泳过去亦或是沿着一个曲线路跑。
对于任何给定的游戏地图都有许多不同的方法可以制作寻路图给到寻路算法。例如地图上的门既作为顶点也可以作为边还可以作为可行走的网格寻路图无须跟游戏中使用的地图保持一模一样网格地图也可以使用非网格的寻路图反之亦然。寻路网格易于制作和展示虽然缺点是节点太多地图中的节点越少寻路算法运行就越快但在此讨论的是寻路算法而不讨论地图的设计因此后续将使用寻路网格来讨论。
有很多基于图的算法接下来讨论的内容包括
广度优先搜索它从起点开始平等地向所有方向进行探索。毋庸置疑这是一个非常有用的算法不仅可以用于常规的寻路还可以用于地图的生成、流场寻路flow field pathfinding、距离图distance maps以及其它类型的地图分析。Dijkstra 算法它让我们确定要探索的路径的优先级不是平等地探索所有可能的路径而是偏向于成本较低的路径。我们可以在推荐走的路径上设置更低的成本在有敌人的路径上设置更高的成本等等。当移动成本不同时我们使用Dijkstra 算法而不是广度优先搜索。A算法它是 Dijkstra 算法的改进版针对单个目标点进行了优化。Dijkstra 算法可以搜索起点到所有顶点的最短路径A寻路算法只能找到起点到一个目标点的最短路径它优先考虑那些似乎更接近目标的路径。
接下来我将从最简单的广度优先搜索开始然后一次添加一个功能直到将其转换为 A* 算法。
2.2 广度优先遍历BFS
所有这些算法的关键思想是跟踪一个称为 openList 的扩展环。在网格地图上这个过程有时被称为“洪水填充”因为探索的过程是中起点开始像水波一样向四周扩散同样的技术也适用于非网格地图算法的具体过程如下
将起点放入到队列 openList 和 visited (记录已访问过的节点) 中重复以下步骤直到 openList 为空 从队列 openList 中取出一个顶点 current遍历 current 所有相邻的节点 neighbors跳过墙将所有未被访问过的节点同时加入到 openList 和 visited 。
void breadth_first_search(Graph graph, Node start)
{queueNode openList;openList.push(start);// 记录顶点是否已被访问过unordered_setNode visited;visited.insert(start);while (!openList.empty()) {Node current openList.front();openList.pop();for (auto neighbor : graph.neighbors(current)) {if (visited.find(neighbor) visited.end()) {openList.push(neighbor);visited.insert(neighbor);}}}
}这段代码中的循环是这个系列图搜索算法包括A*算法的基础。我们怎么才能找到最短路径呢这个函数实际上并没有生成一个路径它仅仅是告诉我们如何遍历整个地图这是因为广度优先搜索的用途远不止寻路。这里我们想用它来寻路需要改一下这个循环让它把移动轨迹保存下来对于每个访问到的节点记录它从哪里来。我们将 visited 重命名为 came_from并记录上一个节点。
unordered_mapNode, Node breadth_first_search(Graph graph, Node start)
{queueNode openList;openList.push(start);// 记录顶点的来路unordered_mapNode, Node came_from;came_from[start] start;while (!openList.empty()) {Node current openList.front();openList.pop();for (auto neighbor : graph.neighbors(current)) {if (came_from.find(neighbor) came_from.end()) {openList.push(neighbor);came_from[neighbor] current;}}}return came_from;
}现在 came_from 中记录了每个到达过的顶点从哪里来。他们虽然看起比较零散但可以重建整个路径。重建的过程也很简单从目标点开始一个一个往回找它从哪里来直到找到起点经过的所有顶点就是从终点到起点的路径逆序之后就是从起点到终点的路径。路径理论上是一组边的集合但通常保存顶点更加容易。
vectorNode reconstruct_path(Node start, Node end, unordered_mapNode, Node came_from)
{vectorNode path;if (came_from.find(goal) came_from.end()) {return path; // 没有找到路径}auto current goal;while(current ! start) {path.push_back(current);current came_from[current]}reverse(path.begin(), path.end());return path;
}这个就是最简单的寻路算法此算法既可以在网格地图寻路中使用也适用于其它任何类型的图结构。
提前退出上面的代码找到了起点到其他所有顶点的路径但通常只需要找到起点到另外一个点即目标点的路径我们可以在找到目标点后立即停止探索 openList。
unordered_mapNode, Node breadth_first_search(Graph graph, Node start)
{queueNode openList;openList.push(start);unordered_mapNode, Node came_from;came_from[start] start;while (!openList.empty()) {Node current openList.front();openList.pop();// 找到目标点后则停止搜索if (current goal) break;for (auto neighbor : graph.neighbors(current)) {if (came_from.find(neighbor) came_from.end()) {openList.push(neighbor);came_from[neighbor] current;}}}return came_from;
}移动成本目前为止我们认为所有的移动都有相同的成本在一些寻路场景中不同类型的移动具有不同的成本比如在游戏《文明》中在平地或沙漠上移动消耗1点能量但在冰川或山上移动需要消耗5个点能量比如在穿过水的成本是穿过草地的10倍另一个例子是在网格地图中对角线上的移动成本高于在轴向上的移动成本所以我们需要在寻路的过程中考虑到移动的成本即 Dijkstra 算法。
2.3 Dijkstra 算法
Dijkstra 算法与广度优先搜索有什么不同呢我们需要记录移动的成本所以我们添加一个新的变量 cost_so_far 保存从起点开始的总移动成本。当我们在选择下一个要探索的顶点时希望将移动成本考虑在内。让我们将队列改为小数优先队列以保证每次选择的都是成本最小的顶点。不太明显的是我们最终可能会以不同的成本多次访问一个顶点因此我们需要稍微改变一下逻辑 —— 将如果从未到达过该顶点则将顶点直接添加到 openList改为当通往该顶点的新路径优于之前的最佳路径时也添加该顶点。
void dijkstra_search(Graph graph, Node start, Node goal)
{priority_queue Node, vectorNode, lessNodeCompare openList; // 使用小值优先队列替代普通队列openList.push(start, 0);unordered_mapNode, Node came_from;came_from[start] start;unordered_mapNode, int cost_so_far; // 记录移动到顶点时的最低成本cost_so_far[start] 0;while (!openList.empty()) {Node current openList.front();openList.pop();if (current goal) break;for (auto neighbor : graph.neighbors(current)) {double new_cost cost_so_far[current] graph.cost(current, neighbor);// 顶点没有访问过或新路径成本更低则更新移动节点的成本if (cost_so_far.find(neighbor) cost_so_far.end() || new_cost cost_so_far[neighbor]) {cost_so_far[neighbor] new_cost;came_from[neighbor] current;openList.push(neighbor, new_cost);}}}
}使用优先队列替代普通队列改变了 openList 队列探索的方式同时探索的速度也变慢了。Dijkstra 算法可是计算除 1 之外的移动成本从而允许我们探索更有趣的图形而不仅仅是网格。 ps: 对比一下 Dijkstra 算法和 Prim 算法 Dijkstra 算法用于求单源最短路径从优先队列中存的是离起点的距离最近的点 Prim 算法用于求最小生成树从优先队列中存的是与MSG相连权值最小边 2.4 A* 算法
2.4.1 贪婪最佳优先搜索GBFS
在广度优先搜索和 Dijkstra 算法中openList 队列都是等价地向所有方向探索。如果我们希望找到所有目标点或多个目标点的路径这是一个情有可原的选择但通常情况我们只是要找起点到一个目标点的路径。我们希望让 openList 优先朝着目标点的方向探索而不是其他方向。首先我们定义一个启发函数 heuristic来预估我们离目标点有多远。
double heuristic(Point from, Point to) {// 网格坐标上两个顶点的曼哈顿距离通常我们使用的欧拉距离但需要开更号运算效率低return abs(from.x - to.x) abs(from.y - to.y);
}在 Dijkstra 算法中我们使用距离离起点的实际距离给优先队列排序这里我们使用到目标点的预估距离给优先队列排序离目标点最近的顶点最优先被考虑。对比 Dijkstra 算法的实现仍然使用最小优先队列不过没有了 cost_so_far。 void greedy_best_first_search(Graph graph, Node start, Node goal)
{priority_queue Node, vectorNode, lessNodeCompare openList; openList.push(start, 0);unordered_mapNode, Node came_from;came_from[start] start;while (!openList.empty()) {Node current openList.front();openList.pop();if (current goal) break;for (auto neighbor : graph.neighbors(current)) {if (came_from.find(neighbor) came_from.end()) {double priority heuristic(goal, neighbor);// 预估距离openList.push(neighbor, priority);came_from[neighbor] current;}}}
}不过这个算法找到的路径不一定是最短路径虽然这个算法在阻挡不多时运算很快只是找到的路径还不够好我们有办法解决这个问题吗当然
2.4.2 A* 算法实现
Dijkstra 算法在寻找最短路径时效果很好但它耗了大量时间去探索那些非预期的方向贪婪最佳优先搜索算法的时预期额方向但找到的不是路径。A* 寻路算法同时使用距离起点的实际距离和到目标点的预估距离。它的代码跟 Dijkstra 算法的代码非常类似。
void a_star_search(Graph graph, Node start, Node goal)
{priority_queue Node, vectorNode, lessNodeCompare openList;openList.push(start, 0);unordered_mapNode, Node came_from;came_from[start] start;unordered_mapNode, int cost_so_far;cost_so_far[start] 0;while (!openList.empty()) {Node current openList.front();openList.pop();if (current goal) break;for (auto neighbor : graph.neighbors(current)) {double new_cost cost_so_far[current] graph.cost(current, neighbor);if (cost_so_far.find(neighbor) cost_so_far.end() || new_cost cost_so_far[neighbor]) {cost_so_far[neighbor] new_cost;double priority heuristic(neighbor, goal);// 实际距离 预估距离 openList.push(neighbor, priority);came_from[neighbor] current;}}}
}比较这几个算法
Dijkstra 算法计算距离起点的距离 g(n)贪婪最佳优先搜索算法使用到终点的预估距离 h(n)A* 寻路算法使用了距离起点的距离和到终点的预估距离之和 f(n) g(n) h(n)
在贪婪最佳优先搜索算法能正确搜索最短路径的情况下A也能找到正确的结果在在贪婪最佳优先搜索算法不能正确找到最短路径的情况下A还是可以找到正确的结果像Dijkstra 算法那样而且A寻路算法探索更少的格子。A 算法可以两全其美只要启发算法评估正确就可以像Dijkstra 算法那样找到最短路径。A* 算法使用启发式方法对节点进行重新排序以便更有可能更快地找到目标节点。
如何在游戏地图中选择合适的寻路算法呢
如果需要找出从所有顶点开始或是到所有顶点路径使用广度优先搜索或者Dijkstra 算法 如果移动的消耗都是一样的使用广度优先搜索如果移动的消耗是变化的使用Dijkstra 算法。如果需要找到到一个或几个目标点的最短路径使用贪婪最佳优先搜索算法或 A寻路算法。当您想使用贪婪的最佳优先搜索时请考虑使用带有“不可接受”启发式的 A 寻路算法。
关于最佳路径广度优先搜索和 Dijkstra 算法可以保证给定的图中找到的最短路径贪婪的最佳优先搜索不能保证。如果启发式方法永远不会大于真实距离则保证 A找到最短路径。随着启发式算法变小A 变成了 Dijkstra 算法。随着启发式方法变大A* 变为贪婪的最佳首次搜索。
关于性能最好的办法是减少图表中不必要的顶点。如果使用网格地图减小图形的大小有助于所有图形搜索算法。然后就是尽可能使用最简单的算法。贪婪最佳优先搜索算法通常比 Dijkstra 算法运行得更快但不会产生最佳路径。对于大多数寻路需求来说A* 是一个不错的选择。
关于非地图图的搜索算法可以用于任何类型的图不仅仅是游戏地图。移动代价表示图中边的权重。启发式方法无法通用我们必须为不同类型图设计相应的启发式方法。对于平面地图距离是一个不错的选择所以这就是这里使用的。
请记住图形搜索只是我们需要内容的一部分。A* 寻路算法本身不处理诸如协作移动、移动障碍物、地图更改、危险区域评估、编队、转弯半径、对象大小、动画、路径平滑或许多其他主题等内容。
