目录
- 1、介绍
- 2、思想
- 3、定义及快捷
- 4、创建四叉树节点
- 5、判断能不能走
- 6、准备工作
- 7、寻路
- A、标记走过
- B、对预测点进行移动处理
- C、能走的情况下怎么处理
- D、切换层数
- 8、效果展示
- 9、综合代码
- 10、总结
正文
1、介绍
广度寻路算法是一种基于图的搜索算法，用于寻找两个节点之间的最短路径。它从起点开始展开搜索，并逐步向外扩展，直到找到目标节点或所有节点都被访问过。广度寻路算法使用队列作为辅助数据结构来实现搜索。当一个节点被访问时，将其所有的邻居节点加入队列中，并标记为已访问。从队列中取出的节点继续进行扩展搜索，直到队列为空或目标节点被找到为止。广度寻路算法的时间复杂度为O(V+E)，其中V为节点数，E为边数。由于它逐层扩展搜索，因此能够找到最短路径，但会占用较多的空间。需要源代码的私信我~
深度寻路算法：1.循环试探，遇到死胡同回退 2.循环 简单 3.不一定能找到最佳路径 4.空旷地形 深度寻路
广度寻路算法：
1. 不需要回退
2. 一定能找到最短路径
2、思想
深度寻路就好比猴哥的毫毛一样，直接派四个小兵分别去上下左右四个方位寻找，到达下一个位置时，再派四个小兵出去寻找(当然如果有的方向是障碍物，那就不用派人去了)，就这样一直下去，最后会找到终点的，而且是最短路径(后面会解释为什么)
可能有的同学会问了，那要怎么实现呐，每次都要派四个小兵，而且有的不是障碍物的要一直寻路下去，这个时候我们就想到了四叉树来实现，把起点放入根节点，一层就代表一步
有的同学又会问了，那如果一张地图有很多条路径，那广度寻路怎么会找到最短的那一条路径？
其实思想很简单，就是一找到终点就结束循环，从终点往上遍历，这条路径一定是最短路径——因为这条路径是最先结束循环，即最先找到终点
3、定义及快捷
在开始写之前我们先把准备工作写好，比如行和列的定义，最大孩子的数量，因为是试探4个方向，所以最大孩子的数量为4，且这里定义的是四叉树，存储当前层和下一层节点地址的数组大小，地图中路和障碍物的枚举，上下左右方向的枚举，还要定义一个点类型，以及四叉树类型，四叉树中需要定义结构体数组，因为有四个孩子，还有一个重要的是定义当前孩子的数量，因为不仅父亲要指向孩子，孩子也还要指向父亲，因为最后确定最佳路径，还要从终点往上遍历
//行列 #define ROWS 10 #define COLS 10 //最大孩子数量 #define CHILD_NUM 4 //临时数组的最大容量 #define BUFF_SIZE 100 //地图枚举 enum Mymap{road,wall}; //方向枚举 enum Mydirect{p_up,p_left,p_down,p_right}; //点 typedef struct Mypoint { int row, col; }Mypoint; //四叉树节点类型 typedef struct myThree { Mypoint pos; struct myThree* partent; struct myThree* Child[CHILD_NUM]; int Curchild_Num; }myThree; #define SIZE sizeof(myThree)
4、创建四叉树节点
这里先是直接用快捷的方式，把四叉树中都初始化为0，然后再赋值点的坐标
myThree* createThreeNode(Mypoint* pos) { myThree* pNew = malloc(SIZE); assert(pNew); memset(pNew, 0, SIZE); pNew->pos.row = pos->row; pNew->pos.col = pos->col; return pNew; }
5、判断能不能走
当前点越界，以及辅助地图上标记过的点，是墙都不能走
bool can_Walk(Mypoint* pos, bool map[ROWS][COLS], bool pathMap[ROWS][COLS]) { //越界 if (pos->row < 0 || pos->row >= ROWS || pos->col < 0 || pos->col >= COLS) return false; //走过 if (pathMap[pos->row][pos->col]) return false; //是墙 if (map[pos->row][pos->col]) return false; return true; }
6、准备工作
1、简单用数组实现一个二维地图，用于寻路
2、定义起点和终点
3、定义辅助地图，用于标记有没有走过
4、定义两个辅助数组，用来在当前层和下一层之间切换，这两个数组分别是用来存储当前层和下一层节点的地址
5、创建一棵树，起点成为树根，并且根节点还有独占一层
6、准备一个预测点
7、定义isFindend，用来判断是否找到终点，因为寻找的过程是多层循环，一个break结束不了循环，所以定义了一个标记
//1 地图 1表示障碍 0表示路 bool map[ROWS][COLS] = { { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 0, 1, 1, 0, 0, 0, 1, 1, 1 }, { 1, 0, 1, 1, 0, 1, 0, 1, 1, 1 }, { 1, 0, 1, 1, 0, 1, 0, 0, 0, 1 }, { 1, 0, 1, 1, 0, 1, 1, 0, 1, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 1, 1 }, { 1, 0, 1, 1, 1, 1, 1, 0, 1, 1 }, { 1, 0, 1, 1, 0, 0, 0, 0, 0, 1 }, { 1, 0, 1, 0, 0, 1, 1, 1, 0, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } }; //点--起点和终点 Mypoint begPos = { 1,1 }; Mypoint endPos = { 8,8 }; //辅助地图 bool pathMap[ROWS][COLS] = { 0 }; //创建一颗树 myThree* pRoot = NULL; //起点成为树根 pRoot = createThreeNode(&begPos); //辅助数组 //记录当前层节点的地址 myThree* currentLayer[BUFF_SIZE] = { 0 }; // 当前层节点的数量 int currentLayerSize = 0; //记录下一层节点的地址 myThree* nextLayer[BUFF_SIZE] = { 0 }; //下一层节点的数量 int nextLayerSize = 0; //树的根节点独占一层 currentLayer[currentLayerSize++] = pRoot; //预测点 Mypoint search; //标记是否走到终点 bool isFindend = false; //准备一个临时变量 myThree* temp_Node = NULL;
7、寻路
寻路的思想前面已经讲过了，我们一层一层的遍历(即一步一步的遍历)，然后对每一步的四个方向进行处理
A、标记走过
处理之前，我们还要标记当前点已经走过并且要把当前的孩子数量清空
//标记走过 pathMap[currentLayer[i]->pos.row][currentLayer[i]->pos.col] = true; //孩子数量清空 currentLayer[i]->Curchild_Num = 0;
B、对预测点进行移动处理
预测点就是当前的点，然后用switch进行处理
//预测点就是当前点 search.row = currentLayer[i]->pos.row; search.col = currentLayer[i]->pos.col; switch(j) { case p_up: search.row--; break; case p_down: search.row++; break; case p_left: search.col--; break; case p_right: search.col++; break; }
C、能走的情况下怎么处理
能走的情况下当前点就要成为预测点的父节点，预测点还要成为当前点的孩子，除此之外还要把预测点放入下一层数组中，因为它的身份是预测点，即为当前点的孩子，最后还要判断是否到达终点
//能走 if (can_Walk(&search,map,pathMap)) { //创建树节点 temp_Node = createThreeNode(&search); //预测点成为当前点的孩子 currentLayer[i]->Child[currentLayer[i]->Curchild_Num++] = temp_Node; //当前点成为预测点的父亲 temp_Node->partent = currentLayer[i]; //放入下一层数组中 nextLayer[nextLayerSize++] = temp_Node; //判断是否到达终点 if (temp_Node->pos.row==endPos.row&& temp_Node->pos.col == endPos.col) { isFindend = true; break; } }
D、切换层数
如果下一层的数组为空，这时候已经遍历到最后一层了，直接退出，否则切换到下一层
//下一层为空 if (nextLayerSize == 0) break; //切换到下一层中 for (int i = 0; i < nextLayerSize; i++) { currentLayer[i] = nextLayer[i]; } currentLayerSize = nextLayerSize;
