简单的使用回溯法生成 Tile Based 迷宫

作者:eastecho
2016-04-18
31 84 6

最近有一些会员反映他们很喜欢那一篇介绍地牢生成的文章《房间和迷宫:一个地牢生成算法》,但是在一些细节的开发方面,这篇文章并没有说得太详细。比如迷宫算法,那么今天就给大家介绍一种相对简单的迷宫生成算法。

回溯法生成迷宫

关于回溯法(Back Tracking)的介绍可以看一下简要的介绍

其实这是一种很简单的生成迷宫的算法,大概分为以下几个步骤:

  1. 选择地图的某一点,标记为已访问过,并将这个点加入到(push)回溯点列表堆栈中;
  2. 查看这个点四周有哪里可以前进(也就是没有标记为访问过的点);
  3. 前进到目标点,将这个点也标记为已访问过,并加入到回溯点列表堆栈中;
  4. 重复第 2 步,直到找不到合适的点(周围的点都被访问过了,说明到了死胡同);
  5. 从回溯点堆栈中移除最后一个(pop),然后继续重复第 2 步(相当于往回走一步);
  6. 当回溯点堆栈为空的时候,说明迷宫已经生成完毕了。

伪代码如下:

backtracking = new Array();
start = point(x, y)
// 寻找下一个路径点
function find(point) {
    // 寻找目标点
    next_point = findNext(point);
    if (next_point) {
        // 如果找到路就加入回溯堆栈,并且寻找下一个
        backtracking.push(next_point);
        find(next_point);
    } else {
        // 如果没找到路就移除掉堆栈中的最后一点
        backtracking.pop();
        // 检查是否完成
        if (backtracking.count > 0) {
            // 没有完成,就从堆栈的最后一个位置重新开始
            find(backtracking.last_point)
        } else {
            // 找到就完成
            print('END');
        }
    }
}

经过这样一个递归,我们应该很快就能生成一个完美迷宫,从迷宫中的任何一点都能够到达另外一点。

让它适合 Tile Based 地图

其实迷宫算法并不难,但是我们不少会员被卡在这里,一个主要原因可能是因为大家使用的是 Tile Based 的地图数据,而目前大部分教程描述的都是可以生成如下这种地图:

normal_maze

标准的迷宫生成

这个地图其实也是 Tile Based,只不过在生成地图数据以后,在每一个 Tile 上加上了“墙”,而我们有些时候需要“墙”本身就是作为一个 Tile 的形态存在。

其实这也很简单,我们根据前面讲述的知识,采用如下的代码来实现它:

function query(start) {
    var x = start.x, y = start.y;
    var dirs = '';
    if ((y - 2 >= 0) && (map.mapData[y - 2][x] == 0))  dirs += 'N';
    if ((x - 2 >= 0) && (map.mapData[y][x - 2] == 0))  dirs += 'W';
    if ((y + 2 < map.rows) && (map.mapData[y + 2][x] == 0))  dirs += 'S';
    if ((x + 2 < map.cols) && (map.mapData[y][x + 2] == 0))  dirs += 'E';

    if (dirs == '') {
        moves.pop();
        if (moves.length == 0)
            draw();
        else
            query(moves[moves.length - 1]);
    } else {
        var dir = dirs.substr(Math.floor(Math.random() * dirs.length), 1);

        switch (dir) {
            case 'N' :
                map.mapData[y - 1][x] = 1;
                y = y - 2;
                break;
            case 'W' :
                map.mapData[y][x - 1] = 1;
                x = x - 2;
                break;
            case 'S' :
                map.mapData[y + 1][x] = 1;
                y = y + 2;
                break;
            case 'E' :
                map.mapData[y][x + 1] = 1;
                x = x + 2;
                break;
        }
        map.mapData[y][x] = 1;
        moves.push({ y:y, x:x });
        query({ y:y, x:x });
    }
}

上面是一段可用的 JavaScript 代码,注意它在寻找下一个目标点的时候是采用了 +2 -2 的形式,也就是说,在选择临近点的时候是跳过一个 Tile 的,而当找到合适的目标点的时候,还要多一个步骤将这两点之间的 Tile 也标记为联通路径,这样,就很简单的实现了将 Tile 作为墙的需求。

大家可以尝试一下:

 

生成过程

这里也特地准备了一个带有动画演示生成过程的示例,可以大概看到生成迷宫的过程。浅灰色的代表回溯的过程。(这篇教程准备相对仓促,所以可能偶尔会出现 BUG,请多担待)

 

讨论和交流

我们已经开通了专门针对 Roguelike 学习的小组,大家有兴趣的不妨来这里访问:

Roguelike 开发小组

indienova 小组 去小组

相关教程的问题也可以在小组中交流。

近期点赞的会员

 分享这篇文章

eastecho 

从前的边城浪子,现在的路人乙 

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

参与此文章的讨论

  1. wszz0218 2016-04-18

    很有用,感谢 indienova 大神的无私奉献!!!

  2. haining334 2016-04-19

    很想知道The Beginer's Guide结局的迷宫是不是也是动态生成的

  3. Terean 2016-05-17

    感谢楼主,我用C#实现了并用到unity中了,等实现《房间和迷宫:一个地牢生成算法》这篇文章中的算法后一并发出来给大家参考~

  4. BjChacha 2016-09-08

    很棒,受教了

  5. ZRXSLYG 2016-10-09

    谢谢楼主,我用C实现了

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

登录/注册