深度寻路算法（含图形化界面） |
您所在的位置：网站首页 › for循环图形 › 深度寻路算法（含图形化界面） |
深度寻路算法（含图形化界面）
|
深度寻路算法思想：
文章目录
深度寻路算法思想：1. 深度寻路语言描述2. 栈结构的准备3. 深度寻路算法的实现：准备一个地图和一个辅助地图确定初始点与试探点，终点:循环寻路简单测试寻路过程
4. 深度寻路完整代码
规定试探方向 ： 上右下左 上左下右实时记录每个点，当前试探方向
并且确定每个点是否已经走过 回退：
每走一步，存储一下当前点的位置（利用栈结构）等到需要回退的时候，出栈，返回当前栈顶元素，让当前点返回到上一个 遇到终点，栈结构存储从开始到终点的路径，如果整个栈为空，说明没有终点
1. 深度寻路语言描述
已经走过的路会被标记为true，表示已走过，不可以重复再走一遍；没有走的为false，表示可以行走 起始点为（2，3）；试探点（下一步将要移动的一个临时点）为（2，3）; 试探方向 ： 顺时针 上右下左（优先按照顺序通行） 首先我们在起点试探上方向，为墙壁，所以我们无法移动。我们接着试探右方向，发现也为墙壁，无法移动。接着试探下方向，可以移动，则当前位置移动到（2，4）的位置。接着在新的位置在重新开始上右下左的方向遍历，可以得到，继续往下移动，到达（2，5）接着往右移动，往右移动，往右移动，往上移动，往上移动，注意：此时到达（4，3） 的位置，但是！！！这个地方是一个死胡同。请注意我们无法实现自主回退，因为我们无法重新行走已经走过的路径！！那这样要怎么办呢，我们用到了***栈回退的功能***，我们用一个栈来存储每一步的x，y坐标，栈顶元素即为当前 的位置，我们到达死胡同时，会执行出栈操作，因为出栈会实现回退，这样我们的位置就回退到了（4，4）注意我们此时依旧是死胡同，因为只有一条路，走过的路不能重复走，所以我们必须继续栈回退，直到我们退到了一个可以继续走的位置：（2，5）（是一个十字路口），第一次我们往右走，走不通，所以这次我们会跳过右的路径，进行往下的移动，移动到（2，6），接着往下，往右，往右… 一个重复的步骤总结： 红色的路径表示最终所走的路径，绿色路径表示走到了死胡同进行栈回退的路径； 在多个方向均可以移动的情况下，按 上 右 下 左优先通行， 我们需要一个栈来存储所经过路径，这里采用了顺序栈的形式，当然也可以采用链式栈的形式，栈结构必须要有 入栈 出栈 获取栈顶元素 判断栈是否为空等操作 关于栈和队列的详细操作，请看我这篇博文 #pragma once #include #include #include #include #include using namespace std; template class MyVector { T* pArr; //保存顺序表的首地址 size_t len; //顺序表元素个数 size_t capacity; //当前容量 public: MyVector(); ~MyVector(); //入栈 void push(const T& data); //出栈 void pop() { if (len > 0) { len--; } } //获取栈顶元素 T GetTop() { return pArr[len-1]; } //判断是否为空 bool isempty() { return len == 0; } }; template MyVector::MyVector(){ pArr = NULL; capacity = len = 0; } template MyVector::~MyVector(){ if (pArr){ delete[] pArr; } pArr = NULL; capacity = len = 0; } //入栈 template void MyVector::push(const T& data){ //1.开辟新的内存区域 if (pArr == NULL) { //1. 开辟新的空间 T* pNew = (T*)malloc(sizeof(T) * (len + 1)); //2. 原来的内存指向新的开辟的内存 pArr = pNew; //3. 插入数据 pArr[len++] = data; } else { //1.为后面的开辟新的内存 T* pNew = (T*)malloc(sizeof(T) * (len + 1)); //2.将原有的内存数据的元素拷贝到新的内存里 memcpy(pNew, pArr, sizeof(T) * len); //3.释放原有的内存空间 free(pArr); //4.原来的内存指向新的开辟的内存 pArr = pNew; //5.插入数据 pArr[len++] = data; } return; } 3. 深度寻路算法的实现： 准备一个地图和一个辅助地图地图： #define ROW 10 #define COL 10 int map[ROW][COL] = { {1,1,1,1,1,1,1,1,1,1}, {1,0,1,0,1,1,1,1,1,1}, {1,0,1,0,0,0,0,0,1,1}, {1,0,1,0,1,1,1,0,1,1}, {1,0,0,0,1,1,1,1,1,1}, {1,1,1,0,0,0,1,1,1,1}, {1,1,1,0,1,1,0,0,0,1}, {1,1,1,0,1,0,0,1,1,1}, {1,1,1,0,0,0,1,1,1,1}, {1,1,1,1,1,1,1,1,1,1}, };辅助地图： enum Direct { p_up, p_right, p_down, p_left, }; struct pathNode { int dir; //方向 0 bool isFind; //是否走过 false 0没有走过 }; struct Mypoint { int row; int col; //重载==运算符，为接下来的判断是否到达终点做准备 bool operator==(const Mypoint& pos) { if (row == pos.row && col == pos.col) { return true; } return false; } };辅助地图有一个结构体，记录每个位置的初始方向与是否走过，我们可以设置一个方向枚举，上右下左分别表示0 1 2 3 ；是否走过的标记设置为false 即0；那么我们就可以迅速的给这个辅助地图赋值，即： //辅助地图 pathNode pathMap[ROW][COL] = { 0 }; 确定初始点与试探点，终点:Mypoint结构体记录每个点的位置即 row和col x和y的坐标 //起始点坐标 Mypoint Begpos = { 1,1 }; //终点坐标 Mypoint Endpos = { 6,8 }; //当前点 Mypoint Curpos = Begpos; //试探点 Mypoint Researchpos;起点坐标入栈 //起点坐标入栈 MyVector pStack; pStack.push(Curpos); //起点位置设置为true 已经走过 pathMap[Curpos.row][Curpos.col].isFind = true; 循环寻路寻路过程：来一个循环：由当前点的方向来决定他往哪里走；如果往一个方向走，则试探点先走，更新当前点方向（因为无论如何你的方向都要依次增加）；判断试探点的信息能否走，如果为false并且为0；说明能走，就走，更新当前点的位置为试探点；当前点位置入栈；记录当前点坐标为true，表示已经走过，下次不能走，只能通过退栈的形式返回 注意：上右下这第三个的case语句内容基本是一致的，只有试探点的坐标更新不同，理解了一个则剩下的很容易理解当到达最后一个方向，即左时，如果还不能走，说明死胡同，则需要执行退栈操作，让当前点位置回退到上一个位置，直到到达了一个可以重复走的位置，注意执行顺序：先出栈再获取栈顶元素最后，如果终点的坐标等于当前点的坐标，说明到达终点，记得重载==运算符如果最后栈为空，说明路径没有终点，因为到达死胡同会一直退栈，如果退栈到栈为空，说明整条路没有可以走的路了，则没有终点 while (1) { //试探点重新更新 Researchpos = Curpos; switch (pathMap[Curpos.row][Curpos.col].dir) { case p_up: //试探点的坐标更新 Researchpos.row--; //无论是否能走，它的方向肯定要改变 pathMap[Curpos.row][Curpos.col].dir++; if (pathMap[Researchpos.row][Researchpos.col].isFind == false && map[Researchpos.row][Researchpos.col] == 0) { //能走 就走 Curpos = Researchpos; //当前点位置入栈 pStack.push(Curpos); //当前点标记已经走过 pathMap[Curpos.row][Curpos.col].isFind = true; } break; case p_right: //试探点的坐标更新 Researchpos.col++; //无论是否能走，它的方向肯定要改变 pathMap[Curpos.row][Curpos.col].dir++; if (pathMap[Researchpos.row][Researchpos.col].isFind == false && map[Researchpos.row][Researchpos.col] == 0) { //能走 就走 Curpos = Researchpos; //当前点位置入栈 pStack.push(Curpos); //当前点标记已经走过 pathMap[Curpos.row][Curpos.col].isFind = true; } break; case p_down: //试探点的坐标更新 Researchpos.row++; //无论是否能走，它的方向肯定要改变 pathMap[Curpos.row][Curpos.col].dir++; if (pathMap[Researchpos.row][Researchpos.col].isFind == false && map[Researchpos.row][Researchpos.col] == 0) { //能走 就走 Curpos = Researchpos; //当前点位置入栈 pStack.push(Curpos); //当前点标记已经走过 pathMap[Curpos.row][Curpos.col].isFind = true; } break; case p_left: //试探点的坐标更新 Researchpos.col--; 无论是否能走，它的方向肯定要改变 //pathMap[Curpos.row][Curpos.col].dir++; if (pathMap[Researchpos.row][Researchpos.col].isFind == false && map[Researchpos.row][Researchpos.col] == 0) { //能走 就走 Curpos = Researchpos; //当前点位置入栈 pStack.push(Curpos); //当前点标记已经走过 pathMap[Curpos.row][Curpos.col].isFind = true; } else //死胡同，执行回退操作 { //到达最后一个方向还是没有出去，说明是死胡同 //执行出栈操作 pStack.pop(); //获取栈顶元素 Curpos = pStack.GetTop(); } break; } //是否到达终点 if (Endpos == Curpos) { isFindEnd = true; break; } //没有到达终点 if (pStack.isempty()) { printf("这条路没有终点!\n"); return 0; } } 简单测试寻路过程到达终点后依次从后往前退栈，打印出路径情况 int x, y; if (isFindEnd) { //到达终点 printf("到达终点了!\n"); while (!pStack.isempty()) { x=pStack.GetTop().col; y = pStack.GetTop().row; printf("（%d，%d）", x, y); pStack.pop(); } }
包含寻路的图形化界面 具体素材请点击这里 #include "MyVector.h" #include #include #define ROW 10 #define COL 10 #define SIZE 50 enum Direct { p_up, p_right, p_down, p_left, }; struct pathNode { int dir; //方向 0 bool isFind; //是否走过 false 0没有走过 }; struct Mypoint { int row; int col; bool operator==(const Mypoint& pos) { if (row == pos.row && col == pos.col) { return true; } return false; } }; #if 1 IMAGE road, wall, pos, ren; void printmapCMD(int(*map)[COL], Mypoint pos); void printmapDRAW(int(*map)[COL], Mypoint pos); void load_IMAGE(); int main() { int map[ROW][COL] = { {1,1,1,1,1,1,1,1,1,1}, {1,0,1,0,1,0,0,1,1,1}, {1,0,1,0,1,1,1,0,1,1}, {1,0,1,0,1,1,1,0,1,1}, {1,0,0,0,1,1,1,0,1,1}, {1,1,1,0,0,0,1,0,1,1}, {1,1,1,0,1,1,0,0,0,1}, {1,1,1,0,1,0,0,1,1,1}, {1,1,1,0,0,0,1,1,1,1}, {1,1,1,1,1,1,1,1,1,1}, }; //辅助地图 pathNode pathMap[ROW][COL] = { 0 }; load_IMAGE(); setbkcolor(WHITE); cleardevice(); //起始点坐标 Mypoint Begpos = { 1,1 }; //终点坐标 Mypoint Endpos = { 7,2 }; //当前点 Mypoint Curpos = Begpos; //试探点 Mypoint Researchpos; //起点坐标入栈 MyVector pStack; pStack.push(Curpos); //起点位置设置为true 走过 pathMap[Curpos.row][Curpos.col].isFind = true; //是否到达终点 bool isFindEnd = false; while (1) { //试探点重新更新 Researchpos = Curpos; switch (pathMap[Curpos.row][Curpos.col].dir) { case p_up: //试探点的坐标更新 Researchpos.row--; //无论是否能走，它的方向肯定要改变 pathMap[Curpos.row][Curpos.col].dir++; if (pathMap[Researchpos.row][Researchpos.col].isFind == false && map[Researchpos.row][Researchpos.col] == 0) { //能走 就走 Curpos = Researchpos; //当前点位置入栈 pStack.push(Curpos); //当前点标记已经走过 pathMap[Curpos.row][Curpos.col].isFind = true; } break; case p_right: //试探点的坐标更新 Researchpos.col++; //无论是否能走，它的方向肯定要改变 pathMap[Curpos.row][Curpos.col].dir++; if (pathMap[Researchpos.row][Researchpos.col].isFind == false && map[Researchpos.row][Researchpos.col] == 0) { //能走 就走 Curpos = Researchpos; //当前点位置入栈 pStack.push(Curpos); //当前点标记已经走过 pathMap[Curpos.row][Curpos.col].isFind = true; } break; case p_down: //试探点的坐标更新 Researchpos.row++; //无论是否能走，它的方向肯定要改变 pathMap[Curpos.row][Curpos.col].dir++; if (pathMap[Researchpos.row][Researchpos.col].isFind == false && map[Researchpos.row][Researchpos.col] == 0) { //能走 就走 Curpos = Researchpos; //当前点位置入栈 pStack.push(Curpos); //当前点标记已经走过 pathMap[Curpos.row][Curpos.col].isFind = true; } break; case p_left: //试探点的坐标更新 Researchpos.col--; 无论是否能走，它的方向肯定要改变 //pathMap[Curpos.row][Curpos.col].dir++; if (pathMap[Researchpos.row][Researchpos.col].isFind == false && map[Researchpos.row][Researchpos.col] == 0) { //能走 就走 Curpos = Researchpos; //当前点位置入栈 pStack.push(Curpos); //当前点标记已经走过 pathMap[Curpos.row][Curpos.col].isFind = true; } else { //到达最后一个方向还是没有出去，说明是死胡同 //执行出栈操作 pStack.pop(); Curpos = pStack.GetTop(); } break; } printmapCMD(map, Curpos); printmapDRAW(map, Curpos); //是否到达终点 if (Endpos == Curpos) { isFindEnd = true; break; } //没有到达终点 if (pStack.isempty()) { printf("这条路没有终点!\n"); return 0; } } int x, y; if (isFindEnd) { //到达终点 printf("到达终点了!\n"); while (!pStack.isempty()) { x=pStack.GetTop().col; y = pStack.GetTop().row; printf("（%d，%d）", x, y); putimage(SIZE + x * SIZE, SIZE + y * SIZE, &pos); pStack.pop(); } } system("pause"); return 0; } #else int main() { MyVector a; for (int i = 0; i |
如图：我们在起点（2，3）的位置，要到达终点为（9，7）的位置：紫色为墙壁法无移动，白色为路径
【本文地址】