Unity 记录一种基于深搜的迷宫算法

假设一个5*5的迷宫地图，按下图分割

可见，问题变成了Unit和Unit之间哪些红色方块应该被打通。则，使用深搜算法遍历Unit，随机往一个相邻的、没有被走过（因为只希望有一条正确通道）的其他Unit走，再把路打通即可。如果无路可走则回溯。

效果如图

完整代码

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using System.Linq;
using System.Threading;

public class MazeBuilder : MonoBehaviour
{
    public int height;
    public int width;
    public Vector2Int entrance;
    public Transform wallPrefab;
    public Stuff[] stuffs;

    [System.Serializable]
    public struct Stuff
    {
        public int number;
        public Transform prefab;
    }

    List<Vector2Int> directions = new List<Vector2Int>
    {
        new Vector2Int(0, -1),
        new Vector2Int(1, 0),
        new Vector2Int(0, 1),
        new Vector2Int(-1, 0),
    };

    public void Build()
    {
        // 记录unit
        bool[,] units = new bool[height * 2, width * 2];
        // 记录pass
        bool[,] passs = new bool[height * 4 - 1, width * 4 - 1];

        // 记录路径
        var stack = new Stack<Vector2Int>();
        // 设置入口
        stack.Push(entrance);

        while (stack.Count > 0)
        {
            // 打通这个unit
            var now = stack.Peek();
            units[now.x, now.y] = true;
            passs[now.x * 2, now.y * 2] = true;
            foreach (var item in RandomDirections())
            {
                // 新通向的unit坐标
                var point = now + item;
                
                // 如果这个unit没被打通
                if (!IsOutRange(point) && !units[point.x, point.y])
                {
                    // 打通当前unit和这个unit的通道
                    passs[point.x + now.x, point.y + now.y] = true;
                    // 将这个unit设为当前unit
                    stack.Push(point);
                    break;
                }
            }
            // 无路可走，回溯到上一个unit
            if (stack.Peek() == now)
            {
                stack.Pop();
            }
        }

        List<Vector2> passPoints = new List<Vector2>();

        // 墙根节点
        GameObject wallParent = new GameObject("walls");
        wallParent.transform.SetParent(transform);
        wallParent.transform.localPosition = Vector3.zero;
        wallParent.transform.localScale = Vector3.one;

        for (int i = 0; i < height * 4 - 1; i++)
        {
            for (int j = 0; j < width * 4 - 1; j++)
            {
                if (!passs[i, j])
                {
                    // 生成墙
                    var wall = Instantiate(wallPrefab, wallParent.transform);
                    wall.localPosition = new Vector3(i - width * 2 + 1f, 0, j - width * 2 + 1f);
                    wall.gameObject.name = $"({i},{j})";
                    wall.Rotate(0, Random.Range(0, 4) * 90, 0);
                }
                else
                {
                    // 记录通道
                    passPoints.Add(new Vector2(i, j));
                }
            }
        }

        // 物体根节点
        GameObject stuffParent = new GameObject("Maze Stuffs");
        stuffParent.transform.SetParent(transform);
        stuffParent.transform.localPosition = Vector3.zero;
        stuffParent.transform.localScale = Vector3.one;

        foreach (var item in stuffs)
        {
            for (int i = 0; i < item.number && passPoints.Count > 0; i++)
            {
                // 生成物体
                int r = Random.Range(0, passPoints.Count);
                var stuff = Instantiate(item.prefab, stuffParent.transform);
                stuff.localPosition = new Vector3(passPoints[r].x - width * 2 + 1f, 0, passPoints[r].y - width * 2 + 1f);
                stuff.localScale = new Vector3()
                {
                    x = 1 / transform.lossyScale.x * item.prefab.localScale.x,
                    y = 1 / transform.lossyScale.y * item.prefab.localScale.y,
                    z = 1 / transform.lossyScale.z * item.prefab.localScale.z
                };
                stuff.gameObject.name = $"{item.prefab.gameObject.name} {i}";
                passPoints.RemoveAt(r);
            }
            if (passPoints.Count == 0)
            {
                break;
            }
        }

        // 判断越界
        bool IsOutRange(Vector2Int point)
        {
            return point.x < 0 || point.x >= height * 2 || point.y < 0 || point.y >= width * 2;
        }

    }

    // 洗牌算法
    private List<Vector2Int> RandomDirections()
    {
        for (int i = directions.Count; i >= 0; i--)
        {
            int r = Random.Range(0, i);
            directions.Add(directions[r]);
            directions.RemoveAt(r);
        }
        return directions;
    }
}


复制代码

参考文章

1. jollysoul-三大迷宫生成算法 (Maze generation algorithm) — 深度优先，随机Prim，递归分割
2. 小牛-图的遍历迷宫生成算法浅析