MazeWalkerTv/Assets/Scripts/MazeGenerator.cs

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

/// <summary>
/// Generates procedural mazes with rooms, hallways, and various terrain types
/// Designed with AI pathfinding in mind - guarantees multiple paths and accessibility
/// </summary>
public class MazeGenerator
{
    public delegate void ProgressUpdate(int completedTiles, int totalTiles, string message);

    private MazeConfig config;
    private MazeData mazeData;
    private System.Random random;
    private ProgressUpdate progressCallback;
    private int totalTiles;
    private int completedTiles;
    private string currentPhase;

    public MazeGenerator(MazeConfig config, ProgressUpdate progressCallback = null)
    {
        this.config = config;
        this.progressCallback = progressCallback;
        config.Validate();

        if (config.UseRandomSeed)
        {
            random = new System.Random();
        }
        else
        {
            random = new System.Random(config.RandomSeed);
        }
    }

    private void ReportProgress(string message)
    {
        var fullMessage = string.IsNullOrEmpty(currentPhase)
            ? message
            : $"{currentPhase}: {message}";
        progressCallback?.Invoke(completedTiles, totalTiles, fullMessage);
    }

    private void SetPhase(string phase)
    {
        currentPhase = phase;
        ReportProgress("Starting");
    }

    /// <summary>
    /// Generates a complete maze based on the config
    /// </summary>
    public MazeData Generate()
    {
        mazeData = new MazeData(config.Width, config.Height);
        totalTiles = config.Width * config.Height;
        completedTiles = 0;
        SetPhase("Initialize");

        // Step 1: Generate room layouts
        GenerateRooms();

        // Step 2: Connect rooms with hallways
        ConnectRooms();

        // Step 3: Apply terrain types
        ApplyTerrains();

        // Step 4: Place start and exit points
        PlaceStartAndExitPoints();

        // Step 5: Ensure connectivity (verify all rooms are reachable)
        EnsureConnectivity();

        SetPhase("Complete");
        Debug.Log(mazeData.GetStatistics());

        return mazeData;
    }

    /// <summary>
    /// Step 1: Generates room layouts
    /// </summary>
    private void GenerateRooms()
    {
        SetPhase("Generate Rooms");
        var rooms = new List<MazeRoom>();
        int attempts = 0;
        int maxAttempts = config.TargetRoomCount * 10;

        while (rooms.Count < config.TargetRoomCount && attempts < maxAttempts)
        {
            attempts++;

            int width = random.Next(config.MinRoomWidth, config.MaxRoomWidth + 1);
            int height = random.Next(config.MinRoomHeight, config.MaxRoomHeight + 1);
            int x = random.Next(1, config.Width - width - 1);
            int y = random.Next(1, config.Height - height - 1);

            var newRoom = new MazeRoom(rooms.Count, x, y, x + width - 1, y + height - 1);

            // Check if room overlaps with existing rooms or walls (with spacing)
            if (CanPlaceRoom(newRoom, rooms))
            {
                rooms.Add(newRoom);
            }
        }

        // Assign room types based on configuration
        AssignRoomTypes(rooms);

        // Fill rooms in maze data
        for (int i = 0; i < rooms.Count; i++)
        {
            var room = rooms[i];
            mazeData.AddRoom(room.MinX, room.MinY, room.MaxX, room.MaxY, room.Type);
            int filled = mazeData.FillRoom(room.MinX + 1, room.MinY + 1, room.MaxX - 1, room.MaxY - 1, i);
            completedTiles += filled;
            ReportProgress($"Generated room {i + 1}/{rooms.Count} ({completedTiles}/{totalTiles} tiles)");
        }

        Debug.Log($"Generated {rooms.Count} rooms");
    }

    /// <summary>
    /// Checks if a room can be placed without overlapping or being too close to others
    /// </summary>
    private bool CanPlaceRoom(MazeRoom newRoom, List<MazeRoom> existingRooms)
    {
        // Check bounds
        if (newRoom.MinX - config.MinRoomSpacing < 0 || newRoom.MaxX + config.MinRoomSpacing >= config.Width ||
            newRoom.MinY - config.MinRoomSpacing < 0 || newRoom.MaxY + config.MinRoomSpacing >= config.Height)
        {
            return false;
        }

        // Check overlap/spacing with existing rooms
        foreach (var room in existingRooms)
        {
            // Add spacing buffer
            int minX = room.MinX - config.MinRoomSpacing;
            int minY = room.MinY - config.MinRoomSpacing;
            int maxX = room.MaxX + config.MinRoomSpacing;
            int maxY = room.MaxY + config.MinRoomSpacing;

            if (!(newRoom.MaxX < minX || newRoom.MinX > maxX ||
                  newRoom.MaxY < minY || newRoom.MinY > maxY))
            {
                return false;
            }
        }

        return true;
    }

    /// <summary>
    /// Assigns room types (safe, rest, boss, etc.) to rooms
    /// </summary>
    private void AssignRoomTypes(List<MazeRoom> rooms)
    {
        var roomList = new List<MazeRoom>(rooms);

        // Assign special room types
        DistributeRoomType(roomList, MazeRoom.RoomType.Safe, config.SafeRoomCount);
        DistributeRoomType(roomList, MazeRoom.RoomType.Rest, config.RestRoomCount);
        DistributeRoomType(roomList, MazeRoom.RoomType.Boss, config.BossRoomCount);

        // Reset unassigned rooms to Normal
        foreach (var room in rooms)
        {
            if (room.Type != MazeRoom.RoomType.Safe &&
                room.Type != MazeRoom.RoomType.Rest &&
                room.Type != MazeRoom.RoomType.Boss)
            {
                room.Type = MazeRoom.RoomType.Normal;
            }
        }
    }

    /// <summary>
    /// Distributes a specific room type to random rooms
    /// </summary>
    private void DistributeRoomType(List<MazeRoom> rooms, MazeRoom.RoomType type, int count)
    {
        int assigned = 0;
        var available = rooms.Where(r => r.Type == MazeRoom.RoomType.Normal).ToList();

        while (assigned < count && available.Count > 0)
        {
            int idx = random.Next(available.Count);
            var room = available[idx];
            room.Type = type;
            available.RemoveAt(idx);
            assigned++;
        }
    }

    /// <summary>
    /// Step 2: Connects rooms with hallways
    /// Uses a modified Minimum Spanning Tree approach
    /// </summary>
    private void ConnectRooms()
    {
        SetPhase("Connect Rooms");
        var rooms = mazeData.Rooms;
        if (rooms.Count == 0) return;

        var connected = new HashSet<int> { rooms[0].Id };
        var unconnected = new HashSet<int>(rooms.Select(r => r.Id));
        unconnected.Remove(rooms[0].Id);

        while (unconnected.Count > 0)
        {
            // Find closest connected-unconnected room pair
            float minDist = float.MaxValue;
            MazeRoom from = null;
            MazeRoom to = null;

            foreach (var connectedId in connected)
            {
                var connectedRoom = rooms.First(r => r.Id == connectedId);
                foreach (var unconnectedId in unconnected)
                {
                    var unconnectedRoom = rooms.First(r => r.Id == unconnectedId);
                    float dist = Vector2Int.Distance(connectedRoom.GetCenter(), unconnectedRoom.GetCenter());

                    if (dist < minDist)
                    {
                        minDist = dist;
                        from = connectedRoom;
                        to = unconnectedRoom;
                    }
                }
            }

            if (from != null && to != null)
            {
                // Create hallway between rooms
                CreateHallway(from, to);
                connected.Add(to.Id);
                unconnected.Remove(to.Id);
            }
        }

        // Add extra connections for multiple paths
        AddExtraConnections(rooms);

        Debug.Log("Connected rooms with hallways");
    }

    /// <summary>
    /// Creates a hallway between two rooms
    /// </summary>
    private int CreateHallway(MazeRoom from, MazeRoom to)
    {
        var pathA = GeneratePath(from.GetCenter(), to.GetCenter());
        int changed = mazeData.DrawPath(pathA, config.MinHallwayWidth);
        completedTiles += changed;
        ReportProgress($"Connected room {from.Id} to {to.Id} ({completedTiles}/{totalTiles} tiles)");
        return changed;
    }

    /// <summary>
    /// Generates a path between two points using A* or simple line algorithm
    /// </summary>
    private List<Vector2Int> GeneratePath(Vector2Int start, Vector2Int end)
    {
        var path = new List<Vector2Int>();

        // Simple L-shaped path (can be enhanced with A* for better aesthetics)
        int x = start.x;
        int y = start.y;

        // Move horizontally first
        while (x != end.x)
        {
            x += x < end.x ? 1 : -1;
            path.Add(new Vector2Int(x, y));
        }

        // Then vertically
        while (y != end.y)
        {
            y += y < end.y ? 1 : -1;
            path.Add(new Vector2Int(x, y));
        }

        return path;
    }

    /// <summary>
    /// Adds extra connections between rooms to create multiple paths
    /// </summary>
    private void AddExtraConnections(List<MazeRoom> rooms)
    {
        // For each room, randomly connect to nearby rooms
        int extraConnections = Mathf.Max(1, rooms.Count / 10);

        for (int i = 0; i < extraConnections; i++)
        {
            var room1 = rooms[random.Next(rooms.Count)];
            var room2 = rooms[random.Next(rooms.Count)];

            if (room1 != room2)
            {
                CreateHallway(room1, room2);
            }
        }
    }

    /// <summary>
    /// Step 3: Applies different terrain types to areas
    /// </summary>
    private void ApplyTerrains()
    {
        SetPhase("Apply Terrains");
        var normalRooms = mazeData.GetRoomsByType(MazeRoom.RoomType.Normal);

        // Apply swampy terrain to some normal rooms
        for (int i = 0; i < normalRooms.Count * 0.2f; i++)
        {
            var room = normalRooms[random.Next(normalRooms.Count)];
            ApplyTerrainToRoom(room, MazeTile.TerrainType.Swamp);
        }

        // Apply stone terrain to some normal rooms
        for (int i = 0; i < normalRooms.Count * 0.1f; i++)
        {
            var room = normalRooms[random.Next(normalRooms.Count)];
            ApplyTerrainToRoom(room, MazeTile.TerrainType.Stone);
        }
    }

    /// <summary>
    /// Applies a specific terrain type to a room
    /// </summary>
    private void ApplyTerrainToRoom(MazeRoom room, MazeTile.TerrainType terrain)
    {
        for (int x = room.MinX + 1; x < room.MaxX; x++)
        {
            for (int y = room.MinY + 1; y < room.MaxY; y++)
            {
                var tile = mazeData.GetTile(x, y);
                if (tile.Type == MazeTile.TileType.Floor)
                {
                    tile.Terrain = terrain;
                }
            }
        }
    }

    /// <summary>
    /// Step 4: Places start and exit points
    /// </summary>
    private void PlaceStartAndExitPoints()
    {
        SetPhase("Place Start/Exit Points");
        var rooms = mazeData.Rooms;
        if (rooms.Count == 0) return;

        // Place start points
        int startCount = random.Next(config.MinStartPoints, config.MaxStartPoints + 1);
        for (int i = 0; i < startCount && i < rooms.Count; i++)
        {
            var room = rooms[i];
            room.IsStart = true;
            var point = room.GetRandomPoint();
            mazeData.AddStartPoint(point);
        }

        // Place exit points
        int exitCount = random.Next(config.MinExits, config.MaxExits + 1);
        var endRooms = mazeData.GetRoomsByType(MazeRoom.RoomType.End);

        if (endRooms.Count == 0)
        {
            // Create end rooms if they don't exist
            int exitsPlaced = 0;
            int roomIndex = 0;
            while (exitsPlaced < exitCount && roomIndex < rooms.Count)
            {
                if (!rooms[roomIndex].IsStart)
                {
                    rooms[roomIndex].Type = MazeRoom.RoomType.End;
                    rooms[roomIndex].IsEnd = true;
                    var point = rooms[roomIndex].GetRandomPoint();
                    mazeData.AddExitPoint(point);
                    exitsPlaced++;
                }
                roomIndex++;
            }
        }
        else
        {
            foreach (var room in endRooms.Take(exitCount))
            {
                room.IsEnd = true;
                var point = room.GetRandomPoint();
                mazeData.AddExitPoint(point);
            }
        }

        Debug.Log($"Placed {startCount} start points and {exitCount} exit points");
    }

    /// <summary>
    /// Step 5: Ensures all rooms are connected and reachable
    /// </summary>
    private void EnsureConnectivity()
    {
        SetPhase("Ensure Connectivity");
        // Simple BFS from first start point to check connectivity
        if (mazeData.StartPoints.Count == 0) return;

        var start = mazeData.StartPoints[0];
        var visited = new HashSet<Vector2Int>();
        var queue = new Queue<Vector2Int>();
        queue.Enqueue(start);
        visited.Add(start);

        while (queue.Count > 0)
        {
            var current = queue.Dequeue();
            var adjacent = mazeData.GetAdjacentWalkable(current.x, current.y);

            foreach (var next in adjacent)
            {
                if (!visited.Contains(next))
                {
                    visited.Add(next);
                    queue.Enqueue(next);
                }
            }
        }

        Debug.Log($"Connectivity check: {visited.Count} tiles reachable from start point");
    }
}