如果你玩过MMOARPG游戏，比如魔兽世界，你会发现角色行走会很有趣。为了模仿人物行走的真实体验，他们会选择最短路线到达目的地，期间他们会避开高山或湖泊，绕过箱子或树林，直到你到达你选择的目的地。这种看似普通的寻路，在程序实现的时候需要一定的寻路算法来解决。如何在最短的时间内找到一条路径最短的路径是寻路算法首先要考虑的问题。在本文中，我们将逐步解释寻路算法是如何演变的。你会看到一个算法从简单到高效遇到的问题，以及改进的过程。带着问题阅读，理解更快。本文主要包含以下内容：1.图2.宽***搜索，3.Dijkstra算法，4.贪心算法，***搜索算法，6.B*搜索算法，1.字符在游戏？寻路中看到人物行走的方式：开发者实际看到的方式：或者这样：对于一张地图，开发者需要通过一定的规划将其转化为数据对象，常见的就是上面的一种方式是切地图变成网格。当然，地图的划分方法不一定非要用网格法，也可以用多边形法。这取决于你的游戏。一般来说，面积相同的地图使用的顶点越少，寻路算法的速度就会越快。寻路中常用的数据结构是图。我们先来看一下。2.Graph在讲寻路算法之前，我们先了解一个数据结构——Graph。数据结构是我们算法运算的基础。一个好的数据结构不仅有利于我们对算法的理解，还可以提高算法的效率。从某种意义上说，网格也是图的进化，只是图变了。理解图的概念可以帮助我们更好地理解寻路算法。图的基本定义：图的形式化表达为G=(V,E)，V是顶点的集合，E和V是二元关系，可以理解为边，例如有从顶点U到顶点V有一条边结束，那么E就可以用(u,v)来表示这条边。具体的有向图和无向图也是通过边是否有方向来区分的。为了方便理解，我们文章中所有的数据演示都是基于栅格图进行说明的。下面是几种关系组合，以A为顶点，BCDE为子顶点。我们可以将每个网格视为一个顶点。3.搜索算法搜索一个图就是按照一定的顺序依次访问它的顶点。对于多图算法，广度优先和深度优先搜索算法都非常重要，因为它们提供了一组系统地访问图数据结构的方法。我们专注于广度优先搜索算法。深度优先搜索深度优先算法与最小路径关系不大，我们只简单介绍一下。深度优先搜索算法（简称DFS）是一种遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深入地搜索树的分支。探索完节点v的所有边后，搜索将回溯到找到节点v的边的起始节点。这个过程一直持续到找到所有从源节点可达的节点。广度优先搜索广度优先搜索算法（简称BFS），又称广度优先搜索，是一种非常适合探索最短路径第一种模型的图搜索算法。我们将遵循这一思路。BFS是一种盲目搜索方法，其目的是系统地扩展和检查图中的所有节点以找到结果。换句话说，它会穷尽地搜索整个图，而不管结果的可能地址如何，直到找到结果为止。其步骤如下：-首先将根节点放入队列中。-从队列中取出第一个节点并检查它是否是目标。-如果找到目标，则结束搜索并返回结果。-否则，将所有尚未检查的直接孩子（邻居）入队。-如果队列为空，说明整个地图都检查过了——即地图中没有要搜索的目标。结束搜索并返回“找不到目标”。网格：我们看代码（js）：varfrontier=newArray();frontier.put(start);varvisited=newArray();visited[start]=true;while(frontier.length>0){当前=frontier.get();//查找周围的顶点for(nextingraph.neighbors(current)){varnotInVisited=visited.indexOf(next)==-1;//未访问if(notInVisited){frontier.put(next);已访问[下一个]=true；}}}由上可知，宽度搜索是从起始顶点开始，访问它的子节点（在网格中，访问周围的节点），然后不断循环这个过程，直到找到目标。这个算法比较符合常规逻辑，枚举所有的顶点。但是，这种方法也有明显的缺点。缺陷：1.效率低，时间复杂度：T(n)=O(n^2)2.各个顶点之间没有权值，无法定义优先级，找不到最佳路径。比如遇到水域需要走动，宽度算法就不能涉及。如何解决这个问题呢？让我们看看Dijkstra的算法。4.Dijkstra算法的广度优先搜索算法解决了从起始顶点到目标顶点的路径规划问题，但并不完美适用，因为它的边没有权值（比如距离），路径不能估计和比较***解开。为什么权重如此重要，因为在真实环境中，两个顶点之间的路线并不总是一条直线，需要绕过障碍物才能到达目的地，比如森林、湖泊、山脉，都需要绕过,不直接通过。例如，我使用广度优先算法。在以下情况下，他将直接穿过障碍物（绿色部分）。显然这不是我们想要的结果：解决痛点：找到图中一个顶点到另一个顶点的最短最短的带对路是一个非常重要的提炼过程。在每个顶点之间的边上添加一个权重，用于跟踪所选路径的消耗成本。如果该位置的新路径优于之前的最佳路径，我们将添加它并规划新的路线。Dijkstra算法是在广度优先算法的基础上改进的，将当前最短的边加入到最短路径树中，使用贪心算法计算，最终产生最优结果。具体步骤如下：1.每个顶点都包含一个估计代价（起点到当前顶点的距离），每条边都有一个权重v。一开始只有起始顶点的估计代价为0，并且其他顶点的估计值d是无穷大∞。2.找到cost值最小的顶点A，放入路径队列中3.循环遍历A的直接子顶点，得到子顶点的当前cost值并命名为current_cost，计算新路径new_cost，new_cost=costofparentnodeA+v（父节点到当前节点的边权重），如果new_cost
