廣度優先搜索算法（英語：Breadth-first search，縮寫：BFS），又譯作寬度優先搜索，或橫向優先搜索，是一種圖形搜索算法。
尋路地圖搭建：
游戲AI實現-尋路地圖搭建-CSDN博客
算法過程：遍歷方向為從豎直向上沿順時針方向
1.首先將開始節點加入到隊列中。注：黃色代表已檢測。
2.從隊列中取出第一個節點，檢測是否為目標點。
? 如果是則返回目標點終止算法，否則，遍歷變量v相鄰的子節點，將它的子節點，加入到隊列中。
------------------------------->
------------------------------->
3.重復步驟2，直到找到目標點。
代碼實現：
算法實現類：
public class BFS : FindPathAlgorithm
{public BFS(int[,] mapData, int xCount, int zCount) : base(mapData, xCount, zCount) { }public override List<Vector2Int> FindPath(Vector2Int startPos, Vector2Int goalPos){DataNode dataNode = this.BFSFind(startPos, goalPos);if(dataNode == null){Debug.LogError("尋路有誤，請檢查參數是否正確");return null;}//Utils.DisplayData(path);return Utils.GetPath(dataNode);}DataNode BFSFind(Vector2Int startPos, Vector2Int goalPos){//存儲要檢測的點Queue<DataNode> frontier = new Queue<DataNode>();//存儲已經檢測的點List<Vector2Int> reached = new List<Vector2Int>();frontier.Enqueue(new DataNode(startPos, null));reached.Add(startPos);while (frontier.Count > 0){DataNode currentNode = frontier.Dequeue();if (currentNode.pos == goalPos){return new DataNode(goalPos, currentNode.parent);}List<Vector2Int> neighbors = GetNeighbors(currentNode.pos, reached);foreach (Vector2Int p in neighbors){if (this.mapData[p.y,p.x] != 1){frontier.Enqueue(new DataNode(p, currentNode));}//增加已檢測點reached.Add(p);}}return null;}List<Vector2Int> GetNeighbors(Vector2Int current, List<Vector2Int> reached){List<Vector2Int> neighbors = new List<Vector2Int>();for (int i = 0; i < Utils.pointDir.Count; i++){Vector2Int neighbor = current + Utils.pointDir[i];if (this.IsCanAdd(neighbor, reached)){neighbors.Add(neighbor);}}return neighbors;}bool IsCanAdd(Vector2Int current, List<Vector2Int> reached){if (reached.Contains(current))return false;if (current.x >= 0 && current.y >= 0 && current.x < xCount && current.y < zCount)return true;return false;}
}結果：
參考鏈接：
廣度優先搜索 - 維基百科，自由的百科全書 (wikipedia.org)
)
