Maze Generation Assignment

Tech Stack: Unity, Visual Studio, Github

The Assignment

This project was a solo project I decided to make in my free time. I got the idea from reddit when browsing the algorithm and computer forums. For the generation I used Depth First Search to make the maze. I Implemented this in Unity 2022 and I think this is quite a nice portfolio piece hence why I have made a page for this. For performance reasons I decided to limit the maze to 100 x 100 so that the program would not lag enormously when viewed on less powerful devices. I implemented the GUI and the Camera Behaviour so that this application could be run on mobile devices as well.

Code Highlights

/// <summary>
/// Function called when forming path to delete _walls that interfere with the path direction
/// </summary>
/// <param name="wallToRemove"></param>
public void RemoveWall(int wallToRemove)
{
    if (_walls[wallToRemove])
    {
        _walls[wallToRemove].SetActive(false);
    }
}

/// <summary>
/// Function to set states/colors of the cell to indicate where the algorithm is currently working
/// </summary>
/// <param name="state"></param>
public void SetState(NodeState state)
{
    switch (state) {
        case NodeState.Available:
            _meshRenderer.material.color = Color.white;
            break;
        case NodeState.Current:
            _meshRenderer.material.color = Color.yellow;
            break;
        case NodeState.Completed:
            _meshRenderer.material.color = Color.blue;
            break;
    }
}

Explanation:
This code is responsible for helping manage maze generation. Key features of this code include:
Remove Wall Function:

The ‘RemoveWall‘ function plays a crucial role in maze generation. Given a wall index (‘wallToRemove‘), it deactivates the corresponding wall GameObject within the maze. This function is essential for creating open paths during maze generation.

Set State Function:

The ‘SetState‘ function dynamically adjusts the visual representation of a maze node based on its state during a pathfinding algorithm.

Supports different states:

Available: Represents an open node, painted in white.

Current: Indicates the node the algorithm is currently processing, painted in yellow.

Completed: Marks nodes that have been visited and processed, painted in blue.

//till there are no more unvisited _nodes left
while (completedNodes.Count < _nodes.Count)
{
    // Check _nodes next to the current node
    List<int> possibleNextNodes = new();
    List<int> possibleDirections = new();

    //gets the index of the current node from the _nodes list
    int currentNodeIndex = _nodes.IndexOf(currentPath[^1]);//^1 == currentPath.Count - 1
    //get the x & y of the current node
    int currentNodeX = CalculateXPos(currentNodeIndex, size);
    int currentNodeY = CalculateYPos(currentNodeIndex ,size);

    //Check neighbour node on the right
    if (currentNodeX < size.x - 1) {
        //Check if the current node isn't already in the complete node list or currentpath list
        if (!completedNodes.Contains(_nodes[currentNodeIndex + size.y]) && !currentPath.Contains(_nodes[currentNodeIndex + size.y]))
        {
            possibleDirections.Add(1);
            possibleNextNodes.Add(currentNodeIndex + size.y);
        }
    }
    //Check neighbour node on the left
    if (currentNodeX > 0) {
        if (!completedNodes.Contains(_nodes[currentNodeIndex - size.y]) && !currentPath.Contains(_nodes[currentNodeIndex - size.y]))
        {
            possibleDirections.Add(2);
            possibleNextNodes.Add(currentNodeIndex - size.y);
        }
    }
    //Check neighbour node above current node
    if (currentNodeY < size.y - 1) {
        if (!completedNodes.Contains(_nodes[currentNodeIndex + 1]) && !currentPath.Contains(_nodes[currentNodeIndex + 1]))
        {
            possibleDirections.Add(3);
            possibleNextNodes.Add(currentNodeIndex + 1);
        }
    }
    //Check neighbour node under current node
    if (currentNodeY > 0) {
        if (!completedNodes.Contains(_nodes[currentNodeIndex - 1]) && !currentPath.Contains(_nodes[currentNodeIndex - 1]))
        {
            possibleDirections.Add(4);
            possibleNextNodes.Add(currentNodeIndex - 1);
        }
    }

    //If the algorithm has any unvisited neighbours
    if (possibleDirections.Count > 0)
    {
        int chosenDirection = Random.Range(0, possibleDirections.Count);
        Tile chosenNode = _nodes[possibleNextNodes[chosenDirection]];

        //Remove wall on the side the next chosen cell is going to be
        switch (possibleDirections[chosenDirection])
        {
            case 1://right
                //remove wall on current node
                chosenNode.RemoveWall(0);
                //remove wall on next node
                currentPath[^1].RemoveWall(1);
                break;
            case 2://left
                chosenNode.RemoveWall(1);
                currentPath[^1].RemoveWall(0);
                break;
            case 3://up
                chosenNode.RemoveWall(3);
                currentPath[^1].RemoveWall(2);
                break;
            case 4://down
                chosenNode.RemoveWall(2);
                currentPath[^1].RemoveWall(3);
                break;
        }

        //add neighbor node chosen to path list
        currentPath.Add(chosenNode);
        //change the state/color of the chosenNode to yellow
        chosenNode.SetState(NodeState.Current);
    }
    //if there are no more neighbours available that are unvisited
    else
    {
        //add node to completed list
        completedNodes.Add(currentPath[^1]);

        //set state/color to blue to mark cell as completer (will not visited anymore)
        currentPath[^1].SetState(NodeState.Completed);
        //remove the completed node
        currentPath.RemoveAt(currentPath.Count - 1);
    }
}

The ‘GenerateMaze‘ function employs a randomized maze generation algorithm. It starts by initializing a set of nodes and then iteratively explores and connects these nodes until the entire maze is formed.
Iterative Exploration:

Iterates until all nodes are visited.

Checks neighbors of the current node and identifies unvisited neighbors.

Randomly selects one of the unvisited neighbors and connects it to the current node by removing the wall between them.

Updates the state/color of the chosen neighbor to indicate it‘s the new current node.

Backtracking:

If the current node has no unvisited neighbors, backtracks by marking the current node as completed.

Sets the state/color of the completed node to blue, indicating it has been processed and will not be revisited.

Removes the completed node from the current path.

Visual Representation:

The algorithm dynamically adjusts the color and state of nodes in the maze to provide a visual representation of the maze generation process. Current nodes are shown in yellow, completed nodes in blue, and available nodes in white.

Reflection On The Project

This project was pretty hard to start, but I don‘t back away from challenges! From the beginning to the end I had to think real hard to progress the project. Since this was one of the first time I have had to generate things from scratch in Unity. But when actually thinking clearly about it, I eventually got to the root of the problems I encountered and managed to finish this project on time. I would like to use texture displaying instead of objects if I give it another go. But that is for another time.