前言：最近沒事兒沒作業，計劃每天寫一篇博客，防止對Unity生疏，也可以記錄學習的點點滴滴，
A*尋路在很多面試里都會問到，但實際作業中根本用不著自己寫，網上有成熟的插件，不容易錯還方便，
思路：我們將地塊切成大小均勻的格子，格子分成普通（可通行）、起點、終點、阻擋型別（不可通行），每次回圈時，查找open串列中綜合代價最低的為當前格子，查找當前格子的八個方向(也可以查找四個方向)的鄰格，計算綜合代價并加入到open串列中去，當前格子就加入到close串列里，并從open串列中移除，當open串列內容為空時，或者當前格子已經為結束點時，結束回圈，F代表綜合代價，也就是起始距離 + 結束距離 = 綜合距離；H代表結束距離（忽視阻擋）；G代表起始距離
示例：
第一步，先實作Cell物件
using System.Collections; using System.Collections.Generic; using UnityEngine; using System; public class Cell : MonoBehaviour, IComparable { private CellType m_type; public CellType myType { get => m_type; set { m_type = value; switch (m_type) { case CellType.Normal: SetColor(Color.white); break; case CellType.Start: SetColor(Color.green); break; case CellType.End: SetColor(Color.red); break; case CellType.Block: SetColor(Color.black); break; } } } public Vector2Int pos;//坐標 public int F, G, H;//綜合代價、起始代價、結束代價 public Cell parent;//父物體，為方便查找上一個節點，類似鏈表 private MeshRenderer render; private void Awake() { render = GetComponent<MeshRenderer>(); } public void SetColor(Color color) { render.material.color = color; } /// <summary> /// 兩個cell物件排序，需要實作icompareable介面，指定它倆對比，是指對比F /// </summary> /// <param name="obj"></param> /// <returns></returns> public int CompareTo(object obj) { Cell cell = (Cell)obj; if (cell.F > F) { return -1; } else if (cell.F == F) { return 0; } else { return 1; } } }
第二步，實作查找具體方法
using System.Collections; using System.Collections.Generic; using UnityEngine; /// <summary> /// 這就是格子型別 /// </summary> public enum CellType { Normal = 1, Start = 2, End = 3, Block = 4 } public class AStar : MonoBehaviour { /// <summary> /// 這是生成地圖資料 /// </summary> public int[,] map = { {2, 1, 4, 1, 1 }, {1, 1, 4, 1, 1 }, {1, 1, 4, 1, 1 }, {1, 1, 4, 1, 1 }, {1, 1, 1, 1, 3 } }; /// <summary> /// 預制體 /// </summary> public GameObject prefab; /// <summary> /// 所有格子物件 /// </summary> private Cell[,] cells; /// <summary> /// 開始點坐標和結束點坐標 /// </summary> private Vector2Int startPos, endPos; /// <summary> /// open串列和close串列 /// </summary> private List<Cell> openList, closeList; /// <summary> /// 存盤路徑的堆疊 /// </summary> private Stack<Cell> path; private void Start() { cells = new Cell[map.GetLength(0), map.GetLength(1)]; openList = new List<Cell>(); closeList = new List<Cell>(); path = new Stack<Cell>(); //生成地圖 Vector3 pos = Vector3.zero; for (int i = 0; i < map.GetLength(0); i++) { for (int j = 0; j < map.GetLength(1); j++) { pos.Set(i * 1.5f, 0, j * 1.5f); GameObject obj = GameObject.Instantiate<GameObject>(prefab); obj.transform.parent = transform; obj.transform.position = pos; Cell cell = obj.AddComponent<Cell>(); CellType temp = (CellType)map[i, j]; if (temp == CellType.Start) { startPos.Set(i, j); } else if (temp == CellType.End) { endPos.Set(i, j); } cell.myType = temp; cell.pos.Set(i, j); cells[i, j] = cell; } } } private void Update() { if (Input.GetMouseButton(0)) { Find(); StartCoroutine(Draw()); } } private void Find() { openList.Add(cells[startPos.x, startPos.y]); Cell currentCell = openList[0]; while (openList.Count > 0 && currentCell.myType != CellType.End) { //通過排序找到綜合代價最小的 openList.Sort(); currentCell = openList[0]; //這里已經找到了 if (currentCell.myType == CellType.End) { while (currentCell.parent != null) { if (currentCell.parent.myType != CellType.Start) { path.Push(currentCell.parent); } currentCell = currentCell.parent; } return; } //查找八個鄰格 for (int i = -1; i <= 1; i++) { for (int j = -1; j <= 1; j++) { //增量為0，代表這個坐標指自己，所以直接跳過 if (i == 0 && j == 0) { continue; } //如果想只獲取四個方向的鄰格，就需要排除增量i = 增量j的情況 //if (i == j) //{ // continue; //} int x = currentCell.pos.x + i; int y = currentCell.pos.y + j; if (x < 0 || y < 0 || x >= cells.GetLength(0) || y >= cells.GetLength(1) || cells[x,y].myType == CellType.Block || closeList.Contains(cells[x,y])) { //這里判斷當前鄰格的坐標是否合法？是否為阻塞格子？是否已經存在于close串列中？ continue; } //重新計算起始距離，乘10為了方便計算，當前坐標的格子的起始距離 = CurrenCell的起始距離 + 當前坐標的格子與CurrenCell的距離 int g = (int)(currentCell.G + Mathf.Sqrt(Mathf.Abs(i) + Mathf.Abs(j))* 10); if (cells[x,y].G == 0 || g < cells[x,y].G) { //若當前坐標的格子并未被查找過，或者當前坐標的格子的起始代價大于新算的起始代價，則更新 cells[x, y].G = g; cells[x, y].parent = currentCell; } cells[x, y].H = (Mathf.Abs(x - endPos.x) + Mathf.Abs(y - endPos.y)) * 10;//計算結束距離 cells[x, y].F = cells[x, y].G + cells[x, y].H;//綜合代價 if (!openList.Contains(cells[x,y])) { openList.Add(cells[x, y]); } } } openList.Remove(currentCell); closeList.Add(currentCell); if (openList.Count == 0) { //這里是指open串列都已經沒有內容了，但是仍未查找到結束點，因此可認為無路可達 Debug.LogWarning("窮途末路"); } } } private IEnumerator Draw() { while (path.Count > 0) { Cell cell = path.Pop(); cell.SetColor(Color.blue); yield return new WaitForSeconds(0.2f); } } }
第三步，測驗并查看正確性
這是八個方向的
這是四個方向的
總結：
以前同事做推箱子的時候，就用過A*演算法，還教過我，不過我當時并沒懂，最近又挨著學了一次，發現還是自己動手牢靠，記得比較清晰，當時的我的誤區在于，我以為close串列就是路徑，其實close串列僅僅代表“這個格子我已經檢查過啦，不必再檢查了”，真正的路徑是通過結束點，一步步獲取它的parent直到起始點（起始點的parent為空），這樣才是完整路徑，還需要注意的是，我們每次回圈都會對open串列排序，選擇綜合代價最小的格子，作為本次回圈的“CurrentCell”，所以我們必須為Cell物件實作排序介面，指定排序是通過對比F綜合代價，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/539772.html
標籤：其他