C#三大迷宫生成算法
发表于2018-07-24
今天介绍一下很经典的三大迷宫算法的C#实现,即随机普利姆算法,深度优先算法和十字分割(也就是递归分割算法)。实现参考了[ActionScript 3] 三大迷宫生成算法一文(生成的迷宫预览图也使用的该文中的示意图),并且将三种方法进行分装,方便游戏调用。
1、设计基类Maze类
为了方便我们游戏逻辑去调用三种迷宫算法,我们设计一个基类供继承,基类是一个抽象类,其中包括一些迷宫地图的必要属性和生成迷宫的抽象方法。
Maze.cs:
public abstract class Maze { internal int[,] _map; internal Vector2 _originPos; internal int _hight; internal int _width; public int[,] map { get { return _map; } } public Vector2 originPos { get { return _originPos; } } public int height { get { return _hight; } } public int width { get { return _width; } } public abstract void GenerateMaze(int width, int height, Vector2 originPos); }
2、随机普利姆算法
随机普里姆法生成的迷宫岔路较多,其生成方法通俗来说就是在全是墙的迷宫里打通路,所有可以走的地方上随机挖洞,创造出新的可以走的地方。
随机prim算法的核心是:
1. 让迷宫全是墙
2. 选一个格作为迷宫的通路,然后把它的邻墙放入列表
3. 当列表里还有墙时:
——3.1.从列表里随机选一个墙,如果它对面的格子不是迷宫的通路 :
————把墙打通,让对面的格子成为迷宫的通路
————把那个格子的邻墙加入列表
——3.2.如果对面的格子已经是通路了,那就从列表里移除这面墙
RPMaze.cs:
public class RPMaze : Maze { /// <summary> /// 生成随机普利姆算法迷宫 /// 地图尺寸必须为奇数,坑! /// </summary> public override void GenerateMaze(int width, int height, Vector2 originPos) { // 设置迷宫数据 _map = new int[height, width]; _width = width; _hight = height; _originPos = originPos; for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { _map[i, j] = 0; } } // 设置起点为目标个 var targetX = (int)originPos.x; var targetY = (int)originPos.y; map[targetX, targetY] = 1; // 记录邻墙 var rpBlockPos = new List<MazeBlock>(); // 如果上方有临墙,将临墙加入列表 if (targetX > 1) { var block = new MazeBlock(targetX - 1, targetY, BlockDirection.Up); rpBlockPos.Add(block); } // 如果右方有临墙,将临墙加入列表 if (targetY < width - 2) { var block = new MazeBlock(targetX, targetY + 1, BlockDirection.Right); rpBlockPos.Add(block); } // 如果下方有临墙,将临墙加入列表 if (targetX < height - 2) { var block = new MazeBlock(targetX + 1, targetY, BlockDirection.Down); rpBlockPos.Add(block); } // 如果左方有临墙,将临墙加入列表 if (targetY>1) { var block = new MazeBlock(targetX, targetY - 1, BlockDirection.Left); rpBlockPos.Add(block); } while (rpBlockPos.Count > 0) { // 随机选一面墙 long tick = System.DateTime.Now.Ticks; System.Random ran = new System.Random((int)(tick & 0xffffffffL) | (int)(tick >> 32)); int blockIndex = ran.Next(0, rpBlockPos.Count); switch (rpBlockPos[blockIndex].direction) { case BlockDirection.Up: targetX = rpBlockPos[blockIndex].x - 1; targetY = rpBlockPos[blockIndex].y; break; case BlockDirection.Down: targetX = rpBlockPos[blockIndex].x + 1; targetY = rpBlockPos[blockIndex].y; break; case BlockDirection.Left: targetX = rpBlockPos[blockIndex].x; targetY = rpBlockPos[blockIndex].y - 1; break; case BlockDirection.Right: targetX = rpBlockPos[blockIndex].x ; targetY = rpBlockPos[blockIndex].y + 1; break; } //如果目标墙尚未料筒 if (_map[targetX, targetY] == 0) { // 连通目标墙 _map[rpBlockPos[blockIndex].x, rpBlockPos[blockIndex].y] = 1; _map[targetX, targetY] = 1; // 添加目标墙的临墙 if (rpBlockPos[blockIndex].direction != BlockDirection.Down && targetX > 1 && _map[targetX - 1, targetY] == 0 && _map[targetX - 2, targetY] == 0) { var block = new MazeBlock(targetX - 1, targetY, BlockDirection.Up); rpBlockPos.Add(block); } if (rpBlockPos[blockIndex].direction != BlockDirection.Left && targetY < width - 2 && _map[targetX, targetY + 1] == 0 && _map[targetX, targetY + 2] == 0) { var block = new MazeBlock(targetX, targetY + 1, BlockDirection.Right); rpBlockPos.Add(block); } if (rpBlockPos[blockIndex].direction != BlockDirection.Up && targetX < height - 2 && _map[targetX + 1, targetY] == 0 && _map[targetX + 2, targetY] == 0) { var block = new MazeBlock(targetX + 1, targetY, BlockDirection.Down); rpBlockPos.Add(block); } if (rpBlockPos[blockIndex].direction != BlockDirection.Right && targetY > 1 && _map[targetX, targetY - 1] == 0 && _map[targetX, targetY - 2] == 0) { var block = new MazeBlock(targetX, targetY - 1, BlockDirection.Left); rpBlockPos.Add(block); } } // 移除目标墙 rpBlockPos.RemoveAt(blockIndex); } } }
3、深度优先算法
深度优先法生成的迷宫有着一条明显的主路,看起来比较简单。其生成方法其实就是深度遍历法。
深度优先算法的核心是:
1. 将起点作为当前格并标记
2. 当还存在未标记的格时:
——2.1.如果当前格有未标记的邻格:
————随机选择一个未标记的邻格
————将当前格入栈
————移除当前格与邻格的墙
————标记邻格并用它作为当前格
——2.2.反之,如果栈不空:
————栈顶的格子出栈
————令其成为当前格
——2.3.反之,随机选择一个格子为当前格并标记
RBMaze.cs:
public class RBMaze : Maze { public override void GenerateMaze(int width, int height, Vector2 originPos) { // 设置迷宫数据 _map = new int[height, width]; _width = width; _hight = height; _originPos = originPos; for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { _map[i, j] = 0; } } // 设置起点为目标格 var targetX = (int)originPos.x; var targetY = (int)originPos.y; map[targetX, targetY] = 1; var rbDirection = new List<BlockDirection>(); var blockStack = new List<MazeBlock>(); do { // 检测周围有没有未连通的格子 rbDirection.Clear(); // 检测上方 if(targetX > 1 && map[targetX - 2, targetY] == 0) rbDirection.Add(BlockDirection.Up); // 检测右方 if(targetY < width - 2 && map[targetX, targetY + 2] == 0) rbDirection.Add(BlockDirection.Right); // 检测下方 if(targetX < height - 2 && map[targetX + 2, targetY] == 0) rbDirection.Add(BlockDirection.Down); // 检测左方 if(targetY > 1 && map[targetX, targetY - 2] == 0) rbDirection.Add(BlockDirection.Left); // 选出下一个当前格 if(rbDirection.Count > 0) { long tick = System.DateTime.Now.Ticks; System.Random ran = new System.Random((int)(tick & 0xffffffffL) | (int)(tick >> 32)); int blockIndex = ran.Next(0, rbDirection.Count); // 将当前格入栈 var block = new MazeBlock(targetX, targetY); blockStack.Add(block); // 连通邻格,并将邻格指定为当前格 switch(rbDirection[blockIndex]) { case BlockDirection.Up: map[targetX - 1, targetY] = 1; targetX -= 2; break; case BlockDirection.Down: map[targetX + 1, targetY] = 1; targetX += 2; break; case BlockDirection.Left: map[targetX, targetY - 1] = 1; targetY -= 2; break; case BlockDirection.Right: map[targetX, targetY + 1] = 1; targetY += 2; break; } // 标记当前格 if(targetX > 0 && targetX < height - 1 && targetY > 0 && targetY < width - 1) map[targetX, targetY] = 1; } else if(blockStack.Count > 0) { // 讲栈顶作为当前格,并移除栈顶 var index = blockStack.Count - 1; targetX = blockStack[index].x; targetY = blockStack[index].y; blockStack.RemoveAt(index); } } while(blockStack.Count > 0); } }
4、十字(递归)分割算法:
十字分割法生成的迷宫会形成一个一个大小不一的“房间”,适合制作RPG游戏地图。起生成原理及递归法,先画一个十字分成四个部分,在三面墙上打洞,再在每个子部分中重复这一步骤,直至空间不够分割(这个值需要我们自行设置)
RDMaze.cs:
public class RDMaze : Maze { public void InitRDMaze() { } public override void GenerateMaze(int width, int height, Vector2 originPos) { // 设置迷宫数据 _map = new int[height, width]; _width = width; _hight = height; _originPos = originPos; for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { if (i == 0 || i == height - 1 || j == 0 || j == width - 1) _map[i, j] = 0; else _map[i, j] = 1; } } RecursiveRDMaze((int)originPos.y, (int)originPos.x, width - 2, height - 2); } private void RecursiveRDMaze(int left, int top, int right, int bottom) { // 分各区域的坐标和面积 int rdHeight = bottom - top; int rdWidth = right - left; int area = (rdHeight + 1) * (rdWidth + 1); if (area < 10 || (rdHeight <= 1 && rdWidth <= 1)) return; // 计算分割点坐标并在分割方向上补上墙 int recursiceX = -1; int recursiceY = -1; if (rdWidth > 1) { recursiceY= left + 1 + Random.Range(0, rdWidth / 2) * 2; for (int i = top; i < bottom; i++) map[i, recursiceY] = 0; } if (rdHeight > 1) { recursiceX = top + 1 + Random.Range(0, rdHeight / 2) * 2; for (int i = left; i <= right; i++) map[recursiceX, i] = 0; } if (rdWidth > 1 && rdHeight > 1) { // 选择要打通的墙,确保连通性,打通三面 // 0:上,1:下,2:左,3:右 int side = Random.Range(0, 4); if (side != 0) { var upIndex = Random.Range(0, (recursiceX - 1 - top) / 2 + 1) * 2; map[top + upIndex, recursiceY] = 1; } if (side != 1) { var downIndex = Random.Range(0, (bottom - recursiceX - 1) / 2 + 1) * 2; map[recursiceX + 1 + downIndex, recursiceY] = 1; } if (side != 2) { var leftIndex = Random.Range(0, (recursiceY - 1 - left) / 2 + 1) * 2; map[recursiceX, left + leftIndex] = 1; } if (side != 3) { var rightIndex = Random.Range(0, (right - recursiceY - 1) / 2 + 1) * 2; map[recursiceX, recursiceY + 1 + rightIndex] = 1; } // 递归 RecursiveRDMaze(left, top, recursiceY - 1, recursiceX - 1); RecursiveRDMaze(recursiceY + 1, top, right, recursiceX - 1); RecursiveRDMaze(left, recursiceX + 1, recursiceY - 1, bottom); RecursiveRDMaze(recursiceY + 1, recursiceX + 1, right, bottom); } else { if (rdWidth <= 1) { var index = Random.Range(0, rdWidth / 2 + 1) * 2; map[recursiceX, left + index] = 1; RecursiveRDMaze(left, top, right, recursiceX - 1); RecursiveRDMaze(left, recursiceX + 1, right, bottom); } if (rdHeight <= 1) { var index = Random.Range(0, rdHeight / 2 + 1) * 2; map[top + index, recursiceY] = 1; RecursiveRDMaze(left, top, recursiceY - 1, bottom); RecursiveRDMaze(recursiceY + 1, top, right, bottom); } } } }
来自:https://blog.csdn.net/dark00800/article/details/76359988