之前看到了 作者eastecho 的文章 简单的使用回溯法生成 Tile Based 迷宫
于是自己尝试着做了一下Unity的实现,同时将自己的理解记录下来。
基础算法的简单说明
简单说明一下算法步骤,大家也可以直接去原文章查看:
- 先生成基础地图。
- 选择基础地图的一个点(一个格子),将它标记为已访问过的,并将这个点加入到堆栈中储存起来。
- 取出堆栈顶的这个点作为基准点,检查附近有没有未访问过的点。
- 如果附近有未访问过的点,则随机选取其中的一个点,将它标记为已访问过的,并加入到堆栈中储存。
- 重复第二步,直到出现一个点,基于这个点在附近找不到未访问过的点了。
- 将这个堆栈顶部的点移除,基于新的顶部的点重复第二步。
- 当堆栈为空时,说明迷宫已经生成完毕。
经过以上步骤,我们就可以得到一个完美迷宫,从迷宫中的任何一点都可以到达迷宫中的另外一点。
这个算法就像是忒修斯走米诺斯迷宫,进入迷宫时将毛线头系在迷宫入口,然后随意走向能走的地方,直到走到了死胡同,就顺着毛线返回到上一个还能走的地方。
而我们的算法则像是在空地顺着路线摆砖块,直到摆不了砖块了便返回上一个可以摆砖块的地方继续摆砖块。
适合Tile Based地图的改进算法
我们先假设我们希望生成的迷宫中有两种大小相同的部件,墙 和 地面。
墙是不能移动到的部分,地面是玩家可以移动的部分。
假如未被访问的点是墙,已被访问的点是地面,我们的算法也可以看作是一个人在布满墙的空间里挖路。
这个时候我们发现,如果使用上一个算法,找到身边可以挖开的墙壁然后挖开,最后所有的墙壁都会被我们凿开。
所以我们需要为我们的墙壁预留空间。
我们稍加改良。
简单说明一下改良后的算法步骤:
- 先生成基础地图。
- 选择基础地图的一个点(一个格子),将它标记为已访问过的,并将这个点加入到堆栈中储存起来。
- 取出堆栈顶的这个点作为基准点,检查有没有与这个点相隔一个格子距离,同时又未访问过的点。
- 如果有这样的点,则随机选取其中的一个点,将它标记为已访问过的,并加入到堆栈中储存。
- 将这两个点之间的也标记为已访问过的点,但不将这个点放入堆栈。所以需注意,这个时候堆栈顶部的点是刚才检查到的,距离一个格子的点,而不是附近的这个点。将中间这个点设置为已访问的作用是连通当前点和下一个目标点。
- 重复第二步,直到出现一个点,基于这个点在附近距离一个格子的范围找不到未访问过的点了。
- 将这个堆栈顶部的点移除,基于新的顶部的点重复第二步。
- 当堆栈为空时,说明迷宫已经生成完毕。
不同的地方在于查找下一个目标点的时候,跳过了一个格子。最后只要将已访问过的点设置为路面,将未访问过的点设置为墙面就可以完成迷宫的生成了。
代码实现
首先我们先说明一下变量
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 InitTerrain() { _maze = new int[row, column]; _map = new GameObject[row, column]; //初始化时先将目标点设置为(0,0) _currentPoint = new Vector2(0, 0); }
然后我们每一帧根据当前的目标点查找下一个目标点。
c# void Update() { //如果当前目标点_currentPoint是合法的话就查找下一个目标点 if (_currentPoint != new Vector2(-1, -1)) { QueryRoad((int) _currentPoint.x, (int) _currentPoint.y); } }
然后我们的查找目标点也从递归改成仅仅查找下一个目标点。
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设置为新的目标点。 _currentPoint = new Vector2(x, y); //每一次找到了新的目标点都要绘制一次实际地图 DrawTerrain(); } }
每一次找到了新的目标点都要绘制一次实际地图,这样才能把你挖通的道路显示出来。
下一步就是绘制地图部分,这一部分没有什么变化。
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; } } } }
最后
大家可以自己尝试一下这种生成迷宫的方法。
如果大家有什么问题或者指教,也欢迎来与我交流。
强!
干的想喝水
支持干货