C语言

2024-07-17 01:24| 来源: 网络整理| 查看: 265

老鼠走迷宫-c语言（基于深度优先的寻路算法）

这个是学校的课设，刚开始有点头疼，但是感觉越做越有意思了，于是就有如下代码，可能相较于大佬还有差距，但是这是我目前所能做的最优的程序了吧！

话不多说，说一下代码的核心内容吧！

迷宫是通过二维数组构造的，二维组中的数字2代表墙体，0是通路，1是老鼠，3代表粮；

以下是所有函数及全局变量： void game() //走迷宫游戏，包含时间统计，以及对老鼠的移动控制，游戏模块；void create_plat() //新建地图，并存入文件的模块；文件会保存在程序同目录下，地图文件名是plat.txt；void show_plat() //地图展示模块；void alter_plat() //修改地图模块；void read_plat() //读取文件里的地图模块；在读取地图之前必须先含有该文件（plat.txt）；void path_result(int p,int q) //统计地图的所有可能出现的路径结果，并把次数赋给全局变量answer，并在path_result函数中引用变量，作为递归终止和显示最优解的条件；void path_best(int p,int q,int l) //显示最优路径的模块；void path_find(int p,int q) //寻找通关路径的模块；//全局定义的变量 int m=4,n=4; //老鼠的初始位置 int p=4,q=4; //老鼠位置二次定位 int x=7,y=7; //粮仓初始位置 int g,answer; //g:统计有效路径，防止路径过多，造成循环过度；answer:统计该地图的所有可能性；

这个代码有一定的缺陷，因为自动寻路算法是用深度遍历，所以必须要统计全部结果，而且随着地图越来越空，得到的结果越来越多，运算的复杂度提升将会浪费许多时间，我的是9x9的地图，内部7x7如果全为空，则需要计算不止5亿次，5亿次是得到的结果这么多，而且要引用变量，所以翻倍10亿次运算的结果；本人亲测花了6个小时的时间。所以该部分寻路算法，是很大的缺陷，目前已找到解决办法，深度优先是必须找到路最长的，而广度优先是找到最短的就可以停止，所以不久之后我会再更新一篇博客，用广度优先实现自动寻路，相较于深度优先，会更加快速的找出最短路径。

以下是源代码：

大家可以自己试试，编程软件vc6.0

#include #include #include #include #define M 9 #define N 9 int maze[M][N] = { {2,2,2,2,2,2,2,2,2}, {2,0,0,0,2,0,0,0,2}, {2,0,2,0,0,0,2,2,2}, {2,0,0,2,2,0,0,0,2}, {2,0,2,0,1,2,2,0,2}, {2,0,2,0,2,0,0,0,2}, {2,0,2,0,2,2,0,2,2}, {2,0,0,0,0,2,0,3,2}, {2,2,2,2,2,2,2,2,2} }; struct best //用于记录最短路径的结构体 { int min; int b[M][N]; }Best; int m=4,n=4; //老鼠的初始位置 int p=4,q=4; //老鼠位置二次定位 int x=7,y=7; //粮仓初始位置 int g,answer; //g:统计有效路径，防止路径过多，造成循环过度；answer:统计该地图的所有可能性； void game() //走迷宫游戏，包含时间统计，以及对老鼠的移动控制，游戏模块 { int i,j,v,t=0; //t为初始时间 char str; time_t start,end; start=time(NULL); maze[x][y]=3; m=p; n=q; maze[m][n]=1; //重新定位老鼠位置 printf("显示迷宫：\n"); //地图初始化 for (i = 0 ; i < M ; i++) { for (j = 0 ; j < N ; j++) { if(maze[i][j] == 2){ printf("▉"); } else if(maze[i][j]==1) { printf("鼠"); } else if(maze[i][j]==3) { printf("粮"); } else { printf(" "); } } printf("\n"); } printf("（按w↑s↓a← d→移动）\n请在15秒内通关☆(－ｏ⌒)\n"); //初始化地图 while(1) { printf("时间：%d\r",t); if(kbhit()) //输入控制 { str=getch(); if(str=='w') //上 { if(maze[m-1][n]==0) { maze[m-1][n]=1; maze[m][n]=0; m=m-1; } else if(maze[m-1][n]==3) { maze[m][n]=0; v=1; } } else if(str=='s') //下 { if(maze[m+1][n]==0) { maze[m+1][n]=1; maze[m][n]=0; m=m+1; } else if(maze[m+1][n]==3) { maze[m][n]=0; v=1; } } else if(str=='a') //左 { if(maze[m][n-1]==0) { maze[m][n-1]=1; maze[m][n]=0; n=n-1; } else if(maze[m][n-1]==3) { maze[m][n]=0; v=1; } } else if(str=='d') //右 { if(maze[m][n+1]==0) { maze[m][n+1]=1; maze[m][n]=0; n=n+1; } else if(maze[m][n+1]==3) { maze[m][n]=0; v=1; } } else; system("cls"); printf("显示迷宫：\n"); //显示游戏地图 for (i = 0 ; i < M ; i++) { for (j = 0 ; j < N ; j++) { if(maze[i][j] == 2) { printf("▉"); } else if(maze[i][j]==1) { printf("鼠"); } else if(maze[i][j]==3) { printf("粮"); } else { printf(" "); } } printf("\n"); } printf("（按w↑s↓a← d→移动）\n请在15秒内通关☆(－ｏ⌒) \n"); } else; if(v==1) //判断是否通关 { printf("\n恭喜通关！(￣▽￣)~*\n"); system("pause"); break; } if(t>15) //规定时间到后结束游戏 { printf("\n未在规定时间内通关，游戏失败。(╯︵╰)\n"); maze[m][n]=0; //清除最后所在位置 system("pause"); break; } end=time(NULL); t=difftime(end,start); } } void create_plat() //新建地图，并存入文件的模块 { int i,j,s; cc: printf("请输入0和2,0代表通路，2代表墙体(数字用空格隔开)，输入规格是%dx%d，有边缘墙体无需再次输入(￣▽￣)／\n",M-2,M-2); for(i=1;i

【本文地址】

C语言

C语言

今日新闻

推荐新闻