规则满迷宫地图生成算法1

所谓规则,就是矩形,路线唯一,所谓满,就是不能在原地图里再增加路或者分支,不会出现达不到的地方,如下例图:
█████████████████
    █ █         █
█ ███ ███ █████ █
█   █     █   █ █
█ █ ███████ █ █ █
█ █       █ █   █
█ ███████ █ █████
█ █       █ █   █
█ █ ███████ ███ █
█ █       █     █
█ ███████ █████ █
█   █ █       █ █
███ █ █ ███████ █
█ █   █   █     █
█ ███ ███ █ █████
█       █
█████████████████

简单的来说,就是平面图的任意生成树问题,先讲个简单点的生成算法:随机DFS

用这个算法,生成的迷宫的特点是,分支不多,但往往很深,难度较大。

生成的代码:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAZE_MAX    50
char map[MAZE_MAX+2][MAZE_MAX+2];
int search(int x,int y)
{
    static int d[4][2]={0,1,1,0,0,-1,-1,0};
    int zx=x*2,zy=y*2,next,turn,i;
    map[zx][zy]=1; turn=rand()%2? 1:3;
    for(i=0,next=rand()%4;i<4;i++,next=(next+turn)%4)
        if(map[zx+2*d[next][0]][zy+2*d[next][1]]==0)
            map[zx+d[next][0]][zy+d[next][1]]=1,
            search(x+d[next][0],y+d[next][1]);
    return 0;
}
void Make_Maze(int x,int y)
{
    int z1,z2;
    for(z1=0,z2=2*y+2;z1<=2*x+2;z1++)map[z1][0]=1,map[z1][z2]=1;
    for(z1=0,z2=2*x+2;z1<=2*y+2;z1++)map[0][z1]=1,map[z2][z1]=1;
    map[1][2]=1;map[2*x+1][2*y]=1;  srand((unsigned)time(NULL));
    search(rand()%x+1,rand()%y+1);
}
int main(void)
{
    int x=8,y=8,z1,z2; //x和y的值指定了这个要生成的迷宫的大小
    Make_Maze(x,y);
    for(z2=1;z2<=y*2+1;z2++){
        for(z1=1;z1<=x*2+1;z1++) fputs(map[z1][z2]?" ":"█",stdout);
        if(z2<=y*2)putchar(10);
    }
    return 0;
}

复杂度O(xy),唯一缺点是这个代码用递归,在迷宫较大时,可能出现栈溢出,

要是需要生成大迷宫,就自己模拟栈即可。

代码变形:

为了使生成出来的地图更好看,像以下这种:

━━━━┳━━━┳━━━━━━━━━━━┓
    ┃   ┃           ┃
┃ ┃ ┃ ┃ ┃ ━━┓ ┏━━━━ ┃
┃ ┃ ┃ ┃     ┃ ┃     ┃
┃ ┃ ┃ ┗━━━┳━┛ ┃ ┏━━━┫
┃ ┃ ┃     ┃   ┃ ┃   ┃
┃ ┗━┻━┳━━ ┃ ┏━┫ ┗━┓ ┃
┃     ┃   ┃ ┃ ┃   ┃ ┃
┃ ━━┓ ┃ ┏━┛ ┃ ┗━┓ ┃ ┃
┃   ┃ ┃ ┃   ┃   ┃ ┃ ┃
┣━━ ┃ ┃ ┃ ━━┫ ┃ ┃ ┃ ┃
┃   ┃   ┃   ┃ ┃ ┃   ┃
┃ ━━┻━┳━┫ ┃ ┣━┛ ┣━━ ┃
┃     ┃ ┃ ┃ ┃   ┃   ┃
┣━━━━ ┃ ┗━┛ ┃ ━━┛ ━━┛
┃     ┃     ┃
┗━━━━━┻━━━━━┻━━━━━━━━

要做到这种效果,其实我们只要在原来代码的输出的地方做一点手脚:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
char cw[][4]={" ","┃","━","┗","┃","┃","┏","┣",
              "━","┛","━","┻","┓","┫","┳","╋"
             };
char m[50][50];

char* getw(int x, int y)
{
    return cw[(m[x][y-1]?0:1)|(m[x+1][y]?0:2)|(m[x][y+1]?0:4)|(m[x-1][y]?0:8)];
}
int sr(int x,int y)
{
    static int d[4][2]={0,1,1,0,0,-1,-1,0};
    int zx=x*2,zy=y*2,nx,tn=rand()%2? 1:3,i;
    m[zx][zy]=1;
    for (i=0,nx=rand()%4;i<4;i++,nx=(nx+tn)%4)
        if (m[zx+2*d[nx][0]][zy+2*d[nx][1]]==0)
            m[zx+d[nx][0]][zy+d[nx][1]]=1,sr(x+d[nx][0],y+d[nx][1]);
    return 0;
}
void Make_Maze(int x,int y)
{
    int z1,z2;
    for (z1=0,z2=2*y+2;z1<=2*x+2;z1++)m[z1][0]=1,m[z1][z2]=1;
    for (z1=0,z2=2*x+2;z1<=2*y+2;z1++)m[0][z1]=1,m[z2][z1]=1;
    m[1][2]=1;m[2*x+1][2*y]=1;
    srand((unsigned)time(NULL));
    sr(rand()%x+1,rand()%y+1);
}
int main(void)
{
    int x=10,y=8,z1,z2;Make_Maze(x,y);
    for (z2=1;z2<=y*2+1;z2++)
    {
        for (z1=1;z1<=x*2+1;z1++)printf(m[z1][z2]?" ":getw(z1,z2));
        if (z2<=y*2)putchar(10);
    }
    return 0;
}

出处:www.l1mn.com

原文标题:规则满迷宫地图生成算法1

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

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

评论

皖ICP备2023023451号

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