A星算法的理解以及实现

俗话说，好记性不如烂笔头，对于有了解过寻路算法的同学，对于A星算法应该不陌生；为了巩固下这个算法的理解，所以利用Unity演示了算法的过程；本文的基本构成分为 基本原理+ 算法实现+ Unity演示三个步骤。

A星算法基本原理

什么是寻路算法

寻路算法是在指定地图中，NPC可以根据起始点和目标点，计算出一条比较合理的链接路线（通常需要最短路径）；在地图中，路点可以分为两种，一种是普通路点，一种是障碍路点（墙、水、坑等），算法的目的就是要绕过障碍物，使得NPC尽可能的走最短路线到达目标点(targetPoint)。

对于最基本的A星寻路算法，是把一张地图分为一个二维数组，每一个格子代表一个路点；或者如下图如所示，将一张地图分为一个一个的格子，格子为正方形，下方的绿色格子周围有8个相邻的格子；

算法的思路

对于上述九宫格图，假设最小方格的边长是10,那么从绿色格子出发，到达红色格子的距离为$\sqrt{200}$，这里可以简化为14，因为这样可以简化算法的计算难度（浮点数比整数的计算复杂）；到达黄色格子的距离为10；
每一个路点都有一个评估值F，其中$F=G+H$，G值是起点移动到指定方格的移动代价，H是指定的方格移动到终点的估算成本，H值的计算方式有如下两种：

方式一：计算横向和纵向移动的距离，不能斜着走；

方式二：比如该点和目标点为对角顶点组成的举行的边长是a 和 b，那么H值是 $min(a,b)\times 14+abs(a-b)\times 10$

，

本文算法选择的是方式二，H值的计算需要注意的地方是，不需要考虑障碍物，只需考虑起始点和目标点即可。对于F、G、H三个评估值的什么这么命名，我也不清楚，猜测是就和我们平时用来替代临时变量用的i、j、k一样，仅仅是26英文字母中连续的三个而已，方便记忆😎;

这个算法需要两个数组，openList和closeList，openList里面存放的是当前状态可以到达的路点，closeList存放不能到达的路点和已经经过判断的路点；具体步骤如下：

1. 从当前选中路点a出发，总共有8个路点可能到达，假设可到达的节点为b，如果b是障碍点，则直接加入closeList；如果b在openList中，当且仅当b的G值小于点a的G值时，更新b的G值，并且将路点b的父节点设置为当前a；如果b在closeList中，则跳过该点的判断。否者初始化G值和H值，并将该节点b加入到openlist列表中；最后将初始路点a移出openlist。
2. 如果目标点进入了openList，则遍历停止，找到可到达路径，由于每个节点都保存着到达自己的父节点，所以拿到目标点，一直拿到它的父节点就可以找到到达路径；如果openList为空时还没找都目标路点，则不可到达，算法结束；否则进入下一个步骤；
3. 遍历openList的路点，选出F值最小的那个点，如果有多个最小值，可以选择第一个最小值，也可以选择多个最小值中的最后一个，最后的表现就是到达目标点的最短路径可能有多条；然后把这个点当做选中路点，进行步骤1；

算法实现

这里列出算法用的大部分代码，其中最关键的就是RefreshFind函数和AddOpenlistNode函数，执行的就是算法的关键部分----遍历openList然后不断的进行判断，直到找到目标路点或者openList为空，如果有不理解的地方，请留言。

脚本1————cconst.cs

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

namespace AStar
{
    public static class cconst
    {
        public static int NormalTile = 0;
        public static int WaterTile = 1;
        public static int DestinationTile = 2;
        public static int MarkTile = 3;
        public static int FindTile = 4;
        public static int StartTile = 5;
        public static int RowLineNum = 16;  // 行数
        public static int ColLineNum = 32;  // 列数
        public static Vector2 startPos = new Vector2(-617, 298);
        public static float itemRate = 1.0f;
        public static float width = 40 * itemRate;
        public static float height = 40 * itemRate;


        public static int SlideDis = 14;
        public static int UnSlideDis = 10;

        public static int slideValNum = 4;
        public static List<Vector2> UnSlideDisVal = new List<Vector2> { new Vector2(-1, 0), new Vector2(0, 1), new Vector2(1, 0), new Vector2(0, -1) };
        public static List<Vector2> SlideDisVal = new List<Vector2> { new Vector2(-1, -1), new Vector2(-1, 1), new Vector2(1, 1), new Vector2(1, -1) };

        //障碍点类型
        public static int BattleNum = 5;
        public static int BattleTypeNum = 3;
        public static Dictionary<int, List<List<int>>> BattleTypeDic = new Dictionary<int, List<List<int>>>
        {
            { 0, new List<List<int>>{ new List<int> {1,0,0 }, new List<int> { 1,1,0 }, new List<int> { 1,1,1 },new List<int> { 1,1,1 }, new List<int> { 1,1,0 }, new List<int> { 1,0,0 } } },
            { 1, new List<List<int>>{ new List<int> {1,1,1,1}, new List<int> {1,1,1 }, new List<int> { 1, 1, 1,1,1 } } },
            { 2, new List<List<int>>{ new List<int> {1,0, 0, 0, }, new List<int> {1,1,1,1 }, new List<int> {0,0,0,1 }, new List<int> { 0, 0, 0, 1 } } },
        };
    }
}


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

脚本2————AStar.cs

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UI;


namespace AStar
{

    public class GObject
    {
        public GameObject gameobject;
        public int objType;

        GameObject fValText;
        GameObject gValText;
        GameObject hValText;

        GameObject textPanel;

        public GObject(GameObject _gameobject, int _type) 
        {
            gameobject = _gameobject; 
            objType = _type;
            textPanel = _gameobject.transform.Find("Panel").gameObject;
            fValText = textPanel.transform.Find("FText").gameObject;
            gValText = textPanel.transform.Find("GText").gameObject;
            hValText = textPanel.transform.Find("HText").gameObject;

            textPanel.SetActive(false);
 
        }
        public bool IsObstacle
        {
            get { return objType == cconst.WaterTile;  }
        }

        public void UpdateDis(int g, int h)
        {
            textPanel.SetActive(true);

            gValText.GetComponent<Text>().text = g.ToString();
            hValText.GetComponent<Text>().text = h.ToString();
            int f = g + h;
            fValText.GetComponent<Text>().text = f.ToString();
        }

        public bool Visible
        {
            set { gameobject.SetActive(value);
                if(!value)
                {
                    textPanel.SetActive(false);

                }
            }
            get { return gameobject.activeSelf; }
        }
        public void SetParent(Transform transform)
        {
            gameobject.transform.SetParent(transform);
        }

        public Vector2 localPosition
        {
            set { gameobject.transform.localPosition = value; }
            get { return gameobject.transform.localPosition;  }
        }

    }


    public class Node
    {
        public Node parent;
        public GObject gameobject;
        int idx = 0;

        public Node(GObject obj, int _idx) { gameobject = obj; idx = _idx; }
        int g = 0;
        int h = 0;

        public int Idx
        {
            get { return idx; }
        }

        public int F
        {
            get { return G + H; }
        }

        public int G
        {
            get { return g; }
            set { g = value; }
        }


        public int H
        {
            get { return h; }
            set { h = value;}
        }

        public int xIdx
        {
            get { return idx / cconst.ColLineNum; }
        }

        public int yIdx
        {
            get { return idx % cconst.ColLineNum; }
        }

        public void UpdateGVal(int gVal)
        {
            if(gVal < G)
            {
                G = gVal;
            }
        }

        public void UpdateLocalPosition()
        {
            int rowIdx = xIdx;
            int colIdx = yIdx;

            float posX = cconst.startPos.x + colIdx * cconst.width;
            float posY = cconst.startPos.y - rowIdx * cconst.height;
            gameobject.localPosition = new Vector2(posX, posY);
        }

        public void UpdateDescDis()
        {
            gameobject.UpdateDis(G, H);
        }

        public void UpdateDescDis(Node node)
        {
            G = node.G;
            H = node.H;
            gameobject.UpdateDis(G, H);
        }

        public void SetParrent(Node node)
        {
            parent = node;
        }

        public bool Visible
        {
            set { gameobject.gameobject.SetActive(value); }
            get { return gameobject.gameobject.activeSelf; }
        }

    }

    public class AStarTest : MonoBehaviour
    {

        // Start is called before the first frame update
        public List<int> map;
        public Dictionary<int, string> mapTypeDic;
        public Dictionary<int, GObject> mapTypeObjDic;
        public Dictionary<int, GObject> idxObjDic;
        GameObject normalTile;
        GameObject waterTile;
        GameObject destinationTile;
        GameObject markTile;
        GameObject findTile;
        GameObject startTile;
        public int startIdx;
        public int targetIdx;
        public List<int> battleList;

        public List<Node> openList;
        public Dictionary<int, Node> openListIdxDic;
        public List<Node> closeList;
        public Dictionary<int, Node> closeListIdxDic;

        public List<GObject> totalObjList;

        public Dictionary<int, Stack<GObject>> nodeDicPool;

        Node targetNode;
        Node markTargetNode;
        public List<Node> markNodeList;

        public Coroutine curCoroutine;

        void Start()
        {
            idxObjDic = new Dictionary<int, GObject>();
            nodeDicPool = new Dictionary<int, Stack<GObject>>();
            mapTypeDic = new Dictionary<int, string> {
                {0, "normalTile" },
                {1, "waterTile" },
                {2, "targetTile" },
                {3, "markTile" },
                {4, "findTile" },
                {5, "startTile" },
                };

            normalTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.NormalTile]);
            waterTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.WaterTile]);
            destinationTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.DestinationTile]);
            markTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.MarkTile]);
            findTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.FindTile]);
            startTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.StartTile]);

            mapTypeObjDic = new Dictionary<int, GObject>
            {
                {cconst.NormalTile,  new GObject(normalTile,cconst.NormalTile)},
                {cconst.WaterTile,  new GObject(waterTile,cconst.WaterTile)},
                {cconst.DestinationTile,  new GObject(destinationTile,cconst.DestinationTile)},
                {cconst.MarkTile,  new GObject(markTile,cconst.MarkTile)},
                {cconst.FindTile,  new GObject(findTile,cconst.FindTile)},
                {cconst.StartTile,  new GObject(startTile,cconst.StartTile)},
            };

            InitData();
        }

        public void InitData()
        {
            transform.DetachChildren();
            int _totalIdx = cconst.RowLineNum * cconst.ColLineNum;

            //初始化乜有障碍物的地图
            map = new List<int>();
            for (int i = 0; i < cconst.RowLineNum; ++i)
                for (int j = 0; j < cconst.ColLineNum; ++j)
                {
                    map.Add(cconst.NormalTile);

                }

            //初始化地图障碍物
            battleList = new List<int>();
            for (int i = 0; i < cconst.BattleNum; i++)
            {
                int curBattleType = Random.Range(0, 100) % cconst.BattleTypeNum;
                int curBattleStartIdx = Random.Range(0, _totalIdx);
                List<List<int>> curBattleList = cconst.BattleTypeDic[curBattleType];

                int curBattleRow = curBattleStartIdx / cconst.ColLineNum;
                int curBattleCol = curBattleStartIdx % cconst.ColLineNum;

                curBattleRow = Mathf.Min(curBattleRow, cconst.RowLineNum - curBattleList.Count - 1);
                curBattleCol = Mathf.Min(curBattleCol, cconst.ColLineNum - curBattleList[0].Count - 1);

                for(int j = 0; j< curBattleList.Count; ++j)
                    for(int k=0; k<curBattleList[j].Count; ++k)
                    {
                        if(curBattleList[j][k] > 0)
                        {
                            int curCalIdx = (curBattleRow + j) * cconst.ColLineNum + (curBattleCol + k);
                            map[curCalIdx] = cconst.WaterTile;
                            battleList.Add(curCalIdx);
                        }
                    }
            }

            //初始化起始点
            startIdx = Random.Range(0, _totalIdx / 2);
            while (battleList.Contains(startIdx))
            {
                startIdx = Random.Range(0, _totalIdx / 2);
            }

            //初始化目标点
            targetIdx = Random.Range(_totalIdx / 2, _totalIdx);
            while (battleList.Contains(targetIdx) || startIdx == targetIdx)
            {
                targetIdx = Random.Range(_totalIdx / 2, _totalIdx);
            }

            totalObjList = new List<GObject>();

            map[startIdx] = cconst.StartTile;
            map[targetIdx] = cconst.DestinationTile;

            InitMapRes();

            // ---------------- A*
            openList = new List<Node>();
            openListIdxDic = new Dictionary<int, Node>();
            closeList = new List<Node>();
            closeListIdxDic = new Dictionary<int, Node>();
            markNodeList = new List<Node>();
            targetNode = new Node(idxObjDic[targetIdx], targetIdx);
            markTargetNode = null;
            InitAStarStart();
            curCoroutine = StartCoroutine(FindNextPoint());
        }

        public IEnumerator FindNextPoint()
        {
            RefreshFind();
            yield return new WaitForSeconds(0.05f);

            if (!openListIdxDic.ContainsKey(targetNode.Idx))
            {
                curCoroutine = StartCoroutine(FindNextPoint());  //目标点没在dic里面，继续执行
            }
            else
            {
                markTargetNode = openListIdxDic[targetNode.Idx];
                curCoroutine = StartCoroutine(ShowFindPath(markTargetNode));
                Debug.Log("find the way to the target !!!");
            }
            
        }

        void InitMapRes()
        {
            int _totalIdx = cconst.RowLineNum * cconst.ColLineNum;
            for (int i=0; i< _totalIdx; ++i)
            {
                int rowIdx = i / cconst.ColLineNum;
                int colIdx = i % cconst.ColLineNum;
                var obj = GetTypeObject(map[i]);
                idxObjDic[i] = obj;
                float posX = cconst.startPos.x + colIdx * cconst.width;
                float posY = cconst.startPos.y - rowIdx * cconst.height;
                obj.localPosition = new Vector2(posX, posY);
            }
        }

        void InitAStarStart()
        {
            GObject startObj = idxObjDic[startIdx];
            Node startNode = new Node(startObj, startIdx);
            AddOpenlistNode(startNode);

        }

        void AddOpenlistNode(Node node)  //出发点是node，遍历其周围8个点，更细其F、G、H值
        {
            if(openListIdxDic.ContainsKey(targetNode.Idx))
            {
                Debug.Log("find the way to the target !!!");
                return;
            }

            int xIdx = node.xIdx;
            int yIdx = node.yIdx;
            List<Vector2> curDisVal;
            int curValDis;
            for (int i =0; i<2; i++)
            {
                if(i == 0)
                {
                    curDisVal = cconst.UnSlideDisVal;
                    curValDis = cconst.UnSlideDis;
                }
                else
                {
                    curDisVal = cconst.SlideDisVal;
                    curValDis = cconst.SlideDis;
                }

                for (int j = 0; j < cconst.slideValNum; ++j)
                {
                    var addVal = curDisVal[j];
                    var curXIdx = xIdx + (int)addVal.x;
                    var curYIdx = yIdx + (int)addVal.y;
                    if (curXIdx < 0 || curXIdx >= cconst.RowLineNum || curYIdx < 0 || curYIdx >= cconst.ColLineNum) continue;
                    int cur_Idx = curXIdx * cconst.ColLineNum + curYIdx;
                    if (closeListIdxDic.ContainsKey(cur_Idx)) continue;
                    Node curNode = null;
                    if (openListIdxDic.ContainsKey(cur_Idx))
                    {
                        curNode = openListIdxDic[cur_Idx];
                        int cur_G = node.G + curValDis;
                        if (curNode.G > cur_G)
                        {
                            curNode.SetParrent(node);
                            curNode.UpdateGVal(cur_G);
                        }
                        
                    }
                    else
                    {
                        GObject gobject = GetTypeObject(cconst.FindTile);
                        float posX = cconst.startPos.x + curYIdx * cconst.width;
                        float posY = cconst.startPos.y - curXIdx * cconst.height;
                        gobject.localPosition = new Vector2(posX, posY);
                        curNode = new Node(gobject, cur_Idx);
                        if (idxObjDic[curXIdx * cconst.ColLineNum + curYIdx].IsObstacle)
                        {
                            closeListIdxDic[cur_Idx] = curNode;
                            curNode.gameobject.gameobject.SetActive(false);
                            return;
                        }
                        curNode.SetParrent(node);
                        openList.Add(curNode);
                        openListIdxDic[cur_Idx] = curNode;
                        curNode.G = node.G + curValDis;
                        SetHVal(curNode);
                    }
                    curNode.UpdateDescDis();
                }
            }
            closeListIdxDic[node.Idx] = node;
            closeList.Add(node);

        }

        // Update is called once per frame
        void Update()
        {
            if(Input.GetKeyDown(KeyCode.A))
            {
                //dosomething
            }
            
        }

        void DoNextOperation()
        {
            StopCoroutine(curCoroutine);
            foreach (var obj in totalObjList)
            {
                obj.Visible = false;
                Stack<GObject> tmpList;
                if (nodeDicPool.ContainsKey(obj.objType))
                {
                    tmpList = nodeDicPool[obj.objType];
                    tmpList.Push(obj);

                }
                else
                {
                    tmpList = new Stack<GObject>();
                    tmpList.Push(obj);
                }
                nodeDicPool[obj.objType] = tmpList;
            }
 
            InitData();
        }

        void RefreshFind()
        {
            Node findNode = null;
            int tmpMax = int.MaxValue;
            if(openList.Count == 0)
            {
                Debug.Log("can not find the way to the target !!!");
                DoNextOperation();
                return;
            }

            foreach(var node in openList)
            {
                if (node.F < tmpMax)
                {
                    tmpMax = node.F;
                    findNode = node;
                }
            }
            if (findNode == null) return;
            GObject gobject = GetTypeObject(cconst.MarkTile);
            Node curNode = new Node(gobject, findNode.Idx);
            curNode.UpdateLocalPosition();
            curNode.UpdateDescDis(findNode);
            markNodeList.Add(curNode);
            openList.Remove(findNode);
            AddOpenlistNode(findNode);
        }

        IEnumerator ShowFindPath(Node targetNode)
        {
            foreach (var _node in markNodeList)
            {
                _node.Visible = false;
            }
            Node temp_node = targetNode;
            while(temp_node != null)
            {
                int curTile = cconst.MarkTile;
                if(temp_node.Idx == startIdx)
                {
                    curTile = cconst.StartTile;
                }
                else if(temp_node.Idx == targetIdx)
                {
                    curTile = cconst.DestinationTile;
                }
                GObject gobject = GetTypeObject(curTile);
                Node curNode = new Node(gobject, temp_node.Idx);
                curNode.Visible = true;
                curNode.UpdateLocalPosition();
                temp_node = temp_node.parent;
                yield return new WaitForSeconds(0.2f);
            }
            yield return new WaitForSeconds(0.5f);
            DoNextOperation();

        }    

        void SetHVal(Node node)
        {
            int xDelVal = Mathf.Abs(node.xIdx - targetNode.xIdx);
            int yDelVal = Mathf.Abs(node.yIdx - targetNode.yIdx);
            node.H =  Mathf.Min(xDelVal, yDelVal) * cconst.SlideDis + Mathf.Abs(xDelVal - yDelVal) * cconst.UnSlideDis;
        }

        GObject GetTypeObject(int objType)
        {
            if(nodeDicPool.ContainsKey(objType))
            {
                var typeStack = nodeDicPool[objType];
                if(typeStack.Count > 0)
                {
                    var obj = typeStack.Pop();
                    obj.SetParent(transform);
                    nodeDicPool[objType] = typeStack;
                    obj.Visible = true;
                    totalObjList.Add(obj);
                    return obj;
                }
                else
                {
                    GameObject gameObject = Instantiate(mapTypeObjDic[objType].gameobject);
                    gameObject.transform.SetParent(transform);
                    GObject obj = new GObject(gameObject, objType);
                    totalObjList.Add(obj);
                    return obj;
                }
            }
            else
            {
                GameObject gameObject = Instantiate(mapTypeObjDic[objType].gameobject);
                gameObject.transform.SetParent(transform);
                GObject obj = new GObject(gameObject, objType);
                obj.Visible = true;
                totalObjList.Add(obj);
                return obj;

            }
        }

    }
        

}


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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551

Unity演示

这里的演示样例，都是跑的同一份代码，每次循环都是随机出发点、目的点、障碍物。

演示样例一

演示样例二

演示样例三

演示样例四