GameAlgorithm 0x01 - Maze Creater - 秘境工坊

源起

一直以来我都认为算法是编程中的灵魂，也许有人认为没有算法一样能够写出可以运行的程序。但对于写出好的程序，并认识到为什么好，没有算法的知识就是经验主义的瞎摸索。由于我又是个半路出家的游戏程序，计算机基础实在薄弱，想要在这个方面补充些知识，阅读像《算法》、《算法导论》这样的算法书是一方面，另一方面想要学习一些算法在工程中的实际使用（虽然也没那么工程）。于是，这个游戏算法的系列就是为此而生，记录在算法实践中的思路和资料整合。因为工作原因，主力工具是Unity，所以大部分的代码是在Unity中完成的，会有一些Unity组件的加入。

迷宫生成算法

作为一个Roguelike游戏的爱好者，我对于所有的程序生成（内容）技术都非常感兴趣。在学习游戏程序之前甚至还学了点深度学习（非常皮毛，基本上是当作工具在用，当然现在基本快忘光了…捂脸）。作为Roguelike游戏的基础，地图生成就成为了不二之选。而且Wiki也有详细的介绍。

根据Wikipedia的Maze generation algorithm条目，有如下迷宫生成算法：

基于图论的算法
1. 深度优先搜索 Depth-first Search
2. 递归回溯 Recursive Backtracker
3. 随机Kruskal算法 Randomized Kruskal’s Algorithm
4. 随机Prim算法 Randomized Prim’s Algorithm
递归分割算法 Recursive Division
…

这篇文章中的迷宫是使用的单元是周围有墙的，也就是说和周边单元的连通性存储在单元内（当然这样会有重复的数据）。后面的章节也许会修改成墙作为单独的单元存在（大部分的Roguelike游戏也是这样做的）。

深度优先

从任意一个起点（或者指定单元）开始，随机选择一个邻近的单元，将这个单元设置为已访问，然后把这个单元设置为当前单元。重复上面的步骤，直到当前单元没有未访问的邻近单元。然后重新选择未访问的单元，重复步骤。按照wiki上的深度优先的解释，似乎和递归回溯是一样的。不过看旁边的图的似乎有的路径没有和主路径连通（即不是完美迷宫），所以差别应该在一条路径走到尽头，然后选取第二个点重开路径上。

递归回溯

全称是使用递归回溯的深度优先算法，深度优先的加强版。区别在于每次更新当前单元的时候，会把上一个单元作为节点存储到一个栈中，这样当一个路径到死路时，从栈顶取出单元作为当前单元，如果当前单元没有未访问的邻近单元，再取出下一个栈顶，这称为“递归回溯”。

Wiki的流程说明（翻译请见核心循环段落）：

Make the initial cell the current cell and mark it as visited

While there are unvisited cells

If the current cell has any neighbours which have not been visited

Choose randomly one of the unvisited neighbours

Push the current cell to the stack

Remove the wall between the current cell and the chosen cell

Make the chosen cell the current cell and mark it as visited

Else if stack is not empty

Pop a cell from the stack

Make it the current cell

随机Kruskal算法

随机Kruskal算法看起来像是随机选择某个单元和它随机的邻近的单元连结（去除中间的墙）。

Create a list of all walls, and create a set for each cell, each containing just that one cell.
创建所有墙的列表，并且创建所有单元的集合，每个集合中只包含一个单元。

For each wall, in some random order:
以随机的顺序选取每一个墙：

If the cells divided by this wall belong to distinct sets:
如果被当前的墙分隔的两个单元属于不同的集合：

Remove the current wall.
去除当前的墙。

Join the sets of the formerly divided cells.
把单元加入到之前分隔的单元。

唔…没有仔细研究，不知道怎么确保连通性的。看上去生成的迷宫比较支离破碎，有很多那种在路口就能一眼看穿的死路。

随机Prim算法

Start with a grid full of walls.
创建全是墙的网格。

Pick a cell, mark it as part of the maze. Add the walls of the cell to the wall list.
选取一个单元，标记为迷宫路线。将这个单元的墙加入到墙的列表。

While there are walls in the list:
（循环）当列表中还有墙的时候：

Pick a random wall from the list. If only one of the two cells that the wall divides is visited, then:
从列表中随机选择一个墙，如果墙两边的单元只有一个被访问过，那么：

Make the wall a passage and mark the unvisited cell as part of the maze.
移除墙，变成通道，把未访问的单元标记未迷宫路线。

Add the neighboring walls of the cell to the wall list.
把这个单元的邻墙加入到墙的列表。

Remove the wall from the list.
从列表中把墙移除。

Prim算法生成的迷宫和Kruskal生成的算法有点类似，非常多短小的支线。和深度优先比起来没有明显的主要路线，走起来会更加困难。

递归分隔算法

递归分隔算法把整个迷宫单元分成数个子迷宫，子迷宫之间生成通路。然后继续把小迷宫分隔直到不能分隔为止。递归分隔算法生成的迷宫看上去更适合有明显区域概念的游戏，比如去掉一些小迷宫中的墙可以生成大的房间（关于生成带有小房间的迷宫之后应该会写一篇的吧，不过可能不会用递归分隔来做）。

递归生成迷宫实例

上面都是流程步骤，我比较喜欢递归回溯生成的迷宫，嗯，比较好看。所以我把递归回溯的迷宫的详细代码写在下面。

由于在Unity中工作，我把逻辑和表现分开了，表现层只负责初始化和迷宫展示。首先定义迷宫的单元：

// 迷宫单元，存储迷宫单元的数据
public class Cell
{
    // 四周的连通性： 0 上， 1 下， 2 左， 3 右
    public bool[] links = new bool[4];

    // 到开始点最近路线的上一个点，生成迷宫路线用的
    public Point? LastCell = null;
    
    // 当前点到起点的距离，后面A*算法中会使用
    public int Gweight = int.MaxValue;

    /// <summary>
    /// 设置连通性
    /// </summary>
    public void SetLink(Dir dir)
    {
        links[(int) dir] = true;
    }
}

ps：后来发现方向还是顺时针写比较好，不容易出错，后面在显示层旋转图片的时候吃了点亏，不过算了，有机会再改。

整型坐标

由于Vector2是浮点型的，为了方便计算，写了一个Point类型，相当于一个整型的Vector2.

public enum Dir
{
    Up = 0,
    Down = 1,
    Left = 2,
    Right = 3,
}

// 定义一个整型的Point2
public struct Point
{
    public int x;
    public int y;

    public Point(int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    public void Add(Point point)
    {
        this.x += point.x;
        this.y += point.y;
    }

    public static Point operator +(Point a, Point b)
    {
        return new Point(a.x + b.x , a.y + b.y);
    }

    public static Point operator -(Point a, Point b)
    {
        return new Point(b.x - a.x, b.y - a.y);
    }

    public static bool operator ==(Point a, Point b)
    {
        return a.x == b.x && a.y == b.y;
    }

    public static bool operator !=(Point a, Point b)
    {
        return a.x != b.x || a.y != b.y;
    }

    public static Point Up()
    {
        return new Point(0, 1);
    }

    public static Point Down()
    {
        return new Point(0, -1);
    }

    public static Point Left()
    {
        return new Point(-1, 0);
    }

    public static Point Right()
    {
        return new Point(1, 0);
    }

    public static Point[] DirPoints = new Point[] {Point.Up(), Point.Down(), Point.Left(), Point.Right()};

    public override string ToString()
    {
        return string.Format("({0}, {1})", x, y);
    }
}

迷宫创建器

重头戏当然是迷宫创建器，参考Wiki对递归回溯的说明。

为了方便做展示动画，创建方法写成了协程，每一帧访问一个单元，并在结束的时候执行结束方法（这里其实只是把走迷宫的按钮显示出来）。

public IEnumerator CreatMazeWithAnima(Action<Cell[,]> args = null)
{
    // 初始化
    cells = new Cell[Width, Height];
    MarkedArr = new bool[Width, Height];
    // 初始化初始坐标
    curIndex = StartPoint;
    // 访问过的格子栈
    cellStack = new Stack<Point>();
    // 随机选择下一步的时候用的单元列表
    CellForSelect = new List<Dir>();
    // 初始化单元
    for (int i = 0; i < Width; i++)
    {
        for (int j = 0; j < Height; j++)
        {
            cells[i, j] = new Cell();
        }
    }

    // 主循环，如果还有单元没被标记为访问过，从当前的单元开始检查
    while (!CheckAllMarked())
    {
        CheckCurCell(curIndex);
        yield return null;
    }

    // 执行完成方法
    if (args != null)
        args(cells);
}

核心循环

按照Wiki的流程说明，

如果当前的单元有没有访问过的邻单元

随机选择邻单元

将当前单元加入栈

移除选择的单元和当前单元之间的墙

把选择的单元标记为当前单元并标记为已访问

如果当前单元没有未访问的邻单元

从栈顶去除一个单元

标记为当前单元

循环

为了展示过程，在每次修改的单元的时候使用Action委托，调用了显示层的方法。

public List<Dir> CellForSelect;

public Point[] dirPoints = new Point[4] {new Point(0, 1), new Point(0, -1), new Point(-1, 0), new Point(1, 0)};

public Dir[] dirs = new Dir[4] { Dir.Up, Dir.Down, Dir.Left, Dir.Right };

public Dir[] antiDirs = new Dir[4] { Dir.Down, Dir.Up, Dir.Right, Dir.Left };

private readonly System.Random rand = new System.Random();

public void CheckCurCell(Point curPoint)
{
    // 标记当前单元
    MarkedArr[curPoint.x, curPoint.y] = true;

    // 检查周边元素
    CheckNearbyMarked(curPoint);

    if (CellForSelect.Count != 0)
    {
        // 如果存在未访问的单元
        int nextPoint = rand.Next(0, CellForSelect.Count);
        // 当前元素入栈
        cellStack.Push(curPoint);
        // 移除当前单元墙壁
        cells[curPoint.x, curPoint.y].SetLink(CellForSelect[nextPoint]);
        // 移除目标单元墙壁
        Point target = curPoint + dirPoints[(int)CellForSelect[nextPoint]];
        //Debug.Log(curPoint + " " + CellForSelect[nextPoint]);
        cells[target.x, target.y].SetLink(antiDirs[(int)CellForSelect[nextPoint]]);
        // 修改图片的Action，在创建Creator的时候给Action赋值
        SetLinkAct(cells[curPoint.x, curPoint.y], curPoint);
        SetLinkAct(cells[target.x, target.y], target);
        // 目标单元作为当前单元
        curIndex = target;
    }
    else if(cellStack.Count != 0)
    {
        curIndex = cellStack.Pop();
    }
    else
    {
        Debug.LogError("Something wrong");
        Assert.IsTrue(true);
    }
}

/// <summary>
/// 是否全部被标记
/// </summary>
public bool CheckAllMarked()
{
    for (int i = 0; i < MarkedArr.GetLength(0); i++)
    {
        for (int j = 0; j < MarkedArr.GetLength(1); j++)
        {
            if (!UseCells[i, j]) continue;
            if (!MarkedArr[i, j]) return false;
        }
    }
    return true;
}

/// <summary>
/// 判断周边是否被标记
/// </summary>
public List<Dir> CheckNearbyMarked(Point index)
{
    CellForSelect.Clear();
    for (int q = 0; q < 4; q++)
    {
        Point targetPIndex = index + dirPoints[q];
        // 判断越界
        if(targetPIndex.x < 0 || targetPIndex.x >= Width) continue;
        if(targetPIndex.y < 0 || targetPIndex.y >= Height) continue;
        if (!UseCells[targetPIndex.x, targetPIndex.y]) continue;
        if (!CheckMarked(targetPIndex)) CellForSelect.Add(dirs[q]);
    }
    return CellForSelect;
}

public bool CheckMarked(Point point)
{
    return MarkedArr[point.x, point.y];
}

private int b2int(bool x)
{
    return x ? 1 : 0;
}

动画效果

这样，就可以生成一个还看得过去的迷宫了。

SimpleMaze Generate Animation

完整的代码可以在 GithubRepo 中找到。

参考资料：

“Wiki: Maze_generation_algorithm”

“知乎: 基于深度优先从图片生成迷宫 by 破晓”

“CSDN: 三大迷宫生成算法 by jollysoul”

如有错误或者遗漏，欢迎联系指正。

唯一指定联系邮箱：xysjoshua@hotmail.com

GameAlgorithm 0x01 - Maze Creater

游戏算法01 - 迷宫创建器

源起