不太规则的迷宫生成算法2
发布时间：2020-12-16 09:09:03 所属栏目：百科 来源：网络整理
导读：先直接给一个直观的例子： ＿ ＿ ＿ ＿ ＿ ＿ ＿ ＿ ╲＿╱ ╲＿╱ ╲＿╱ ╲＿╱ ╲＿╱ ╲＿╱ ╲＿╱ ╲ ╲＿ ╲＿ ╲ ＿ ＿╱ ＿╱ ＿╱ ╱ ╱ ╱ ╱ ╲＿╱ ╲＿ ╲ ╲＿ ＿╱ ╲ ╲ ╱ ＿╱ ╲＿ ╲ ╱ ╲＿ ╲＿ ╲＿╱ ＿╱ ╱ ╲＿╱ ＿╱ ╲ ╱ ＿
|
先直接给一个直观的例子： ＿ ＿ ＿ ＿ ＿ ＿ ＿ ＿
╲＿╱ ╲＿╱ ╲＿╱ ╲＿╱ ╲＿╱ ╲＿╱ ╲＿╱ ╲
╲＿ ╲＿ ╲ ＿ ＿╱ ＿╱ ＿╱ ╱
╱ ╱ ╱ ╲＿╱ ╲＿ ╲ ╲＿ ＿╱ ╲
╲ ╱ ＿╱ ╲＿ ╲ ╱ ╲＿ ╲＿ ╲＿╱ ＿╱
╱ ╲＿╱ ＿╱ ╲ ╱ ＿ ╲＿╱ ＿ ╲＿ ╲
╲ ╱ ＿╱ ╱ ╲＿╱ ╲ ╲＿ ╲＿╱ ＿╱
╱ ╲＿╱ ＿╱ ╲＿ ╱ ╲＿╱ ╲ ╱ ╲＿ ╲
╲＿ ╲ ╱ ＿╱ ╲＿╱ ╲ ╱ ╱ ╲ ╲ ╱
╱ ╱ ╲＿ ╱ ＿╱ ╲ ╱ ╱ ╲＿ ╲
╲ ╱ ╲＿ ╲＿╱ ╲＿ ╲ ╱ ╲＿╱ ╲＿ ╲＿╱
╱ ╲＿╱ ＿╱ ╲ ╱ ＿╱ ╲ ╱ ╲＿╱ ＿╱ ╲
╲ ╱ ╲＿ ＿╱ ╲＿ ╱ ╱ ╲＿ ╲ ╱
╱ ＿ ＿╱ ＿ ╲＿╱ ╲＿╱ ╱ ＿╱ ╲
╲ ╱ ╲＿╱ ＿╱ ╲＿╱ ╲＿ ╲＿╱ ╲＿ ╲ ╱
╱ ╲ ╱ ＿╱ ╱ ╱ ＿╱ ╲＿ ╲ ╱ ╲
╲ ╱ ╲＿ ╲ ╱ ╲ ╱ ＿╱ ＿╱ ＿╱ ╱
╱ ╲＿ ╲ ╱ ╲＿ ╲＿╱ ╱ ＿╱ ╲＿╱ ╲
╲ ╱ ╱ ＿╱ ╲＿╱ ╲＿╱ ╲ ╱ ╲ ＿╱
╱ ＿╱ ╲＿ ＿ ＿ ＿╱ ＿ ╲＿ ╲
╲＿╱ ╲＿╱ ╲＿╱ ╲＿╱ ╲＿╱ ╲＿╱ ╲＿╱ ╲＿
?
以上的蜂窝形迷宫，看起来已经跳出了一般的矩形模式的框架，
但实际上，我们仍然可以进行转换，使得几乎可以继续套用矩形生成的办法
首先数据结构仍然用的二维数组，但是，表示方式需要变化：
0 0 0 0 0 0 0...
0 0 0 0 0 0 0...
0 0 x 0 x 0 x
0 0 0 x 0 x 0
0 0 x 0 x 0 x
0 0 0 x 0 x 0
0 0?x 0 x 0 x
...
每个x对应着一个六边形，其值有7位有效位，1位访问标志位，6位连通标志位，
它和相邻哪一块连通，就哪个标志位置为1（同时与它相连的那个x对应的位也要标记上）
有效数据矩阵的边界留了2，以保证不会发生访问越界的问题，并且访问标志位置上1
后面就和一般的迷宫生成算法区别不大了。
?
完整生成代码如下：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
?
int yzfy[999][999];
int dxy[][2] = {{-1,-1},{-2,0},{-1,1},{1,{2,-1}};
?
int dfs(int y,int x)
{
????if (yzfy[y][x]) return 0;
????yzfy[y][x] |= 1;
????int d = rand()&1?5:1;
????for (int f=rand()%6,i=0; i<6; ++i,f=(f+d)%6)
????{
????????if (dfs(y+dxy[f][0],x+dxy[f][1]))
????????{
????????????yzfy[y][x] |= 2<<f;
????????????yzfy[y+dxy[f][0]][x+dxy[f][1]] |= 2<<((f+3)%6);
????????}
????}
????return 1;
}
?
void Gen(int w,int h)
{
????int rw = w*2+3,rh = h*2+3;
????memset(yzfy,sizeof(yzfy));
????for (int y=0; y<rh; ++y)
????{
????????yzfy[y][0] = yzfy[y][1] = 1;
????????yzfy[y][rw-1] = yzfy[y][rw-2] = 1;
????}
????for (int x=0; x<rw; ++x)
????{
????????yzfy[0][x] = yzfy[1][x] = 11;
????????yzfy[rh-1][x] = yzfy[rh-2][x] = 1;
????}
????srand(time(NULL));
????dfs(rand()%(w-1)*2+2,rand()%(h-1)*2+2);
????yzfy[2][2] |= 2;
????yzfy[rh-2][rw-2] |= 2;
}
?
int main(int argc,char *argv[])
{
????int w = 8,h = 10,y,x;
????int rw = w*2+3,rh = h*2+3;
????Gen(w,h);
????for (y=1; y<rh-1; ++y)
????{
????????if (y&1)
????????{
????????????for (x=2; x<rw-2; x+=2,printf(" "))
????????????{
????????????????printf((yzfy[y][x-1]>>3)&1?" ":"╲");
????????????????printf((yzfy[y+1][x]>>2)&1?" ":"＿");
????????????????printf((yzfy[y][x+1]>>1)&1?" ":"╱");
????????????}
????????}
????????else
????????{
????????????for (x=2; x<rw-2; x+=2)
????????????{
????????????????if (x>2)printf((yzfy[y+1][x-1]>>2)&1?" ":"＿");
????????????????printf(yzfy[y][x]&2?" ":"╱");
????????????????printf(" ");
????????????????printf((yzfy[y][x]>>3)&1?" ":"╲");
????????????}
????????}
????????puts("");
????}
????return 0;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |