1.深度优先搜索
定义:深度优先搜索如字面意思,朝着一个方向先找到底,如果不满足条件了就返回上一个节点,直到找不到了
图示:
代码:
////// 寻路四个方向 /// private static Vector2Int[] _path = new Vector2Int[4] { new Vector2Int(-1, 0), new Vector2Int(1, 0), new Vector2Int(0, 1), new Vector2Int(0, -1) }; ////// 深度优先搜索 /// public static void DepthFristSearch(INode[,] _board,INode target,ref Listblocks) { int count = 0; for (int i = 0; i < _path.Length; i++) { count++; Vector2Int pos = _path[i] + target.ArrayPos; if (pos.x > _board.GetLength(0) - 1 || pos.y > _board.GetLength(1) - 1 ||pos.x < 0 || pos.y < 0) { Debug.Log("越界"); } else { INode block = _board[pos.x, pos.y]; if (block != null && block.NodeType == target.NodeType && !ListIsHaveBlock(blocks, block)) { blocks.Add(_board[pos.x, pos.y]); GameUtlis.Waits(blocks.Count*0.1f, () => { _board[pos.x, pos.y].SetColor(); }); DepthFristSearch(_board,block, ref blocks); } else if (count == _path.Length) { return; } } } } /// /// 是否重复节点 /// private static bool ListIsHaveBlock(Listlist,INode block) { for (int i = 0; i < list.Count; i++) { if (list[i].GUID == block.GUID) { return true; } } return false; }
2.广度优先搜索
定义:广度优先搜索字面含义就是先找完当前的节点,找完之后找下一层的节点,如此重复,直到无法继续,则停止
图示:
代码:
public static void BreadthFristSearch(INode[,] _board, INode target, ref Listblocks) { List nodes = new List (); nodes.Add(target); BreadthFrist(_board, nodes, ref blocks); } /// /// 二维数组的广度优先搜索 /// private static void BreadthFrist(INode[,] _board,Listtarget,ref List blocks) { List nodes = new List (); for (int i = 0; i < target.Count; i++) { for (int j = 0; j < _path.Length; j++) { Vector2Int pos = _path[j] + target[i].ArrayPos; if (pos.x > _board.GetLength(0) - 1 || pos.y > _board.GetLength(1) - 1 ||pos.x < 0 || pos.y < 0) { Debug.Log("越界"); } else { INode block = _board[pos.x, pos.y]; if (block != null && block.NodeType == target[i].NodeType && !ListIsHaveBlock(blocks, block)) { nodes.Add(block); GameUtlis.Waits(blocks.Count*0.1f, () => { _board[pos.x, pos.y].SetColor(); }); blocks.Add(block); } } if (j == _path.Length-1)//达到最大搜索阈值 { BreadthFrist(_board,nodes,ref blocks); } } } } /// /// 是否重复节点 /// private static bool ListIsHaveBlock(Listlist,INode block) { for (int i = 0; i < list.Count; i++) { if (list[i].GUID == block.GUID) { return true; } } return false; }



