首页 复盘生成随机迷宫算法
文章
取消

复盘生成随机迷宫算法

发表于 2022/05/29 更新于 2022/10/07
作者 ,
9 分钟阅读

一、回溯生成普通迷宫

原理

XIduwt.jpg

  1. 首先要像上图一样，将地面和墙块分隔开来，绿色的是地面，灰色的是墙体

  2. 然后选择靠近边缘的地面（上下左右的边）作为起点，在这个地面砖块周围即上下左右四个方向随机寻找一个地面砖块，找到就将他们联通，把两个地砖之间的墙变为绿色的地砖

  3. 然后以第二步找到的格子作为新的起点，开始递归，重复第二步，直到某个格子的周围无法找到地面砖块

  4. 这时候就回溯，看之前的格子的周围还有没有地砖

  5. 直到最后就可以填充完毕 XIdKTP.jpg

代码实现

  1. 创建一个脚本MACRO_randomMaze，用于存放宏定义的变量

    1
2
3
4
5
6
7
8
9
10
11
12
13
14

    //***随机生成地图
   
//路面、墙体
#macro FLOOR -5
#macro WALL -6
//栅格大小
#macro CELL_WIDTH 16
#macro CELL_HEIGHT 16
//标记地图宽高
#macro MAP_STAMP_WIDTH 31
#macro MAP_STAMP_HEIGHT 23
//显示地图宽高
#macro MAP_SHOW_WIDTH MAP_STAMP_WIDTH*2+1
#macro MAP_SHOW_HEIGHT MAP_STAMP_HEIGHT*2+1

  2. 新建一个object，作为随机生成迷宫的物体obj_maze，在create事件中添加以下代码

        其中标记栅格指的就是地面部分的grid，显示栅格指的是既包括地面还有墙体的grid，所以显示栅格是要比标记栅格大一倍的。

    1
2
3
4
5
6
7
8
9
10
11
12
13
14

    ///@description 初始化地图
// You can write your code in this editor
   
//标记地图栅格建立和显示地图栅格建立
map_stamp_grid_=ds_grid_create(MAP_STAMP_WIDTH,MAP_STAMP_HEIGHT);
map_show_grid_=ds_grid_create(MAP_SHOW_WIDTH,MAP_SHOW_HEIGHT);
map_stamp_number=0;//已标记的栅格数量
//获取图块集
tilemap_wall=layer_tilemap_get_id("WALL");
tilemap_x(tilemap_wall,8);
tilemap_y(tilemap_wall,8);
tilemap_floor=layer_tilemap_get_id("FLOOR");
tilemap_x(tilemap_floor,8);
tilemap_y(tilemap_floor,8);

  3. 创建一个步事件，并在步事件中添加以下代码（填在步事件，是为了能够通过按键重新随机生成，可以看到效果）

    其中注释掉的是接下来用作块状分割型迷宫和填充。

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

    if(keyboard_check_pressed(vk_enter))
{
    #region 地图初始化
        map_stamp_number=0;
        //将显示地图全部栅格初始化为墙体
        ds_grid_clear(map_show_grid_,WALL);
        //将标记地图初始化为未标记
        ds_grid_clear(map_stamp_grid_,0);
        //清除上一次绘制的图块集
        tilemap_clear(tilemap_floor, 0);
        tilemap_clear(tilemap_wall, 0);
        //清除路径中和运动规划网格中的点
        path_clear_points(path_id);
        mp_grid_clear_all(path_map_path_id);
        //将显示地图奇数位栅格全部设置为地面
        for(var i=1;i<MAP_SHOW_WIDTH;i++)
        {
            for(var j=1;j<MAP_SHOW_HEIGHT;j++)
            {
                if((i mod 2)&&(j mod 2)) map_show_grid_[# i,j]=FLOOR;
            }
        }
    #endregion
   
    #region 设置出入口
        randomize();
        var _random_dir=random(1);//随机选择出入口为上下两侧还是左右两侧
        var _random_inout=random(1);//随机选择出入口分别位于哪一侧
        if(_random_dir)//上下两侧
        {
            var _inx_no=irandom_range(1,MAP_STAMP_WIDTH);//相当于是第几个可选择的入口
            var _inx=_inx_no*2-1;
            var _outx_no=irandom_range(1,MAP_STAMP_WIDTH);//相当于是第几个可选择的出口
            var _outx=_outx_no*2-1;
            if(_random_inout)//入口在上侧，出口在下侧
            {
                var _iny=0;
                var _outy=MAP_SHOW_HEIGHT-1;
            }else//入口在下侧
            {
                var _iny=MAP_SHOW_HEIGHT-1;
                var _outy=0;
            }
        }else//左右两侧
        {
            var _iny_no=irandom_range(1,MAP_STAMP_HEIGHT);
            var _iny=_iny_no*2-1;
            var _outy_no=irandom_range(1,MAP_STAMP_HEIGHT);
            var _outy=_outy_no*2-1;
            if(_random_inout)//入口在左侧，出口在右侧
            {
                var _inx=0;
                var _outx=MAP_SHOW_WIDTH-1;                
            }else//入口在右侧，出口在左侧
            {
                var _inx=MAP_SHOW_WIDTH-1;
                var _outx=0;
            }
        }
        map_show_grid_[# _inx,_iny]=FLOOR;
        map_show_grid_[# _outx,_outy]=FLOOR;
    #endregion
   
    #region 地图计算
   
        //生成房间
        //scr_create_room();
        //scr_room_door();//为房间生成门
        //scr_create_maze(0,0);
        //遍历未标记的
        var _ix=0;
        var _jy=0;
        var _end=0;
        do
        {
            for(var _i=0;_i<MAP_STAMP_WIDTH;_i++)
            {
                for(var _j=0;_j<MAP_STAMP_HEIGHT;_j++)
                {
                    if(!map_stamp_grid_[# _i,_j])//如果该标记网格没有被标记
                    {
                        _ix=_i;
                        _jy=_j;
                        _end=1;
                        break;
                    }
                }
                if(_end)break;
            }
            scr_create_maze(_ix,_jy);
            _end=0;
        }until(map_stamp_number==MAP_STAMP_HEIGHT*MAP_STAMP_WIDTH);
   
        with(obj_mask)instance_destroy();
        //scr_fill_path();
   
    #endregion
   
    #region 绘制地图
        for(var i=0;i<MAP_SHOW_WIDTH;i++)
        {
            for(var j=0;j<MAP_SHOW_HEIGHT;j++)
            {
                if(map_show_grid_[# i,j]==WALL)
                {
                    tilemap_set(tilemap_wall,1,i,j);
                    mp_grid_add_cell(path_map_path_id,i,j);//添加路径中不碰撞的栅格
   
                }
                else if(map_show_grid_[# i,j]==FLOOR)
                {
                    tilemap_set(tilemap_floor,1,i,j);
                }
            }
        }
    #endregion
   
}

  4. 在上述代码中，使用了脚本scr_create_maze，这个脚本需要我们自己创建

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

    function scr_create_maze(_x,_y){
    //_x标记地图的横坐标
    //_y标记地图的纵坐标
    //随机选择方向
    randomize();
    var _dir=choose(0,90,180,270);
    var _dx=lengthdir_x(1,_dir);
    var _dy=lengthdir_y(1,_dir);
   
    if(!scr_can_through(_x+_dx,_y+_dy))exit;//如果不能通过则退出
    else
    {
        map_show_grid_[# _x*2+1+_dx,_y*2+1+_dy]=FLOOR;//连通所要选择的下一个网格
        //更新当前标记地图网格坐标
        _x+=_dx;
        _y+=_dy;
        //将更新后的网格标记为1
        map_stamp_grid_[# _x,_y]=1;
        //标记过的网格数量+1
        map_stamp_number++;
   
    }
   
    //递归，回溯
    while(map_stamp_number<MAP_STAMP_HEIGHT*MAP_STAMP_WIDTH)
    {
        if(scr_can_choose(_x,_y))//如果当前坐标不是死路一条
        {
            scr_create_maze(_x,_y);
        }
        else
        {
            break;    
        }
    }
   
}

  5. 在上述脚本中，还使用了scr_can_through、scr_can_choose方法，当然这些也需要我们创建脚本实现

1
2
3
4
5
6
7
8
9
10
11
12

function scr_can_through(_x,_y){

    if(_x>=0&&_x<MAP_STAMP_WIDTH&&_y>=0&&_y<MAP_STAMP_HEIGHT)
    {
        if(map_stamp_grid_[# _x,_y]==0)//未被标记
        {
            return 1;//返回可通过
        }
    }
    return 0;//返回不可通过

}

1
2
3
4
5
6
7

function scr_can_choose(_x,_y){
    if(scr_can_through(_x+1,_y)||scr_can_through(_x,_y+1)||scr_can_through(_x-1,_y)||scr_can_through(_x,_y-1))
    {
        return 1;//返回下一步可选择
    }
    return 0;//返回下一步不能选择，即是死路
}

二、块状分割型迷宫

原理

  1. 在上述迷宫的基础上进行改动，在生成迷宫之前，要为地图创建房间

    XIdeOA.jpg

  2. 然后跟之前的方法一样，使用回溯生成迷宫

    XIdneI.jpg

  3. 在房间周围，随机取点作为门来连接迷宫的路

    XIdQFf.jpg

  4. 接下来优化地图，填充死路，把一些三条边都是墙块的地面设置为墙块即可

    XId1fS.jpg

    

代码实现

  1. 创建两个脚本scr_create_room()、scr_room_door()

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

    function scr_create_room(){
   
    with(obj_mask)instance_destroy();
    //设置临时变量
    var _i,_j,_w,_h;//位置以及宽高
   
    randomize();
    repeat(30)
    {
    _w=irandom_range(6,10);
    _h=irandom_range(6,10);
    _i=irandom(MAP_STAMP_WIDTH-1-_w);
    _j=irandom(MAP_STAMP_HEIGHT-1-_h);
   
    tmp=instance_create_depth((_i*2+1)*16+8,(_j*2+1)*16+8,0,obj_mask);
    tmp.image_xscale=_w*2-1;
    tmp.image_yscale=_h*2-1;
    tmp.i=_i;
    tmp.j=_j;
    tmp.w=_w;
    tmp.h=_h;
   
    with(tmp)
    {
        if(place_meeting(x,y,obj_mask))instance_destroy();
        else
        {
            ds_grid_set_region(other.map_stamp_grid_,_i,_j,_i+_w-1,_j+_h-1,1);//将房间里的网格标记为1
            other.map_stamp_number+=_w*_h;
            ds_grid_set_region(other.map_show_grid_,_i*2+1,_j*2+1,(_i+_w-1)*2+1,(_j+_h-1)*2+1,FLOOR);//将显示地图中房间设置为地板
   
        }
    }
    }
   
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

    ```
function scr_room_door(){

    with(obj_mask)
    {
        randomize();
        var _door_max=2;
        var _num=0;
        do
        {
            if(irandom(1))
            {
                var _i=irandom_range(i,i+w-1)*2+1;//随机一个门在显示地图的横坐标
                var _j=choose(j*2,(j+h-1)*2+1+1);//随机一个门在显示地图的纵坐标
            }else
            {
                var _i=choose((i+w-1)*2+1+1,i*2);
                var _j=irandom_range(j,j+h-1)*2+1;
            }

        if(_i==0||_j==0||_i==MAP_SHOW_WIDTH-1||_j==MAP_SHOW_HEIGHT-1)continue;
        else{
        _num++;
        other.map_show_grid_[# _i,_j]=FLOOR;
        instance_create_depth(_i*16+8,_j*16+8,-10,obj_mask);
        }
        }until(_num==_door_max);
    }


}

  1. 创建两个脚本scr_fill_path()、scr_fill_dead_way()

    1
2
3
4
5
6
7
8
9
10
11
12
13

    function scr_fill_path(){
    var i,j;
   
    for(i=1;i<MAP_SHOW_WIDTH-1;i++)
    {
        for(j=1;j<MAP_SHOW_HEIGHT-1;j++)
        {
            scr_fill_dead_way(i,j);
        }
   
    }
   
}

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

       function scr_fill_dead_way(i,j){
    var _pos;
    _pos[0]=map_show_grid_[# i+1,j];    
    _pos[1]=map_show_grid_[# i-1,j];    
    _pos[2]=map_show_grid_[# i,j+1];    
    _pos[3]=map_show_grid_[# i,j-1];
    //如果一块地板周围有三块墙
    if(((_pos[0]+_pos[1]+_pos[2]+_pos[3])==-23)&&map_show_grid_[# i,j]==-5)
    {
        map_show_grid_[# i,j]=WALL;    
        for(var k=0;k<4;k++)
        {
            var _dir=k*90;
            var iout=i+lengthdir_x(1,_dir);
            var jout=j+lengthdir_y(1,_dir);
            if(iout>0&&iout<MAP_SHOW_WIDTH-1&&jout>0&&jout<MAP_SHOW_HEIGHT-1)
            scr_fill_dead_way(iout,jout);
        }
    }
   
}

三、应用到我的项目

XIdlY8.jpg

GameMaker Studio2
随机迷宫 回溯 块状分割型随机迷宫
本文由作者按照 CC BY 4.0 进行授权
最近更新
文章内容