Collision detection for maze generation

Trying to create a procedurally generate maze but having difficulties getting the collision detection to work when attempting to place pieces of the maze. Any pointers would be greatly appreciated as this has been driving me mad.

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

public class Generate : MonoBehaviour, Interactable
{
    private Renderer buttonRenderer;

    public GameObject tShapePrefab;
    public GameObject plusShapePrefab;
    public GameObject lShapePrefab;
    public GameObject iShapePrefab;

    public GameObject platform;

    public Transform playerTransform;

    private int maxPieces = 3;
    private int currentPieces = 0;
    private int maxAttemptsPerPiece = 20;

    private Vector3 spawnPosition = new Vector3(10, 10, 20);
    private Quaternion rotation;

    private List<Vector3> openEnds = new List<Vector3>();
    private List<Vector3> tempOpenEnds = new List<Vector3>();
    private List<Vector3> remainingOpenEnds = new List<Vector3>();
    private List<Vector3> deadOpenEnds = new List<Vector3>();

    private int layerMask;

    void Start() {
        layerMask = LayerMask.GetMask("whatIsGround");

        buttonRenderer = GetComponent<Renderer>();
    }

    public void Interact() {
        StartCoroutine(InteractRoutine());
    }

    private IEnumerator InteractRoutine() {
        // GetInitialSpawn(platform);

        (GameObject newPiece, List<Vector3> pieceOpenEnds, Vector3 selectedEnd) = GetPieceAndEnd();
        bool piecePlaced = TryPlacePiece(newPiece, selectedEnd);

        if (piecePlaced) {
            UpdateOpenEnds(newPiece, pieceOpenEnds, selectedEnd);
            currentPieces++;

            Debug.Log("Piece no. 1: " + newPiece.name);

            openEnds.Clear();
            openEnds.AddRange(tempOpenEnds);
            tempOpenEnds.Clear();
        } else {
            Destroy(newPiece);
            Debug.LogWarning("Initial piece could not be placed");
        }

        bool skip = false;
        int maxmax = 0;

        while (currentPieces <= maxPieces && maxmax < 1000) {
            foreach (Vector3 end in openEnds) {
                if (skip) {
                    remainingOpenEnds.Add(end);

                    continue;
                }

                if (currentPieces == maxPieces) {
                    remainingOpenEnds.Add(end);

                    skip = true;
                    currentPieces = maxPieces + 1;

                    continue;
                }

                spawnPosition = end;

                int attemptCounter = 0;
                piecePlaced = false;

                while (!piecePlaced && attemptCounter < maxAttemptsPerPiece) {
                    (newPiece, pieceOpenEnds, selectedEnd) = GetPieceAndEnd();

                    piecePlaced = TryPlacePiece(newPiece, selectedEnd);

                    if (piecePlaced) {
                        UpdateOpenEnds(newPiece, pieceOpenEnds, selectedEnd);

                        currentPieces++;
                        piecePlaced = true;

                        Debug.Log("Piece no. " + currentPieces + ": " + newPiece.name);

                    } else {
                        Destroy(newPiece);
                        attemptCounter++;

                        yield return null;
                    }
                }

                if (attemptCounter == maxAttemptsPerPiece) {
                    deadOpenEnds.Add(end);
                }
            }

            if (!skip) {
                openEnds.Clear();
                openEnds.AddRange(tempOpenEnds);
                tempOpenEnds.Clear();
            } else {
                openEnds.AddRange(remainingOpenEnds);
            }

            maxmax++;
            if (maxmax >= 1000) {
                Debug.LogWarning("Generator timed out");
            }
        }

        openEnds.AddRange(deadOpenEnds);
    }

    /* Select a semi-random piece from the prefab options */

    private GameObject SelectRandomPiece() {
        // Define pieces and their probabilities
        var pieceProbabilities = new Dictionary<GameObject, int> {
            { plusShapePrefab, 10 },
            { iShapePrefab, 40 },
            { lShapePrefab, 30 },
            { tShapePrefab, 20 }
        };

        // Calculate total probability
        int totalProbability = 0;
        foreach (int probability in pieceProbabilities.Values) {
            totalProbability += probability;
        }

        // Generate a random number between 0 and totalProbability
        int randomValue = Random.Range(0, totalProbability);

        // Select the piece based on cumulative probability
        int cumulative = 0;
        foreach (var kvp in pieceProbabilities) {
            cumulative += kvp.Value;

            if (randomValue < cumulative) {
                return kvp.Key;
            }
        }

        // Fallback (should never hit this if probabilities are correct)
        return iShapePrefab;
    }

    /* Retrieve all open ends from the selected prefab */

    private List<Vector3> GetOpenEnds(GameObject piece) {
        List<Vector3> pieceOpenEnds = new List<Vector3>();

        foreach (Transform child in piece.transform) {
            if (child.CompareTag("Open End")) {
                pieceOpenEnds.Add(child.localPosition);
            }
        }

        return pieceOpenEnds;
    }

    /* Keep up to date list on all remaining open ends (dead ends) */

    private void UpdateOpenEnds(GameObject piece, List<Vector3> pieceOpenEnds, Vector3 selectedEnd) {
        Vector3 absolutePosition;

        foreach (Vector3 openEnd in pieceOpenEnds) {
            if (openEnd != selectedEnd) {
                absolutePosition = piece.transform.TransformPoint(openEnd);
                tempOpenEnds.Add(absolutePosition);
            }
        }
    }

    /* Try placing a piece, ensuring no collision takes place */

    private bool TryPlacePiece(GameObject piece, Vector3 selectedEnd) {
        Vector3 selectedEndAbsolutePosition = piece.transform.TransformPoint(selectedEnd);
        Vector3 initialOffset = spawnPosition - selectedEndAbsolutePosition;

        piece.transform.position += initialOffset;

        for (int rotationAttempts = 0; rotationAttempts < 4; rotationAttempts++) {
            // Reset rotation
            piece.transform.rotation = Quaternion.identity;

            // Try new rotation
            piece.transform.RotateAround(selectedEndAbsolutePosition, Vector3.up, 90 * rotationAttempts);
            
            // Update position
            selectedEndAbsolutePosition = piece.transform.TransformPoint(selectedEnd);

            Vector3 rotationOffset = spawnPosition - selectedEndAbsolutePosition;
            piece.transform.position += rotationOffset;

            if (!CollisionCheck(piece)) {
                return true;
            }
        }

        return false;
    }

    /* Check for collisions before finalising piece position */

    private bool CollisionCheck(GameObject piece) {
        Collider collider = piece.GetComponentInChildren<Collider>();

        // Temporarily disable collider to avoid self-collision
        collider.enabled = false;

        // Calculate bounds
        Bounds pieceBounds = collider.bounds;
        Vector3 center = pieceBounds.center + piece.transform.position;
        Vector3 extents = pieceBounds.extents + Vector3.one * 1.0f;

        // Check for collisions
        Collider[] hitColliders = Physics.OverlapBox(center, extents, piece.transform.rotation, layerMask, QueryTriggerInteraction.Ignore);

        Debug.Log("Current: " + currentPieces + "===============================");
        foreach (Collider hitCollider in hitColliders) {
            Debug.Log(piece.gameObject.name + " collided with " + hitCollider.gameObject.name);
        }
        Debug.Log("===================================================================");

        // Re-enable collider
        collider.enabled = true;
        
        // Detect if other objects are colliding
        foreach (Collider hitCollider in hitColliders) {
            if (hitCollider.gameObject != piece) {
                return true;
            }
        }

        // Re-enable collider
        return false;
    }

    private void OnDrawGizmos() {
    if (Application.isPlaying) {
        // Get only active maze pieces with a specific tag or layer
        GameObject[] mazePieces = GameObject.FindGameObjectsWithTag("Maze Piece");

        foreach (GameObject piece in mazePieces) {
            Collider collider = piece.GetComponentInChildren<Collider>();

            if (collider != null) {
                Bounds pieceBounds = collider.bounds;
                Vector3 center = pieceBounds.center;
                Vector3 size = pieceBounds.size;

                Gizmos.color = Color.red;
                Gizmos.matrix = Matrix4x4.TRS(center, Quaternion.identity, Vector3.one);
                Gizmos.DrawWireCube(Vector3.zero, size);
            }
        }
    }
}


    /* Function to avoid repeating code */

    private (GameObject, List<Vector3>, Vector3) GetPieceAndEnd() {
        GameObject selectedPrefab = SelectRandomPiece();
        GameObject newPiece = Instantiate(selectedPrefab, spawnPosition, Quaternion.identity);

        List<Vector3> pieceOpenEnds = GetOpenEnds(newPiece);
        Vector3 selectedEnd = pieceOpenEnds[Random.Range(0, pieceOpenEnds.Count)];

        return (newPiece, pieceOpenEnds, selectedEnd);
    }

    /* Subject to change depending on what the game needs */
    
    private void GetInitialSpawn(GameObject plane) {
        Vector3 position = plane.transform.position;
        Vector3 scale = plane.transform.localScale;
        Quaternion rotation = plane.transform.rotation;

        float halfWidth = 5f * scale.x;
        float halfHeight = 5f * scale.z;

        Vector3 topLeft = new Vector3(-halfWidth, 0, halfHeight);
        Vector3 topRight = new Vector3(halfWidth, 0, halfHeight);

        topLeft = position + rotation * topLeft;
        topRight = position + rotation * topRight;

        spawnPosition = new Vector3((topLeft.x + topRight.x) / 2, topLeft.y, topLeft.z);
    }
}

Some added context for the prefab structure (with tShapePrefab as example):

tShapePrefab
→ Shape (contains mesh renderer, mesh collider)
→ OpenEnd_1
→ OpenEnd_2
→ OpenEnd_3

Have tried with both mesh and box colliders, both lead to bugs or perhaps I am completely misusing them.

You don’t use collision for this sort of thing. A maze can be expressed purely as simple data, and this data can be used to determine where walls are, etc. You generate the maze data, then you build the visual representation via this data.

I’ve not done proc-gen for a maze, but you’d just need a grid of structs/classes that define a position, and where walls are (north, east, south, west).

Or you could have two grids. One of a set of points with connections between points (the walls), and the grid for the positions within the maze itself. In either case, the data can tell you all this without the need for physics or collisions.

Maybe maze was the wrong word. I’m aiming more so for a tunnel where it branches out in all directions, so creating a maze out of data stored in a grid might feel limiting in that regard. I have already tried the various maze generation algorithms out there but they all feel too obviously maze-like instead of a tunnel. So if I was to pursue my current method, is there anything I should work on?

The same concept of working with data first still applies. You make your own data structure that you have full control over. Doesn’t have to be a grid, can be anything. You build up your data, then make your visual representation.

It’s a tried and tested method.

Otherwise if you want to continue with the current method, it’s really a matter of debugging it.

I think you should read the documentation on Collider.bounds though: Unity - Scripting API: Collider.bounds

Note that this will be an empty bounding box if the collider is disabled or the game object is inactive.

You disable the collider before you get the bounds, so your overlap box is always going to fail. That’s the only thing that sounds out to me at a glance. Anything else you should debug on your end.

1 Like