A星寻路算法_a星算法

A星寻路算法简介
A星寻路算法（A* Search Algorithm）是一种启发式搜索算法，它在图形平面上进行搜索，寻找从起始点到终点的最短路径。A星算法结合了广度优先搜索（BFS）和最佳优先搜索（Best-First Search）的特点，通过使用启发式函数评估节点的重要性，优先选择最有希望达到目标节点的节点进行扩展，从而有效地缩小搜索范围。
A星寻路算法的核心概念

1. 节点（Node）：在图形平面上，每个可移动的点都可以被视为一个节点。节点可以是地图上的障碍物、可移动的实体等。
2. 边（Edge）：节点之间的连接称为边。在路径搜索中，边通常表示可移动的路径或移动方向。
3. 代价函数（Cost Function）：F=G+H,用于评估从起始节点到当前节点的代价。在A星算法中，代价函数通常由两个部分组成：实际代价（Actual Cost）和启发式代价（Heuristic Cost）。
4. 父节点（Parent Node）：在搜索过程中，每个节点都有一个指向其父节点的指针，表示该节点是如何从父节点扩展而来的。
5. 开放列表（Open List）：包含所有正在被考虑的节点。这些节点尚未被扩展，且具有最小的实际代价+启发式代价。
6. 关闭列表（Closed List）：包含所有已经扩展过的节点。这些节点不再被考虑。

A星寻路算法的步骤

1. 初始化：设置起始节点和目标节点，将起始节点添加到开放列表中。
2. 循环执行以下步骤，直到开放列表为空或找到目标点：
   a. 从开放列表中选择具有最小代价的节点n，并将其从开放列表中移除。
   b. 将节点n添加到关闭列表中，并遍历其所有相邻节点。对于每个相邻节点m：

• 如果m不在关闭列表中，计算从起始节点到m的实际代价g(m)（g(m) = g(n）+n到m的代价）和启发式代价h(m)。如果m的代价小于其之前的代价，或者m尚未设置父节点，则将m的父节点设置为n，并更新m的代价g(m)。将m添加到开放列表中。如果节点m是目标节点，则找到了最短路径，结束算法。

1. 如果开放列表为空而未找到最短路径，则说明存在无法达到目标的路径或目标不可达，结束算法。
2. 输出最短路径：从目标节点回溯到起始节点，按照父节点指针依次访问节点，得到最短路径。

代码实现

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;

//节点
public class AstarNode:IComparable<AstarNode> //继承接口实现重载排序方式
{
   public int x;//x坐标
   public int y;//y坐标
   public Vector2Int pos;//x,y坐标
   public int G;//起点到该点的距离
   public int H;//该点到终点的曼哈顿距离
   public int F;//F = G + F
   public AstarNode()   //无参构造函数
   {

   }
   public AstarNode(Vector2Int pos) //有参构造函数
   {
    this.pos = pos;
    this.x = pos.x;
    this.y = pos.y;
   }
    public int CompareTo(AstarNode other) //排序方式
    {
        return this.F-other.F; //F小排在前
    }
}

//A星
public class AStar 
{
    bool result =false;
    //单例模式
    private static AStar instance;
    public static AStar Instance
    {
        get
        {
            if(instance==null)
            {
                instance = new AStar();
            }
            return instance;
        }
    }
    //上右下左四个方向
    private Vector2Int[] directions = new Vector2Int[]{new Vector2Int(1,0),new Vector2Int(0,1),new Vector2Int(-1,0),new Vector2Int(0,-1)};//上右下左

    //开放表
    private List<AstarNode> openList = new List<AstarNode>();
    //关闭表，但这里没用到，用cameFrom代替了它的作用
    //private HashSet<Vector2Int> closeList = new HashSet<Vector2Int>();
    //路径字典，用来存储路径以及作为关闭表来判断该点是否已经走过
    private Dictionary<Vector2Int,Vector2Int> cameFrom = new Dictionary<Vector2Int, Vector2Int>();
    //记录最终路径，作为返回值
    private List<Vector2Int> path = new List<Vector2Int>();
    //寻路方法
    public List<Vector2Int> FindPath(List<List<Transform>> map,Vector2Int startP,Vector2Int targetP)//地图，起点，终点
    {
        Debug.Log("开始寻路");
        //计算起点G,H,F，将起点加入开放表，
        AstarNode rNode = new AstarNode(startP);
        rNode.G = 0;
        rNode.H = Manhattan(rNode.pos,targetP);
        rNode.F = rNode.G+rNode.H;
        openList.Add(rNode);
        cameFrom[startP] = new Vector2Int(-1,-1); //记录路径，当前点坐标作为key，上一个点的坐标作为value，表示从上一个点坐标到达该点
        //循环直到找到路径，或者开放表没有节点
        while(openList.Count>0&&!result)
        {
            //开放表以F为标准排序，F小在前
            openList.Sort(); 
            //取出开放表中F最小的节点
            AstarNode curNode = openList[0];
            //取出的节点要从开放表中移除，加入到关闭表
            openList.RemoveAt(0);
            //遍历这个点周围的四个方向
            foreach(Vector2Int dir in directions)
            {
                Vector2Int newP = curNode.pos+dir;
                //判断边界，有没有超出地图范围
                if(newP.x<0||newP.x>=map.Count||newP.y<0||newP.y>=map[0].Count) //边界点判断
                {
                    continue;
                }
                //判断是否在关闭表
                if(cameFrom.ContainsValue(newP))
                {
                    continue;
                }
                //判断该点是否是障碍物
                if(!map[newP.x][newP.y].gameObject.GetComponent<Tile>().CheckObstacle())
                {
                    continue;
                }
                //查看是否在开放表
                AstarNode node = openList.FirstOrDefault(p => p.pos == newP);//linq查询openlist中是否有该点的节点
                //不在开放表就计算G,H,F,加入开放表，边的代价默认为1
                if(node==null)
                {
                    //Debug.Log("添加");
                    AstarNode newNode = new AstarNode();
                    newNode.pos = newP;
                    newNode.G = curNode.G+1;
                    newNode.H = Manhattan(newNode.pos,targetP);
                    newNode.F = newNode.G+newNode.H;
                    cameFrom[newNode.pos] = curNode.pos; //记录路径
                    openList.Add(newNode);
                }
                else    //在开放表，判断当前路径代价是否更小，是否要更新代价
                {
                    //如果当前路径代价更小，更新代价和路径
                    if(node.G > curNode.G+1) 
                    {
                        node.G = curNode.G+1;
                        node.F = node.G+node.H;
                        cameFrom[node.pos] = curNode.pos;
                    }
                }
                //如果当前点就是目标点，则停止寻路
                if(curNode.pos == targetP)
                {
                    result = true;
                    break;
                }
                
            }
        }
        //如果找到路径，通过终点与cameFrom，从后往前找到整条路径。
        if(result)
        {
            //通过栈把路径节点转成从起点到终点
            Stack<Vector2Int> path_stack = new Stack<Vector2Int>();
            Vector2Int pos = targetP;
            path_stack.Push(targetP);
            //将节点压入栈内
            while(pos!=startP)
            {
                Vector2Int newP = cameFrom[pos];
                pos = newP;
                path_stack.Push(pos);
            }
            //将栈内节点弹出
            while(path_stack.Count>0)
            {
                pos = path_stack.Pop();
                path.Add(pos);
                //Debug.Log(pos);
            }
        }
        else
        {
            Debug.Log("没找到");
        }
        return path;

    }
    public int Manhattan(Vector2Int a,Vector2Int b) //获取两点曼哈顿距离
    {
        return Mathf.Abs(a.x -b.x)+Mathf.Abs(a.y-b.y);
    }


}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

这段代码通过传递地图网格，地点和终点，实现了简单的A星寻路算法。首先构建一个新的Astar节点，设置为起点节点。起点的G为0，H采用曼哈顿距离，F = G + H。将起点节点加入到开放表。要取到开放表中F最小的节点，因为数据量较小，这里在每次从开放表取节点前都以F进行一次排序得到F最小节点（用优先队列会更好）。通过该节点访问其上右下左的四个点，并判断这些点是否能够加入开放表（坐标超出网格范围，节点在关闭表，节点是障碍点。都不能加入开放表）关闭表使用字典存储，在实现关闭表的同时还记录了节点之间的路径信息。最后判断坐标点是否在开放表，不在开放表的点构建节点并加入开放表，这里默认两点间的代价为1；在开放表中的则判断新的路径中代价是否更小，更小则更新代价和路径信息，否则不做处理。最后判断坐标点是否为目标坐标，如果是目标坐标即停止寻路。最后通过存储的路径信息找到完整路径。
A星寻路算法的优化技巧

1. 合理选择启发式函数：启发式函数用于估计从当前节点到目标节点的代价。选择合适的启发式函数能够提高算法的性能和准确性。常见的启发式函数有曼哈顿距离、欧几里得距离等。
2. 权重调整：根据实际应用场景和需求，可以对边的权重进行调整，以优化搜索效率和找到更符合特定要求的路径。
3. 动态调整开放列表的大小：在搜索过程中，可以根据需要动态调整开放列表的大小，以平衡搜索效率和内存消耗。
4. 利用优先队列进行节点排序：将开放列表中的节点按照代价从小到大排序，可以利用优先队列数据结构实现高效的排序操作，从而提高算法性能。
5. 预处理和缓存：在某些情况下，可以对地图进行预处理或使用缓存机制来提高搜索效率。例如，可以将一些已知的信息存储起来以便快速访问，或者预先计算某些节点的代价等。
6. 多线程并行处理：在多核处理器环境下，可以利用多线程技术对不同区域或方向的搜索进行并行处理，以提高算法的整体性能。
7. 局部搜索和回溯策略：在搜索过程中，可以结合局部搜索和回溯策略来优化路径选择和调整方向。当遇到局部最优解时，可以通过回溯或尝试其他方向来寻找更好的解。
8. 增量式更新地图：对于动态变化的地图环境，可以采用增量式更新地图的方法来提高算法的适应性。当地图发生变化时，只对变化区域进行重新搜索和处理，而保持其他区域的搜索

A星寻路算法的应用
A星寻路算法广泛应用于游戏开发、机器人导航、路径规划等领域。以下是一些具体的应用场景：

1. 游戏开发：在角色扮演游戏、策略游戏等类型中，A星算法常被用于实现智能角色的寻路和移动。通过找到最短路径，玩家可以更流畅地控制角色，提高游戏的可玩性和体验。
2. 机器人导航：在机器人领域，A星算法用于指导机器人从起点到目标点的路径规划。这种算法能够帮助机器人避开障碍物，选择最佳路径，从而实现高效、安全的导航。
3. 路径规划：在交通、物流等领域，A星算法用于规划最短或最优路径。例如，在物流配送中，通过使用A星算法，可以找到从起点到目的地的最短路径，从而提高配送效率。
4. 图形编辑和可视化：在处理复杂的图形数据时，A星算法可以帮助找到从一个节点到另一个节点的最短路径，从而进行高效的编辑和可视化操作。

总结
A星寻路算法是一种高效、实用的路径搜索算法，它结合了广度优先搜索和最佳优先搜索的特点，通过启发式函数评估节点的重要性，从而快速找到最短路径。通过合理的优化技巧，A星算法能够适多种应用场景，提高性能和准确性。