C#三大迷宫生成算法

发表于2018-07-24
评论1 4.4k浏览
今天介绍一下很经典的三大迷宫算法的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

如社区发表内容存在侵权行为,您可以点击这里查看侵权投诉指引