简陋迷宫生成和寻路

#include <iostream>
#include<graphics.h>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define W 801
#define S 801
#define X 1
struct point {
    int x, y;
};
void initMap(vector<vector<int>> &map) {
    if (map.size() > 0) {
        for (int i = 0; i < W; i++) {
            for (int j = 0; j < W; j++) {
                if (i % 2 == 0 || j % 2 == 0) map[i][j]=1;
                else map[i][j]=0;
            }
        }
    }
    for (int i = 0; i < W; i++) {
        map.push_back(vector<int>());
        for (int j = 0; j < W; j++) {
            if (i % 2 == 0 || j % 2 == 0) map[i].push_back(1);
            else map[i].push_back(0);
        }
    }
}
void displayMap(vector<vector<int>>& map) {
    for (int i = 0; i < W; i++) {
        map.push_back(vector<int>());
        for (int j = 0; j < W; j++) {
            if (map[i][j] == -1) setfillcolor(WHITE);
            else setfillcolor(BLACK);
            if(map[i][j]==-2)setfillcolor(RGB(0, 255, 0));
            solidrectangle(j * X, i * X, j * X + X, i * X + X);
        }
    }
}

void maze(vector<vector<int>>& map, int x, int y) {
    map[x][y] = -1;
    int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
    point p = { x,y };
    stack<point> s;
    s.push(p);
    while (!s.empty()) {
        p = s.top();
        s.pop();
        x = p.x;
        y = p.y;
        while (1) {
            bool end = true;
            for (int i = 0; i < 3; i++) {
                end = true;
                int seed;
                vector<int>temp;
                if (y + 2 < W && map[x][y + 2] == 0) temp.push_back(0);
                if (y - 2 > 0 && map[x][y - 2] == 0)temp.push_back(1);
                if (x + 2 < W && map[x + 2][y] == 0)temp.push_back(2);
                if (x - 2 > 0 && map[x - 2][y] == 0)temp.push_back(3);
                if (temp.size() > 0) {
                    seed = temp[rand() % temp.size()];
                }
                else break;
                int dx = dir[seed][0];
                int dy = dir[seed][1];
                int nx = x + 2 * dx;
                int ny = y + 2 * dy;
                if (nx > 0 && ny > 0 && nx < W && ny < W) {
                    if (map[nx][ny] != -1)
                    {
                        end = false;
                        x = nx;
                        y = ny;
                        map[x][y] = -1;
                        map[x - dx][y - dy] = -1;
                        p = { nx,ny };
                        s.push(p);
                        break;
                    }
                }
            }
            //  displayMap(map);
            if (end) break;
        }
    }
}

void findRoad(vector<vector<int>>& map, int sx, int sy, int ox, int oy) {
    map[sx][sy] = -2;
    int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
    point p = { sx,sy };
    stack<point> s;
    s.push(p);
    s.push(p);
    while (!s.empty()) {
        p = s.top();
        s.pop();
        sx = p.x;
        sy = p.y;
        while (true) {
            bool end = false;
            for (int i = 0; i < 3; i++) {
                vector<int>temp;
                int seed;
                if (sy + 1 < W && map[sx][sy + 1] == -1) temp.push_back(0);
                if (sy - 1 > 0 && map[sx][sy - 1] ==-1)temp.push_back(1);
                if (sx + 1 < W && map[sx + 1][sy] == -1)temp.push_back(2);
                if (sx - 1 > 0 && map[sx - 1][sy] ==-1)temp.push_back(3);
                if (temp.size() > 0) {
                    seed = temp[rand() % temp.size()];
                }else break;
                int dx = dir[seed][0];
                int dy = dir[seed][1];
                int nx = sx + dx;
                int ny = sy + dy;
                if (nx > 0 && ny > 0 && nx < W && ny < W) {
                    if (map[nx][ny] == -1)
                    {
                        end = true;
                        sx = nx;
                        sy = ny;
                        map[sx][sy] = -2;
                        setfillcolor(RGB(0,255,0));
                        solidrectangle(sy * X, sx * X, sy * X + X, sx * X + X);
                        //Sleep(100) 减缓寻路过程,其他对应地方也可以通过此方法延长运行时间。
                        if (sx == ox && sy == oy) return;
                        p = { nx,ny };
                        s.push(p);
                        break;
                    }
                }
            }
            if (!end) break;
        }
    }
}

int main()
{
    vector<vector<int>> map;
    srand(unsigned int(time(0)));
    //#include<graphics.h> 需要安装Easyx的图形库,方便查看地图的生成过程
    initgraph(S, S);
    setbkcolor(WHITE);
    srand(unsigned int(time(0)));
    cleardevice();
    while (1) {
        initMap(map);
        int a = rand() % (W - 2);
        int b = rand() % (W - 2);
        if (a % 2 == 0) a += 1;
        if (b % 2 == 0) b += 1;
        maze(map, a, b);
        displayMap(map);
        findRoad(map, 1, 1, W - 2, W - 2);
        displayMap(map);
        Sleep(1000);
    }
    system("pause");
    closegraph();
}

        这是第二次写这个函数,显然比上一次熟练多了。但是由于学习原因,没有进行优化,问题还是很多很多。假期再继续使用其他方法来实现,优化生成的速度。之前看过一个博主的视频,感觉迷宫的运用还是有很多的潜力,探索过程蛮有趣的。

以下是实际效果

简陋迷宫生成和寻路

简陋迷宫生成和寻路

简陋迷宫生成和寻路

上一篇:P1101单词方阵


下一篇:AcWing 4217. 机器人移动(二分+向量前缀和)