寻路算法浅析

全栈程序员-站长 • 2026年3月17日上午8:36 • 未分类 • 阅读 2

宽度优先搜索算法，解决了起始顶点到目标顶点路径规划问题，但不是最优以及合适的，因为它的边没有权值（比如距离），路径无法进行估算比较最优解。

在某些寻路方案中，不同类型的移动会有不同的成本。例如，在《文明》中，穿越平原或沙漠可能需要1个移动点，但穿越森林或丘陵可能需要5个移动点。

当我们希望探路者将这些费用考虑在内的时候，就引入了Dijkstra的算法

二、Dijkstra的算法【迪杰斯特拉算法】(or Uniform Cost Search)

图片展示

2.0 与广度优先搜索有何不同？

我们来看Greedy Best First Search算法（贪婪最佳优先搜索）。

三、贪婪最佳优先搜索

图片展示

3.0 与Dijkstra的算法有何不同？

每个顶点到目标顶点的距离这个距离有多种方式可以计算：

一、对角线距离【允许对角运动】有下面这3种表示方法

return D * sqrt(dx * dx + dy dy)
不要用平方根，这样做会靠近g(n)的极端情况而不再计算任何东西，A

退化成BFS：
3.2 缺陷

路径不是最短路径，只能是较优

四、A星算法

图片展示
4.0 与Dijkstra 算法和贪婪最佳优先搜索的不同？

下图中A是起点，B是终点，方格中的数值，左上方表示G值，右上方表示H值，下方表示F值。

图片展示
举例：鼠标指向的方格，G值为14（斜向），H值为28（当前节点距离终点B最近的距离为两个对角线的距离也就是28），所以F=G+H = 42

4.2.1 A星算法核心公式就是F值的计算：

4.2.2 G值是怎么计算的？

4.2.3 H值是如何预估出来的？

最后，A星算法还需要用到两个列表：

4.3 A星算法伪代码：

图片展示
4.4 核心算法实现：

///  /// A*计算 ///  IEnumerator Count () { 
    //等待前面操作完成 yield return new WaitForSeconds (0.1f); //添加起始点 openList.Add (grids [startX, startY]); //声明当前格子变量，并赋初值 Grid currentGrid = openList [0] as Grid; //循环遍历路径最小F的点 while (openList.Count > 0 && currentGrid.type != GridType.End) { 
    //获取此时最小F点 currentGrid = openList [0] as Grid; //如果当前点就是目标 if (currentGrid.type == GridType.End) { 
    Debug.Log ("Find"); //生成结果 GenerateResult (currentGrid); } //上下左右，左上左下，右上右下，遍历 for (int i = -1; i <= 1; i++) { 
    for (int j = -1; j <= 1; j++) { 
    if (i != 0 || j != 0) { 
    //计算坐标 int x = currentGrid.x + i; int y = currentGrid.y + j; //如果未超出所有格子范围，不是障碍物，不是重复点 if (x >= 0 && y >= 0 && x < row && y < colomn && grids [x, y].type != GridType.Obstacle && !closeList.Contains (grids [x, y])) { 
    //计算G值 int g = currentGrid.g + (int)(Mathf.Sqrt ((Mathf.Abs (i) + Mathf.Abs (j))) * 10); //与原G值对照 if (grids [x, y].g == 0 || grids [x, y].g > g) { 
    //更新G值 grids [x, y].g = g; //更新父格子 grids [x, y].parent = currentGrid; } //计算H值 grids [x, y].h = Manhattan(x, y); //计算F值 grids [x, y].f = grids [x, y].g + grids [x, y].h; //如果未添加到开启列表 if (!openList.Contains (grids [x, y])) { 
    //添加 openList.Add (grids [x, y]); } } } } } //重新排序 openList.Sort();