MazeWalkerTv-try2/Assets/Scripts/Maze/Generation/MazeGenerator.cs

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

namespace MazeGen
{
    /// <summary>
    /// Owns the MazeGraph and knows how to grow it one room at a time, on demand
    /// (i.e. lazily - a room beyond an exit only exists once something actually
    /// walks through that exit). This is what makes "huge quantity of rooms" cheap:
    /// nothing is generated until it's needed.
    /// </summary>
    public class MazeGenerator : MonoBehaviour
    {
        private static readonly float[] CardinalAngles = { 0f, 90f, 180f, 270f };

        [SerializeField] private MazeGenerationSettings settings;

        private MazeGraph _graph;

        public MazeGraph Graph => _graph;

        /// <summary>Fired whenever a new room (including start rooms) is created.</summary>
        public event Action<Room> RoomGenerated;

        /// <summary>Fired whenever an exit is resolved to a connected room (new room, or a connection into an existing one).</summary>
        public event Action<Room, Exit, Room> RoomsConnected;

        /// <summary>Fired when a door is added to an already-registered room after the fact (see TryConnectViaExistingDoor), so its marker can be spawned.</summary>
        public event Action<Room, Exit> ExitAdded;

        private void Awake()
        {
            if (settings == null)
                settings = ScriptableObject.CreateInstance<MazeGenerationSettings>();

            _graph = new MazeGraph(settings.roomSpacing);
        }

        public Room GenerateStartRoom(Vector2 position)
        {
            int exitCount = UnityEngine.Random.Range(settings.minExitsPerRoom, settings.maxExitsPerRoom + 1);
            var angles = PickCardinalAngles(exitCount, null);

            var room = new Room(_graph.AllocateRoomId(), RoomKind.Start, position, settings.startRoomRadius, 0);
            foreach (var angle in angles)
                _graph.AddExit(room, new Exit { Id = _graph.AllocateExitId(), OwnerRoomId = room.Id, DirectionDegrees = angle });

            _graph.Register(room);
            RoomGenerated?.Invoke(room);
            return room;
        }

        /// <summary>
        /// Resolves an exit: if it already leads somewhere, returns that room. Otherwise first
        /// checks whether the spawn spot would overlap an existing room that has an unused door
        /// facing back toward fromRoom - if so, connects into that door (straight, or via a
        /// single 90-degree elbow hallway) instead of creating a new, overlapping room. Failing
        /// that, if the spawn spot overlaps anything, the candidate room is nudged to a nearby
        /// clear spot. Either way, the two-way connection is wired up before returning.
        /// </summary>
        public Room GenerateConnectedRoom(Room fromRoom, Exit fromExit, MazeAgent agent)
        {
            if (fromExit.ConnectedRoomId.HasValue)
                return _graph.Get(fromExit.ConnectedRoomId.Value);

            RoomKind kind = DecideNextRoomKind(agent);
            float entryAngle = NormalizeAngle(fromExit.DirectionDegrees + 180f);
            Vector2 position = fromRoom.Position + fromExit.Direction * settings.roomSpacing;
            float radius = RadiusFor(kind);

            Room connectedThroughDoor = TryConnectViaExistingDoor(fromRoom, fromExit, position, radius);
            if (connectedThroughDoor != null)
                return connectedThroughDoor;

            if (HasOverlap(position, radius, fromRoom.Id))
            {
                if (TryRouteAroundObstruction(fromRoom, fromExit, radius, out Vector2 routedPosition, out Vector2? bendCorner, out float routedEntryAngle))
                {
                    if (bendCorner.HasValue)
                        return CreateRoomViaBend(fromRoom, fromExit, kind, bendCorner.Value, routedPosition, radius, routedEntryAngle);

                    position = routedPosition;
                    entryAngle = routedEntryAngle;
                }
                else
                {
                    position = FindClearPosition(position, radius, fromRoom.Id);
                }
            }

            return BuildRoom(kind, position, radius, fromRoom.DepthFromStart + 1, fromRoom, fromExit, entryAngle);
        }

        /// <summary>
        /// Creates a room of the given kind at `position`, wires its entry door to
        /// `connectingExit` (owned by `connectingRoom`), rolls its extra exits, registers it
        /// and fires the generation/connection events. Shared by the plain straight-line
        /// spawn path and the bend-routing path (where the "connecting" side is a freshly
        /// built elbow hallway rather than fromRoom itself).
        /// </summary>
        private Room BuildRoom(RoomKind kind, Vector2 position, float radius, int depthFromStart, Room connectingRoom, Exit connectingExit, float entryAngle)
        {
            var room = new Room(_graph.AllocateRoomId(), kind, position, radius, depthFromStart);

            var entryExit = new Exit
            {
                Id = _graph.AllocateExitId(),
                OwnerRoomId = room.Id,
                DirectionDegrees = entryAngle
            };
            _graph.AddExit(room, entryExit);

            if (kind != RoomKind.Exit)
            {
                int extraExits = kind == RoomKind.Hallway
                    ? 1
                    : Mathf.Max(0, UnityEngine.Random.Range(settings.minExitsPerRoom, settings.maxExitsPerRoom + 1) - 1);

                // Safety net: never let this generation be the one that drains the maze's
                // last unused exit before an Exit room exists anywhere.
                int projectedPool = (_graph.UnusedExitCount - 1) + extraExits;
                if (projectedPool <= 0 && _graph.ExitRooms.Count == 0)
                    extraExits = Mathf.Max(extraExits, 1);

                var extraAngles = PickCardinalAngles(extraExits, entryAngle);
                foreach (var angle in extraAngles)
                    _graph.AddExit(room, new Exit { Id = _graph.AllocateExitId(), OwnerRoomId = room.Id, DirectionDegrees = angle });
            }

            ConnectExits(connectingExit, entryExit);

            _graph.Register(room);
            RoomGenerated?.Invoke(room);
            RoomsConnected?.Invoke(connectingRoom, connectingExit, room);
            return room;
        }

        /// <summary>
        /// Called only once the straight-line spawn spot is known to overlap something and no
        /// existing door offered a connection. First tries extending further out along the
        /// exit's own direction; if that never clears, tries a single 90-degree bend (to
        /// either side) at increasing distances. Each candidate is checked both for a clear
        /// footprint and a clear path leading to it. Returns false if nothing within the
        /// search range works, in which case the caller falls back to a plain nudge.
        /// </summary>
        private bool TryRouteAroundObstruction(Room fromRoom, Exit fromExit, float radius,
            out Vector2 finalPosition, out Vector2? bendCorner, out float finalEntryAngle)
        {
            Vector2 dir = fromExit.Direction;
            Vector2 edgeFrom = fromRoom.Position + dir * fromRoom.Radius;
            float straightEntryAngle = NormalizeAngle(fromExit.DirectionDegrees + 180f);

            for (int i = 0; i < settings.maxRepositionRings; i++)
            {
                float distance = settings.roomSpacing + i * settings.repositionRingStep;
                Vector2 candidate = fromRoom.Position + dir * distance;
                if (!HasOverlap(candidate, radius, fromRoom.Id) && IsPathClear(edgeFrom, candidate, fromRoom.Id, -1))
                {
                    finalPosition = candidate;
                    bendCorner = null;
                    finalEntryAngle = straightEntryAngle;
                    return true;
                }
            }

            Vector2[] perpendiculars = { new Vector2(-dir.y, dir.x), new Vector2(dir.y, -dir.x) };
            for (int i = 0; i < settings.maxRepositionRings; i++)
            {
                float cornerDistance = settings.roomSpacing + i * settings.repositionRingStep;
                Vector2 corner = fromRoom.Position + dir * cornerDistance;
                if (!IsPathClear(edgeFrom, corner, fromRoom.Id, -1)) continue;
                if (HasOverlap(corner, settings.hallwayRadius, fromRoom.Id)) continue;

                foreach (var perp in perpendiculars)
                {
                    for (int j = 0; j < settings.maxRepositionRings; j++)
                    {
                        float sideDistance = settings.roomSpacing + j * settings.repositionRingStep;
                        Vector2 candidate = corner + perp * sideDistance;
                        if (HasOverlap(candidate, radius, fromRoom.Id)) continue;
                        if (!IsPathClear(corner, candidate, fromRoom.Id, -1)) continue;

                        finalPosition = candidate;
                        bendCorner = corner;
                        finalEntryAngle = NormalizeAngle(AngleOf(perp) + 180f);
                        return true;
                    }
                }
            }

            finalPosition = fromRoom.Position + dir * settings.roomSpacing;
            bendCorner = null;
            finalEntryAngle = straightEntryAngle;
            return false;
        }

        /// <summary>
        /// Builds the elbow hallway room at `corner` connecting fromExit to it, then builds
        /// the brand-new destination room beyond the bend and wires the hallway's forward
        /// door into it. Returns the hallway - the room fromExit now immediately leads to.
        /// </summary>
        private Room CreateRoomViaBend(Room fromRoom, Exit fromExit, RoomKind kind, Vector2 corner, Vector2 finalPosition, float radius, float entryAngle)
        {
            var hallway = new Room(_graph.AllocateRoomId(), RoomKind.Hallway, corner, settings.hallwayRadius, fromRoom.DepthFromStart + 1);

            var backExit = new Exit
            {
                Id = _graph.AllocateExitId(),
                OwnerRoomId = hallway.Id,
                DirectionDegrees = NormalizeAngle(fromExit.DirectionDegrees + 180f)
            };
            var forwardExit = new Exit
            {
                Id = _graph.AllocateExitId(),
                OwnerRoomId = hallway.Id,
                DirectionDegrees = NormalizeAngle(entryAngle + 180f)
            };
            _graph.AddExit(hallway, backExit);
            _graph.AddExit(hallway, forwardExit);

            Vector2 pFrom = fromRoom.Position + fromExit.Direction * fromRoom.Radius;
            Vector2 pInto = finalPosition + DirectionFromAngle(entryAngle) * radius;
            hallway.CorridorWaypoints = new[] { pFrom, corner, pInto };

            ConnectExits(fromExit, backExit);

            _graph.Register(hallway);
            RoomGenerated?.Invoke(hallway);
            RoomsConnected?.Invoke(fromRoom, fromExit, hallway);

            BuildRoom(kind, finalPosition, radius, hallway.DepthFromStart + 1, hallway, forwardExit, entryAngle);

            return hallway;
        }

        /// <summary>
        /// Looks for an already-placed room whose footprint overlaps the candidate spawn
        /// position, on the side that faces fromRoom. Prefers an existing unused exit there;
        /// if that side simply has no door on it yet, adds one on the fly instead (not the
        /// most "logical" world - the room retroactively grows a doorway - but it closes far
        /// more loops than only ever matching pre-existing doors, and keeps rooms from just
        /// sitting on top of each other). If one is found (and the resulting path can be
        /// routed without crossing anything else), fromExit is wired into that door instead of
        /// a brand new room being created. Returns the room fromExit now leads to, or null if
        /// no overlapping room offers a usable, reachable door.
        /// </summary>
        private Room TryConnectViaExistingDoor(Room fromRoom, Exit fromExit, Vector2 candidatePosition, float candidateRadius)
        {
            float searchRadius = candidateRadius + MaxRoomRadius();
            var overlapping = new List<Room>();
            foreach (var other in _graph.QueryRoomsNear(candidatePosition, searchRadius))
            {
                if (other.Id == fromRoom.Id) continue;
                float dist = Vector2.Distance(candidatePosition, other.Position);
                if (dist > candidateRadius + other.Radius) continue; // footprints don't actually overlap
                overlapping.Add(other);
            }

            overlapping.Sort((a, b) =>
                Vector2.Distance(candidatePosition, a.Position).CompareTo(Vector2.Distance(candidatePosition, b.Position)));

            foreach (var other in overlapping)
            {
                Vector2 towardFromRoom = fromRoom.Position - other.Position;
                if (towardFromRoom.sqrMagnitude < 0.0001f) continue;
                float desiredAngle = NearestCardinal(Mathf.Atan2(towardFromRoom.y, towardFromRoom.x) * Mathf.Rad2Deg);

                Exit targetExit = null;
                foreach (var exit in other.UnusedExits)
                {
                    if (Mathf.Approximately(NormalizeAngle(exit.DirectionDegrees), desiredAngle))
                    {
                        targetExit = exit;
                        break;
                    }
                }

                bool needsNewExit = targetExit == null;
                if (needsNewExit)
                {
                    // That side's already spoken for by a different (used) door - can't add
                    // one here, this room can't be the merge target.
                    bool sideOccupied = other.Exits.Exists(e => Mathf.Approximately(NormalizeAngle(e.DirectionDegrees), desiredAngle));
                    if (sideOccupied) continue;
                }

                // A connection consumes fromExit (+ targetExit, unless it's a freshly added
                // door, which nets to zero). Refuse it if that would leave zero unused exits
                // anywhere with no Exit room placed yet - fall back to normal generation
                // instead, which always can add fresh exits.
                int exitsConsumed = needsNewExit ? 1 : 2;
                bool wouldStarveMaze = _graph.UnusedExitCount - exitsConsumed < 1 && _graph.ExitRooms.Count == 0;
                if (wouldStarveMaze) continue;

                if (needsNewExit)
                {
                    targetExit = new Exit { Id = _graph.AllocateExitId(), OwnerRoomId = other.Id, DirectionDegrees = desiredAngle };
                    _graph.AddExit(other, targetExit);
                }

                Room connected = TryBuildDoorConnection(fromRoom, fromExit, other, targetExit);
                if (connected != null)
                {
                    if (needsNewExit) ExitAdded?.Invoke(other, targetExit);
                    return connected;
                }

                // Didn't pan out (blocked path) - don't leave a dangling unusable door behind.
                if (needsNewExit)
                    _graph.RemoveUnusedExit(other, targetExit);
            }

            return null;
        }

        /// <summary>
        /// Builds the actual path between two facing doors: a direct link if they already
        /// face each other head-on, or a single 90-degree elbow hallway room if they're on
        /// perpendicular sides. Returns null (without mutating anything) if the geometry
        /// isn't supported (doors facing the same way) or the path would cross another
        /// room/hallway.
        /// </summary>
        private Room TryBuildDoorConnection(Room fromRoom, Exit fromExit, Room other, Exit targetExit)
        {
            float d1 = NormalizeAngle(fromExit.DirectionDegrees);
            float d2 = NormalizeAngle(targetExit.DirectionDegrees);
            float absDiff = Mathf.Abs(Mathf.DeltaAngle(d1, d2));

            if (Mathf.Approximately(absDiff, 180f))
                return ConnectStraight(fromRoom, fromExit, other, targetExit);

            if (Mathf.Approximately(absDiff, 90f))
                return ConnectWithElbow(fromRoom, fromExit, other, targetExit);

            // Doors facing the same direction would require a U-turn (two bends) - not
            // supported by the single-elbow hallway model.
            return null;
        }

        private Room ConnectStraight(Room fromRoom, Exit fromExit, Room other, Exit targetExit)
        {
            Vector2 pFrom = fromRoom.Position + fromExit.Direction * fromRoom.Radius;
            Vector2 pTo = other.Position + targetExit.Direction * other.Radius;
            if (!IsPathClear(pFrom, pTo, fromRoom.Id, other.Id)) return null;

            ConnectExits(fromExit, targetExit);
            RoomsConnected?.Invoke(fromRoom, fromExit, other);
            return other;
        }

        private Room ConnectWithElbow(Room fromRoom, Exit fromExit, Room other, Exit targetExit)
        {
            Vector2 pFrom = fromRoom.Position + fromExit.Direction * (fromRoom.Radius + settings.hallwayRadius);
            Vector2 pTo = other.Position + targetExit.Direction * (other.Radius + settings.hallwayRadius);

            bool fromIsHorizontal = Mathf.Abs(fromExit.Direction.x) > 0.5f;
            Vector2 corner = fromIsHorizontal ? new Vector2(pTo.x, pFrom.y) : new Vector2(pFrom.x, pTo.y);

            // The elbow must travel outward from each door, never doubling back through the
            // room it just left or approaching the target door from the wrong side.
            if (Vector2.Dot(corner - pFrom, fromExit.Direction) <= 0f) return null;
            if (Vector2.Dot(pTo - corner, -targetExit.Direction) <= 0f) return null;

            if (!IsPathClear(pFrom, corner, fromRoom.Id, other.Id)) return null;
            if (!IsPathClear(corner, pTo, fromRoom.Id, other.Id)) return null;
            if (HasOverlap(corner, settings.hallwayRadius, fromRoom.Id, other.Id)) return null;

            var hallway = new Room(_graph.AllocateRoomId(), RoomKind.Hallway, corner, settings.hallwayRadius, fromRoom.DepthFromStart + 1);

            var backExit = new Exit
            {
                Id = _graph.AllocateExitId(),
                OwnerRoomId = hallway.Id,
                DirectionDegrees = NormalizeAngle(fromExit.DirectionDegrees + 180f)
            };
            var forwardExit = new Exit
            {
                Id = _graph.AllocateExitId(),
                OwnerRoomId = hallway.Id,
                DirectionDegrees = NormalizeAngle(targetExit.DirectionDegrees + 180f)
            };
            _graph.AddExit(hallway, backExit);
            _graph.AddExit(hallway, forwardExit);
            hallway.CorridorWaypoints = new[] { pFrom, corner, pTo };

            ConnectExits(fromExit, backExit);
            ConnectExits(forwardExit, targetExit);

            _graph.Register(hallway);
            RoomGenerated?.Invoke(hallway);
            RoomsConnected?.Invoke(fromRoom, fromExit, hallway);
            return hallway;
        }

        /// <summary>True if any registered room (other than those excluded) overlaps a circle at position/radius.</summary>
        private bool HasOverlap(Vector2 position, float radius, params int[] excludeRoomIds)
        {
            float searchRadius = radius + MaxRoomRadius();
            foreach (var room in _graph.QueryRoomsNear(position, searchRadius))
            {
                if (Array.IndexOf(excludeRoomIds, room.Id) >= 0) continue;
                if (Vector2.Distance(position, room.Position) <= radius + room.Radius) return true;
            }
            return false;
        }

        /// <summary>True if the straight segment a-b stays clear of every room's footprint (other than those excluded), with a small buffer.</summary>
        private bool IsPathClear(Vector2 a, Vector2 b, int excludeRoomId1, int excludeRoomId2)
        {
            Vector2 mid = (a + b) * 0.5f;
            float searchRadius = Vector2.Distance(a, b) * 0.5f + MaxRoomRadius() + settings.hallwayRadius;

            foreach (var room in _graph.QueryRoomsNear(mid, searchRadius))
            {
                if (room.Id == excludeRoomId1 || room.Id == excludeRoomId2) continue;
                float distToSegment = DistancePointToSegment(room.Position, a, b);
                float requiredClearance = room.Radius + settings.hallwayRadius + settings.hallwayClearance;
                if (distToSegment < requiredClearance) return false;
            }
            return true;
        }

        private static float DistancePointToSegment(Vector2 p, Vector2 a, Vector2 b)
        {
            Vector2 ab = b - a;
            float lengthSq = ab.sqrMagnitude;
            if (lengthSq < 0.0001f) return Vector2.Distance(p, a);

            float t = Mathf.Clamp01(Vector2.Dot(p - a, ab) / lengthSq);
            Vector2 closest = a + ab * t;
            return Vector2.Distance(p, closest);
        }

        /// <summary>
        /// Searches outward in a ring pattern around `origin` for the nearest spot where a
        /// room of `radius` wouldn't overlap anything already placed, so an overlapping spawn
        /// can be nudged aside instead of just sitting on top of another room.
        /// </summary>
        private Vector2 FindClearPosition(Vector2 origin, float radius, int excludeRoomId)
        {
            for (int ring = 1; ring <= settings.maxRepositionRings; ring++)
            {
                float ringRadius = ring * settings.repositionRingStep;
                for (int i = 0; i < settings.repositionSamplesPerRing; i++)
                {
                    float angle = (360f / settings.repositionSamplesPerRing) * i;
                    Vector2 offset = new Vector2(Mathf.Cos(angle * Mathf.Deg2Rad), Mathf.Sin(angle * Mathf.Deg2Rad)) * ringRadius;
                    Vector2 candidate = origin + offset;
                    if (!HasOverlap(candidate, radius, excludeRoomId))
                        return candidate;
                }
            }

            Debug.LogWarning("[MazeGen] Could not find a collision-free spot for an overlapping room; leaving it at its original (overlapping) position.");
            return origin;
        }

        private void ConnectExits(Exit a, Exit b)
        {
            _graph.MarkExitUsed(a);
            _graph.MarkExitUsed(b);
            a.ConnectedRoomId = b.OwnerRoomId;
            a.ConnectedExitId = b.Id;
            b.ConnectedRoomId = a.OwnerRoomId;
            b.ConnectedExitId = a.Id;
        }

        private RoomKind DecideNextRoomKind(MazeAgent agent)
        {
            bool eligible = agent.NewRoomsVisited >= settings.minNewRoomsBeforeExitEligible;
            bool mustForce = agent.NewRoomsVisited >= settings.forceExitAfterNewRooms && _graph.ExitRooms.Count == 0;

            if (mustForce) return RoomKind.Exit;
            if (eligible && UnityEngine.Random.value < settings.exitRoomChanceOnceEligible) return RoomKind.Exit;
            if (UnityEngine.Random.value < settings.hallwayChance) return RoomKind.Hallway;
            return RoomKind.Normal;
        }

        private float RadiusFor(RoomKind kind)
        {
            switch (kind)
            {
                case RoomKind.Start: return settings.startRoomRadius;
                case RoomKind.Hallway: return settings.hallwayRadius;
                case RoomKind.Exit: return settings.exitRoomRadius;
                default: return settings.normalRoomRadius;
            }
        }

        private float MaxRoomRadius() => Mathf.Max(
            Mathf.Max(settings.startRoomRadius, settings.normalRoomRadius),
            Mathf.Max(settings.hallwayRadius, settings.exitRoomRadius));

        /// <summary>
        /// Picks up to `count` distinct cardinal directions (N/E/S/W), excluding the reserved
        /// angle (the entry door) if given, in random order. Since a room can only have one
        /// exit per side, this returns fewer than `count` if not enough free sides remain.
        /// </summary>
        private List<float> PickCardinalAngles(int count, float? reservedAngle)
        {
            var available = new List<float>(CardinalAngles);
            if (reservedAngle.HasValue)
                available.RemoveAll(a => Mathf.Approximately(NormalizeAngle(a), NormalizeAngle(reservedAngle.Value)));

            for (int i = available.Count - 1; i > 0; i--)
            {
                int j = UnityEngine.Random.Range(0, i + 1);
                (available[i], available[j]) = (available[j], available[i]);
            }

            return available.GetRange(0, Mathf.Min(count, available.Count));
        }

        private static float NearestCardinal(float angleDegrees)
        {
            float normalized = NormalizeAngle(angleDegrees);
            float best = CardinalAngles[0];
            float bestDiff = float.MaxValue;
            foreach (var cardinal in CardinalAngles)
            {
                float diff = Mathf.Abs(Mathf.DeltaAngle(normalized, cardinal));
                if (diff < bestDiff)
                {
                    bestDiff = diff;
                    best = cardinal;
                }
            }
            return best;
        }

        private static float NormalizeAngle(float angle)
        {
            angle %= 360f;
            if (angle < 0f) angle += 360f;
            return angle;
        }

        private static float AngleOf(Vector2 v) => NormalizeAngle(Mathf.Atan2(v.y, v.x) * Mathf.Rad2Deg);

        private static Vector2 DirectionFromAngle(float degrees) =>
            new Vector2(Mathf.Cos(degrees * Mathf.Deg2Rad), Mathf.Sin(degrees * Mathf.Deg2Rad));
    }
}