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

回溯法生成迷宫

关于回溯法（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 的地图数据，而目前大部分教程描述的都是可以生成如下这种地图：

这个地图其实也是 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 学习的小组，大家有兴趣的不妨来这里访问：

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