不太规则的迷宫生成算法2

先直接给一个直观的例子:

 _   _   _   _   _   _   _   _
  ╲_╱ ╲_╱ ╲_╱ ╲_╱ ╲_╱ ╲_╱ ╲_╱ ╲
╲_  ╲_  ╲    _   _╱  _╱  _╱   ╱
╱   ╱   ╱ ╲_╱ ╲_  ╲   ╲_   _╱ ╲
╲ ╱  _╱ ╲_  ╲ ╱ ╲_  ╲_  ╲_╱  _╱
╱ ╲_╱  _╱ ╲ ╱  _  ╲_╱  _  ╲_  ╲
╲ ╱  _╱   ╱ ╲_╱ ╲   ╲_  ╲_╱  _╱
╱ ╲_╱  _╱ ╲_    ╱ ╲_╱ ╲ ╱ ╲_  ╲
╲_  ╲ ╱  _╱ ╲_╱ ╲ ╱   ╱ ╲   ╲ ╱
╱   ╱ ╲_    ╱  _╱ ╲ ╱   ╱ ╲_  ╲
╲ ╱ ╲_  ╲_╱ ╲_  ╲ ╱ ╲_╱ ╲_  ╲_╱
╱ ╲_╱  _╱ ╲ ╱  _╱ ╲ ╱ ╲_╱  _╱ ╲
╲ ╱ ╲_   _╱ ╲_    ╱   ╱ ╲_  ╲ ╱
╱  _   _╱  _  ╲_╱ ╲_╱   ╱  _╱ ╲
╲ ╱ ╲_╱  _╱ ╲_╱ ╲_  ╲_╱ ╲_  ╲ ╱
╱ ╲ ╱  _╱   ╱   ╱  _╱ ╲_  ╲ ╱ ╲
╲ ╱ ╲_  ╲ ╱ ╲ ╱  _╱  _╱  _╱   ╱
╱ ╲_  ╲ ╱ ╲_  ╲_╱   ╱  _╱ ╲_╱ ╲
╲ ╱   ╱  _╱ ╲_╱ ╲_╱ ╲ ╱ ╲    _╱
╱  _╱ ╲_   _   _   _╱  _  ╲_  ╲
╲_╱ ╲_╱ ╲_╱ ╲_╱ ╲_╱ ╲_╱ ╲_╱ ╲_

以上的蜂窝形迷宫,看起来已经跳出了一般的矩形模式的框架,
但实际上,我们仍然可以进行转换,使得几乎可以继续套用矩形生成的办法
首先数据结构仍然用的二维数组,但是,表示方式需要变化:
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, 1},{2, 0},{1, -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, 0, 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;
}

出处:www.l1mn.com

原文标题:不太规则的迷宫生成算法2

原文地址:https://www.l1mn.com/p/jbnk44.html

本文版权归作者所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接。

评论

皖ICP备2023023451号

Copyright © L1MN.COM 联系方式:l1mnfw@163.com