Unity 算法实现简单回溯法 Tile Based 迷宫生成

作者:Relinke
2017-02-13
27 44 8

引言

针对一篇老文章的 Unity 版算法实现。

之前看到了eastecho 的文章《简单的使用回溯法生成 Tile Based 迷宫》,于是自己尝试着做了一下Unity的实现,同时将自己的理解记录下来。

基础算法的简单说明

简单说明一下算法步骤,大家也可以直接去原文章查看:

  1. 先生成基础地图。
  2. 选择基础地图的一个点(一个格子),将它标记为已访问过的,并将这个点加入到堆栈中储存起来。
  3. 取出堆栈顶的这个点作为基准点,检查附近有没有未访问过的点。
  4. 如果附近有未访问过的点,则随机选取其中的一个点,将它标记为已访问过的,并加入到堆栈中储存。
  5. 重复第二步,直到出现一个点,基于这个点在附近找不到未访问过的点了。
  6. 将这个堆栈顶部的点移除,基于新的顶部的点重复第二步。 当堆栈为空时,说明迷宫已经生成完毕。

经过以上步骤,我们就可以得到一个完美迷宫,从迷宫中的任何一点都可以到达迷宫中的另外一点。

这个算法就像是忒修斯走米诺斯迷宫,进入迷宫时将毛线头系在迷宫入口,然后随意走向能走的地方,直到走到了死胡同,就顺着毛线返回到上一个还能走的地方。

而我们的算法则像是在空地顺着路线摆砖块,直到摆不了砖块了便返回上一个可以摆砖块的地方继续摆砖块。

适合 Tile Based 地图的改进算法

我们先假设我们希望生成的迷宫中有两种大小相同的部件,地面

墙是不能移动到的部分,地面是玩家可以移动的部分。 假如未被访问的点是墙,已被访问的点是地面,我们的算法也可以看作是一个人在布满墙的空间里挖路。

这个时候我们发现,如果使用上一个算法,找到身边可以挖开的墙壁然后挖开,最后所有的墙壁都会被我们凿开。 所以我们需要为我们的墙壁预留空间。 我们稍加改良。

简单说明一下改良后的算法步骤:

  1. 先生成基础地图。
  2. 选择基础地图的一个点(一个格子),将它标记为已访问过的,并将这个点加入到堆栈中储存起来。
  3. 取出堆栈顶的这个点作为基准点,检查有没有与这个点相隔一个格子距离,同时又未访问过的点。 如果有这样的点,则随机选取其中的一个点,将它标记为已访问过的,并加入到堆栈中储存。
  4. 将这两个点之间的也标记为已访问过的点,但不将这个点放入堆栈。所以需注意,这个时候堆栈顶部的点是刚才检查到的,距离一个格子的点,而不是附近的这个点。将中间这个点设置为已访问的作用是连通当前点和下一个目标点。
  5. 重复第二步,直到出现一个点,基于这个点在附近距离一个格子的范围找不到未访问过的点了。
  6. 将这个堆栈顶部的点移除,基于新的顶部的点重复第二步。
  7. 当堆栈为空时,说明迷宫已经生成完毕。

不同的地方在于查找下一个目标点的时候,跳过了一个格子。

最后只要将已访问过的点设置为路面,将未访问过的点设置为墙面就可以完成迷宫的生成了。

代码实现

首先我们先说明一下变量。

 c#

    //需要生成地图的行数
    public int row = 35;

    //需要生成地图的列数
    public int column = 30;

    //生成地图的基准点
    public Vector2 originPoint;

    //格子之间的偏移
    public float offset;

    //地面格子预设
    public GameObject floorPrefab;

    //墙壁格子预设
    public GameObject wallPrefab;

    //迷宫的逻辑地图
    private int[,] _maze;

    //根据逻辑地图生成的实际地图
    private GameObject[,] _map;

    //储存目标点的容器
    private List<Vector2> _moves = new List<Vector2>();

首先我们初始化逻辑地图和实际地图两个地图,然后以(0,0)为起始点开始找寻下一个目标点。即,我们从(0,0)开始挖墙。

c#

 void Start()
    {
        //初始化地形
        InitTerrain();
    }

void InitTerrain()
    {
        //初始化逻辑地图
        _maze = new int[row, column];

        //初始化实际地图
        _map = new GameObject[row, column];

        //以(0,0)为基准点开始查找目标点生成迷宫
        QueryRoad(0, 0);
    }

接下来我们来看看关键的挖墙部分

c#

void QueryRoad(int r, int c)
    {
        string dirs = "";

        //检查北面的格子是否被访问
        if ((r - 2 >= 0) && (_maze[r - 2, c] == 0)) dirs += "N";

        //检查西面的格子是否被访问
        if ((c - 2 >= 0) && (_maze[r, c - 2] == 0)) dirs += "W";

        //检查南面的格子是否被访问
        if ((r + 2 < row) && (_maze[r + 2, c] == 0)) dirs += "S";

        //检查东面的格子是否被访问
        if ((c + 2 < column) && (_maze[r, c + 2] == 0)) dirs += "E";

        //如果方位为空,则说明没有未访问的格子了
        if (dirs == "")
        {
            //删除顶上的这个格子
            _moves.RemoveAt(_moves.Count - 1);

            if (_moves.Count == 0)
            {
                //如果容器空了,说明迷宫生成完毕,可以开始绘制迷宫了
                DrawTerrain();
            }
            else
            {
                //否则基于新的点,继续查找下一个目标点
                QueryRoad((int)_moves[_moves.Count - 1].x, (int)_moves[_moves.Count - 1].y);
            }
        }
        else
        {
            //随机一个可以被访问的点
            int ran = Random.Range(0, dirs.Length);
            char dir = dirs[ran];

            //连通目标点和当前点之间的这个点
            switch (dir)
            {
                case 'E':
                    //将中间这个点设置为已访问的
                    _maze[r, c + 1] = 1;
                    c = c + 2;
                    break;

                case 'S':
                    //将中间这个点设置为已访问的
                    _maze[r + 1, c] = 1;
                    r = r + 2;
                    break;

                case 'W':
                    //将中间这个点设置为已访问的
                    _maze[r, c - 1] = 1;
                    c = c - 2;
                    break;

                case 'N':
                    //将中间这个点设置为已访问的
                    _maze[r - 1, c] = 1;
                    r = r - 2;
                    break;
            }

            //将这个新的目标点设置为已访问的
            _maze[r, c] = 1;

            //将这个新的目标点加入容器
            _moves.Add(new Vector2(r, c));

            //基于新的点,继续查找下一个目标点
            QueryRoad(r, c);
        }
    }

算法原理和之前叙述的是一样的。 最后只需要将实际地图根据逻辑地图绘制出来就好了。

c#

void DrawTerrain()
    {
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < column; j++)
            {
                switch (_maze[i, j])
                {
                    case 1:
                        if (_map[i, j] != null)
                        {
                            if (_map[i, j].tag == "Floor")
                            {
                                continue;
                            }
                            else if (_map[i, j].tag == "Wall")
                            {
                                Destroy(_map[i, j]);
                                _map[i, j] = null;
                            }
                        }
                        _map[i, j] = Instantiate(floorPrefab, originPoint + new Vector2(j * offset, i * offset), Quaternion.identity);
                        break;

                    case 0:
                        if (_map[i, j] != null)
                        {
                            if (_map[i, j].tag == "Wall")
                            {
                                continue;
                            }
                            else if (_map[i, j].tag == "Floor")
                            {
                                Destroy(_map[i, j]);
                                _map[i, j] = null;
                            }
                        }
                        _map[i, j] = Instantiate(wallPrefab, originPoint + new Vector2(j * offset, i * offset), Quaternion.identity);
                        break;
                }
            }
        }

    }

如何让绘制迷宫的过程可见

迷宫一下就出现难免有些无趣,毕竟看着空无一物的地图逐渐被道路充满也是一种乐趣。我真心觉得看着迷宫渐渐生成非常令人愉悦。所以提供一种让迷宫的生成可见的方法。

c#

//用来储存目标点

    private Vector2 _currentPoint;

这是关键变量,将之前的递归改为一帧一次,相当于每一帧挖一块墙,获取到了新的目标点之后不会立刻找下一个,而是等到下一帧再执行。 记得增加执行条件,以免无限执行查找。 我这里设置成如果这个点是(-1,-1)则不执行查找。当我在绘制完成实际地图后会将这个点设置成(-1,-1)。

c#

void QueryRoad(int x, int y)
    {

        string dirs = "";

        if ((x - 2 >= 0) && (_maze[x - 2, y] == 0)) dirs += "N";
        if ((y - 2 >= 0) && (_maze[x, y - 2] == 0)) dirs += "W";
        if ((x + 2 < row) && (_maze[x + 2, y] == 0)) dirs += "S";
        if ((y + 2 < column) && (_maze[x, y + 2] == 0)) dirs += "E";

        if (dirs == "")
        {
            _moves.RemoveAt(_moves.Count - 1);

            if (_moves.Count == 0)
            {
                DrawTerrain();
                _currentPoint = new Vector2(-1, -1);
            }
            else
            {
                //QueryRoad((int) _moves[_moves.Count - 1].x, (int) _moves[_moves.Count - 1].y);
                _currentPoint = _moves[_moves.Count - 1];
            }
        }
        else
        {

            int ran = Random.Range(0, dirs.Length);
            char dir = dirs[ran];

            switch (dir)
            {
                case 'E':
                    _maze[x, y + 1] = 1;
                    y = y + 2;
                    break;

                case 'S':
                    _maze[x + 1, y] = 1;
                    x = x + 2;
                    break;

                case 'W':
                    _maze[x, y - 1] = 1;
                    y = y - 2;
                    break;

                case 'N':
                    _maze[x - 1, y] = 1;
                    x = x - 2;
                    break;
            }
            _maze[x, y] = 1;
            _moves.Add(new Vector2(x, y));
            //QueryRoad(x, y);
            _currentPoint = new Vector2(x, y);
            DrawTerrain();
        }
    }

void DrawTerrain()
    {
        for (int i = 0; i < row; i++)
        {

            for (int j = 0; j < column; j++)
            {
                switch (_maze[i, j])
                {
                    case 1:
                        if (_map[i, j] != null)
                        {
                            if (_map[i, j].tag == "Floor")
                            {
                                continue;
                            }
                            else if (_map[i, j].tag == "Wall")
                            {
                                Destroy(_map[i, j]);
                                _map[i, j] = null;
                            }
                        }
                        _map[i, j] = Instantiate(floorPrefab, originPoint + new Vector2(j * offset, i * offset), Quaternion.identity);
                        break;

                    case 0:
                        if (_map[i, j] != null)
                        {
                            if (_map[i, j].tag == "Wall")
                            {
                                continue;
                            }
                            else if (_map[i, j].tag == "Floor")
                            {
                                Destroy(_map[i, j]);
                                _map[i, j] = null;
                            }
                        }
                        _map[i, j] = Instantiate(wallPrefab, originPoint + new Vector2(j * offset, i * offset), Quaternion.identity);
                        break;
                }
            }
        }
    }

最后

大家可以自己尝试一下这种生成迷宫的方法。 如果大家有什么问题或者指教,也欢迎来与我交流。

近期点赞的会员

 分享这篇文章

Relinke 

Gamer and Game Programer 

您可能还会对这些文章感兴趣

参与此文章的讨论

  1. leesoar07 2017-02-13

    学习了

  2. rickrui 2017-02-13

    厉害啊

  3. helixngc7293 2017-02-14

    关于迷宫生成有个小技巧,在生成以后随机挖掉一些墙,反而会让迷宫变得更难~

    以前做过一个基于Socket.io的多人迷宫,现在应该还能运行
    https://immense-eyrie-3245.herokuapp.com/

  4. apophenia 2017-02-14

    和这篇一模一样:http://www.jianshu.com/p/26798290ed43

    • Relinke 2017-02-15

      @apophenia:非常抱歉,那篇也是我写的,不过我比较喜欢简书的Mark Down写作环境所以先在简书写的。

  5. ToBeGamePartner 2017-02-14

    代码有误,private List _moves = new List();改成原作者的private List _moves = new List();

    • Relinke 2017-02-15

      @ToBeGamePartner:我会再仔细检查一下的。

  6. wtksana 2017-02-16

    请问能发一个demo学习一下吗

您需要登录或者注册后才能发表评论

登录/注册