C语言实现走迷宫游戏：栈回溯算法与可视化演示

程序设计思路与核心逻辑

本程序旨在通过编程模拟走迷宫的过程。主要涉及以下几个关键环节：

• 地图构建：使用二维数组 map[100][100] 表示迷宫，其中特定数值代表墙体、通路、起点和终点。
• 数据结构选择：虽然传统栈只用于单向存储，但此处使用 std::deque<node> 作为栈的容器，支持在需要时访问和修改路径节点的状态，方便演示回溯过程。
• 寻路算法：采用深度优先搜索（DFS）。从起点开始，按优先级尝试上下左右四个方向。若前方无路，则根据栈顶信息进行回溯；若到达终点则成功。
• 实时显示：利用 system("cls") 清屏和 Sleep() 延时，动态展示机器人（或探索者）的移动轨迹。

第1步：定义数据模型

首先定义 node 类，用于封装当前位置 x,y 以及上一步的操作方向 lastOpt，这对于回溯时恢复位置至关重要。

#include <cstdio>
#include <deque>
#include <windows.h>
using namespace std;

class node {
public:
 int x, y;
 int lastOpt; // 记录最后一步的操作，用于回溯
};
deque<node> sta; // 用作栈的结构，存储走过的路径
// 全局变量定义
int x, y;         // 当前坐标
int endx, endy;   // 终点坐标
int mapW, mapH;   // 迷宫宽高
int steps;        // 步数计数器
// 方向数组：0=原地(占位), 1=右, 2=下, 3=左, 4=上
int xopt[5] = {0, 0, 1, 0, -1};
int yopt[5] = {0, 1, 0, -1, 0};
int map[100][100]; // 迷宫地图

第2步：初始化迷宫环境

init() 函数负责设置迷宫尺寸、边界墙壁以及内部障碍物。在此示例中，硬编码了一个 10x10 的简易迷宫布局。

• 起点设定为 (1, 1)。
• 终点设定为 (1, 9)，并用特殊值 5 标记。
• 外围一圈设为 -1 表示不可通行的边界。
• 内部通过赋值 -1 设置具体的墙壁位置。

void init() {
 x = 1;
 y = 1;
 endx = 1;
 endy = 9;
 mapH = 10;
 mapW = 10;
 
 // 设置边界
 for(int i=0; i<=mapH; i++)
  for(int j=0; j<=mapW; j++)
   if(i==0 ||j==0 ||i==mapH||j==mapW)
    map[i][j]=-1;
 
 steps=0;
 // 手动设置内部障碍墙体 (-1)
 map[1][2]=-1; map[2][2]=-1; map[3][2]=-1; map[4][2]=-1;
 map[6][2]=-1; map[7][2]=-1; map[8][2]=-1; map[9][2]=-1;
 map[9][3]=-1; map[8][3]=-1;
 map[1][4]=-1; map[3][4]=-1; map[4][4]=-1; map[5][4]=-1;
 map[6][4]=-1; map[7][4]=-1;
 map[1][6]=-1; map[2][6]=-1; map[3][6]=-1; map[4][6]=-1;
 map[5][6]=-1; map[6][6]=-1; map[7][6]=-1; map[8][6]=-1;
 map[8][7]=-1; map[8][8]=-1;
 map[7][8]=-1; map[6][8]=-1; map[5][8]=-1;
 map[4][8]=-1; map[3][8]=-1; map[2][8]=-1; map[1][8]=-1;
 
 map[endx][endy]=5; // 设置终点
}

第3步：实现图形渲染

dis() 函数负责在控制台绘制当前状态。通过遍历地图数组，输出不同字符代表不同元素：

• (空格): 空旷通路 (值0)
• # (井号): 墙壁/障碍物 (值-1)
• @ (@符号): 当前探索者位置 (临时值1)
• . (点): 已走过且确认有效的路径 (值2)
• ! (!符号): 终点 (值5)

void dis() {
 system("cls"); // Windows环境下清屏
 int ori = map[x][y]; // 保存当前点原始状态
 map[x][y]=1; // 暂时标记为当前点
 
 for(int i=0; i<=mapH; ++i) {
  for(int j=0; j<=mapW; ++j) {
   if(map[i][j]==0) printf(" ");
   else if(map[i][j]==-1) printf(" #");
   else if(map[i][j]==1) printf(" @");
   else if(map[i][j]==2) printf(" .");
   else if(map[i][j]==5) printf(" !");
  }
  cout<<i<<endl;
 }
 // 打印底部坐标轴
 for(int j=0; j<=mapW; ++j)
  cout<<j<<" ";
 printf("\n\n > steps:%d Exit:(%d,%d)\n",steps,endx,endy);
 
 map[x][y] = ori; // 恢复当前点真实状态，避免污染地图数据
}

第4步：核心寻路与回溯逻辑

这是程序的大脑部分。循环检查当前是否到达终点，未到达则尝试向四个可行方向移动。若遇死胡同，则从队列尾部弹出节点进行回溯。

1. 可行性检查 (can)：

int can(int n) {
 // 检查下一步是否是空地(0)或者终点(5)
 if(map[x+xopt[n]][y+yopt[n]] == 0 || map[x+xopt[n]][y+yopt[n]] == 5)
  return 1;
 return 0;
}

2. 移动记录 (visit)：

void visit(int n) {
 map[x][y]=2; // 将当前点标记为已走过有效路径
 x+=xopt[n];
 y+=yopt[n];   // 更新坐标
 
 node tem;
 tem.x = x;
 tem.y = y;
 tem.lastOpt = n; // 记录这一步的方向
 sta.push_back(tem); // 压栈
 steps++;
}

3. 主循环与回溯：

int main() {
 init();
 node tem;
 
 // 只要没到终点就持续运行
 while( x != endx || y!=endy) {
  int cans = 0;
  // 尝试四个方向 (索引1-4)
  for(int i=1; i<=4; i++) {
   if(can(i)) {
    cans = 1;
    visit(i);
    break;
   }
  }
  
  if(!cans) { // 如果四周都无法前进，执行回溯
   if(!sta.empty()) {
    tem = sta.back();
    // 注意：这里简单地将退回来的位置清空，实际复杂迷宫需更严谨的状态管理
    map[tem.x][tem.y]=0;
    sta.pop_back();
   } else {
    // 栈空且未到终点，说明无解或逻辑异常
    map[x][y]=2;
    // 此分支为兜底退出，正常情况应在之前找到路径
    break;
   }
  }
  
  dis();      // 刷新画面
  Sleep(500); // 延时0.5秒，形成动画效果
 }
 
 if(x==endx && y == endy)
  cout<<"\n > i am finished....(Success!)"<<endl;
 else
  cout<<"\n > I cannot find the right way."<<endl;
 
 return 0;
}

运行效果演示

编译并运行上述代码后，您将看到控制台不断刷新显示迷宫的变化。蓝色/灰色背景的网格中，@ 代表当前探索头，. 代表已经验证过可行性的路径，! 是目标终点。

扩展与注意事项

• 跨平台兼容：代码中使用了 <windows.h> 和 system("cls")，仅在 Windows 环境下有效。在 Linux/Mac 上替换为 curses 库或 ANSI 转义序列可实现类似效果。
• 算法优化：当前使用的是简单的 DFS。对于更复杂的迷宫，可能需要引入 BFS（广度优先搜索）来寻找最短路径，或使用 A* 算法提高效率。
• 内存管理：deque` 在使用完毕后应确保清空，以免占用过多内存资源。

以上就是基于C/C++实现走迷宫游戏的详细内容，更多关于C语言算法实战的资料请关注本站其它相关文章！