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;
        public MazeGenerationSettings Settings => settings;

        /// <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, tries routing around it via cardinal
        /// directions. If all cardinal routing fails, retries TryConnectViaExistingDoor with a
        /// much wider search radius. If that also fails, marks the exit as blocked and returns
        /// null (agent will pick a different exit next decision tick).
        /// </summary>
        public Room GenerateConnectedRoom(Room fromRoom, Exit fromExit, MazeAgent agent)
        {
            if (fromExit.ConnectedRoomId.HasValue)
                return _graph.Get(fromExit.ConnectedRoomId.Value);

            RoomKind kind = DecideNextRoomKind(agent, fromRoom);
            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
                {
                    // Routing failed - try one more time with a much wider search in TryConnectViaExistingDoor
                    float extraSearchRadius = settings.maxRouteSearchSteps * settings.repositionRingStep;
                    Room wideConnected = TryConnectViaExistingDoorWidened(fromRoom, fromExit, position, radius, extraSearchRadius);
                    if (wideConnected != null)
                        return wideConnected;

                    // All options exhausted - mark the exit as blocked and refuse to generate
                    Debug.LogError($"[MazeGen] Could not find any collision-free, path-clear spot for a room beyond room {fromRoom.Id}'s exit {fromExit.Id} even after widening the search. Blocking this exit permanently.");
                    fromExit.IsBlocked = true;
                    return null;
                }
            }

            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 this branch's
                // last unused exit before an Exit room exists anywhere in it. Scoped to
                // connectingRoom's own connected component - a different, disconnected branch
                // already having an exit doesn't help this one.
                int projectedPool = _graph.ComponentUnusedExitCount(connectingRoom.Id) - 1 + extraExits;
                if (projectedPool <= 0 && !_graph.ComponentHasExit(connectingRoom.Id))
                    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.maxRouteSearchSteps; i++)
            {
                float distance = settings.roomSpacing + i * settings.repositionRingStep;
                Vector2 candidate = fromRoom.Position + dir * distance;
                if (!HasOverlap(candidate, radius, fromRoom.Id) && IsPathClear(edgeFrom, candidate, settings.hallwayRadius, 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.maxRouteSearchSteps; i++)
            {
                float cornerDistance = settings.roomSpacing + i * settings.repositionRingStep;
                Vector2 corner = fromRoom.Position + dir * cornerDistance;
                if (!IsPathClear(edgeFrom, corner, settings.hallwayRadius, fromRoom.Id, -1)) continue;
                if (HasOverlap(corner, settings.hallwayRadius, fromRoom.Id)) continue;

                foreach (var perp in perpendiculars)
                {
                    for (int j = 0; j < settings.maxRouteSearchSteps; j++)
                    {
                        float sideDistance = settings.roomSpacing + j * settings.repositionRingStep;
                        Vector2 candidate = corner + perp * sideDistance;
                        if (HasOverlap(candidate, radius, fromRoom.Id)) continue;
                        if (!IsPathClear(corner, candidate, settings.hallwayRadius, 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>
        /// <summary>
        /// Last-resort version of TryConnectViaExistingDoor: searches with a much larger radius
        /// to find *any* room that can be reached and merged, not just ones overlapping the
        /// immediate candidate spot.
        /// </summary>
        private Room TryConnectViaExistingDoorWidened(Room fromRoom, Exit fromExit, Vector2 candidatePosition, float candidateRadius, float extraSearchRadius)
        {
            float searchRadius = candidateRadius + MaxRoomRadius() + extraSearchRadius;
            var candidates = new List<Room>();
            foreach (var other in _graph.QueryRoomsNear(fromRoom.Position, searchRadius))
            {
                if (other.Id == fromRoom.Id) continue;
                candidates.Add(other);
            }

            // Sort by distance to fromRoom position (try nearest first)
            candidates.Sort((a, b) => Vector2.Distance(fromRoom.Position, a.Position).CompareTo(Vector2.Distance(fromRoom.Position, b.Position)));

            foreach (var other in candidates)
            {
                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)
                {
                    bool sideOccupied = other.Exits.Exists(e => Mathf.Approximately(NormalizeAngle(e.DirectionDegrees), desiredAngle));
                    if (sideOccupied) continue;
                    if (other.Exits.Count >= settings.maxExitsPerRoom) continue;
                }

                int exitsConsumed = needsNewExit ? 1 : 2;
                if (WouldStarveComponent(fromRoom, other, exitsConsumed)) 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;
                }

                if (needsNewExit)
                    _graph.RemoveUnusedExit(other, targetExit);
            }

            return null;
        }

        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;
                if (!SquaresOverlap(candidatePosition, candidateRadius, other.Position, other.Radius)) continue;
                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;

                    // Respect the configured per-room exit cap even for doors added on the fly.
                    if (other.Exits.Count >= settings.maxExitsPerRoom) continue;
                }

                // A connection consumes fromExit (+ targetExit, unless it's a freshly added
                // door, which nets to zero). Refuse it if that would leave the merged
                // component (fromRoom's + other's, which this connection is about to join)
                // with zero unused exits and no Exit room in it - fall back to normal
                // generation instead, which always can add fresh exits.
                int exitsConsumed = needsNewExit ? 1 : 2;
                if (WouldStarveComponent(fromRoom, other, exitsConsumed)) 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)
        {
            // Defensive check: the two rooms shouldn't already overlap
            if (SquaresOverlap(fromRoom.Position, fromRoom.Radius, other.Position, other.Radius))
            {
                Debug.LogWarning($"[MazeGen] ConnectStraight refused: room {fromRoom.Id} and room {other.Id} already overlap.");
                return null;
            }

            Vector2 pFrom = fromRoom.Position + fromExit.Direction * fromRoom.Radius;
            Vector2 pTo = other.Position + targetExit.Direction * other.Radius;
            if (!IsPathClear(pFrom, pTo, settings.hallwayRadius, 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, settings.hallwayRadius, fromRoom.Id, other.Id)) return null;
            if (!IsPathClear(corner, pTo, settings.hallwayRadius, 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 or corridor segment (other than those excluded) overlaps a square 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 (SquaresOverlap(position, radius, room.Position, room.Radius)) return true;
            }
            foreach (var seg in _graph.QueryCorridorSegmentsNear(position, radius))
            {
                if (Array.IndexOf(excludeRoomIds, seg.OwnerRoomId) >= 0) continue;
                if (SquareOverlapsRect(position, radius, seg.Min, seg.Max)) return true;
            }
            return false;
        }

        /// <summary>True if the axis-aligned corridor rectangle from a to b (thickness 2*halfWidth) stays clear of every room's square footprint and every other registered corridor segment (other than those excluded).</summary>
        private bool IsPathClear(Vector2 a, Vector2 b, float halfWidth, int excludeRoomId1, int excludeRoomId2)
        {
            Vector2 min = new Vector2(Mathf.Min(a.x, b.x), Mathf.Min(a.y, b.y));
            Vector2 max = new Vector2(Mathf.Max(a.x, b.x), Mathf.Max(a.y, b.y));

            // Pad only in the thin (perpendicular) axis
            if (Mathf.Approximately(min.y, max.y))
            {
                min.y -= halfWidth;
                max.y += halfWidth;
            }
            else
            {
                min.x -= halfWidth;
                max.x += halfWidth;
            }

            // Add clearance buffer
            min -= Vector2.one * settings.hallwayClearance;
            max += Vector2.one * settings.hallwayClearance;

            Vector2 mid = (a + b) * 0.5f;
            float searchRadius = Vector2.Distance(a, b) * 0.5f + MaxRoomRadius() + halfWidth + settings.hallwayClearance;

            foreach (var room in _graph.QueryRoomsNear(mid, searchRadius))
            {
                if (room.Id == excludeRoomId1 || room.Id == excludeRoomId2) continue;
                if (SquareOverlapsRect(room.Position, room.Radius, min, max)) return false;
            }
            foreach (var seg in _graph.QueryCorridorSegmentsNear(mid, searchRadius))
            {
                if (seg.OwnerRoomId == excludeRoomId1 || seg.OwnerRoomId == excludeRoomId2) continue;
                if (RectsOverlap(min, max, seg.Min, seg.Max)) return false;
            }
            return true;
        }

        // AABB overlap primitives (axis-aligned, since all directions are cardinal)

        /// <summary>True if two axis-aligned squares (centers posA/posB, half-sides rA/rB) overlap.</summary>
        private static bool SquaresOverlap(Vector2 posA, float rA, Vector2 posB, float rB) =>
            Mathf.Abs(posA.x - posB.x) < rA + rB && Mathf.Abs(posA.y - posB.y) < rA + rB;

        /// <summary>True if an axis-aligned square (pos/radius) overlaps an axis-aligned rect [min,max].</summary>
        private static bool SquareOverlapsRect(Vector2 pos, float radius, Vector2 rectMin, Vector2 rectMax) =>
            pos.x + radius > rectMin.x && pos.x - radius < rectMax.x &&
            pos.y + radius > rectMin.y && pos.y - radius < rectMax.y;

        /// <summary>True if two axis-aligned rects overlap.</summary>
        private static bool RectsOverlap(Vector2 aMin, Vector2 aMax, Vector2 bMin, Vector2 bMax) =>
            aMin.x < bMax.x && aMax.x > bMin.x && aMin.y < bMax.y && aMax.y > bMin.y;


        /// <summary>
        /// True if connecting fromRoom and other (consuming `exitsConsumed` unused exits in
        /// the process) would leave their merged connected component with no unused exits and
        /// no Exit room - i.e. a dead branch that could never produce a reachable exit.
        /// </summary>
        private bool WouldStarveComponent(Room fromRoom, Room other, int exitsConsumed)
        {
            bool sameComponent = _graph.AreSameComponent(fromRoom.Id, other.Id);

            bool mergedHasExit = _graph.ComponentHasExit(fromRoom.Id)
                || (!sameComponent && _graph.ComponentHasExit(other.Id));
            if (mergedHasExit) return false;

            int mergedUnused = _graph.ComponentUnusedExitCount(fromRoom.Id);
            if (!sameComponent) mergedUnused += _graph.ComponentUnusedExitCount(other.Id);

            return mergedUnused - exitsConsumed < 1;
        }

        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;
            _graph.Union(a.OwnerRoomId, b.OwnerRoomId);
        }

        private RoomKind DecideNextRoomKind(MazeAgent agent, Room fromRoom)
        {
            // Scoped to fromRoom's own connected component - a different, disconnected branch
            // already having an exit room doesn't make this one reachable.
            bool componentHasExit = _graph.ComponentHasExit(fromRoom.Id);
            bool eligible = agent.NewRoomsVisited >= settings.minNewRoomsBeforeExitEligible;
            bool mustForce = agent.NewRoomsVisited >= settings.forceExitAfterNewRooms && !componentHasExit;

            // A maxExitRooms cap can block both the safety-valve force and the random roll
            // below - once hit, a branch without its own exit has to grow toward and merge
            // into an existing one (via TryConnectViaExistingDoor) instead of minting a new
            // one. This is what pushes separate maze branches to join up.
            bool exitRoomsAvailable = settings.maxExitRooms <= 0 || _graph.ExitRooms.Count < settings.maxExitRooms;

            if (mustForce && exitRoomsAvailable) return RoomKind.Exit;
            if (eligible && exitRoomsAvailable && 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));
    }
}