Generating a "perfect" maze using recursive backtracking

MazeGenerator.cs

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

public class MazeGenerator : MonoBehaviour
{
    [SerializeField]
    int seed;

    [SerializeField]
    int height = 5;

    [SerializeField]
    int width = 5;

    [SerializeField]
    Transform tilePrefab;

    [SerializeField]
    Transform wallPrefab;

    [SerializeField]
    Transform playerPrefab;

    [SerializeField]
    Transform goalPrefab;

    GameObject[,] acrossWalls;
    GameObject[,] upWalls;

    Node startingCell;
    Node finalCell;

    public static event Action<int, int> OnMazeGenerated;

    public void GenerateMaze(int _width, int _height)
    {
        width = _width; 
        height = _height;

        ClearExistingMaze();
        SetSeed();

        GenerateInitialGrid();
        GenerateWalls();

        GeneratePath();

        SpawnPlayer();
        SpawnGoal();

        // Needs to be always called last
        OnMazeGenerated?.Invoke(width, height);
    }

    public void ClearExistingMaze()
    {
        foreach (Transform child in transform)
        {
            Destroy(child.gameObject);
        }
    }

    void SetSeed()
    {
        if (seed == 0)
        {
            // Let the engine handle the seeding if it's zero
            // to make the maze random
            return;
        }
        UnityEngine.Random.InitState(seed);
    }

    void GenerateInitialGrid()
    {
        for (int i = 0; i < width; i++)
        {
            for (int j = 0; j < height; j++)
            {
                Instantiate(tilePrefab, new(i, j), Quaternion.identity, transform);
            }
        }
    }

    void GenerateWalls()
    {
        acrossWalls = new GameObject[width + 1, height + 1];
        upWalls = new GameObject[width + 1, height + 1];

        // Walls going across the bottoms of cells
        for (int i = 0; i < width; i++)
        {
            for (int j = 0; j < height + 1; j++)
            {

                var wallObj = Instantiate(wallPrefab, new(i, j), Quaternion.identity, transform);
                wallObj.name = $"Wall left/right ({i}, {j})";
                acrossWalls[i, j] = wallObj.gameObject;
            }
        }

        // Walls going up the sides of cells
        for (int i = -1; i < width; i++)
        {
            for (int j = 0; j < height; j++)
            {
                var wallObj = Instantiate(wallPrefab, new(i, j), Quaternion.Euler(0, 0, 90), transform);
                wallObj.name = $"Wall up/down ({i}, {j})";
                upWalls[i + 1, j] = wallObj.gameObject;
            }
        }
    }

    void GeneratePath()
    {
        HashSet<Node> visited = new();

        startingCell = StartingCell();
        visited.Add(startingCell);
        RecursiveBacktrack(startingCell, visited);
        finalCell = visited.Last();
    }

    void RecursiveBacktrack(Node currentCell, HashSet<Node> visited)
    {
        var unvisitedNeighbours = GetNeighbours(currentCell).Where(n => !visited.Contains(n)).ToList();

        while (unvisitedNeighbours.Count > 0)
        {
            var nextCell = RandomUtils.GetFromList(unvisitedNeighbours);

            Direction travelDirection = TravelDirection(currentCell, nextCell);
            DeleteCorrespondingWall(travelDirection, currentCell, nextCell);

            visited.Add(nextCell);

            RecursiveBacktrack(nextCell, visited);

            unvisitedNeighbours = GetNeighbours(currentCell).Where(n => !visited.Contains(n)).ToList();
        }

        // If no unvisited neighbours remain, the function will return (backtracking)
    }

    List<Node> GetNeighbours(Node node)
    {
        var neighbours = new List<Node>();
        int x = node.X;
        int y = node.Y;
        if (x > 0)
        {
            var left = new Node(x - 1, y);
            neighbours.Add(left);
        }

        if (x + 1 < width)
        {
            var right = new Node(x + 1, y);
            neighbours.Add(right);
        }

        if (y + 1 < height)
        {
            var top = new Node(x, y + 1);
            neighbours.Add(top);
        }

        if (y > 0)
        {
            var bottom = new Node(x, y - 1);
            neighbours.Add(bottom);
        }
        return neighbours;
    }

    void SpawnPlayer()
    {
        var location = new Vector3(startingCell.X, startingCell.Y, 0);
        Instantiate(playerPrefab, location, Quaternion.identity, transform);
    }

    void SpawnGoal()
    {
        var location = new Vector3(finalCell.X, finalCell.Y, 0);
        Instantiate(goalPrefab, location, Quaternion.identity, transform);
    }

    Node StartingCell()
    {
        int x = UnityEngine.Random.Range(0, width);
        int y = UnityEngine.Random.Range(0, height);
        return new Node(x, y);
    }

    public readonly struct Node
    {
        public Node(int _x, int _y)
        {
            X = _x;
            Y = _y;
        }
        public int X { get; }
        public int Y { get; }

        public override string ToString() => $"({X}, {Y})";
    }

    Direction TravelDirection(Node a, Node b)
    {
        if (a.X - b.X > 0)
        {
            return Direction.Left;
        }

        if (a.X - b.X < 0)
        {
            return Direction.Right;
        }

        if (a.Y - b.Y > 0)
        {
            return Direction.Down;
        }

        return Direction.Up;
    }

    void DeleteCorrespondingWall(Direction dir, Node a, Node b)
    {
        GameObject wallObj = null;

        if (dir == Direction.Left)
        {
            wallObj = upWalls[a.X, a.Y];
        }

        if (dir == Direction.Right)
        {
            wallObj = upWalls[b.X, b.Y];
        }

        if (dir == Direction.Up)
        {
            wallObj = acrossWalls[b.X, b.Y];
        }

        if (dir == Direction.Down)
        {
            wallObj = acrossWalls[a.X, a.Y];
        }
        Destroy(wallObj.gameObject);
    }

    public enum Direction
    {
        Up,
        Down,
        Left,
        Right,
    }
}