用C++写一个迷宫代码,要求自动生成迷宫并且可以自动寻路
时间: 2024-05-06 18:17:48 浏览: 10
以下是使用C++语言生成迷宫并自动寻路的示例代码:
```cpp
#include <iostream>
#include <vector>
#include <stack>
#include <cstdlib>
#include <ctime>
using namespace std;
const int MAX_ROW = 20;
const int MAX_COL = 20;
const int WALL = 1;
const int PATH = 0;
struct Point {
int row, col;
Point(int r, int c) : row(r), col(c) {}
};
// 随机生成一个迷宫
void generateMaze(vector<vector<int>>& maze) {
srand(time(nullptr));
int rows = maze.size();
int cols = maze[0].size();
// 初始化迷宫所有位置为墙
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
maze[i][j] = WALL;
}
}
// 随机选择一个起始点
Point start(rand() % rows, rand() % cols);
maze[start.row][start.col] = PATH;
stack<Point> path;
path.push(start);
while (!path.empty()) {
Point cur = path.top();
path.pop();
// 获取当前点的所有邻居
vector<Point> neighbors;
if (cur.row > 1 && maze[cur.row - 2][cur.col] == WALL) {
neighbors.emplace_back(Point(cur.row - 2, cur.col));
}
if (cur.row < rows - 2 && maze[cur.row + 2][cur.col] == WALL) {
neighbors.emplace_back(Point(cur.row + 2, cur.col));
}
if (cur.col > 1 && maze[cur.row][cur.col - 2] == WALL) {
neighbors.emplace_back(Point(cur.row, cur.col - 2));
}
if (cur.col < cols - 2 && maze[cur.row][cur.col + 2] == WALL) {
neighbors.emplace_back(Point(cur.row, cur.col + 2));
}
// 随机选择一个邻居作为下一个点
if (!neighbors.empty()) {
Point next = neighbors[rand() % neighbors.size()];
int wall_row = (cur.row + next.row) / 2;
int wall_col = (cur.col + next.col) / 2;
maze[wall_row][wall_col] = PATH; // 将中间的墙打通
maze[next.row][next.col] = PATH; // 将下一个点标记为路径
path.push(cur);
path.push(next);
}
}
}
// 显示迷宫
void printMaze(const vector<vector<int>>& maze) {
for (const auto& row : maze) {
for (int cell : row) {
cout << (cell == WALL ? "█" : " ");
}
cout << endl;
}
}
// 深度优先搜索寻找通路
bool findPath(vector<vector<int>>& maze, Point start, Point end, vector<Point>& path) {
static const int DIRECTIONS[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
path.clear();
stack<Point> s;
s.push(start);
maze[start.row][start.col] = WALL;
while (!s.empty()) {
Point cur = s.top();
s.pop();
path.push_back(cur);
if (cur.row == end.row && cur.col == end.col) {
return true;
}
for (const auto& dir : DIRECTIONS) {
int r = cur.row + dir[0];
int c = cur.col + dir[1];
if (r < 0 || r >= maze.size() || c < 0 || c >= maze[0].size()) {
continue;
}
if (maze[r][c] == PATH) {
maze[r][c] = WALL;
s.push(Point(r, c));
}
}
}
return false;
}
int main() {
vector<vector<int>> maze(MAX_ROW, vector<int>(MAX_COL));
generateMaze(maze);
printMaze(maze);
Point start(0, 0);
Point end(MAX_ROW - 1, MAX_COL - 1);
vector<Point> path;
if (findPath(maze, start, end, path)) {
cout << "Path found:" << endl;
for (const auto& p : path) {
cout << "(" << p.row << ", " << p.col << ")" << endl;
}
} else {
cout << "No path found!" << endl;
}
return 0;
}
```
该程序首先使用深度优先搜索算法生成一个迷宫,然后使用同样的算法寻找从左上角到右下角的通路并输出路径。