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

现在介绍第二种算法,使用并查集 合并生成。

简单介绍一下算法思想:首先把地图关键点的连结(墙),编号1-x*y*2,然后random shuffle

然后按照打乱后的次序,打通一些墙,用并查集检查是否要打通的两边是已经连通的就行了,

生成的例子如下:

█████████████████████
          █   █     █
█████████ █ █ █ █████
█   █     █ █   █ █ █
█ █ █ ███ █████ █ █ █
█ █ █ █   █ █   █   █
█ █ ███ ███ ███ ███ █
█ █   █             █
█████ ███ █ █ ███ ███
█         █ █   █ █ █
█████ ███ ███████ █ █
█       █   █       █
█ ███ █ ███ █ █ █████
█   █ █ █   █ █     █
███ ███████ █ █ ███ █
█   █       █ █   █
█████████████████████

这种算法生成的特点是,分支数非常的多,较多短小分支,难度往往较DFS生成的简单

但效率非常高,生成1000*1000的迷宫,只要1秒(DFS生成的常数上要大一些)

但需要一个辅助的并查集数据结构,空间消耗大。

代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SWAP(a,b,c) {c t=a;a=b;b=t;}
int uf[9000000], Map[3000][3000]; //并查集表,迷宫地图
struct PT{int x; int y;}que[5000000]; //生成序列
int x=10,y=8,xy=0; //x,y指定要生成的大小
int findP(int& n)
{
    int a=++n;
    while (uf[a]) a=uf[a];
    if (a!=n) uf[n] = a;
    return n=a;
}
int Ins(PT xy)
{
    int a=(xy.y-1)/2*x+(xy.x-1)/2, b=(xy.y&1)?a+1:a+x;
    if (findP(a)!=findP(b)) {uf[b] = a; return 1;}
    return 0;
}
int main()
{
    int n=0,_y,_x,o;
    srand(time(NULL)); Map[1][0]=Map[y*2-1][x*2]=1;
    for (_y=1; o=_y!=y,_y<=y; ++_y)
        for (_x=1; _x<=x; ++_x)
        {
            if (_x<x)que[n].y = _y*2-1, que[n].x = _x*2,++n;
            if (o)que[n].y = _y*2, que[n].x = _x*2-1,++n;
        }
    for (xy=n,n=0; n<xy; ++n) {int z=rand()%xy; SWAP(que[n],que[z],PT);}
    for (n=0; n<xy; ++n)
    {
        if (!Ins(que[n])) continue;
        Map[que[n].y][que[n].x] = 1;
        if (que[n].y&1) Map[que[n].y][que[n].x-1] = Map[que[n].y][que[n].x+1] = 1;
        else Map[que[n].y-1][que[n].x] = Map[que[n].y+1][que[n].x] = 1;
    }
    for (_y=0; _y<=y*2; ++_y)
    {
        for (_x=0; _x<=x*2; ++_x)
                if (Map[_y][_x]) fputs(" ", stdout); else fputs("█", stdout);
        putchar(10);
    }
    return 0;
}

出处:www.l1mn.com

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

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

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

评论

皖ICP备2023023451号

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