深度优先搜索算法(英语:Depth-First-Search,缩写为DFS)是一种用于遍历或搜索树或图的算法。
寻路地图搭建:
游戏AI实现-寻路地图搭建-CSDN博客
算法过程:遍历方向为从竖直向上沿顺时针方向
1.首先将开始节点放入队列中。注:黄色代表已检测、灰色代表已检测不符合的节点。
------------------>
2.从队列中取出第一个节点,检测是否为目标点。
如果是则返回目标点,否则将没有检测过的子节点加入到队列中。
按照从遍历方向不停的将子节点加入队列。。。。
3.如果当前不存在未检测的直接子节点,则将父节点加入到队列中,
重复步骤2,直到找到目标点。
代码实现:
寻路算法类:
public class DFS : FindPathAlgorithm
{public DFS(int[,] mapData, int xCount, int zCount) : base(mapData, xCount, zCount){}public override List<Vector2Int> FindPath(Vector2Int startPos, Vector2Int goalPos){DataNode dataNode = this.DFSFind(startPos, goalPos);if (dataNode == null){Debug.LogError("寻路有误,请检查参数是否正确");return null;}return Utils.GetPath(dataNode);}public DataNode DFSFind(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);}Vector2Int nextNodePos = GetNextNode(currentNode.pos, reached);//如果没有找到合适的子节点,就将当前节点的父节点加入队列if(nextNodePos.x >= 99999999){frontier.Enqueue(currentNode.parent);}else{frontier.Enqueue(new DataNode(nextNodePos, currentNode));reached.Add(nextNodePos);}}return null;}Vector2Int GetNextNode(Vector2Int current, List<Vector2Int> reached) {for (int i = 0; i < Utils.pointDir.Count; i++){Vector2Int neighbor = current + Utils.pointDir[i];if (this.IsCanAdd(neighbor, reached)){return neighbor;}}return Vector2Int.one * int.MaxValue;}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){//如果是障碍物,则不能被Addif (this.mapData[current.y, current.x] == 1){return false;}return true; }return false;}
}
结果:
参考链接:
DFS Pathfinding | Unity (youtube.com)
深度优先搜索 - 维基百科,自由的百科全书 (wikipedia.org)
Depth First Search (DFS) Explained: Algorithm, Examples, and Code - YouTube