TheriapolisV3/Theriapolis.Core/Dungeons/RoomGraphAssembler.cs

using Theriapolis.Core.Data;
using Theriapolis.Core.Util;

namespace Theriapolis.Core.Dungeons;

/// <summary>
/// Phase 7 M1 — pure deterministic room-graph assembly. Given a list of
/// picked templates (in order: entry first, others in pick order) and a
/// branching policy, returns:
///   - Per-room placement (AABB top-left + Role)
///   - List of <see cref="RoomConnection"/> binding rooms via matched
///     door tiles
///
/// The assembler does NOT paint tiles — it only decides geometry. Tile
/// painting + corridor stamping is <see cref="RoomTilePainter"/>'s job.
///
/// Placement algorithm: rooms snap to a 16-tile grid, placed left-to-right
/// in chains; each non-entry room picks an existing-room neighbour from
/// the eligible set (linear → previous; branching → uniform-random prior;
/// loop → branching + one extra closing connection). The neighbour's
/// available-side pool determines which AABB slot the new room takes.
///
/// Returns null on failure (overlap, unreachable). Caller retries with a
/// fresh seed up to <see cref="C.DUNGEON_LAYOUT_MAX_ATTEMPTS"/> times then
/// falls back to the linear policy.
/// </summary>
internal static class RoomGraphAssembler
{
    public sealed class Plan
    {
        public Room[]            Rooms;
        public RoomConnection[]  Connections;
        public int               DungeonW;
        public int               DungeonH;
        public (int X, int Y)    EntranceTile;

        public Plan(Room[] rooms, RoomConnection[] connections, int w, int h, (int, int) entranceTile)
        {
            Rooms        = rooms;
            Connections  = connections;
            DungeonW     = w;
            DungeonH     = h;
            EntranceTile = entranceTile;
        }
    }

    /// <summary>
    /// Try to assemble. <paramref name="branching"/> is one of
    /// <c>linear</c> / <c>branching</c> / <c>loop</c>. Returns null on
    /// any geometric failure; caller retries.
    /// </summary>
    public static Plan? TryAssemble(
        IReadOnlyList<RoomTemplateDef> picks,
        IReadOnlyList<RoomRole> roles,
        string branching,
        SeededRng rng)
    {
        if (picks.Count == 0) return null;
        if (picks.Count != roles.Count) throw new ArgumentException("picks and roles length mismatch");

        // Step 1: place the entry room at the origin, padded by AABB padding.
        int pad   = C.DUNGEON_AABB_PADDING;
        int gap   = C.ROOM_INTER_ROOM_GAP_TILES;

        var rooms = new Room[picks.Count];
        // Track absolute AABBs for overlap testing.
        var bounds = new (int x, int y, int w, int h)[picks.Count];

        var entry = picks[0];
        rooms[0] = new Room
        {
            Id          = 0,
            TemplateId  = entry.Id,
            AabbX       = pad,
            AabbY       = pad,
            AabbW       = entry.FootprintWTiles,
            AabbH       = entry.FootprintHTiles,
            BuiltBy     = entry.BuiltBy,
            Role        = roles[0],
            NarrativeText = entry.NarrativeText,
        };
        bounds[0] = (pad, pad, entry.FootprintWTiles, entry.FootprintHTiles);

        var connections = new List<RoomConnection>(picks.Count);

        // Step 2: place each subsequent room next to a chosen prior room.
        for (int i = 1; i < picks.Count; i++)
        {
            int parentIdx = ChooseParent(branching, i, rng);
            var parent = bounds[parentIdx];
            var tpl = picks[i];

            // Try each cardinal direction in a deterministic order; pick the
            // first that doesn't overlap. Order rotates per `i` so different
            // seeds produce different-looking layouts.
            int[] dirOrder = RotateDirOrder(i, rng);
            (int x, int y, int dir)? placement = null;
            foreach (int d in dirOrder)
            {
                var topLeft = TryPlaceAdjacent(parent, tpl.FootprintWTiles, tpl.FootprintHTiles, d, gap);
                if (topLeft is null) continue;
                var candBounds = (topLeft.Value.x, topLeft.Value.y, tpl.FootprintWTiles, tpl.FootprintHTiles);
                if (Overlaps(candBounds, bounds, i)) continue;
                placement = (topLeft.Value.x, topLeft.Value.y, d);
                break;
            }
            if (placement is null) return null; // ran out of room sides

            rooms[i] = new Room
            {
                Id          = i,
                TemplateId  = tpl.Id,
                AabbX       = placement.Value.x,
                AabbY       = placement.Value.y,
                AabbW       = tpl.FootprintWTiles,
                AabbH       = tpl.FootprintHTiles,
                BuiltBy     = tpl.BuiltBy,
                Role        = roles[i],
                NarrativeText = tpl.NarrativeText,
            };
            bounds[i] = (placement.Value.x, placement.Value.y, tpl.FootprintWTiles, tpl.FootprintHTiles);

            // Pick the door pair: parent's near-side door, this room's
            // far-side door. If neither template has a matching door we
            // synthesize a door at the AABB midpoint of the touching edge —
            // the painter will carve it through the wall.
            var conn = MatchDoors(rooms[parentIdx], picks[parentIdx], rooms[i], tpl, placement.Value.dir);
            connections.Add(conn);
        }

        // Step 3 (loop policy only): add one extra closing connection if a
        // suitable pair exists. The closing connection must not duplicate
        // an existing edge.
        if (branching == "loop" && rooms.Length >= 4)
        {
            // Pick room i (not 0) and j > 1, j != i, with no existing edge.
            int triesLeft = 8;
            while (triesLeft-- > 0)
            {
                int i = rng.NextInt(2, rooms.Length);
                int j = rng.NextInt(2, rooms.Length);
                if (i == j) continue;
                if (HasEdge(connections, i, j)) continue;
                var dir = AdjacentDirection(bounds[i], bounds[j], gap + 2);
                if (dir is null) continue;
                connections.Add(MatchDoors(rooms[i], picks[i], rooms[j], picks[j], dir.Value));
                break;
            }
        }

        // Step 4: BFS reachability — every room must be reachable from room 0.
        if (!IsReachable(rooms.Length, connections)) return null;

        // Step 5: compute dungeon bounds.
        int minX = int.MaxValue, minY = int.MaxValue, maxX = 0, maxY = 0;
        foreach (var b in bounds)
        {
            if (b.x < minX) minX = b.x;
            if (b.y < minY) minY = b.y;
            if (b.x + b.w > maxX) maxX = b.x + b.w;
            if (b.y + b.h > maxY) maxY = b.y + b.h;
        }
        // Translate everything so origin is (pad, pad).
        int dx = pad - minX;
        int dy = pad - minY;
        if (dx != 0 || dy != 0)
        {
            for (int i = 0; i < rooms.Length; i++)
            {
                rooms[i] = new Room
                {
                    Id            = rooms[i].Id,
                    TemplateId    = rooms[i].TemplateId,
                    AabbX         = rooms[i].AabbX + dx,
                    AabbY         = rooms[i].AabbY + dy,
                    AabbW         = rooms[i].AabbW,
                    AabbH         = rooms[i].AabbH,
                    BuiltBy       = rooms[i].BuiltBy,
                    Role          = rooms[i].Role,
                    NarrativeText = rooms[i].NarrativeText,
                };
            }
            for (int k = 0; k < connections.Count; k++)
            {
                var c = connections[k];
                connections[k] = c with
                {
                    DoorAx = c.DoorAx + dx,
                    DoorAy = c.DoorAy + dy,
                    DoorBx = c.DoorBx + dx,
                    DoorBy = c.DoorBy + dy,
                };
            }
        }

        int dungeonW = maxX - minX + 2 * pad;
        int dungeonH = maxY - minY + 2 * pad;

        // Entrance tile — pick the entry room's first declared door if any,
        // otherwise the centre of its top edge. (M1 always has a door because
        // every authored entry template declares at least one.)
        var entryDoor = picks[0].Doors.Length > 0 ? picks[0].Doors[0] : null;
        (int X, int Y) entranceTile;
        if (entryDoor is not null)
            entranceTile = (rooms[0].AabbX + entryDoor.X, rooms[0].AabbY + entryDoor.Y);
        else
            entranceTile = (rooms[0].AabbX + rooms[0].AabbW / 2, rooms[0].AabbY);

        return new Plan(rooms, connections.ToArray(), dungeonW, dungeonH, entranceTile);
    }

    // ── Helpers ──────────────────────────────────────────────────────────

    private static int ChooseParent(string branching, int childIdx, SeededRng rng) => branching switch
    {
        "linear"    => childIdx - 1,
        "branching" => rng.NextInt(0, childIdx),
        "loop"      => rng.NextInt(0, childIdx),
        _           => childIdx - 1,
    };

    private static int[] RotateDirOrder(int i, SeededRng rng)
    {
        // Rotate base order by `i % 4` so adjacent rooms don't pile up on
        // the same axis. Add a small RNG-driven secondary shuffle so seeds
        // diverge.
        int[] baseOrder = new[] { 0, 1, 2, 3 }; // 0=E, 1=S, 2=W, 3=N
        int rot = i % 4;
        var rotated = new int[4];
        for (int k = 0; k < 4; k++) rotated[k] = baseOrder[(k + rot) % 4];
        // 50% chance to swap pairs (small variation)
        if ((rng.NextUInt64() & 1) == 1)
        {
            (rotated[0], rotated[2]) = (rotated[2], rotated[0]);
        }
        return rotated;
    }

    private static (int x, int y)? TryPlaceAdjacent(
        (int x, int y, int w, int h) parent,
        int childW, int childH, int direction, int gap)
    {
        // direction: 0=E, 1=S, 2=W, 3=N. Child’s top-left is offset from
        // parent's outer edge by `gap` tiles so a corridor segment fits.
        return direction switch
        {
            0 => (parent.x + parent.w + gap, parent.y),                                   // east
            1 => (parent.x,                  parent.y + parent.h + gap),                  // south
            2 => (parent.x - childW - gap,   parent.y),                                   // west
            3 => (parent.x,                  parent.y - childH - gap),                    // north
            _ => null,
        };
    }

    private static bool Overlaps(
        (int x, int y, int w, int h) cand,
        (int x, int y, int w, int h)[] bounds,
        int countSoFar)
    {
        for (int k = 0; k < countSoFar; k++)
        {
            var b = bounds[k];
            // AABB overlap: not (cand right of b OR cand left of b OR cand below b OR cand above b)
            bool noOverlap = cand.x + cand.w <= b.x
                          || b.x   + b.w   <= cand.x
                          || cand.y + cand.h <= b.y
                          || b.y   + b.h   <= cand.y;
            if (!noOverlap) return true;
        }
        return false;
    }

    private static int? AdjacentDirection(
        (int x, int y, int w, int h) a,
        (int x, int y, int w, int h) b, int slack)
    {
        // Returns a direction code (0=E,1=S,2=W,3=N) for "b is to the X of
        // a within `slack` tiles" — used for loop-policy closing edges.
        if (Math.Abs((a.x + a.w) - b.x) <= slack && OverlapsRange(a.y, a.h, b.y, b.h))
            return 0;
        if (Math.Abs((a.y + a.h) - b.y) <= slack && OverlapsRange(a.x, a.w, b.x, b.w))
            return 1;
        if (Math.Abs(a.x - (b.x + b.w)) <= slack && OverlapsRange(a.y, a.h, b.y, b.h))
            return 2;
        if (Math.Abs(a.y - (b.y + b.h)) <= slack && OverlapsRange(a.x, a.w, b.x, b.w))
            return 3;
        return null;
    }

    private static bool OverlapsRange(int a0, int aLen, int b0, int bLen)
        => !(a0 + aLen <= b0 || b0 + bLen <= a0);

    private static bool HasEdge(List<RoomConnection> conns, int a, int b)
    {
        foreach (var c in conns)
            if ((c.RoomA == a && c.RoomB == b) || (c.RoomA == b && c.RoomB == a))
                return true;
        return false;
    }

    private static bool IsReachable(int roomCount, List<RoomConnection> connections)
    {
        if (roomCount == 0) return true;
        var adj = new List<int>[roomCount];
        for (int i = 0; i < roomCount; i++) adj[i] = new List<int>();
        foreach (var c in connections)
        {
            adj[c.RoomA].Add(c.RoomB);
            adj[c.RoomB].Add(c.RoomA);
        }
        var visited = new bool[roomCount];
        var queue   = new Queue<int>();
        queue.Enqueue(0);
        visited[0] = true;
        int reached = 1;
        while (queue.Count > 0)
        {
            int n = queue.Dequeue();
            foreach (int m in adj[n])
            {
                if (visited[m]) continue;
                visited[m] = true;
                reached++;
                queue.Enqueue(m);
            }
        }
        return reached == roomCount;
    }

    /// <summary>
    /// Match door tiles between two rooms placed adjacent in
    /// <paramref name="direction"/>. Returns the connection record with
    /// dungeon-local door coords on each side. Falls back to the AABB
    /// midpoint of the touching edge when neither template declares a door
    /// on the relevant side.
    /// </summary>
    private static RoomConnection MatchDoors(
        Room a, RoomTemplateDef aDef,
        Room b, RoomTemplateDef bDef,
        int direction)
    {
        // Direction is from A's perspective: 0=B east of A; 1=B south; 2=B west; 3=B north.
        // Pick A's door on the matching side; pick B's door on the opposite side.
        string aFacing = direction switch { 0 => "E", 1 => "S", 2 => "W", 3 => "N", _ => "E" };
        string bFacing = direction switch { 0 => "W", 1 => "N", 2 => "E", 3 => "S", _ => "W" };

        var aDoor = FindDoorByFacing(aDef, aFacing) ?? AabbEdgeMidpoint(aDef, aFacing);
        var bDoor = FindDoorByFacing(bDef, bFacing) ?? AabbEdgeMidpoint(bDef, bFacing);

        return new RoomConnection(
            RoomA: a.Id, DoorAx: a.AabbX + aDoor.x, DoorAy: a.AabbY + aDoor.y,
            RoomB: b.Id, DoorBx: b.AabbX + bDoor.x, DoorBy: b.AabbY + bDoor.y,
            Lock: aDoor.lockTier);
    }

    private static (int x, int y, string lockTier)? FindDoorByFacing(RoomTemplateDef def, string facing)
    {
        foreach (var d in def.Doors)
            if (string.Equals(d.Facing, facing, StringComparison.OrdinalIgnoreCase))
                return (d.X, d.Y, d.Lock);
        return null;
    }

    private static (int x, int y, string lockTier) AabbEdgeMidpoint(RoomTemplateDef def, string facing)
    {
        int w = def.FootprintWTiles, h = def.FootprintHTiles;
        return facing switch
        {
            "E" => (w - 1, h / 2, ""),
            "W" => (0,     h / 2, ""),
            "N" => (w / 2, 0,     ""),
            "S" => (w / 2, h - 1, ""),
            _   => (w / 2, h / 2, ""),
        };
    }
}