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