C++迷宫游戏开发 二维地图生成与寻路算法

#include <vector>
#include <cstdlib>
#include <ctime>
<p>const int WIDTH = 21;  // 必须为奇数，便于处理墙
const int HEIGHT = 21;</p><p>std::vector<std::vector<int>> maze(HEIGHT, std::vector<int>(WIDTH, 1));
// 方向：上、右、下、左
int dx[4] = {0, 2, 0, -2};
int dy[4] = {-2, 0, 2, 0};</p><p>void generateMaze(int x, int y) {
maze[y][x] = 0;  // 当前位置设为通路</p><pre class='brush:php;toolbar:false;'>// 随机打乱方向顺序
std::vector<int> dirs = {0, 1, 2, 3};
for (int i = 3; i > 0; i--) {
    int j = rand() % (i + 1);
    std::swap(dirs[i], dirs[j]);
}

for (int d : dirs) {
    int nx = x + dx[d];
    int ny = y + dy[d];

    if (nx > 0 && nx < WIDTH-1 && ny > 0 && ny < HEIGHT-1 && maze[ny][nx] == 1) {
        maze[y + dy[d]/2][x + dx[d]/2] = 0;  // 打通中间墙
        generateMaze(nx, ny);
    }
}

struct Point {
    int x, y, g, h;
    bool operator<(const Point& p) const {
        return (g + h) > (p.g + p.h); // 优先队列用最大堆，反向比较
    }
};
<p>int heuristic(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2); // 曼哈顿距离
}</p><p>std::vector<std::pair<int, int>> findPath(int start_x, int start_y, int end_x, int end_y) {
std::priority_queue<Point> pq;
std::vector<std::vector<bool>> visited(HEIGHT, std::vector<bool>(WIDTH, false));
std::vector<std::vector<int>> g_val(HEIGHT, std::vector<int>(WIDTH, INT_MAX));
std::vector<std::vector<std::pair<int, int>>> parent(HEIGHT, std::vector<std::pair<int, int>>(WIDTH, {-1, -1}));</p><pre class='brush:php;toolbar:false;'>pq.push({start_x, start_y, 0, heuristic(start_x, start_y, end_x, end_y)});
g_val[start_y][start_x] = 0;

int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};

while (!pq.empty()) {
    Point cur = pq.top(); pq.pop();
    int x = cur.x, y = cur.y;

    if (visited[y][x]) continue;
    visited[y][x] = true;

    if (x == end_x && y == end_y) break;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || nx >= WIDTH || ny < 0 || ny >= HEIGHT) continue;
        if (maze[ny][nx] != 0) continue; // 不是通路
        if (visited[ny][nx]) continue;

        int new_g = g_val[y][x] + 1;
        if (new_g < g_val[ny][nx]) {
            g_val[ny][nx] = new_g;
            parent[ny][nx] = {x, y};
            pq.push({nx, ny, new_g, heuristic(nx, ny, end_x, end_y)});
        }
    }
}

// 回溯路径
std::vector<std::pair<int, int>> path;
int x = end_x, y = end_y;
while (x != -1 && y != -1) {
    path.push_back({x, y});
    auto [px, py] = parent[y][x];
    x = px; y = py;
}
reverse(path.begin(), path.end());
return path;

void printMaze(int px, int py) {
    for (int i = 0; i < HEIGHT; i++) {
        for (int j = 0; j < WIDTH; j++) {
            if (i == py && j == px) std::cout << "P";
            else std::cout << (maze[i][j] ? "#" : " ");
        }
        std::cout << "\n";
    }
}