Unity的迷宫生成算法
发表于2019-01-25
思路：
定义一个二维数组，二维数组中奇数行列视为围墙，偶数为路径。 从起始点开始，随机从上下左右四个位置寻找周围没有被找到过的位置，找到后此点标记为1，并把此点与前一点之间的位置设置为1。 如果全部位置已经找到过，则退回到上一个点重复次逻辑，直到所有点都记录到或 退回到起始点且没有可用点。
文章最后我会附上完整代码。
下面我们来实现一下
新建一个迷宫生成类：MazeCreate
定一个二维列表，用来存储我们的数据，因为迷宫的尺寸需要是可配置的，所有我们用list来进行存储：
public List<List<int>> mapList = new List<List<int>>();
为了区分每个点代表的不同内容，我们定义一个枚举：
public enum PointType｛
wall = 0,//墙
way = 1,//路
startpoint = 2,//起始点
endpoint = 3,//结束点
nullpoint = 4,//空位置，不进行任何操作
｝
在构造函数中对迷宫的尺寸进行设置：
private MazeCeator(int row, int col)｛
this.row = row;
this.col = col;
｝
然后定义Start方法开始迷宫数据的生成
初始化数组，按照行数和列数对数据进行初始化：
for (int i = 0; i < row; i++)
｛
mapList.Add(new List<int>());
for (int j = 0; j < col; j++)
｛
mapList[i].Add((int)PointType.wall);
｝
｝
然后随机找一个点作为起始点，因为我们前面说过，奇数行为墙，偶数行为路线，所以要对随机的结果进行判断，避免起始点在墙上，像这样：
int _row = Random.Range(1, row - 1);
int _col = Random.Range(1, col - 1);
if (_row % 2 == 0) ｛ _row += 1; ｝
if (_col % 2 == 0) ｛ _col += 1; ｝
然后给起始点的数据赋值：
mapList[_row][_col] = (int)PointType.startpoint;
开始生成迷宫
首先实现一下寻找周围可用点的方法：
void FindNearPoint(List<int> nearpoint,int index)｛
nearpoint.Clear();
int _row = index / col;
int _col = index % col;
//up
if (_row >= 2)
｛
AddNearPoint(nearpoint, (_row - 2) * col + _col);
｝
//down
if (_row < row - 2)
｛
AddNearPoint(nearpoint, (_row + 2) * col + _col);
｝
//left
if (_col >= 2)
｛
AddNearPoint(nearpoint, _row * col + _col - 2);
｝
//up
if (_col < col - 2)
｛
AddNearPoint(nearpoint, _row * col + _col + 2);
｝
｝
nearpoint参数用来记录所有的可用点，index为要寻找的点，这里为了传递参数更加方便，把二维索引转换成一维来进行传递。
AddNearPoint方法用来判断这个点是否满足可一个被找到的条件：
void AddNearPoint(List<int> nearpoint, int p)
｛
int _row = p / col;
int _col = p % col;
if (p >= 0 && p < maxcount && mapList[_row][_col] == (int)PointType.wall)
｛
nearpoint.Add(p);
｝
｝
接下来进行生成逻辑，定义一个方法void FindPoint(int nowindex)；nowindex为当前的点。
然后在Start调用FindPoint并传入起始点：
int nowindex = _row * col + _col;
FindPoint(nowindex);
FindPoint里面我们使用递归的方式来找到所有的点。
首先判断是否找到所有的点：
if(findList.Count >= maxcount)｛
return;
｝
其中maxcount=row * col，为了方便使用，把它定义成全局变量并在Start中赋值。
然后我们定义一个列表用来存储附近可用的点，即值为0的点并开始寻找：
List<int> nearpoint = new List<int>();
FindNearPoint(nearpoint,nowindex);
如果找到了附近可用的点，这遍历这些点并对其进行处理：
while (nearpoint.Count > 0)
｛
int rand = Random.Range(0, nearpoint.Count);
//中间的格子
int midindex = nowindex + (nearpoint[rand] - nowindex) / 2;
SetPoint(midindex);
//新的格子
int newindex = nearpoint[rand];
SetPoint(newindex);
nearpoint.RemoveAt(rand);
//递归
FindPoint(newindex);
FindNearPoint(nearpoint, nowindex);
｝
还需要一个设置目标点的方法：
void SetPoint(int index)
｛
int _row = index / col;
int _col = index % col;
mapList[_row][_col] = (int)PointType.way;
findList.Add(index);
｝
这里先是在所有可用点中随机找出一个即rand，然后把当前点与rand之间的点打通，即设置为1，把目标点从nearpoint中移除，
然后递归调用FindPoint，并传入新的目标点。
这里因为在每一次循环后，之前找到的nearpoint中的点的状态有可能会改变，所以最后需要重新寻找一次附近可用的点。
这样我们的迷宫就可以正常生成了，我们来测试一下。
创建一个cube并做成预制体，放在Resources/Prefabs中取名为maze。
创建一个测试脚本MazeTest:
定义地图的宽高已经迷宫生成类：
const int row = 41, col = 41;
MazeCreate mazeCreate;
Start方法中初始化迷宫类
mazeCreate = MazeCreate.GetMaze(row, col);
然后遍历迷宫数据并生成物体，这里我们判断是在路径上生成物体：
for (int i = 0; i < row; i++)
｛
for (int j = 0; j < col; j++)
｛
if (mazeCreate.mapList[i][j] == (int)MazeCreate.PointType.startpoint ||
mazeCreate.mapList[i][j] == (int)MazeCreate.PointType.way)
｛
GameObject column = (GameObject)Resources.Load("Prefabs/maze");
column = MonoBehaviour.Instantiate(column);
column.transform.position = new Vector3(i, 0, j);
｝
｝
｝
把MazeTest挂到摄像机上并运行场景，我们可以看到：
这样我们的迷宫就生成成功了。
为了看到迷宫的生成过程，我们使用findList，这里记录了路径点的先后顺序，我们来试一下：
还是上边的测试类，我们把for循环的部分注释调，然后在Update中加入如下代码：
float addTime = 0;
int addindex = 0;
// Update is called once per frame
void Update () ｛
if (addindex >= mazeCreate.findList.Count)
｛
return;
｝
addTime += Time.deltaTime;
if (addTime > 0.05)
｛
addTime = 0;
int index = mazeCreate.findList[addindex];
int _row = index / col;
int _col = index % col;
GameObject column = (GameObject)Resources.Load("Prefabs/maze");
column = MonoBehaviour.Instantiate(column);
column.transform.position = new Vector3(_row, 0, _col);
addindex++;
｝
｝
效果：
最后附上MazeCreate的完整代码：
/// <summary>
/// 迷宫生成类
/// 迷宫生成思路：
/// 规则:二维数组中奇数行列视为围墙，偶数为路径
/// 从起始点开始，随机从上下左右四个位置寻找周围没有被找到过的位置，找到后此点标记为1，并把此点与前一点之间的位置设置为1
/// 如果全部位置已经找到过，则退回到上一个点重复次逻辑，直到所有点都记录到或 退回到起始点且没有可用点
/// </summary>
public class MazeCreate : MonoBehaviour
｛
public enum PointType｛
wall = 0,//墙
way = 1,//路
startpoint = 2,//起始点
endpoint = 3,//结束点
nullpoint = 4,//空位置，不进行任何操作
｝
//行数
public int row｛ get; private set; ｝
//列数
public int col｛ get; private set; ｝
//全部点数量
int maxcount;
private MazeCreate(int row, int col)｛
this.row = row;
this.col = col;
Start();
｝
public static MazeCreate GetMaze(int row, int col)
｛
MazeCreate maze = new MazeCreate(row,col);
return maze;
｝
/// <summary>
/// 迷宫生成过程中，记录已经找到的点
/// </summary>
public List<int> findList = new List<int>();
//迷宫数据
public List<List<int>> mapList = new List<List<int>>();
void Start()｛
maxcount = row * col;
//初始化数组
for (int i = 0; i < row; i++)
｛
mapList.Add(new List<int>());
for (int j = 0; j < col; j++)
｛
mapList[i].Add((int)PointType.wall);
｝
｝
//for (int i = 0; i < 10; i++)
//｛
// for (int j = 0; j < 10; j ++)｛
// mapList[row / 2 - 2 + i][col / 2 - 2 + j] = (int)PointType.nullpoint;
// ｝
//｝
//起始点
int _row = Random.Range(1, row - 1);
int _col = Random.Range(1, col - 1);
if (_row % 2 == 0) ｛ _row += 1; ｝
if (_col % 2 == 0) ｛ _col += 1; ｝
mapList[_row][_col] = (int)PointType.startpoint;
int nowindex = _row * col + _col;
findList.Add(nowindex);
//递归生成路径
FindPoint(nowindex);
｝
void FindPoint(int nowindex)｛
if(findList.Count >= maxcount)｛
return;
｝
List<int> nearpoint = new List<int>();
FindNearPoint(nearpoint,nowindex);
while (nearpoint.Count > 0)
｛
int rand = Random.Range(0, nearpoint.Count);
//中间的格子
int midindex = nowindex + (nearpoint[rand] - nowindex) / 2;
SetPoint(midindex);
//新的格子
int newindex = nearpoint[rand];
SetPoint(newindex);
nearpoint.RemoveAt(rand);
//递归
FindPoint(newindex);
FindNearPoint(nearpoint, nowindex);
｝
｝
//寻找附近可用的点
void FindNearPoint(List<int> nearpoint,int index)｛
nearpoint.Clear();
int _row = index / col;
int _col = index % col;
//up
if (_row >= 2)
｛
AddNearPoint(nearpoint, (_row - 2) * col + _col);
｝
//down
if (_row < row - 2)
｛
AddNearPoint(nearpoint, (_row + 2) * col + _col);
｝
//left
if (_col >= 2)
｛
AddNearPoint(nearpoint, _row * col + _col - 2);
｝
//up
if (_col < col - 2)
｛
AddNearPoint(nearpoint, _row * col + _col + 2);
｝
｝
//设置路径
void SetPoint(int index)
｛
int _row = index / col;
int _col = index % col;
mapList[_row][_col] = (int)PointType.way;
findList.Add(index);
｝
//附近的点是否满足寻找条件
void AddNearPoint(List<int> nearpoint, int p)
｛
int _row = p / col;
int _col = p % col;
if (p >= 0 && p < maxcount && mapList[_row][_col] == (int)PointType.wall)
｛
nearpoint.Add(p);
｝
｝
｝