【记录】2种随机迷宫生成算法的cpp实现

2019-11-10 18:16:34

字体：大中小

来源：转载

供稿：网友

1.DFS

dfs(x,y) 标记(x,y 若(x,y)存在未标记的相邻位置从中随机选择一个(nx,ny) 联通(x,y)和这个位置 dfs（nx,ny）若(x,y)所有相邻位置都被标记返回

2.递归分割

dv(xa,ya,xb,yb) /*(xa,ya)为当前区域的左上角， (xb,yb)为当前区域的右下角*/ 如果当前区域太小无法继续分割将这个区域全部打通返回否则在当前区域随机选择一个点作为中心中心向四边做垂线，将当前区域分成四个小区域在这4个区域的临边中随机选择3个在随机位置打通继续分割这四个区域 dv(...)#include<bits/stdc++.h>#include<windows.h>using namespace std;#define MAX 1000char mapp[MAX][MAX];char vis[MAX][MAX];/* U R D L */const int xx[] = {0, 1, 0, -1, -1, -1, 1, 1};const int yy[] = { -1, 0, 1, 0, -1, 1, -1, 1};const int x2[] = {0, 2, 0, -2, -2, -2, 2, 2};const int y2[] = { -2, 0, 2, 0, -2, 2, -2, 2};int W, H;char WALL = '#';char PATH = ' ';int sx, sy, ex, ey;inline void gotoxy(int x, int y) { SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), (COORD) {x, y});}void border(char mapp[MAX][MAX], char v) { for (int i = 0; i <= W; i++) mapp[0][i] = mapp[H][i] = v; for (int i = 0; i <= H; i++) mapp[i][0] = mapp[i][W] = v;}void fill(char mapp[MAX][MAX], char v) { for (int i = 0; i <= H; i++) for (int j = 0; j <= W; j++) mapp[i][j] = v;}void PRintMap() { for (int i = 0; i <= H; i++) { for (int j = 0; j <= W; j++) { printf("%c", mapp[i][j]); } puts(""); }}inline bool checkBorder(int x, int y) { return x < W && x > 0 && y < H && y > 0;}void dfsp(int x, int y) { int d, dic = 0; vis[y][x] = 1; /* go until no new direction */ for (; dic != (1 << 4) - 1; dic |= 1 << d) { /* choose a random direction */ do d = rand() % 4; while (dic & (1 << d)); if (checkBorder(x + x2[d], y + y2[d]) && !vis[y + y2[d]][x + x2[d]]) { /* connect CurrentPosition and NewPosition */ mapp[y + yy[d]][x + xx[d]] = PATH; /* show progress */ Sleep(20);gotoxy(x+xx[d],y+yy[d]);putchar(PATH); dfsp(x + x2[d], y + y2[d]); } }}void dfsMazeCreate(char mapp[MAX][MAX], int w, int h) { W = w << 1, H = h << 1; srand(time(NULL)); memset(mapp, 0, sizeof(mapp)); memset(vis, 0, sizeof(vis)); border(mapp, WALL); fill(mapp, WALL); for (int i = 0; i <= H; i++) for (int j = 0; j <= W; j++) if (i & 1 && j & 1) mapp[i][j] = PATH; gotoxy(0, 0); printMap(); dfsp(1, 1);}/* Create a random hole on Wall(a,b) */inline int randomHoleOn(int a, int b) { if (a > b) a ^= b ^= a ^= b; a++; b--; int r; do r = rand() % (b - a + 1) + a; while (!r & 1); return r;}void dvp(int ax, int ay, int bx, int by) { /* if the current area is too small to divide, then clear current area. */ if (bx - ax < 3 || by - ay < 3) { if (bx - ax < 3) { for (int i = ay + 1; i < by; i++) mapp[i][ax + 1] = PATH; } if (by - ay < 3) { for (int i = ax + 1; i < bx; i++) mapp[ay + 1][i] = PATH; } return; } int tmp, cx, cy, a, b; /* choose a random dividing center in CurrentArea */ do { cx = rand() % (bx - ax - 1) + ax + 1; cy = rand() % (by - ay - 1) + ay + 1; } while (cx & 1 || cy & 1); /* Choose a random Wall between this 4 areas which divided by center. And connect other Walls with random postion. */ tmp = rand() % 4 + 10; if (tmp != 0) mapp[cy][randomHoleOn(ax, cx)] = PATH; if (tmp != 1) mapp[cy][randomHoleOn(cx, bx)] = PATH; if (tmp != 2) mapp[randomHoleOn(ay, cy)][cx] = PATH; if (tmp != 3) mapp[randomHoleOn(cy, by)][cx] = PATH; /* divide the new area */ dvp(ax, ay, cx, cy); dvp(cx, ay, bx, cy); dvp(ax, cy, cx, by); dvp(cx, cy, bx, by);}void dvMazeCreate(char mapp[MAX][MAX], int w, int h) { W = w << 1, H = h << 1; srand(time(NULL)); memset(mapp, 0, sizeof(mapp)); memset(vis, 0, sizeof(vis)); border(mapp, WALL); fill(mapp, WALL); for (int i = 0; i <= H; i++) for (int j = 0; j <= W; j++) if (i & 1 && j & 1) mapp[i][j] = PATH; dvp(0, 0, W, H);}int main(void) { system("mode con: cols=120 lines=45"); int w,h; w = 40, h = 10; dfsMazeCreate(mapp, w,h); gotoxy(0, 0); printMap(); gotoxy(w*2+2, h*2); puts("Created by DFS."); dvMazeCreate(mapp, w,h); gotoxy(0, h*2+2); printMap(); gotoxy(w*2+2, h*4+2); puts("Created by Recursive Partitioning."); getchar(); return 0;}

效果这里写图片描述