unity的迷宫生成算法

2023-12-19 00:15| 来源: 网络整理| 查看: 265

思路：

定义一个二维数组，二维数组中奇数行列视为围墙，偶数为路径。从起始点开始，随机从上下左右四个位置寻找周围没有被找到过的位置，找到后此点标记为1，并把此点与前一点之间的位置设置为1。如果全部位置已经找到过，则退回到上一个点重复次逻辑，直到所有点都记录到或退回到起始点且没有可用点。

文章最后我会附上完整代码。

下面我们来实现一下

新建一个迷宫生成类:MazeCreate

定一个二维列表，用来存储我们的数据，因为迷宫的尺寸需要是可配置的，所有我们用list来进行存储：

public List mapList = new List();为了区分每个点代表的不同内容，我们定义一个枚举：

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()); 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 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 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 nearpoint = new List(); 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的完整代码：

/// /// 迷宫生成类 /// 迷宫生成思路： /// 规则:二维数组中奇数行列视为围墙，偶数为路径 /// 从起始点开始，随机从上下左右四个位置寻找周围没有被找到过的位置，找到后此点标记为1，并把此点与前一点之间的位置设置为1 /// 如果全部位置已经找到过，则退回到上一个点重复次逻辑，直到所有点都记录到或退回到起始点且没有可用点 /// 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; } /// /// 迷宫生成过程中，记录已经找到的点 /// public List findList = new List(); //迷宫数据 public List mapList = new List(); void Start(){ maxcount = row * col; //初始化数组 for (int i = 0; i < row; i++) { mapList.Add(new List()); 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 nearpoint = new List(); 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 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 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); } } }

【本文地址】

公司简介

联系我们