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

/// <summary>
/// AI Agent that navigates the maze with limited knowledge
/// Only knows about the room it's currently in and rooms visited by same character type
/// </summary>
public class AIAgent : MonoBehaviour
{
    [Header("Agent Identity")]
    [SerializeField] private string agentCharacterType = "Default";
    [SerializeField] private int agentId;

    [Header("AI Settings")]
    [SerializeField] private float movementSpeed = 2f;
    [SerializeField] private float pathUpdateInterval = 0.5f;
    [SerializeField] private float stoppingDistance = 0.1f;

    private float actualMovementSpeed; // Per-agent speed variation to reduce synchronization

    [Header("Pathfinding")]
    [SerializeField] private bool showPath = true;
    [SerializeField] private LineRenderer pathRenderer;
    [SerializeField] private Color pathColor = Color.yellow;

    private MazeController mazeController;
    private MazeData maze;
    private MazePathfinder pathfinder;
    private AIRoomMemory roomMemory;

    private List<Vector2Int> currentPath = new();
    private int currentPathIndex = 0;
    private float lastPathUpdate = 0f;
    private Vector2Int currentRoom = Vector2Int.zero;
    private Vector2Int targetRoom = Vector2Int.zero;
    private Vector2Int targetExitTile = Vector2Int.zero; // Target hallway exit to move toward
    private Queue<int> recentRooms = new Queue<int>(); // Track last N rooms to avoid backtracking
    private const int RECENT_ROOMS_BUFFER_SIZE = 10; // Larger buffer = less backtracking
    private MazeRoom lastRoomExitedFrom = null; // Track which room we exited to prevent immediate backtracking
    private bool hasReachedGoal = false; // Track if agent has reached the goal room
    private bool commitedToExit = false; // Track if agent has committed to a specific hallway exit
    private float nextRandomWait = 0f; // Random wait time before exploring new areas
    private float agentRandomOffset = 0f; // Per-agent random offset to desync movement

    void Start()
    {
        mazeController = FindAnyObjectByType<MazeController>();
        if (mazeController == null)
        {
            Debug.LogError("AIAgent: MazeController not found in scene!");
            enabled = false;
            return;
        }

        maze = mazeController.GetCurrentMaze();
        if (maze == null)
        {
            Debug.LogError("AIAgent: Current maze is null!");
            enabled = false;
            return;
        }

        pathfinder = new MazePathfinder(maze);
        roomMemory = AIRoomMemoryManager.GetMemory(agentCharacterType);

        // Initialize with a random start point
        if (maze.StartPoints.Count > 0)
        {
            int startIndex = agentId % maze.StartPoints.Count; // Distribute agents across start points
            Vector2Int startPos = maze.StartPoints[startIndex];

            // Get the start room and spawn randomly within it
            MazeRoom startRoom = maze.GetRoomAtTile(startPos.x, startPos.y);
            if (startRoom != null)
            {
                // Spawn at random position within start room
                Vector2Int randomPosInRoom = new Vector2Int(
                    Random.Range(startRoom.MinX + 1, startRoom.MaxX),
                    Random.Range(startRoom.MinY + 1, startRoom.MaxY)
                );
                transform.position = new Vector3(randomPosInRoom.x + 0.5f, 1f, randomPosInRoom.y + 0.5f);
            }
            else
            {
                // Fallback to exact start point
                transform.position = new Vector3(startPos.x + 0.5f, 1f, startPos.y + 0.5f);
            }

            // Rotate to be visible from above - 90 degrees around X axis
            transform.rotation = Quaternion.Euler(90, 0, 0);
            UpdateCurrentRoom(); // This will add to recentRooms and visit room
        }
        else
        {
            Debug.LogError("AIAgent: No start points found in maze!");
            enabled = false;
            return;
        }

        // Setup per-agent random offset to desync decision timings (prevents all agents moving in sync)
        agentRandomOffset = Random.Range(0f, pathUpdateInterval * 0.5f);
        nextRandomWait = Time.time + Random.Range(2f, 4f); // Random initial wait before first decision

        // Randomize movement speed slightly per agent (±20% variation)
        actualMovementSpeed = movementSpeed * Random.Range(0.8f, 1.2f);

        // Setup path renderer
        if (showPath && pathRenderer == null)
        {
            pathRenderer = gameObject.AddComponent<LineRenderer>();
            pathRenderer.startWidth = 0.1f;
            pathRenderer.endWidth = 0.1f;
            pathRenderer.material = new Material(Shader.Find("Sprites/Default"));
            pathRenderer.startColor = pathColor;
            pathRenderer.endColor = pathColor;
        }

    }

    void Update()
    {
        if (maze == null) return;

        // Update current room
        UpdateCurrentRoom();

        // Update pathfinding periodically with agent-specific offset to desync behavior
        if (Time.time - lastPathUpdate > pathUpdateInterval + agentRandomOffset)
        {
            UpdatePathToGoal();
            lastPathUpdate = Time.time;
        }

        // Move along path
        FollowPath();

        // Debug visualization
        if (showPath && pathRenderer != null)
        {
            UpdatePathVisualization();
        }
    }

    /// <summary>
    /// Updates the current room based on position
    /// </summary>
    private void UpdateCurrentRoom()
    {
        Vector2Int tilePos = WorldToTile(transform.position);
        MazeRoom room = maze.GetRoomAtTile(tilePos.x, tilePos.y);

        if (room != null)
        {
            if (currentRoom.x != room.Id)
            {
                currentRoom = new Vector2Int(room.Id, 0);
                roomMemory.VisitRoom(room.Id);

                // Track recent rooms to avoid immediate backtracking
                recentRooms.Enqueue(room.Id);
                if (recentRooms.Count > RECENT_ROOMS_BUFFER_SIZE)
                    recentRooms.Dequeue();

            }
        }
    }

    /// <summary>
    /// Updates pathfinding to reach the goal
    /// Agent only knows about current room and visited rooms
    /// NEW LOGIC: Pick a hallway exit from current room and move straight to it
    /// </summary>
    private void UpdatePathToGoal()
    {
        if (maze.ExitPoints.Count == 0)
        {
            Debug.LogWarning($"AIAgent {agentId}: No exit points in maze!");
            return;
        }

        Vector2Int currentPos = WorldToTile(transform.position);
        MazeRoom currentRoomData = maze.GetRoomAtTile(currentPos.x, currentPos.y);

        // CHECK FOR GOAL ROOM FIRST - this should work even while following path
        var goalRooms = maze.GetRoomsByType(MazeRoom.RoomType.End);
        if (currentRoomData != null && goalRooms.Contains(currentRoomData))
        {
            if (!hasReachedGoal)
            {
                hasReachedGoal = true;
                currentPath.Clear();
                currentPathIndex = 0;
            }
            return; // Stay stopped
        }

        // If we already have a valid path and we're following it, don't recalculate (stay committed)
        if (currentPath.Count > 0 && currentPathIndex < currentPath.Count)
        {
            return; // Keep following existing path
        }

        // If we've committed to reaching an exit and haven't reached it yet, keep trying
        if (commitedToExit && targetExitTile != Vector2Int.zero)
        {
            // Try to find a path to the committed exit
            if (currentPath.Count == 0)
            {
                currentPath = FindPathInRoom(currentPos, targetExitTile, currentRoomData);
                currentPathIndex = 0;
                if (currentPath.Count > 0)
                {
                    Debug.Log($"AIAgent {agentId}: Re-committed to exit {targetExitTile}");
                    return;
                }
            }
        }

        // If in hallway (no room), just keep moving along current path
        // The hallway pathfinding will naturally move us toward exits
        if (currentRoomData == null)
        {
            // If we have a current path, keep following it through hallway
            if (currentPath.Count > 0 && currentPathIndex < currentPath.Count)
            {
                return; // Keep following path
            }

            // In hallway with no path - find next room to enter
            // PRIORITY 1: Find unvisited rooms, avoid the room we just exited

            // Collect all unvisited rooms
            List<MazeRoom> unvisitedRooms = new();
            foreach (var room in maze.Rooms)
            {
                // Skip the room we just exited (backtracking prevention)
                if (lastRoomExitedFrom != null && room.Id == lastRoomExitedFrom.Id)
                    continue;

                // Prioritize unvisited rooms
                if (!roomMemory.HasVisited(room.Id))
                {
                    unvisitedRooms.Add(room);
                }
            }

            MazeRoom targetRoom = null;

            // Random decision: 70% closest unvisited, 30% random unvisited (increases exploration variety)
            if (unvisitedRooms.Count > 0)
            {
                if (Random.value < 0.7f && unvisitedRooms.Count > 0)
                {
                    // Pick closest unvisited room
                    float closestUnvisitedDistance = float.MaxValue;
                    foreach (var room in unvisitedRooms)
                    {
                        Vector2Int roomCenter = room.GetCenter();
                        float distance = Vector2Int.Distance(currentPos, roomCenter);
                        if (distance < closestUnvisitedDistance)
                        {
                            closestUnvisitedDistance = distance;
                            targetRoom = room;
                        }
                    }
                }
                else
                {
                    // Pick random unvisited room for variety
                    targetRoom = unvisitedRooms[Random.Range(0, unvisitedRooms.Count)];
                }
            }

            // If no unvisited room found, pick nearest room (except the one we came from)
            if (targetRoom == null)
            {
                float closestDistance = float.MaxValue;
                foreach (var room in maze.Rooms)
                {
                    // Skip the room we just exited
                    if (lastRoomExitedFrom != null && room.Id == lastRoomExitedFrom.Id)
                        continue;

                    Vector2Int roomCenter = room.GetCenter();
                    float distance = Vector2Int.Distance(currentPos, roomCenter);
                    if (distance < closestDistance)
                    {
                        closestDistance = distance;
                        targetRoom = room;
                    }
                }
            }

            if (targetRoom != null)
            {
                currentPath = FindPathToNearestRoom(currentPos, targetRoom);
                currentPathIndex = 0;

                if (currentPath.Count > 0)
                {
                    bool isUnvisited = !roomMemory.HasVisited(targetRoom.Id);
                    return;
                }
                else
                {
                    Debug.LogWarning($"AIAgent {agentId}: Failed to path to room {targetRoom.Id} from hallway at {currentPos}. Trying any adjacent room.");
                    // Fallback: try to find ANY adjacent room and move directly toward it
                    foreach (var room in maze.Rooms)
                    {
                        if (lastRoomExitedFrom != null && room.Id == lastRoomExitedFrom.Id)
                            continue;

                        currentPath = FindPathToNearestRoom(currentPos, room);
                        if (currentPath.Count > 0)
                        {
                            return;
                        }
                    }

                    Debug.LogError($"AIAgent {agentId}: STUCK in hallway at {currentPos} - no paths found to any room!");
                    return;
                }
            }

            Debug.LogWarning($"AIAgent {agentId}: In hallway but no reachable rooms!");
            return;
        }



        // MAIN LOGIC: In regular room, find a hallway exit and path to it
        // Get all hallway tiles adjacent to this room
        List<Vector2Int> hallwayExits = FindHallwayExits(currentRoomData, currentPos);

        if (hallwayExits.Count > 0)
        {
            // Pick a random hallway exit to move toward (commit to it)
            Vector2Int chosenExit = hallwayExits[Random.Range(0, hallwayExits.Count)];

            // Path directly to that exit
            currentPath = FindPathInRoom(currentPos, chosenExit, currentRoomData);
            currentPathIndex = 0;

            if (currentPath.Count > 0)
            {
                targetExitTile = chosenExit;
                commitedToExit = true;

                // Add random delay before next decision to increase variety
                nextRandomWait = Time.time + Random.Range(1.5f, 3.5f);

            }
            else
            {
                Debug.LogWarning($"AIAgent {agentId}: Could not path to hallway exit");
                commitedToExit = false;
            }
        }
        else
        {
            Debug.LogWarning($"AIAgent {agentId}: No hallway exits found from room {currentRoomData.Id}");
            commitedToExit = false;
        }
    }

    /// <summary>
    /// Chooses the next room to move to
    /// Searches around the current room to find adjacent rooms
    /// Avoids recently visited rooms to prevent backtracking
    /// </summary>
    private MazeRoom ChooseNextRoom(MazeRoom currentRoom)
    {
        // Find all adjacent rooms by checking walkable tiles in all directions from room boundaries
        List<MazeRoom> connectedRooms = new();
        Vector2Int roomCenter = currentRoom.GetCenter();

        // Check from each direction outward from the room center
        Vector2Int[] directions = new Vector2Int[]
        {
            Vector2Int.up, Vector2Int.down, Vector2Int.left, Vector2Int.right,
            Vector2Int.up + Vector2Int.left, Vector2Int.up + Vector2Int.right,
            Vector2Int.down + Vector2Int.left, Vector2Int.down + Vector2Int.right
        };

        // Shuffle directions for randomness
        for (int i = directions.Length - 1; i > 0; i--)
        {
            int randomIndex = Random.Range(0, i + 1);
            var temp = directions[i];
            directions[i] = directions[randomIndex];
            directions[randomIndex] = temp;
        }

        // Try each direction and look for tiles that lead to other rooms
        foreach (var dir in directions)
        {
            for (int dist = 1; dist < 20; dist++) // Search up to 20 tiles away
            {
                Vector2Int testPos = roomCenter + (dir * dist);

                if (!maze.IsInBounds(testPos.x, testPos.y) || !maze.IsWalkable(testPos.x, testPos.y))
                    continue;

                MazeRoom testRoom = maze.GetRoomAtTile(testPos.x, testPos.y);
                if (testRoom != null && testRoom.Id != currentRoom.Id && !connectedRooms.Contains(testRoom))
                {
                    connectedRooms.Add(testRoom);
                    break; // Found a room in this direction, move to next direction
                }
            }
        }

        if (connectedRooms.Count == 0)
        {
            Debug.LogWarning($"AIAgent {agentId}: No adjacent rooms found from room {currentRoom.Id}");
            return null;
        }

        // Filter out recently visited rooms (to avoid backtracking)
        List<MazeRoom> nonRecentRooms = connectedRooms.Where(r => !recentRooms.Contains(r.Id)).ToList();

        // PRIORITY 1: Strongly prefer completely unvisited rooms (not recently visited either)
        var completelyUnvisited = nonRecentRooms.Where(r => !roomMemory.HasVisited(r.Id)).ToList();
        if (completelyUnvisited.Count > 0)
        {
            MazeRoom chosen = completelyUnvisited[Random.Range(0, completelyUnvisited.Count)];
            return chosen;
        }

        // PRIORITY 2: Try non-recent rooms even if visited by this character type
        if (nonRecentRooms.Count > 0)
        {
            // Among non-recent rooms, prefer unvisited by this agent's character type
            var unvisitedByType = nonRecentRooms.Where(r => !roomMemory.HasVisited(r.Id)).ToList();
            if (unvisitedByType.Count > 0)
            {
                MazeRoom chosen = unvisitedByType[Random.Range(0, unvisitedByType.Count)];
                return chosen;
            }

            // Otherwise just pick a random non-recent room
            MazeRoom chosen2 = nonRecentRooms[Random.Range(0, nonRecentRooms.Count)];
            return chosen2;
        }

        // PRIORITY 3: If all rooms are recent, pick one that's been visited least recently
        // Find the room in connectedRooms that was added to recentRooms earliest (will be dequeued first)
        MazeRoom leastRecentRoom = connectedRooms[0];
        foreach (var room in connectedRooms)
        {
            if (!roomMemory.HasVisited(room.Id))
            {
                leastRecentRoom = room;
                break;
            }
        }

        Debug.Log($"AIAgent {agentId}: All rooms recent, choosing least-recent room {leastRecentRoom.Id}");
        return leastRecentRoom;
    }

    /// <summary>
    /// Finds the nearest room from a position (used when in hallway)
    /// </summary>
    private MazeRoom FindNearestRoom(Vector2Int position)
    {
        MazeRoom nearest = null;
        float nearestDistance = float.MaxValue;

        foreach (var room in maze.Rooms)
        {
            Vector2Int roomCenter = room.GetCenter();
            float distance = Vector2Int.Distance(position, roomCenter);
            if (distance < nearestDistance)
            {
                nearestDistance = distance;
                nearest = room;
            }
        }

        return nearest;
    }

    /// <summary>
    /// Finds all hallway exit tiles adjacent to a room
    /// These are walkable tiles just outside the room boundary
    /// </summary>
    private List<Vector2Int> FindHallwayExits(MazeRoom room, Vector2Int currentPos)
    {
        List<Vector2Int> exits = new();
        HashSet<Vector2Int> addedExits = new();

        // Check all tiles on the boundary of the room
        // North boundary
        for (int x = room.MinX; x <= room.MaxX; x++)
        {
            int y = room.MinY - 1;
            if (maze.IsInBounds(x, y) && maze.IsWalkable(x, y) && !addedExits.Contains(new Vector2Int(x, y)))
            {
                exits.Add(new Vector2Int(x, y));
                addedExits.Add(new Vector2Int(x, y));
            }
        }

        // South boundary
        for (int x = room.MinX; x <= room.MaxX; x++)
        {
            int y = room.MaxY + 1;
            if (maze.IsInBounds(x, y) && maze.IsWalkable(x, y) && !addedExits.Contains(new Vector2Int(x, y)))
            {
                exits.Add(new Vector2Int(x, y));
                addedExits.Add(new Vector2Int(x, y));
            }
        }

        // West boundary
        for (int y = room.MinY; y <= room.MaxY; y++)
        {
            int x = room.MinX - 1;
            if (maze.IsInBounds(x, y) && maze.IsWalkable(x, y) && !addedExits.Contains(new Vector2Int(x, y)))
            {
                exits.Add(new Vector2Int(x, y));
                addedExits.Add(new Vector2Int(x, y));
            }
        }

        // East boundary
        for (int y = room.MinY; y <= room.MaxY; y++)
        {
            int x = room.MaxX + 1;
            if (maze.IsInBounds(x, y) && maze.IsWalkable(x, y) && !addedExits.Contains(new Vector2Int(x, y)))
            {
                exits.Add(new Vector2Int(x, y));
                addedExits.Add(new Vector2Int(x, y));
            }
        }

        return exits;
    }

    /// <summary>
    /// Finds a path from current position to the nearest room (when in hallway)
    /// </summary>
    private List<Vector2Int> FindPathToNearestRoom(Vector2Int start, MazeRoom targetRoom)
    {
        // Simple pathfinding through hallways using A*
        var openSet = new List<Vector2Int> { start };
        var cameFrom = new Dictionary<Vector2Int, Vector2Int>();
        var gScore = new Dictionary<Vector2Int, float> { [start] = 0 };
        var targetCenter = targetRoom.GetCenter();
        var fScore = new Dictionary<Vector2Int, float> { [start] = Vector2Int.Distance(start, targetCenter) };

        int iterations = 0;
        const int maxIterations = 2000; // Increased from 500 to handle larger mazes

        while (openSet.Count > 0 && iterations < maxIterations)
        {
            iterations++;

            // Find node with lowest fScore
            Vector2Int current = openSet[0];
            float lowestF = fScore[current];

            for (int i = 1; i < openSet.Count; i++)
            {
                if (fScore[openSet[i]] < lowestF)
                {
                    current = openSet[i];
                    lowestF = fScore[current];
                }
            }

            // If we reached the target room, we're done
            MazeRoom currentRoom = maze.GetRoomAtTile(current.x, current.y);
            if (currentRoom != null && currentRoom.Id == targetRoom.Id)
            {
                return ReconstructPath(cameFrom, current);
            }

            openSet.Remove(current);

            // Check neighbors
            Vector2Int[] neighbors = new[]
            {
                new Vector2Int(current.x + 1, current.y),
                new Vector2Int(current.x - 1, current.y),
                new Vector2Int(current.x, current.y + 1),
                new Vector2Int(current.x, current.y - 1),
            };

            foreach (var neighbor in neighbors)
            {
                if (!maze.IsInBounds(neighbor.x, neighbor.y) || !maze.IsWalkable(neighbor.x, neighbor.y))
                    continue;

                float tentativeG = gScore[current] + 1;

                if (!gScore.ContainsKey(neighbor) || tentativeG < gScore[neighbor])
                {
                    cameFrom[neighbor] = current;
                    gScore[neighbor] = tentativeG;
                    fScore[neighbor] = tentativeG + Vector2Int.Distance(neighbor, targetCenter);

                    if (!openSet.Contains(neighbor))
                    {
                        openSet.Add(neighbor);
                    }
                }
            }
        }

        Debug.LogWarning($"AIAgent {agentId}: FindPathToNearestRoom FAILED after {iterations} iterations. Start: {start}, Target room {targetRoom.Id} center: {targetCenter}");
        return new List<Vector2Int>();
    }

    /// <summary>
    /// Finds a boundary tile of the current room that points toward the next room
    /// </summary>
    private Vector2Int FindBoundaryTileToward(MazeRoom currentRoom, MazeRoom nextRoom, Vector2Int currentPos)
    {
        Vector2Int nextRoomCenter = nextRoom.GetCenter();
        Vector2Int closestBoundary = currentRoom.GetCenter();
        float closestDistance = float.MaxValue;

        // Check all boundary tiles of current room
        for (int x = currentRoom.MinX; x <= currentRoom.MaxX; x++)
        {
            for (int y = currentRoom.MinY; y <= currentRoom.MaxY; y++)
            {
                // Only check boundary and walkable tiles
                if ((x == currentRoom.MinX || x == currentRoom.MaxX || y == currentRoom.MinY || y == currentRoom.MaxY) &&
                    maze.IsWalkable(x, y))
                {
                    // Find boundary tile closest to next room center
                    float distToNext = Vector2Int.Distance(new Vector2Int(x, y), nextRoomCenter);
                    if (distToNext < closestDistance)
                    {
                        closestDistance = distToNext;
                        closestBoundary = new Vector2Int(x, y);
                    }
                }
            }
        }

        return closestBoundary;
    }

    /// <summary>
    /// Finds a path within a single room (limited knowledge)
    /// </summary>
    private List<Vector2Int> FindPathInRoom(Vector2Int start, Vector2Int goal, MazeRoom room)
    {
        // Use simple A* within room bounds
        var openSet = new List<Vector2Int> { start };
        var cameFrom = new Dictionary<Vector2Int, Vector2Int>();
        var gScore = new Dictionary<Vector2Int, float> { [start] = 0 };
        var fScore = new Dictionary<Vector2Int, float> { [start] = Vector2Int.Distance(start, goal) };

        int iterations = 0;
        const int maxIterations = 1000;

        while (openSet.Count > 0 && iterations < maxIterations)
        {
            iterations++;

            // Find node with lowest fScore
            Vector2Int current = openSet[0];
            float lowestF = fScore[current];

            for (int i = 1; i < openSet.Count; i++)
            {
                if (fScore[openSet[i]] < lowestF)
                {
                    current = openSet[i];
                    lowestF = fScore[current];
                }
            }

            if (current == goal)
            {
                return ReconstructPath(cameFrom, current);
            }

            openSet.Remove(current);

            // Check only neighbors within the room
            var neighbors = GetRoomNeighbors(current, room);
            foreach (var neighbor in neighbors)
            {
                float tentativeG = gScore[current] + 1;

                if (!gScore.ContainsKey(neighbor) || tentativeG < gScore[neighbor])
                {
                    cameFrom[neighbor] = current;
                    gScore[neighbor] = tentativeG;
                    fScore[neighbor] = tentativeG + Vector2Int.Distance(neighbor, goal);

                    if (!openSet.Contains(neighbor))
                    {
                        openSet.Add(neighbor);
                    }
                }
            }
        }

        return new List<Vector2Int>();
    }

    /// <summary>
    /// Gets walkable neighbors within a room or at room boundary
    /// Allows pathfinding to reach hallway exits outside room
    /// </summary>
    private List<Vector2Int> GetRoomNeighbors(Vector2Int position, MazeRoom room)
    {
        var neighbors = new List<Vector2Int>();
        Vector2Int[] directions = new[]
        {
            new Vector2Int(position.x + 1, position.y),
            new Vector2Int(position.x - 1, position.y),
            new Vector2Int(position.x, position.y + 1),
            new Vector2Int(position.x, position.y - 1),
        };

        foreach (var dir in directions)
        {
            // Allow tiles within room OR immediately adjacent to room (boundary)
            bool inBounds = maze.IsInBounds(dir.x, dir.y);
            bool isWalkable = maze.IsWalkable(dir.x, dir.y);
            bool inRoom = room.Contains(dir.x, dir.y);
            bool nearBoundary = (dir.x == room.MinX - 1 || dir.x == room.MaxX + 1 ||
                                 dir.y == room.MinY - 1 || dir.y == room.MaxY + 1);

            if (inBounds && isWalkable && (inRoom || nearBoundary))
            {
                neighbors.Add(dir);
            }
        }

        return neighbors;
    }

    /// <summary>
    /// Reconstructs path from A* results
    /// </summary>
    private List<Vector2Int> ReconstructPath(Dictionary<Vector2Int, Vector2Int> cameFrom, Vector2Int current)
    {
        var path = new List<Vector2Int> { current };
        while (cameFrom.ContainsKey(current))
        {
            current = cameFrom[current];
            path.Insert(0, current);
        }
        return path;
    }

    /// <summary>
    /// Follows the current path
    /// </summary>
    private void FollowPath()
    {
        if (currentPath.Count == 0) return;

        Vector2Int currentTarget = currentPath[currentPathIndex];
        // Maze coordinates: X,Y → World: X,Z (Y=0 is ground level)
        // Keep Y at 1f to stay above the maze floor
        Vector3 targetWorldPos = new Vector3(currentTarget.x + 0.5f, 1f, currentTarget.y + 0.5f);

        Vector3 direction = (targetWorldPos - transform.position).normalized;
        // Move directly instead of using Translate (no rigidbody)
        transform.position += direction * actualMovementSpeed * Time.deltaTime;

        // Check if we've exited the room (entered hallway)
        Vector2Int currentPos = WorldToTile(transform.position);
        MazeRoom roomAtPos = maze.GetRoomAtTile(currentPos.x, currentPos.y);
        if (roomAtPos == null && currentRoom.x != -1)
        {
            // We've entered a hallway - track which room we came from to prevent immediate backtracking
            lastRoomExitedFrom = maze.Rooms.FirstOrDefault(r => r.Id == currentRoom.x);
            commitedToExit = false; // No longer committed to that exit, now in hallway
            targetExitTile = Vector2Int.zero; // Clear the target exit
        }

        // Move to next waypoint when close enough
        if (Vector3.Distance(transform.position, targetWorldPos) < stoppingDistance)
        {
            currentPathIndex++;
            if (currentPathIndex >= currentPath.Count)
            {
                currentPath.Clear();
            }
        }
    }

    /// <summary>
    /// Updates the path visualization
    /// </summary>
    private void UpdatePathVisualization()
    {
        if (currentPath.Count == 0)
        {
            pathRenderer.positionCount = 0;
            return;
        }

        var positions = new Vector3[currentPath.Count];
        for (int i = 0; i < currentPath.Count; i++)
        {
            // Maze coordinates: X,Y → World: X,Z (Y=0 is ground level)
            // Keep Y at 1f to stay above the maze floor
            positions[i] = new Vector3(currentPath[i].x + 0.5f, 1f, currentPath[i].y + 0.5f);
        }

        pathRenderer.positionCount = positions.Length;
        pathRenderer.SetPositions(positions);
    }

    /// <summary>
    /// Converts world position to tile coordinate
    /// Maze coordinates: X,Y ← World: X,Z (Y=0 is ground level)
    /// </summary>
    private Vector2Int WorldToTile(Vector3 worldPos)
    {
        return new Vector2Int(Mathf.FloorToInt(worldPos.x), Mathf.FloorToInt(worldPos.z));
    }

    /// <summary>
    /// Gets agent ID
    /// </summary>
    public int AgentId => agentId;

    /// <summary>
    /// Gets agent character type
    /// </summary>
    public string CharacterType => agentCharacterType;

    /// <summary>
    /// Gets current room
    /// </summary>
    public Vector2Int CurrentRoom => currentRoom;

    /// <summary>
    /// Gets room memory
    /// </summary>
    public AIRoomMemory RoomMemory => roomMemory;

    /// <summary>
    /// Gets agent ID (public accessor for triggers)
    /// </summary>
    public int GetAgentId() => agentId;

    /// <summary>
    /// Called by ExitRoomTrigger when agent enters the goal room
    /// Immediately stops all movement
    /// </summary>
    public void StopAtGoal()
    {
        hasReachedGoal = true;
        currentPath.Clear();
        currentPathIndex = 0;
        commitedToExit = false;
    }

    /// <summary>
    /// Gets whether this agent has reached the goal
    /// </summary>
    public bool HasReachedGoal => hasReachedGoal;
}