RPG-RougeLiteBattler/Assets/Scripts/MapMaker2/Features/RoadGenerator.cs

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

public class RoadGenerator
{
    public void GenerateRoads(MapData mapData)
    {
        var settlements = mapData.GetTowns();
        settlements.AddRange(mapData.GetVillages());

        // Connect settlements with roads
        ConnectSettlements(mapData, settlements);

        // Connect to map edges
        ConnectToMapEdges(mapData, settlements);

        // Add standalone harbours on lakes
        GenerateLakeHarbours(mapData);
    }

    private void ConnectSettlements(MapData mapData, List<Settlement> settlements)
    {
        var towns = settlements.Where(s => s.Type == SettlementType.Town).ToList();
        var villages = settlements.Where(s => s.Type == SettlementType.Village).ToList();

        Debug.Log($"Connecting {towns.Count} towns and {villages.Count} villages");

        // Connect towns to each other (main highway network)
        List<List<Vector2Int>> mainRoads = new List<List<Vector2Int>>();
        int townConnections = 0;
        int maxTownConnections = towns.Count * (towns.Count - 1) / 2; // Limit total connections

        for (int i = 0; i < towns.Count; i++)
        {
            for (int j = i + 1; j < towns.Count; j++)
            {
                townConnections++;
                if (townConnections > maxTownConnections)
                {
                    Debug.LogWarning($"Limiting town connections to prevent performance issues ({townConnections}/{maxTownConnections})");
                    break;
                }

                Debug.Log($"Creating road between towns {i} and {j}");
                var roadPath = CreateRoad(mapData, towns[i].position, towns[j].position);
                mainRoads.Add(roadPath);
            }
            if (townConnections > maxTownConnections) break;
        }

        // Create village chains - connect villages to nearest settlements (including other villages)
        var unconnectedVillages = new List<Settlement>(villages);
        var connectedSettlements = new List<Settlement>(towns); // Towns are already connected
        int villageConnections = 0;
        int maxVillageConnections = villages.Count + 10; // Safety limit

        Debug.Log($"Connecting {unconnectedVillages.Count} villages to settlement network");

        while (unconnectedVillages.Count > 0 && villageConnections < maxVillageConnections)
        {
            villageConnections++;
            Settlement nearestVillage = null;
            Settlement nearestTarget = null;
            float shortestDistance = float.MaxValue;

            // Find the closest unconnected village to any connected settlement
            foreach (var village in unconnectedVillages)
            {
                foreach (var connectedSettlement in connectedSettlements)
                {
                    float distance = Vector2.Distance(
                        new Vector2(village.position.x, village.position.y),
                        new Vector2(connectedSettlement.position.x, connectedSettlement.position.y));

                    if (distance < shortestDistance)
                    {
                        shortestDistance = distance;
                        nearestVillage = village;
                        nearestTarget = connectedSettlement;
                    }
                }
            }

            // Connect the nearest village and add it to connected settlements
            if (nearestVillage != null && nearestTarget != null)
            {
                Debug.Log($"Connecting village {villageConnections}/{villages.Count}");
                CreateRoad(mapData, nearestVillage.position, nearestTarget.position);
                connectedSettlements.Add(nearestVillage);
                unconnectedVillages.Remove(nearestVillage);
            }
            else
            {
                Debug.LogWarning("Could not find village connection, breaking loop");
                break; // Safety break
            }
        }

        if (villageConnections >= maxVillageConnections)
        {
            Debug.LogWarning($"Village connection limit reached ({maxVillageConnections}), some villages may remain unconnected");
        }
    }

    private Vector2Int FindNearestRoadConnection(MapData mapData, Vector2Int villagePos, List<List<Vector2Int>> mainRoads, List<Settlement> towns)
    {
        Vector2Int nearestPoint = villagePos;
        float nearestDistance = float.MaxValue;

        // Check all main road points
        foreach (var road in mainRoads)
        {
            foreach (var roadPoint in road)
            {
                float distance = Vector2.Distance(new Vector2(villagePos.x, villagePos.y), new Vector2(roadPoint.x, roadPoint.y));
                if (distance < nearestDistance && distance > 5) // Don't connect too close to avoid overlaps
                {
                    nearestDistance = distance;
                    nearestPoint = roadPoint;
                }
            }
        }

        // If no good road connection found, connect to nearest town
        if (nearestDistance > 50f || nearestPoint == villagePos)
        {
            foreach (var town in towns)
            {
                float distance = Vector2.Distance(new Vector2(villagePos.x, villagePos.y), new Vector2(town.position.x, town.position.y));
                if (distance < nearestDistance)
                {
                    nearestDistance = distance;
                    nearestPoint = town.position;
                }
            }
        }

        return nearestPoint;
    }

    private void ConnectToMapEdges(MapData mapData, List<Settlement> settlements)
    {
        var towns = settlements.Where(s => s.Type == SettlementType.Town).ToList();

        // Only connect 1-2 towns to map edges (trade routes)
        int edgeConnections = Mathf.Min(2, towns.Count);

        for (int i = 0; i < edgeConnections; i++)
        {
            var town = towns[i];
            Vector2Int edgePoint = FindNearestEdgePoint(mapData, town.position);
            CreateRoad(mapData, town.position, edgePoint);
        }
    }

    private Vector2Int FindNearestEdgePoint(MapData mapData, Vector2Int position)
    {
        int distToLeft = position.x;
        int distToRight = mapData.Width - 1 - position.x;
        int distToTop = mapData.Height - 1 - position.y;
        int distToBottom = position.y;

        int minDist = Mathf.Min(distToLeft, distToRight, distToTop, distToBottom);

        if (minDist == distToLeft)
            return new Vector2Int(0, position.y);
        else if (minDist == distToRight)
            return new Vector2Int(mapData.Width - 1, position.y);
        else if (minDist == distToTop)
            return new Vector2Int(position.x, mapData.Height - 1);
        else
            return new Vector2Int(position.x, 0);
    }

    private List<Vector2Int> CreateRoad(MapData mapData, Vector2Int start, Vector2Int end)
    {
        var path = FindPath(mapData, start, end);

        // Process the path to handle water crossings and mountain tunnels
        path = ProcessRoadPath(mapData, path);

        foreach (var point in path)
        {
            if (mapData.IsValidPosition(point.x, point.y))
            {
                MapTile tile = mapData.GetTile(point.x, point.y);
                if (tile.featureType == FeatureType.None)
                {
                    // Determine road type based on terrain
                    if (tile.IsWater())
                    {
                        tile.featureType = FeatureType.Bridge;
                    }
                    else if (tile.terrainType == TerrainType.Mountain)
                    {
                        tile.featureType = FeatureType.Tunnel;
                    }
                    else
                    {
                        tile.featureType = FeatureType.Road;
                    }
                    tile.isWalkable = true;
                }
            }
        }

        return path;
    }

    private List<Vector2Int> ProcessRoadPath(MapData mapData, List<Vector2Int> originalPath)
    {
        List<Vector2Int> processedPath = new List<Vector2Int>();

        for (int i = 0; i < originalPath.Count; i++)
        {
            Vector2Int current = originalPath[i];
            processedPath.Add(current);

            // Check if we're about to cross water and need a bridge
            if (i < originalPath.Count - 1)
            {
                Vector2Int next = originalPath[i + 1];

                if (mapData.IsValidPosition(next.x, next.y) && mapData.GetTile(next.x, next.y).IsWater())
                {
                    // We're about to enter water, check bridge length
                    List<Vector2Int> waterCrossing = GetWaterCrossingSegment(mapData, originalPath, i + 1);

                    Debug.Log($"Water crossing detected: {waterCrossing.Count} tiles");

                    if (waterCrossing.Count > 5) // Bridge too long
                    {
                        // Check if this is an ocean crossing - perfect for harbours and ferry
                        if (IsOceanCrossing(mapData, waterCrossing))
                        {
                            Debug.Log($"Ocean crossing detected ({waterCrossing.Count} tiles) - creating harbour and ferry connection");
                            CreateHarbourFerryConnection(mapData, current, waterCrossing, originalPath, i);
                            // Continue with the road after the water crossing
                            i += waterCrossing.Count; // Skip over the water tiles
                            continue;
                        }
                        // Check if it's a large lake - also suitable for harbours
                        else if (IsLargeLakeCrossing(mapData, waterCrossing))
                        {
                            Debug.Log($"Large lake crossing detected ({waterCrossing.Count} tiles) - creating harbour connection");
                            CreateHarbourFerryConnection(mapData, current, waterCrossing, originalPath, i);
                            // Continue with the road after the water crossing
                            i += waterCrossing.Count; // Skip over the water tiles
                            continue;
                        }
                        else
                        {
                            // It's a river or small lake - try to find alternative path or skip this connection
                            Debug.LogWarning($"Bridge too long ({waterCrossing.Count} tiles), skipping water crossing - not suitable for harbours");
                            break; // Stop building this road segment
                        }
                    }
                    else
                    {
                        Debug.Log($"Water crossing short enough for bridge ({waterCrossing.Count} tiles)");
                    }
                }
            }
        }

        return processedPath;
    }

    private List<Vector2Int> GetWaterCrossingSegment(MapData mapData, List<Vector2Int> path, int startIndex)
    {
        List<Vector2Int> waterSegment = new List<Vector2Int>();

        for (int i = startIndex; i < path.Count; i++)
        {
            Vector2Int point = path[i];
            if (mapData.IsValidPosition(point.x, point.y) && mapData.GetTile(point.x, point.y).IsWater())
            {
                waterSegment.Add(point);
            }
            else
            {
                break; // End of water crossing
            }
        }

        return waterSegment;
    }

    private bool IsOceanCrossing(MapData mapData, List<Vector2Int> waterCrossing)
    {
        // Check if any of the water tiles are ocean tiles
        int oceanTiles = 0;
        int totalWaterTiles = 0;

        foreach (var waterTile in waterCrossing)
        {
            if (mapData.IsValidPosition(waterTile.x, waterTile.y))
            {
                MapTile tile = mapData.GetTile(waterTile.x, waterTile.y);
                totalWaterTiles++;
                if (tile.terrainType == TerrainType.Ocean)
                {
                    oceanTiles++;
                }
            }
        }

        Debug.Log($"Water crossing analysis: {oceanTiles} ocean tiles out of {totalWaterTiles} total water tiles");

        // Consider it an ocean crossing if more than 30% of the water is ocean
        return oceanTiles > 0 && (float)oceanTiles / totalWaterTiles > 0.3f;
    }

    private bool IsLargeLakeCrossing(MapData mapData, List<Vector2Int> waterCrossing)
    {
        // Check if any of the water tiles are lake tiles and it's a substantial crossing
        int lakeTiles = 0;
        int totalWaterTiles = 0;

        foreach (var waterTile in waterCrossing)
        {
            if (mapData.IsValidPosition(waterTile.x, waterTile.y))
            {
                MapTile tile = mapData.GetTile(waterTile.x, waterTile.y);
                totalWaterTiles++;
                if (tile.terrainType == TerrainType.Lake)
                {
                    lakeTiles++;
                }
            }
        }

        Debug.Log($"Lake crossing analysis: {lakeTiles} lake tiles out of {totalWaterTiles} total water tiles");

        // Consider it a large lake crossing if:
        // 1. More than 50% of the water is lake
        // 2. AND the crossing is at least 8 tiles long (larger than normal bridge)
        return lakeTiles > 0 &&
               (float)lakeTiles / totalWaterTiles > 0.5f &&
               waterCrossing.Count >= 8;
    }

    private void CreateHarbourFerryConnection(MapData mapData, Vector2Int roadStart, List<Vector2Int> waterCrossing, List<Vector2Int> originalPath, int pathIndex)
    {
        // Find the end of the water crossing to place the destination harbour
        Vector2Int roadEnd = Vector2Int.zero;
        int endIndex = pathIndex + 1 + waterCrossing.Count;

        if (endIndex < originalPath.Count)
        {
            roadEnd = originalPath[endIndex];
        }
        else if (waterCrossing.Count > 0)
        {
            // Use the last water tile and find adjacent land
            Vector2Int lastWaterTile = waterCrossing[waterCrossing.Count - 1];
            roadEnd = FindNearestLandTile(mapData, lastWaterTile);
        }

        if (roadEnd != Vector2Int.zero)
        {
            // Create harbour at the start of water crossing
            Vector2Int startHarbour = FindHarbourPosition(mapData, roadStart);
            if (startHarbour != Vector2Int.zero && !HasNearbyHarbour(mapData, startHarbour, 8))
            {
                mapData.GetTile(startHarbour.x, startHarbour.y).featureType = FeatureType.Harbour;
                Debug.Log($"Created start harbour at {startHarbour}");
            }
            else if (startHarbour != Vector2Int.zero)
            {
                Debug.Log($"Skipped start harbour at {startHarbour} - too close to existing harbour");
                // Still try to find the existing nearby harbour for ferry connection
                startHarbour = FindNearestHarbour(mapData, startHarbour, 8);
            }

            // Create harbour at the end of water crossing
            Vector2Int endHarbour = FindHarbourPosition(mapData, roadEnd);
            if (endHarbour != Vector2Int.zero && !HasNearbyHarbour(mapData, endHarbour, 8))
            {
                mapData.GetTile(endHarbour.x, endHarbour.y).featureType = FeatureType.Harbour;
                Debug.Log($"Created end harbour at {endHarbour}");
            }
            else if (endHarbour != Vector2Int.zero)
            {
                Debug.Log($"Skipped end harbour at {endHarbour} - too close to existing harbour");
                // Still try to find the existing nearby harbour for ferry connection
                endHarbour = FindNearestHarbour(mapData, endHarbour, 8);
            }

            // Create ferry route between harbours (visual connection)
            if (startHarbour != Vector2Int.zero && endHarbour != Vector2Int.zero)
            {
                CreateFerryRoute(mapData, startHarbour, endHarbour);
            }
        }
    }

    private Vector2Int FindHarbourPosition(MapData mapData, Vector2Int nearPosition)
    {
        // Look for shore tiles near the given position that can become harbours
        for (int range = 1; range <= 5; range++)
        {
            for (int x = nearPosition.x - range; x <= nearPosition.x + range; x++)
            {
                for (int y = nearPosition.y - range; y <= nearPosition.y + range; y++)
                {
                    if (mapData.IsValidPosition(x, y))
                    {
                        MapTile tile = mapData.GetTile(x, y);

                        // Perfect spot: shore tile adjacent to water
                        if (tile.terrainType == TerrainType.Shore && IsAdjacentToWater(mapData, x, y))
                        {
                            return new Vector2Int(x, y);
                        }

                        // Alternative: land tile adjacent to water that we can convert to shore/harbour
                        if ((tile.terrainType == TerrainType.Plains || tile.terrainType == TerrainType.Forest)
                            && IsAdjacentToWater(mapData, x, y) && tile.featureType == FeatureType.None)
                        {
                            // Convert to shore first, then harbour
                            tile.terrainType = TerrainType.Shore;
                            return new Vector2Int(x, y);
                        }
                    }
                }
            }
        }
        return Vector2Int.zero;
    }

    private Vector2Int FindNearestLandTile(MapData mapData, Vector2Int waterPosition)
    {
        // Find the nearest non-water tile from the given water position
        for (int range = 1; range <= 10; range++)
        {
            for (int x = waterPosition.x - range; x <= waterPosition.x + range; x++)
            {
                for (int y = waterPosition.y - range; y <= waterPosition.y + range; y++)
                {
                    if (mapData.IsValidPosition(x, y))
                    {
                        MapTile tile = mapData.GetTile(x, y);
                        if (!tile.IsWater())
                        {
                            return new Vector2Int(x, y);
                        }
                    }
                }
            }
        }
        return Vector2Int.zero;
    }

    private bool IsAdjacentToWater(MapData mapData, int x, int y)
    {
        // Check if the tile is adjacent to any water tile
        Vector2Int[] directions = {
            new Vector2Int(1, 0), new Vector2Int(-1, 0),
            new Vector2Int(0, 1), new Vector2Int(0, -1)
        };

        foreach (var dir in directions)
        {
            int checkX = x + dir.x;
            int checkY = y + dir.y;

            if (mapData.IsValidPosition(checkX, checkY))
            {
                MapTile tile = mapData.GetTile(checkX, checkY);
                if (tile.IsWater())
                {
                    return true;
                }
            }
        }
        return false;
    }

    private void CreateFerryRoute(MapData mapData, Vector2Int startHarbour, Vector2Int endHarbour)
    {
        // Create a simple straight line ferry route for visualization
        // This could be enhanced with ferry scheduling, costs, etc.

        Vector2Int current = startHarbour;
        Vector2Int direction = new Vector2Int(
            endHarbour.x > startHarbour.x ? 1 : (endHarbour.x < startHarbour.x ? -1 : 0),
            endHarbour.y > startHarbour.y ? 1 : (endHarbour.y < startHarbour.y ? -1 : 0)
        );

        int steps = 0;
        int maxSteps = Mathf.Max(Mathf.Abs(endHarbour.x - startHarbour.x), Mathf.Abs(endHarbour.y - startHarbour.y));

        while (current != endHarbour && steps < maxSteps * 2)
        {
            steps++;
            current += direction;

            if (mapData.IsValidPosition(current.x, current.y))
            {
                MapTile tile = mapData.GetTile(current.x, current.y);

                // Mark water tiles as ferry route
                if (tile.IsWater() && tile.featureType == FeatureType.None)
                {
                    tile.featureType = FeatureType.Ferry;
                    tile.isWalkable = true; // Ferry routes are walkable (for a cost)
                }
            }

            // Adjust direction to reach target
            if (current.x != endHarbour.x)
                direction.x = endHarbour.x > current.x ? 1 : -1;
            if (current.y != endHarbour.y)
                direction.y = endHarbour.y > current.y ? 1 : -1;
        }

        Debug.Log($"Created ferry route from {startHarbour} to {endHarbour}");
    }

    private void GenerateLakeHarbours(MapData mapData)
    {
        // Find lakes and add small harbours to them
        HashSet<Vector2Int> processedAreas = new HashSet<Vector2Int>();
        int harboursCreated = 0;
        int maxHarbours = 3; // Reduced from 6 to prevent too many harbours

        for (int x = 0; x < mapData.Width && harboursCreated < maxHarbours; x++)
        {
            for (int y = 0; y < mapData.Height && harboursCreated < maxHarbours; y++)
            {
                if (processedAreas.Contains(new Vector2Int(x, y)))
                    continue;

                MapTile tile = mapData.GetTile(x, y);
                if (tile.terrainType == TerrainType.Lake)
                {
                    // Check if this lake is large enough for a harbour
                    int lakeSize = MeasureLakeSize(mapData, x, y, processedAreas);

                    if (lakeSize >= 25) // Increased from 15 - only add harbours to larger lakes
                    {
                        Vector2Int harbourPos = FindLakeHarbourPosition(mapData, x, y);
                        if (harbourPos != Vector2Int.zero && !HasNearbyHarbour(mapData, harbourPos, 12))
                        {
                            mapData.GetTile(harbourPos.x, harbourPos.y).featureType = FeatureType.Harbour;
                            harboursCreated++;
                            Debug.Log($"Created lake harbour at {harbourPos} (lake size: {lakeSize})");
                        }
                        else if (harbourPos != Vector2Int.zero)
                        {
                            Debug.Log($"Skipped lake harbour at {harbourPos} - too close to existing harbour");
                        }
                    }
                }
            }
        }

        Debug.Log($"Generated {harboursCreated} lake harbours");
    }

    private int MeasureLakeSize(MapData mapData, int startX, int startY, HashSet<Vector2Int> processedAreas)
    {
        // Simple flood fill to measure lake size
        Queue<Vector2Int> toCheck = new Queue<Vector2Int>();
        HashSet<Vector2Int> lakeArea = new HashSet<Vector2Int>();

        toCheck.Enqueue(new Vector2Int(startX, startY));

        while (toCheck.Count > 0 && lakeArea.Count < 100) // Limit search to prevent performance issues
        {
            Vector2Int current = toCheck.Dequeue();

            if (lakeArea.Contains(current) || !mapData.IsValidPosition(current.x, current.y))
                continue;

            MapTile tile = mapData.GetTile(current.x, current.y);
            if (tile.terrainType != TerrainType.Lake)
                continue;

            lakeArea.Add(current);
            processedAreas.Add(current);

            // Check adjacent tiles
            Vector2Int[] directions = {
                new Vector2Int(1, 0), new Vector2Int(-1, 0),
                new Vector2Int(0, 1), new Vector2Int(0, -1)
            };

            foreach (var dir in directions)
            {
                Vector2Int next = current + dir;
                if (!lakeArea.Contains(next))
                {
                    toCheck.Enqueue(next);
                }
            }
        }

        return lakeArea.Count;
    }

    private Vector2Int FindLakeHarbourPosition(MapData mapData, int lakeX, int lakeY)
    {
        // Find a good position for a harbour near this lake
        for (int range = 1; range <= 8; range++)
        {
            for (int x = lakeX - range; x <= lakeX + range; x++)
            {
                for (int y = lakeY - range; y <= lakeY + range; y++)
                {
                    if (mapData.IsValidPosition(x, y))
                    {
                        MapTile tile = mapData.GetTile(x, y);

                        // Look for shore tiles or land tiles adjacent to the lake
                        if ((tile.terrainType == TerrainType.Shore ||
                             tile.terrainType == TerrainType.Plains ||
                             tile.terrainType == TerrainType.Forest) &&
                            tile.featureType == FeatureType.None &&
                            IsAdjacentToLake(mapData, x, y))
                        {
                            // Convert to shore if it isn't already
                            if (tile.terrainType != TerrainType.Shore)
                            {
                                tile.terrainType = TerrainType.Shore;
                            }
                            return new Vector2Int(x, y);
                        }
                    }
                }
            }
        }
        return Vector2Int.zero;
    }

    private bool HasNearbyHarbour(MapData mapData, Vector2Int position, int checkRadius)
    {
        // Check if there's already a harbour within the specified radius
        for (int x = position.x - checkRadius; x <= position.x + checkRadius; x++)
        {
            for (int y = position.y - checkRadius; y <= position.y + checkRadius; y++)
            {
                if (mapData.IsValidPosition(x, y))
                {
                    MapTile tile = mapData.GetTile(x, y);
                    if (tile.featureType == FeatureType.Harbour)
                    {
                        float distance = Vector2.Distance(
                            new Vector2(position.x, position.y),
                            new Vector2(x, y)
                        );
                        if (distance <= checkRadius)
                        {
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }

    private Vector2Int FindNearestHarbour(MapData mapData, Vector2Int position, int searchRadius)
    {
        // Find the nearest existing harbour within the search radius
        Vector2Int nearestHarbour = Vector2Int.zero;
        float nearestDistance = float.MaxValue;

        for (int x = position.x - searchRadius; x <= position.x + searchRadius; x++)
        {
            for (int y = position.y - searchRadius; y <= position.y + searchRadius; y++)
            {
                if (mapData.IsValidPosition(x, y))
                {
                    MapTile tile = mapData.GetTile(x, y);
                    if (tile.featureType == FeatureType.Harbour)
                    {
                        float distance = Vector2.Distance(
                            new Vector2(position.x, position.y),
                            new Vector2(x, y)
                        );
                        if (distance <= searchRadius && distance < nearestDistance)
                        {
                            nearestDistance = distance;
                            nearestHarbour = new Vector2Int(x, y);
                        }
                    }
                }
            }
        }
        return nearestHarbour;
    }

    private bool IsAdjacentToLake(MapData mapData, int x, int y)
    {
        Vector2Int[] directions = {
            new Vector2Int(1, 0), new Vector2Int(-1, 0),
            new Vector2Int(0, 1), new Vector2Int(0, -1)
        };

        foreach (var dir in directions)
        {
            int checkX = x + dir.x;
            int checkY = y + dir.y;

            if (mapData.IsValidPosition(checkX, checkY))
            {
                MapTile tile = mapData.GetTile(checkX, checkY);
                if (tile.terrainType == TerrainType.Lake)
                {
                    return true;
                }
            }
        }
        return false;
    }

    private List<Vector2Int> FindPath(MapData mapData, Vector2Int start, Vector2Int end)
    {
        // Simple pathfinding with some randomness for variation and water avoidance
        List<Vector2Int> path = new List<Vector2Int>();
        Vector2Int current = start;
        HashSet<Vector2Int> visitedPositions = new HashSet<Vector2Int>();
        int maxIterations = mapData.Width * mapData.Height; // Prevent infinite loops
        int iterations = 0;

        while (current != end && iterations < maxIterations)
        {
            iterations++;

            // Check if we're stuck in a loop
            if (visitedPositions.Contains(current))
            {
                Debug.LogWarning($"Pathfinding detected loop at {current}, breaking to prevent infinite loop");
                break;
            }

            visitedPositions.Add(current);
            path.Add(current);

            Vector2Int direction = new Vector2Int(
                end.x > current.x ? 1 : (end.x < current.x ? -1 : 0),
                end.y > current.y ? 1 : (end.y < current.y ? -1 : 0)
            );

            // Add some randomness to avoid perfectly straight roads
            if (Random.value < 0.3f)
            {
                if (Random.value < 0.5f)
                    direction.x = 0;
                else
                    direction.y = 0;
            }

            Vector2Int nextPos = current + direction;

            // Check if next position would be water and try to avoid long water crossings
            if (mapData.IsValidPosition(nextPos.x, nextPos.y))
            {
                MapTile nextTile = mapData.GetTile(nextPos.x, nextPos.y);

                // If next tile is water, try to find alternative route first
                if (nextTile.IsWater())
                {
                    Vector2Int alternativePos = FindAlternativeRoute(mapData, current, end, visitedPositions);
                    if (alternativePos != current && !visitedPositions.Contains(alternativePos))
                    {
                        nextPos = alternativePos;
                    }
                }
            }

            // Ensure we're making progress and not going to visited positions
            if (!mapData.IsValidPosition(nextPos.x, nextPos.y) || visitedPositions.Contains(nextPos))
            {
                // Find any valid adjacent position that moves toward target
                Vector2Int fallbackPos = FindFallbackMove(mapData, current, end, visitedPositions);
                if (fallbackPos != current)
                {
                    nextPos = fallbackPos;
                }
                else
                {
                    Debug.LogWarning($"Pathfinding stuck at {current}, unable to continue to {end}");
                    break;
                }
            }

            current = nextPos;
        }

        if (iterations >= maxIterations)
        {
            Debug.LogError($"Pathfinding exceeded maximum iterations ({maxIterations}), terminating path from {start} to {end}");
        }

        // Only add end if we actually reached it
        if (current == end)
        {
            path.Add(end);
        }

        return path;
    }

    private Vector2Int FindAlternativeRoute(MapData mapData, Vector2Int current, Vector2Int end, HashSet<Vector2Int> visitedPositions = null)
    {
        // Try to find a non-water adjacent tile that still moves toward the destination
        Vector2Int[] directions = {
            new Vector2Int(1, 0), new Vector2Int(-1, 0),
            new Vector2Int(0, 1), new Vector2Int(0, -1),
            new Vector2Int(1, 1), new Vector2Int(-1, -1),
            new Vector2Int(1, -1), new Vector2Int(-1, 1)
        };

        Vector2Int bestDirection = Vector2Int.zero;
        float bestScore = float.MaxValue;

        foreach (var dir in directions)
        {
            Vector2Int candidate = current + dir;

            if (mapData.IsValidPosition(candidate.x, candidate.y))
            {
                // Skip if we've already visited this position
                if (visitedPositions != null && visitedPositions.Contains(candidate))
                    continue;

                MapTile candidateTile = mapData.GetTile(candidate.x, candidate.y);

                // Prefer non-water tiles
                if (!candidateTile.IsWater())
                {
                    // Calculate distance to end and prefer directions that move toward target
                    float distanceToEnd = Vector2.Distance(new Vector2(candidate.x, candidate.y), new Vector2(end.x, end.y));
                    float currentDistanceToEnd = Vector2.Distance(new Vector2(current.x, current.y), new Vector2(end.x, end.y));

                    // Only consider if it moves us closer or maintains distance
                    if (distanceToEnd <= currentDistanceToEnd + 1f && distanceToEnd < bestScore)
                    {
                        bestScore = distanceToEnd;
                        bestDirection = dir;
                    }
                }
            }
        }

        return bestDirection != Vector2Int.zero ? current + bestDirection : current;
    }

    private Vector2Int FindFallbackMove(MapData mapData, Vector2Int current, Vector2Int end, HashSet<Vector2Int> visitedPositions)
    {
        // Find any valid adjacent position that hasn't been visited and moves toward target
        Vector2Int[] directions = {
            new Vector2Int(1, 0), new Vector2Int(-1, 0),
            new Vector2Int(0, 1), new Vector2Int(0, -1),
            new Vector2Int(1, 1), new Vector2Int(-1, -1),
            new Vector2Int(1, -1), new Vector2Int(-1, 1)
        };

        Vector2Int bestMove = current;
        float bestDistance = float.MaxValue;

        foreach (var dir in directions)
        {
            Vector2Int candidate = current + dir;

            if (mapData.IsValidPosition(candidate.x, candidate.y) && !visitedPositions.Contains(candidate))
            {
                float distanceToEnd = Vector2.Distance(new Vector2(candidate.x, candidate.y), new Vector2(end.x, end.y));
                if (distanceToEnd < bestDistance)
                {
                    bestDistance = distanceToEnd;
                    bestMove = candidate;
                }
            }
        }

        return bestMove;
    }
}