Imagine a 5 by 5 maze map, split as shown belowAs you can see, the question becomes which red blocks should be opened between units and units. Then, the deep search algorithm is used to traverse the Unit and randomly walk to another Unit that is adjacent but not passed (because only one correct channel is desired), and then the path is cleared. If there’s no way out, go back.

The effect is shown in figureThe complete code

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()
    {
        / / record unit
        bool[,] units = new bool[height * 2, width * 2];
        / / pass
        bool[,] passs = new bool[height * 4 - 1, width * 4 - 1];

        // Record the path
        var stack = new Stack<Vector2Int>();
        // Set the entry
        stack.Push(entrance);

        while (stack.Count > 0)
        {
            // Get through the unit
            var now = stack.Peek();
            units[now.x, now.y] = true;
            passs[now.x * 2, now.y * 2] = true;
            foreach (var item in RandomDirections())
            {
                // The unit coordinates of the new route
                var point = now + item;
                
                // If the unit is not called
                if(! IsOutRange(point) && ! units[point.x, point.y]) {// Unblock the current unit from this unit
                    passs[point.x + now.x, point.y + now.y] = true;
                    // Set this unit to the current unit
                    stack.Push(point);
                    break; }}// There is no way out, back to the previous unit
            if (stack.Peek() == now)
            {
                stack.Pop();
            }
        }

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

        // Wall root node
        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]) {/ / generated wall
                    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
                {
                    // Record channel
                    passPoints.Add(newVector2(i, j)); }}}// Object root node
        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++)
            {
                // Generate object
                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; }}// Judge out of bounds
        bool IsOutRange(Vector2Int point)
        {
            return point.x < 0 || point.x >= height * 2 || point.y < 0 || point.y >= width * 2; }}// Shuffle algorithm
    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);
        }
        returndirections; }}Copy the code

Refer to the article

  1. Jollysoul – Three Maze generation algorithms — depth-first, Random Prim and recursive segmentation
  2. A brief analysis of traversal maze generation algorithm for calf – graph