当前位置： 首页 > article >正文

A*寻路详解

article 2025/2/12 5:55:35

【基本概念】

寻路算法

寻路的结果是根据起始点S和目标点T，找到路径Path。

寻路中通常用栅形网格简化表示地图，周围八个格子表示可以通行的方向

游戏中通常需要最快找到该路径（A*算法），而不是找到最短的路径（Dijkstra算法）

距离度量

欧式距离，即两点间直线距离的计算

曼哈顿距离，有方向限制，只能水平或垂直移动

对角距离，在曼哈顿距离基础上，允许沿着对角线移动

切比雪夫距离，有方向限制，取水平或垂直移动两者的最大值

距离因子

在栅形网格下，可以认为上下左右的距离为1，但计算对角距离时为小数，为了都采用整形计算，乘以10的因子

因此，上下左右距离为10，对角距离为14

成本/代价

常用的说法是cost，从一个点到另外一个点的成本，通常成本就是距离的度量，在机器学习中，还会加上其他因素的度量，寻路算法中只有距离度量。

启发函数

搜索最基本的思路是穷举搜索，例如广度优先和深度优先搜索，但当搜索空间过大，也即可能性太多时，最好可以提供一种方式，对可能性做筛选，减少搜索空间，进而提高搜索效率。

如果有提供筛选方法，那么就是启发式搜索，这个方法也叫启发函数。

贪心策略

通常来说，搜索是一步步进行的，每一步会将新的可能加入到待处理队列中，如果每一步都从当前可能中选择一个最优的结果，这就是贪心的。

结果舍弃

在贪心策略下，如果在当前步得到了最优结果，可以将其他结果全部舍弃，以最优结果为基础做下一步搜索时，添加新的可能并从这些可能中找到找到最优结果。

也可以不做结果舍弃，在下一步搜索时，将添加的新的可能和已有的可能合在一起找当前步的最优结构。

寻路算法不做结果舍弃。

搜索结果

有的搜索中只需要知道路径是多大，而有的搜索需要知道路径是什么，寻路中需要知道路径是什么

【寻路算法】

常见的寻路算是迪杰斯特拉算法（Dijkstra）、最佳搜索搜索算法（BFS）、A*算法。他们都遵循相似的算法过程，只在计算和更新cost时有较大区别。算法主要流程如下：

  1. 确定一个起始点和目标点
  2. 将起点加入open队列中，open队列表示需要处理的可能性，这里用Point表示
  3. 从open队列中取出cost最小的Point。只有起点时就是起点，随着队列中的Point变多，要排序取出最小值
  4. 筛选open队列的邻近的Point并加入open队列中，此时open队列逐渐膨胀，在寻路算法中不做结果舍弃
    1. 栅形格子邻近的Point就是周围的八个
    2. 这8个中有的不能通行的格子要舍去
    3. 已经处理过的格子要舍弃
    4. 已经在open队列中的格子，需要更新cost
    5. 不在open队列中的格子，需要计算cost，并当如open队列中
  5. 将此次取出来的最小的Point放入close队列中，close队列表示已经处理过的Point
  6. 重复3-5步骤，直到open队列为空，或者取出来的最小的Point就是目标点

Dijkstra算法

Dijkstra算法是典型最短路径算法，可以计算一个起始节点到路径中其他所有节点的最短路径。

计算cost时：Point的cost是累加的，当前筛选出来的Point的cost = 当前从open队列中取出的Point的cost + 筛选Point到取出point的cost

因为计算cost是不断累加的，因此距离起点越远的点cost越大

更新cost时: 筛选的Point可能已经在open队列中存在，这表明有多条路径可以到达该Point。因为要找出来最短路径，所以需要比较筛选出来的Point与已经存在的Point谁的cost更低，将更低的cost作为新的cost。

如果已经存在的更低，说明之前的路径更短；如果筛选的更低，说明从起点到当前选择最小的Point再到当前筛选的Point的路径是从起点到Point的最短路径

算法特点：可以看到在搜索邻近的Point时，除了可以通行的Point外，没对Point做任何筛选，因为Point的cost是累加的，距离起点越近的点cost越小，也就越可能从open队列中取出来。

如果所有的点都可以通行，被取出来的点基本就是沿着起点一圈圈往外扩散的。

随着搜索的进行，目标Point的cost可能是open队列中最小，被取出来，此时就已经找到了通向这个点的最短路径了。

时间复杂度：所有可能点都会被放入到open队列中，也会被选择出来，如果可能的点总数为N，最外层循环次数为N，内层有一个获取邻近点的循环，这里的次数为8，同时还有一个排序的计算，如果用最小堆，时间复杂度为logN，总的时间复杂度为（N+8）logN

BFS

最佳优先搜索算法中每个Point的cost是不变的，其cost是该Point到目标Point的路径cost，不需要更新cost

其特点为：每次都会选择距离目标点最近的Point，如果起始点和目标点有凹形阻挡，将会导航进入凹形内部很长时间后才出来，实际表现为角色来回转圈

A*

A*寻路算法在计算cost时即会像Dijkstra一样考虑累积路径cost,也会像BFS一样考虑到目标点的cost。其cost计算公式为：

F = G + H 。其中G表示累积路径cost，H表示到目标点的cost

计算cost时，需先按照累积路径方式计算G,H只需在首次计算一次

更新cost时，H保持不变，实际就是更新G，只有当前计算的G更小时才做更新

其特点为：此时cost表示从起点到该点的最短路径+该点到目标点的估计距离，这种计算cost的方式更为科学，能更快更好的找到接近目标点的点位,也即寻路速度更快

在游戏中，更快寻路往往更重要，通过计算合适的cost，引导点位选择是寻路算法的核心所在。

当起点和终点距离很远时，刚开始寻路，H远大于G，此时相当于按照BFS的方式寻路；邻近终点时，G远大于H，此时相当于按照Dijkstra方式寻路

【代码实现】

下文是最原始的版本实现，不足以用到实际项目中，后文针对A*看一看如何优化

public class Navigate
{
    public SearchType searchType;
    public enum SearchType
    {
        Dijkstra,
        BFS,
        AStar,
    }


    public HCostType costType = HCostType.Diagonal;
    public enum HCostType
    {
        Manhattan,
        Euclidean,
        Diagonal,
    }

    public static int DisFactor = 10;
    public static int DiagonalDisFactor = 14;

    public Dictionary<SearchType, ISearch> algorithm = new Dictionary<SearchType, ISearch>();

    public bool FindPath(int2 start, int2 target, List<int2> path)
    {
        if (path == null || path.Count > 0) return false;
        if (!algorithm.TryGetValue(searchType, out var algo))
        {
            algorithm[searchType] = CreateSearch(searchType);
        }
        return algo.FindPath(start, target, path);
    }

    public ISearch CreateSearch(SearchType searchType)
    {
        ISearch res = null;
        switch (searchType)
        {
            case SearchType.Dijkstra: res = new Dijkstra(GetCost); break;
            case SearchType.BFS: res = new BFS(GetHCost); break;
            case SearchType.AStar: res = new AStar(GetCost, GetHCost); break;
        }
        return res;
    }

    public int GetCost(int2 cur, int2 next)
    {
        if (next.x == -1 && next.y == -1)
        {
            return -1;
        }
        int cost = 0;
        if (cur.x == next.x || cur.y == next.y)
        {
            cost = DisFactor;
        }
        else
        {
            cost = DiagonalDisFactor;
        }
        return cost;
    }

    public int GetHCost(int2 pos, int2 target)
    {
        int hCost = 0;
        if (costType == HCostType.Manhattan)
        {
            hCost = Mathf.Abs(pos.x - target.x) * DisFactor + Mathf.Abs(pos.y - target.y) * DisFactor;
        }
        else if (costType == HCostType.Euclidean)
        {
            hCost = (int)Mathf.Sqrt(Mathf.Pow((pos.x - target.x) * DisFactor, 2) + Mathf.Pow((pos.y - target.y) * DisFactor, 2));
        }
        else if (costType == HCostType.Diagonal)
        {
            int x = Mathf.Abs(pos.x - target.x);
            int y = Mathf.Abs(pos.y - target.y);
            int a = Mathf.Min(x, y);
            hCost = a * DiagonalDisFactor + Mathf.Abs(x - y) * DisFactor;
        }
        return hCost;
    }
}

public interface ISearch
{
    bool FindPath(int2 start, int2 target, List<int2> path);
}

public class Dijkstra : ISearch
{
    private Dictionary<int2, Point> openDic = new Dictionary<int2, Point>();
    private Dictionary<int2, Point> closeDic = new Dictionary<int2, Point>();
    private Dictionary<int2, Point> pos2Point = new Dictionary<int2, Point>();

    public bool FindPath(int2 startPoint, int2 targetPoint, List<int2> path)
    {
        if (path == null || path.Count > 0) return false;
        var start = GetOrCreatePoint(startPoint);
        var target = GetOrCreatePoint(targetPoint);
        openDic.Clear();
        closeDic.Clear();
        openDic.Add(startPoint, start);
        start.Reset();
        target.Reset();
        bool res = false;
        while (openDic.Count > 0)
        {
            var point = openDic.First().Value;
            if (point == target)
            {
                res = true;
                break;
            }
            //删除该点
            openDic.Remove(point.pos);
            ProcessNeighbouringPoints(point, target);
            //该点已被处理过
            closeDic.Add(point.pos, point);
            openDic = openDic.OrderBy(kv => kv.Value.cost).ToDictionary(p => p.Key, o => o.Value);
        }
        foreach (var point in target.path)
        {
            path.Add(point.pos);
        }
        res = true;
        return res;
    }

    private Func<int2, int2, int> getCost;
    private static int2 NullPos = new int2(-1, -1);
    public Dijkstra(Func<int2, int2, int> getCost)
    {
        this.getCost = getCost;
    }
    private Point GetOrCreatePoint(int2 pos)
    {
        if (!pos2Point.TryGetValue(pos, out var point))
        {
            pos2Point[pos] = point = new Point();
            point.pos = pos;
        }
        return point;
    }

    private List<int2> nPoints = new List<int2>();
    public void ProcessNeighbouringPoints(Point point, Point target)
    {
        nPoints.Clear();
        point.GetNeighbouringPoints(nPoints);

        foreach (var item in nPoints)
        {
            if (closeDic.TryGetValue(item, out var npoint))
            {
                continue;
            }

            if (getCost(item, NullPos) == -1)//-1表示点不可通行
            {
                continue;
            }

            UpdateCost(point, item, target);
        }

    }

    public void UpdateCost(Point point, int2 pos, Point target)
    {
        int cost = getCost(point.pos, pos);

        if (openDic.TryGetValue(pos, out var npoint))
        {
            if (cost + point.cost < npoint.cost)
            {
                npoint.cost = cost + point.cost;
                npoint.path.Clear();
                npoint.path.AddRange(point.path);
            }
        }
        else
        {
            npoint = GetOrCreatePoint(pos);
            npoint.Reset();
            npoint.cost = cost + point.cost;
            npoint.path.AddRange(point.path);
            openDic[pos] = npoint;
        }
    }

    public class Point
    {
        public int2 pos;
        public int cost;
        public List<Point> path = new List<Point>();

        public void Reset()
        {
            path.Clear();
            cost = int.MaxValue;
        }

        public bool GetNeighbouringPoints(List<int2> points)
        {
            if (points == null || points.Count > 0) return false;
            for (int i = -1; i < 2; i++)
            {
                for (int j = -1; j < 2; j++)
                {
                    if (i == 0 && j == 0) continue;
                    int2 newpos = new int2(pos.x + i, pos.y + j);

                    //超出地图范围
                    if (newpos.x < 0 || newpos.x >= MapM || newpos.y < 0 || newpos.y >= MapN)
                        continue;

                    points.Add(newpos);
                }
            }
            return true;
        }
    }
}

public class BFS : ISearch
{
    private Dictionary<int2, Point> openDic = new Dictionary<int2, Point>();
    private Dictionary<int2, Point> closeDic = new Dictionary<int2, Point>();
    private Dictionary<int2, Point> pos2Point = new Dictionary<int2, Point>();

    public bool FindPath(int2 startPoint, int2 targetPoint, List<int2> path)
    {
        if (path == null || path.Count > 0) return false;
        var start = GetOrCreatePoint(startPoint);
        var target = GetOrCreatePoint(targetPoint);
        openDic.Clear();
        closeDic.Clear();
        openDic.Add(startPoint, start);
        start.Reset();
        target.Reset();
        bool res = false;
        while (openDic.Count > 0)
        {
            var point = openDic.First().Value;
            path.Add(point.pos);
            if (point == target)
            {               
                res = true;
                break;
            }
            openDic.Remove(point.pos);
            ProcessNeighbouringPoints(point, target);
            closeDic.Add(point.pos, point);
            openDic = openDic.OrderBy(kv => kv.Value.cost).ToDictionary(p => p.Key, o => o.Value);
        }
        return res;
    }

    private Func<int2, int2, int> getCost;
    private static int2 NullPos = new int2(-1, -1);
    public BFS(Func<int2, int2, int> getCost)
    {
        this.getCost = getCost;
    }
    private Point GetOrCreatePoint(int2 pos)
    {
        if (!pos2Point.TryGetValue(pos, out var point))
        {
            pos2Point[pos] = point = new Point();
            point.pos = pos;
        }
        return point;
    }

    private List<int2> nPoints = new List<int2>();
    public void ProcessNeighbouringPoints(Point point, Point target)
    {
        nPoints.Clear();
        point.GetNeighbouringPoints(nPoints);

        foreach (var item in nPoints)
        {
            if (closeDic.TryGetValue(item, out var npoint))
            {
                continue;
            }

            if (getCost(item, NullPos) == -1)//-1表示点不可通行
            {
                continue;
            }

            UpdateCost(point, item, target);
        }

    }

    public void UpdateCost(Point point, int2 pos, Point target)
    {
        int cost = getCost(target.pos, pos);

        if (!openDic.TryGetValue(pos, out var npoint))
        {
            npoint = GetOrCreatePoint(pos);
            npoint.Reset();
            npoint.cost = cost;
            openDic[pos] = npoint;
        }
    }

    public class Point
    {
        public int2 pos;
        public int cost;

        public void Reset()
        {
            cost = int.MaxValue;
        }

        public bool GetNeighbouringPoints(List<int2> points)
        {
            if (points == null || points.Count > 0) return false;
            for (int i = -1; i < 2; i++)
            {
                for (int j = -1; j < 2; j++)
                {
                    if (i == 0 && j == 0) continue;
                    int2 newpos = new int2(pos.x + i, pos.y + j);

                    //超出地图范围
                    if (newpos.x < 0 || newpos.x >= MapM || newpos.y < 0 || newpos.y >= MapN)
                        continue;

                    points.Add(newpos);
                }
            }
            return true;
        }
    }
}
public class AStar : ISearch
{
    private Dictionary<int2, Point> openDic = new Dictionary<int2, Point>();
    private Dictionary<int2, Point> closeDic = new Dictionary<int2, Point>();
    private Dictionary<int2, Point> pos2Point = new Dictionary<int2, Point>();

    public bool FindPath(int2 startPoint, int2 targetPoint, List<int2> path)
    {
        if (path == null || path.Count > 0) return false;
        var start = GetOrCreatePoint(startPoint);
        var target = GetOrCreatePoint(targetPoint);
        openDic.Clear();
        closeDic.Clear();
        openDic.Add(startPoint, start);
        start.Reset();
        target.Reset();
        bool res = false;
        while (openDic.Count > 0)
        {
            var point = openDic.First().Value;
            path.Add(point.pos);
            if (point == target)
            {
                res = true;
                break;
            }
            openDic.Remove(point.pos);
            ProcessNeighbouringPoints(point, target);
            closeDic.Add(point.pos, point);
            openDic = openDic.OrderBy(kv => kv.Value.F).ThenBy(kv => kv.Value.H).ToDictionary(p => p.Key, o => o.Value);
        }
        return res;
    }

    private Func<int2, int2, int> getCost;
    private Func<int2, int2, int> getHCost;
    private static int2 NullPos = new int2(-1, -1);
    public AStar(Func<int2, int2, int> getCost, Func<int2, int2, int> getHCost)
    {
        this.getCost = getCost;
        this.getHCost = getHCost;
    }
    private Point GetOrCreatePoint(int2 pos)
    {
        if (!pos2Point.TryGetValue(pos, out var point))
        {
            pos2Point[pos] = point = new Point();
            point.pos = pos;
        }
        return point;
    }

    private List<int2> nPoints = new List<int2>();
    public void ProcessNeighbouringPoints(Point point, Point target)
    {
        nPoints.Clear();
        point.GetNeighbouringPoints(nPoints);

        foreach (var item in nPoints)
        {
            if (closeDic.TryGetValue(item, out var npoint))
            {
                continue;
            }

            if (getCost(item, NullPos) == -1)//-1表示点不可通行
            {
                continue;
            }

            UpdateCost(point, item, target);
        }

    }



    public void UpdateCost(Point point, int2 pos, Point target)
    {
        int cost = getCost(target.pos, pos);

        int gCost = point.G + cost;

        if (openDic.TryGetValue(pos, out var npoint))
        {
            if (npoint.G < gCost)
            {
                npoint.G = gCost;
            }
        }
        else
        {
            npoint = GetOrCreatePoint(pos);
            npoint.G = gCost;
            npoint.H = getHCost(pos, target.pos);
            openDic[pos] = npoint;
        }
    }

    public class Point
    {
        public int2 pos;
        public int H
        {
            get => _h;
            set
            {
                _h = value;
                _f = _h + _g;
            }
        }
        private int _h;
        public int G
        {
            get => _g;
            set
            {
                _g = value;
                _h = _g + _h;
            }
        }

        private int _g;

        public int F => _f;
        private int _f;

        public void Reset()
        {
            H = 0;
            G = 0;
        }

        public bool GetNeighbouringPoints(List<int2> points)
        {
            if (points == null || points.Count > 0) return false;
            for (int i = -1; i < 2; i++)
            {
                for (int j = -1; j < 2; j++)
                {
                    if (i == 0 && j == 0) continue;
                    int2 newpos = new int2(pos.x + i, pos.y + j);

                    //超出地图范围
                    if (newpos.x < 0 || newpos.x >= MapM || newpos.y < 0 || newpos.y >= MapN)
                        continue;

                    points.Add(newpos);
                }
            }
            return true;
        }
    }
}

【参考】

（七）通俗易懂理解——dijkstra算法求最短路径

https://zhuanlan.zhihu.com/p/385733813


http://www.kler.cn/a/541665.html

相关文章：

  • Vue3（1）
  • Qt文本处理【正则表达式】示例详解：【QRegularExpression】
  • collabora online+nextcloud+mariadb在线文档协助
  • 【C++八股】 前置 ++i vs. 后置 i++ 的区别
  • Hive之[Hive]详细安装步骤
  • ArgoCD实战指南：GitOps驱动下的Kubernetes自动化部署与Helm/Kustomize集成
  • 热敏电阻的主要作用是什么
  • Java面试题-Spring Boot
  • 海明码的认识理解与延伸
  • 【算法解析】（2）分治算法：归并排序和快速排序
  • Unity3D Shader 简析：变体与缓存详解
  • RabbitMQ学习—day2—安装
  • 2025年前端面试,性能相关的面试题汇总
  • FFMPEG3.0 增加RTSP拉取PCM音频流功能
  • Elasticsearch 7 集群搭建问题排查：常见故障解决方案与优化技巧
  • macbook键盘进残渣，按键难回弹的简单处理方法
  • web3是什么，最简单的介绍
  • vue3学习之待办事项列表（Todo List）
  • 支持向量机原理
  • 如何在Node.js中使用中间件处理请求
  • 后盾人JS -- 模块化开发
  • 小游戏源码开发之可跨app软件对接是如何设计和开发的
  • Flutter_学习记录_基本组件的使用记录_2
  • 后盾人JS -- 异步编程，宏任务与微任务
  • HTML之JavaScript对象声明
  • MySQL下载过程