[A*演算法]基于Unity實作A*演算法（二）

寫在前面:上一篇當時是非常簡單的了解一下A*，昨天還有一些問題沒解決，就暫時把自己查閱的文壇摘抄了過來（畢竟人家寫的比我要好的多 :> ）

今天終于解決了，就又寫了這一篇，正好我自己再梳理一遍，把Unity的實作也記錄一下（Unity版本：2019.3.7.f1）

====================================================================================

• 一、Unity UI表現實作

　　UI制作很簡單，如下圖

1. Canvas

　　　　UGUI畫布（參考官網檔案）

　　　　我這邊主要是在上面掛載一個尋路腳本CSPathFindManager_AStar.CS

　　2.Panel

　　　　這里我用的是UGUI創建的Panel，主要是用來生成尋路點，掛載生成腳本CopyManager.CS

　　3.Node

　　　　UGUI創建的Image，用的純色，用來充當路徑點，掛載路徑點腳本CSNode.CS

　　4.F/G/H/Pos/Index

　　　　UGUI創建的Text，通過修改檔案對齊方式，使他們的文字分別位于Node的上下左右和中間，用來方便顯示相關的值

二、Unity UI顯示代碼

  1 using System;
  2 using System.Collections;
  3 using System.Collections.Generic;
  4 using UnityEngine;
  5 
  6 public class CSPathFindManager : MonoBehaviour
  7 {
  8     internal CopyObjs copyObjs;
  9 
 10     public Vector2 CellSize = new Vector2();
 11 
 12     public List<CSNode> AllNodesList = new List<CSNode>();
 13     public List<CSNode> openNodeList = new List<CSNode>();
 14     public List<CSNode> closeNodeList = new List<CSNode>();
 15 
 16 
 17     public int notMoveNodeCount = 0;
 18     public CSNode curNode = null;
 19 
 20     public bool isEndFind = false;
 21 
 22     public bool isFinding = false;
 23 
 24     public bool isAutoFind = true;
 25 
 26     public bool canBevel = true;
 27 
 28     // Start is called before the first frame update
 29     void Start()
 30     {
 31         copyObjs = gameObject.GetComponentInChildren<CopyObjs>();
 32         if (copyObjs == null) return;
 33         InitAllPath();
 34     }
 35 
 36     // Update is called once per frame
 37     void Update()
 38     {
 39         if (Input.GetKeyDown(KeyCode.Space))
 40         {
 41             if (isAutoFind)
 42             {
 43                 isFinding = !isFinding;
 44             }
 45             else
 46             {
 47                 InitNearNodes();
 48             }
 49         }
 50 
 51         if (isFinding)
 52         {
 53             InitNearNodes();
 54         }
 55     }
 56 
 57     public virtual void InitAllPath()
 58     {
 59         AllNodesList.Clear();
 60         openNodeList.Clear();
 61         closeNodeList.Clear();
 62 
 63         if (copyObjs == null) return;
 64         copyObjs.MaxCount = (int)(CellSize.x * CellSize.y);
 65 
 66         int nodeIndex = 0;
 67         //System.Random tempRandom = new System.Random(GetRandomSeedbyGuid());
 68 
 69         for (int y = 0; y < CellSize.x; y++)
 70         {
 71             for (int x = 0; x < CellSize.y; x++)
 72             {
 73                 CSNode tempNode = copyObjs.copyObjList[nodeIndex].GetComponent<CSNode>();
 74                 tempNode.SetPos(x, y);
 75 
 76                 if (tempNode.curMoveState == EnumMoveState.NULL)
 77                 {
 78                     tempNode.SetMoveState(EnumMoveState.moveing);
 79                 }
 80 
 81                 AllNodesList.Add(tempNode);
 82                 nodeIndex++;
 83             }
 84         }
 85     }
 86 
 87     public virtual List<CSNode> GetNearNode(CSNode node)
 88     {
 89         List<CSNode> tempNode = AllNodesList.FindAll(temp => IsChild(node, temp));
 90 
 91         if (tempNode != null) tempNode.Remove(node);
 92         return tempNode;
 93     }
 94 
 95     public virtual bool IsChild(CSNode parentNode, CSNode childNode)
 96     {
 97         if (parentNode == null || childNode == null) return false;
 98         if (canBevel)
 99         {
100             return Mathf.Abs(childNode.pos.y - parentNode.pos.y) <= 1 && Mathf.Abs(childNode.pos.x - parentNode.pos.x) <= 1;
101         }
102         else
103         {
104             return (childNode.pos.x == parentNode.pos.x && Mathf.Abs(childNode.pos.y - parentNode.pos.y) == 1) || (childNode.pos.y == parentNode.pos.y && Mathf.Abs(childNode.pos.x - parentNode.pos.x) == 1);
105         }
106     }
107 
108 
109     public virtual int GetGValue(CSNode startNode, CSNode targetNode)
110     {
111         int gV;
112         if (targetNode.pos.x == startNode.pos.x || targetNode.pos.y == startNode.pos.y) gV = 10;
113         int absX = (int)Mathf.Abs(targetNode.pos.x - startNode.pos.x);
114         int absY = (int)Mathf.Abs(targetNode.pos.y - startNode.pos.y);
115         if (canBevel)
116         {
117             if (absX > absY)
118             {
119                 gV = 14 * absY + 10 * (absX - absY);
120             }
121             else
122             {
123                 gV = 14 * absX + 10 * (absY - absX);
124             }
125         }
126         else
127         {
128             gV = 10 * absX + 10 * absY;
129         }
130         return gV + startNode.GValue;
131     }
132 
133     public virtual int GetHValue(CSNode node)
134     {
135         if (CSNode.FinialNode == null) return 99;
136         return (int)Mathf.Abs(node.pos.x - CSNode.FinialNode.pos.x) * 10 + (int)Mathf.Abs(node.pos.y - CSNode.FinialNode.pos.y) * 10;
137     }
138 
139     public virtual void InitNearNodes()
140     { }
141 
142     //int GetRandomSeedbyGuid()
143     //{
144     //    return new Guid().GetHashCode();
145     //}
146 
147     public virtual void ReSetPath()
148     {
149         curNode = null;
150         for (int i = 0; i < openNodeList.Count; i++)
151         {
152             openNodeList[i].SetIndex(0);
153             openNodeList[i].parent = null;
154         }
155         openNodeList.Clear();
156         for (int i = 0; i < closeNodeList.Count; i++)
157         {
158             if ((int)closeNodeList[i].curMoveState > 4 && (int)closeNodeList[i].curMoveState < 8) closeNodeList[i].SetMoveState(EnumMoveState.moveing);
159             closeNodeList[i].parent = null;
160         }
161         closeNodeList.Clear();
162         isEndFind = false;
163     }
164 
165 
166     public virtual CSNode GetMinNode(List<CSNode> nodes)
167     {
168         if (nodes == null || nodes.Count == 0) return null;
169         nodes.Sort((x, y) => x.FValue.CompareTo(y.FValue));
170         return nodes[0];
171     }
172 
173     public virtual void RemoveNotMoveNode(ref List<CSNode> tempNearList)
174     {
175         List<CSNode> notMoveNode = tempNearList.FindAll(temp => temp.curMoveState == EnumMoveState.notmove);
176         tempNearList.RemoveAll(temp => temp.curMoveState == EnumMoveState.notmove);
177         for (int i = 0; i < notMoveNode.Count; i++)
178         {
179             if (notMoveNode[i].pos.y == curNode.pos.y || notMoveNode[i].pos.x == curNode.pos.x) tempNearList.RemoveAll(temp => temp.pos.y != curNode.pos.y && temp.pos.x != curNode.pos.x && (temp.pos.x == notMoveNode[i].pos.x || temp.pos.y == notMoveNode[i].pos.y));
180             tempNearList.Remove(notMoveNode[i]);
181         }
182     }
183 }

 1 using System;
 2 using System.Collections;
 3 using System.Collections.Generic;
 4 using System.Linq;
 5 using UnityEngine;
 6 
 7 public class CSPathFindManager_AStar : CSPathFindManager
 8 {
 9 
10 
11     public override void InitNearNodes()
12     {
13         if (CSNode.StartNode == null || CSNode.FinialNode == null)
14         {
15             isFinding = false;
16             return;
17         }
18         if (!isEndFind)
19         {
20             if (curNode == null)
21             {
22                 curNode = CSNode.StartNode;
23                 curNode.SetIndex(0);
24             }
25             else if (curNode != CSNode.FinialNode)
26             {
27                 curNode = GetMinNode(openNodeList);
28 
29                 curNode.SetIndex(curNode.parent.Index + 1);
30             }
31             else
32             {
33                 isEndFind = true;
34             }
35         }
36 
37         if(isEndFind)
38         {
39             if (curNode!= null && curNode.parent != null && curNode.parent != CSNode.StartNode)
40             {
41                 curNode = curNode.parent;
42                 curNode.SetMoveState(EnumMoveState.best);
43             }
44             else
45             {
46                 isFinding = false;
47 
48                 Debug.LogError("找到了！");
49             }
50             return;
51         }
52         if (curNode.curMoveState == EnumMoveState.moveing) curNode.SetMoveState(EnumMoveState.select);
53         if (AllNodesList == null) return;
54         for (int i = 0; i < closeNodeList.Count; i++)
55         {
56             if (closeNodeList[i].curMoveState == EnumMoveState.select) closeNodeList[i].SetMoveState(EnumMoveState.path);
57         }
58         closeNodeList.Add(curNode);
59         openNodeList.Remove(curNode);
60         List<CSNode> tempNearList = GetNearNode(curNode);
61         tempNearList.RemoveAll(temp => closeNodeList.Contains(temp));
62         RemoveNotMoveNode(ref tempNearList);
63 
64         for (int i = 0; i < tempNearList.Count; i++)
65         {
66             if (tempNearList[i].parent == null || tempNearList[i].parent.Index >= curNode.Index)
67             {
68                 if (tempNearList[i].parent!= null && tempNearList[i].parent.Index == curNode.Index)
69                 {
70                     int gV1 = GetGValue(curNode, tempNearList[i]);
71                     int gV2 = GetGValue(tempNearList[i].parent, tempNearList[i]);
72                     if (gV1 > gV2)
73                     {
74                         continue;
75                     }
76                 }
77                 tempNearList[i].parent = curNode;
78                 int gV = GetGValue(tempNearList[i].parent, tempNearList[i]);
79                 int hV = GetHValue(tempNearList[i]);
80                 tempNearList[i].SetNodeInfo(gV, hV);
81             }
82         }
83 
84         openNodeList.AddRange(tempNearList.FindAll(temp=>!closeNodeList.Contains(temp) && !openNodeList.Contains(temp)));
85 
86         //for (int i = 0; i < openNodeList.Count; i++)
87         //{
88         //    int gV = GetGValue(openNodeList[i].parent, openNodeList[i]);
89         //    int hV = GetHValue(openNodeList[i]);
90         //    openNodeList[i].SetNodeInfo(gV, hV);
91         //}
92         if (openNodeList.Count == 0)
93         {
94             isFinding = false;
95             Debug.LogError("死路！");
96         }
97     }
98 }

  1 using System;
  2 using System.Collections;
  3 using System.Collections.Generic;
  4 using UnityEngine;
  5 using UnityEngine.EventSystems;
  6 using UnityEngine.UI;
  7 
  8 public enum EnumMoveState
  9 {
 10     NULL,
 11     moveing,
 12     notmove,
 13     start,
 14     finial,
 15     path,
 16     select,
 17     best,
 18 }
 19 
 20 public class CSNode : MonoBehaviour
 21 {
 22 
 23     private Text F;
 24     private Text G;
 25     private Text H;
 26     private Text PosText;
 27     private Text IndexText;
 28     private Image movePoint;
 29 
 30     public Vector2 pos;
 31     public int FValue;
 32     public int GValue;
 33     public int HValue;
 34     public int Index;
 35 
 36     public CSNode parent;
 37     public EnumMoveState curMoveState;
 38 
 39     private EventTrigger eventTrigger;
 40     private CSPathFindManager cSPathFindManager;
 41 
 42     public static CSNode StartNode;
 43     public static CSNode FinialNode;
 44     public static List<CSNode> NotMoveNodeList = new List<CSNode>();
 45 
 46     public CSNode(int _x,int _y)
 47     {
 48         pos.x = _x;
 49         pos.y = _y;
 50     }
 51 
 52     public static Dictionary<EnumMoveState, Color> pointColorDic = new Dictionary<EnumMoveState, Color>()
 53     {
 54         { EnumMoveState.moveing,Color.white},
 55         { EnumMoveState.notmove,Color.red},
 56         { EnumMoveState.start,Color.blue},
 57         { EnumMoveState.finial,Color.yellow},
 58         { EnumMoveState.path,Color.gray},
 59         { EnumMoveState.select,Color.cyan},
 60         { EnumMoveState.best,Color.green},
 61     };
 62     // Start is called before the first frame update
 63     void Awake()
 64     {
 65         F = transform.Find("F").GetComponent<Text>();
 66         G = transform.Find("G").GetComponent<Text>();
 67         H = transform.Find("H").GetComponent<Text>();
 68         PosText = transform.Find("Pos").GetComponent<Text>();
 69         IndexText = transform.Find("Index").GetComponent<Text>();
 70         movePoint = GetComponent<Image>();
 71         eventTrigger = gameObject.GetComponent<EventTrigger>();
 72         if (eventTrigger == null) eventTrigger = gameObject.AddComponent<EventTrigger>();
 73         List<EventTrigger.Entry> entryList = eventTrigger.triggers;
 74         if (entryList == null) entryList = new List<EventTrigger.Entry>();
 75         EventTrigger.Entry tempEntry = new EventTrigger.Entry();
 76         bool isExist = false;
 77         for (int i = 0; i < entryList.Count; i++)
 78         {
 79             if (entryList[i].eventID == EventTriggerType.PointerDown)
 80             {
 81                 tempEntry = entryList[i];
 82                 isExist = true;
 83                 break;
 84             }
 85         }
 86         tempEntry.callback.AddListener(OnClick);
 87         if (!isExist)
 88         {
 89             tempEntry.eventID = EventTriggerType.PointerDown;
 90             entryList.Add(tempEntry);
 91         }
 92         cSPathFindManager = GetComponentInParent<CSPathFindManager>();
 93     }
 94 
 95     private void OnClick(BaseEventData arg0)
 96     {
 97         SetMoveState((EnumMoveState)SetNextType());
 98         cSPathFindManager.ReSetPath();
 99     }
100 
101     public int SetNextType()
102     {
103         int tempType = ((int)curMoveState + 1) % 8;
104         if (tempType < 1 || tempType > 4) tempType = 1;
105         return tempType;
106     }
107 
108     // Update is called once per frame
109     void Update()
110     {
111         
112     }
113 
114     public void SetMoveState(EnumMoveState state)
115     {
116         if (state != curMoveState)
117         {
118             ResetNodeInfo(curMoveState, true);
119             ResetNodeInfo(state,false);
120             curMoveState = state;
121             if (movePoint) movePoint.color = pointColorDic[state];
122 
123         }
124     }
125 
126     public void ResetNodeInfo(EnumMoveState state,bool isDel = false)
127     {
128         switch (state)
129         {
130             case EnumMoveState.notmove:
131                 if (isDel)
132                 {
133                     NotMoveNodeList.Remove(this);
134                 }
135                 else
136                 {
137                     if (NotMoveNodeList.Contains(this)) NotMoveNodeList.Add(this);
138                 }
139                 break;
140             case EnumMoveState.start:
141                 if (isDel)
142                 {
143                     if (StartNode == this)
144                     {
145                         StartNode = null;
146                     }
147                 }
148                 else
149                 {
150                     if (StartNode != this)
151                     {
152                         if(StartNode != null)StartNode.SetMoveState(EnumMoveState.moveing);
153                         StartNode = this;
154                     }
155                 }
156                 break;
157             case EnumMoveState.finial:
158                 if (isDel)
159                 {
160                     if (FinialNode == this)
161                     {
162                         FinialNode = null;
163                     }
164                 }
165                 else
166                 {
167                     if (FinialNode != this)
168                     {
169                         if (FinialNode != null) FinialNode.SetMoveState(EnumMoveState.moveing);
170                         FinialNode = this;
171                     }
172                 }
173                 break;
174             default:
175                 break;
176         }
177         //Debug.LogErrorFormat("當前狀態：{0}; 是否洗掉：{3} 起點:{1}; 終點:{2}",state,StartNode,FinialNode,isDel);
178     }
179 
180     public void SetNodeInfo(int _G,int _H)
181     {
182         FValue = https://www.cnblogs.com/lovewaits/p/_G + _H;
183         GValue =https://www.cnblogs.com/lovewaits/p/ _G;
184         HValue =https://www.cnblogs.com/lovewaits/p/ _H;
185         if (F) F.text = (_G + _H).ToString();
186         if (G) G.text = _G.ToString();
187         if (H) H.text = _H.ToString();
188     }
189 
190     internal void SetPos(int _x, int _y)
191     {
192         pos.x = _x;
193         pos.y = _y;
194         if (PosText) PosText.text = string.Format("{0},{1}", _x, _y);
195     }
196 
197     internal void SetIndex(int index)
198     {
199         Index = index;
200         if (IndexText) IndexText.text = string.Format("{0}", index);
201     }
202 }

三、尋路演算法

　　尋路演算法邏輯都在CSPathFindManager_AStar

　　1.獲取當前點cueNode

　　初始化當前點為出發點，之后為從搜索串列openNodeList中FValue(下面會有介紹)最小的節點，并為其設定當前索引值為父節點的索引值+1

　　2.獲取FValue最小節點（GetMinNode）

　　　　串列排序，取第一個

　　3.獲取當前點的子節點

 　　　　設定當前點的UI表現為選中狀態

　　　　遍歷挑選出來的串列，將其UI表現設定為已挑選過狀態

　　　　將當前點加入已挑選串列

　　　　獲取當前點的子節點，刪選掉已挑選過的節點，（在RemoveNotMoveNode里面處理不可走點的刪選）

　　4.為上面獲取到的子節點賦值

　　　　這塊就是昨天我困擾很久的地方，下面是我曾踩過的坑

　　　　(1).在這里遍歷子節點，為他們賦值GValue是相對于當前點的移動距離

　　　　(2).把所有子節點加入搜索串列，再為串列里面的所有節點賦值GValue為當前相對于當前點的移動距離

　　　　(3).把所有子節點加入搜索串列，再為串列里面的所有節點賦值GValue為當前相對于起點的移動距離

　　　　我這么修改是因為下面這種情況：

　　　　后來我改了第四種方式，并將獲取G的方式改為子節點到中轉點的G+中轉點到起點的G：

　　　　(4). 在這里遍歷子節點，判斷如果自己點的父節點不存在或者父節點的索引值大于當前點的索引點，將當前點設為子節點的當前父節點，為他們賦值GValue是當前點為中轉點的移動距離

　　　　結果一樣，因為這里索引值是相同的，于是我又加了=

　　　　(5). 在這里遍歷子節點，判斷如果自己點的父節點不存在或者父節點的索引值大于或等于當前點的索引點，將當前點設為子節點的當前父節點，為他們賦值GValue是當前點為中轉點的移動距離

 　　　　　就在我以為沒問題的時候 :>

　　　　　　在我一步一步看選點順序的時候，發現也沒毛病，但總有哪里不對勁 :>

　　　　　　后來我發現，他是在搜索點里面去找F值最小的，但是主要就是在第5遍修改后加的==判斷，當索引一樣的時候，該子節點在當前點的斜方向上，G值可能會更大

　　　　　　(6).在這里遍歷子節點，判斷如果自己點的父節點不存在或者父節點的索引值大于當前點的索引點，將當前點設為子節點的當前父節點，為他們賦值GValue是當前點為中轉點的移動距離;而當索引值相等時，比較分別以當前點和父節點為中轉點的G值

　　　　nice！！！！ :>

====================================================================================

我估計上面幾種困擾可能也是我理解不夠造成的，走過路過的還請不吝賜教，:>

標籤：其他

上一篇：資料結構與演算法

下一篇：[Dijkstra尋路演算法]基于Unity簡單實作Dijkstra尋路演算法