【記錄】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;}

效果這里寫圖片描述