Help with maze generation

Unity Engine
1

I know the title is really vague but I didn’t know how to keep it concise enough. I found this maze generation script for C# and I wanted to implement it in Unity, but I’m having a little trouble with converting the output to instantiated rooms for each cell in the maze.

I have a room prefab with 4 walls, and a Room script which enables/disables each wall (I renamed the cell states to cardinals since it works better for my brain):

public class Room : MonoBehaviour
{
    public GameObject[] walls; // 0 - North : 1 - East : 2 - South : 3 - West

    public void UpdateWalls(CellState cs)
    {
        walls[0].SetActive(cs.HasFlag(CellState.North));
        walls[1].SetActive(cs.HasFlag(CellState.East));
        walls[2].SetActive(cs.HasFlag(CellState.South));
        walls[3].SetActive(cs.HasFlag(CellState.West));
    }
}

Then I have a quick generator script that implements things:

public class Generator : MonoBehaviour
{
    public int mazeWidth;
    public int mazeHeight;

    public Vector2 roomDims;
    public GameObject room;

    void Start()
    {
        var maze = new Maze(mazeWidth, mazeHeight);
        for (int x = 0; x < maze.Width; x++)
        {
            for (int y = 0; y < maze.Height; y++)
            {
                var pos = new Vector3(x * roomDims.x, 0, y * roomDims.y);
                var go = Instantiate(room, pos, Quaternion.identity);
                go.GetComponent<Room>().UpdateWalls(maze[x, y]);
            }
        }
    }
}

It obviously doesn’t work since I get this:

7575304--938452--upload_2021-10-16_3-19-23.png
7575304--938452--upload_2021-10-16_3-19-23.png699×690 5.21 KB

I tried following the original code in the Display function but I don’t think I got it quite right. Any help would be appreciated!

2

So I just happened to notice that your bottom row pictured has a north wall in every cell, and the top row has a south wall in every cell. (West and east columns look okay.) Are you sure you have your Y coordinates correct for north and south?

3

You’re definitely right on that, though I’m not sure why it’s happening. I didn’t change anything major in the original maze generator script. The only reason I can see is that the Display function doesn’t translate as nicely as I’d hoped, and that there needs to be some adjustments. I’m really not certain how to even approach this.

4

Just switch to anti-clockwise direction starting from south.

public class Room : MonoBehaviour
{
    public GameObject[] walls; // 0 - South : 1 - East : 2 - North : 3 - West
    public void UpdateWalls(CellState cs)
    {
        walls[0].SetActive(cs.HasFlag(CellState.South));
        walls[1].SetActive(cs.HasFlag(CellState.East));
        walls[2].SetActive(cs.HasFlag(CellState.North));
        walls[3].SetActive(cs.HasFlag(CellState.West));
    }
}

I think this should work, unless something else we don’t know about is happening somewhere.

1 Like
5

Oh wow, this worked! Thank you. Do you know why it needs to be flipped? I made sure all the walls in the prefab were correct.

6

Without seeing the entire algorithm and understanding how it works, it probably caused by difference between the coordinate systems.

1 Like
7

Yeah, Unity is a left-handed universe.

8

The algorithm is in the link I put in my original post, but here it is in my project:

namespace MazeGeneration
{
    public static class Extensions
    {
        public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
        {
            var e = source.ToArray();
            for (var i = e.Length - 1; i >= 0; i--)
            {
                var swapIndex = rng.Next(i + 1);
                yield return e[swapIndex];
                e[swapIndex] = e[i];
            }
        }

        public static CellState OppositeWall(this CellState orig)
        {
            return (CellState)(((int)orig >> 2) | ((int)orig << 2)) & CellState.Initial;
        }

        public static bool HasFlag(this CellState cs, CellState flag)
        {
            return ((int)cs & (int)flag) != 0;
        }
    }

    [Flags]
    public enum CellState
    {
        North = 1,
        East = 2,
        South = 4,
        West = 8,
        Visited = 128,
        Initial = North | East | South | West
    }

    public struct RemoveWall
    {
        public Point Neighbour;
        public CellState Wall;
    }

    public class Maze
    {
        private readonly CellState[,] _cells;
        private readonly int _width;
        private readonly int _height;
        private readonly Random _rng;

        public Maze(int width, int height)
        {
            _width = width;
            _height = height;
            _cells = new CellState[width, height];
            for (var x = 0; x < width; x++)
                for (var y = 0; y < height; y++)
                    _cells[x, y] = CellState.Initial;
            _rng = new Random();
            VisitCell(_rng.Next(width), _rng.Next(height));
        }

        public int Height
        {
            get { return _height; }
        }
        public int Width
        {
            get { return _width; }
        }

        public CellState this[int x, int y]
        {
            get { return _cells[x, y]; }
            set { _cells[x, y] = value; }
        }

        public IEnumerable<RemoveWall> GetNeighbours(Point p)
        {
            if (p.X > 0) yield return new RemoveWall { Neighbour = new Point(p.X - 1, p.Y), Wall = CellState.West };
            if (p.Y > 0) yield return new RemoveWall { Neighbour = new Point(p.X, p.Y - 1), Wall = CellState.North };
            if (p.X < _width - 1) yield return new RemoveWall { Neighbour = new Point(p.X + 1, p.Y), Wall = CellState.East };
            if (p.Y < _height - 1) yield return new RemoveWall { Neighbour = new Point(p.X, p.Y + 1), Wall = CellState.South };
        }

        public void VisitCell(int x, int y)
        {
            this[x, y] |= CellState.Visited;
            foreach (var p in GetNeighbours(new Point(x, y)).Shuffle(_rng).Where(z => !(this[z.Neighbour.X, z.Neighbour.Y].HasFlag(CellState.Visited))))
            {
                this[x, y] -= p.Wall;
                this[p.Neighbour.X, p.Neighbour.Y] -= p.Wall.OppositeWall();
                VisitCell(p.Neighbour.X, p.Neighbour.Y);
            }
        }
    }
}
9

Oh! I had no idea, TIL. Thank you :smile: