using System;
using System.Collections.Generic;
using Socer;

public sealed record SquadSkillRoute(SquadSkillConnection Connection,Point[] Points,Point Marker);

public static class SquadSkillLinkGeometry
{
    const float HalfWidth=77.5f,HalfHeight=101.5f;
    public static bool InsideCard(Point point,Point center,float padding=5)=>
        Math.Abs(point.X-center.X)<HalfWidth+padding && Math.Abs(point.Y-center.Y)<HalfHeight+padding;

    static bool Hits(Point a,Point b,Point center,float padding=6)
    {
        float low=0,high=1;var delta=b-a;
        bool Axis(float origin,float direction,float min,float max)
        {
            if(Math.Abs(direction)<.001f)return origin>min && origin<max;
            float x=(min-origin)/direction,y=(max-origin)/direction;
            low=Math.Max(low,Math.Min(x,y));high=Math.Min(high,Math.Max(x,y));
            return low<high;
        }
        return Axis(a.X,delta.X,center.X-HalfWidth-padding,center.X+HalfWidth+padding) &&
            Axis(a.Y,delta.Y,center.Y-HalfHeight-padding,center.Y+HalfHeight+padding);
    }
    static Point Edge(Point center,Point toward)
    {
        var d=toward-center;
        float t=Math.Min((HalfWidth+5)/Math.Max(.001f,Math.Abs(d.X)),(HalfHeight+5)/Math.Max(.001f,Math.Abs(d.Y)));
        return center+d*Math.Min(1,t);
    }
    static Point Marker(Point[] path,Point[] centers,List<SquadSkillRoute> previous)
    {
        Point best=(path[0]+path[^1])*.5f;float score=float.MaxValue;
        float length=0;for(int i=1;i<path.Length;i++)length+=(path[i]-path[i-1]).Length;
        float travelled=0;
        for(int i=1;i<path.Length;i++)
        {
            var a=path[i-1];var d=path[i]-a;float segment=d.Length;
            for(int step=1;step<10;step++)
            {
                float fraction=step/10f;var point=a+d*fraction;
                float penalty=Math.Abs(travelled+segment*fraction-length*.5f);
                foreach(var center in centers)if(InsideCard(point,center,35))penalty+=10000;
                foreach(var route in previous)if((point-route.Marker).Length<76)penalty+=1000;
                if(penalty<score){score=penalty;best=point;}
            }
            travelled+=segment;
        }
        return best;
    }

    // Built only after a lineup/layout change. Straight segments go around cards;
    // their endpoints stop at card edges.
    public static SquadSkillRoute[] Build(SquadSkillConnection[] links,Point[] centers,float width,float height)
    {
        var corners=new List<Point>();
        foreach(var center in centers)
            foreach(int x in new[]{-1,1})foreach(int y in new[]{-1,1})
            {
                var point=center+new Point(x*(HalfWidth+8),y*(HalfHeight+8));
                if(point.X>=12 && point.X<=width-12 && point.Y>=12 && point.Y<=height-12)corners.Add(point);
            }
        var routes=new List<SquadSkillRoute>();
        foreach(var link in links)
        {
            var nodes=new List<Point>{centers[link.FirstSlot],centers[link.SecondSlot]};nodes.AddRange(corners);
            int count=nodes.Count;var costs=new float[count];var visited=new bool[count];var parent=new int[count];
            Array.Fill(costs,float.MaxValue);Array.Fill(parent,-1);costs[0]=0;
            for(int iteration=0;iteration<count;iteration++)
            {
                int from=-1;float distance=float.MaxValue;
                for(int i=0;i<count;i++)if(!visited[i] && costs[i]<distance){from=i;distance=costs[i];}
                if(from<0 || from==1)break;visited[from]=true;
                for(int to=1;to<count;to++)
                {
                    if(to==from || visited[to])continue;
                    bool blocked=false;
                    for(int slot=0;slot<centers.Length;slot++)
                    {
                        if(slot==link.FirstSlot && from==0 || slot==link.SecondSlot && to==1)continue;
                        if(Hits(nodes[from],nodes[to],centers[slot])){blocked=true;break;}
                    }
                    if(blocked)continue;
                    float next=distance+(nodes[to]-nodes[from]).Length+8;
                    if(next<costs[to]){costs[to]=next;parent[to]=from;}
                }
            }
            var path=new List<Point>();
            if(parent[1]>=0){for(int node=1;node>=0;node=parent[node])path.Add(nodes[node]);path.Reverse();}
            else{path.Add(nodes[0]);path.Add(nodes[1]);}
            // A badge still needs room when two cards almost touch vertically.
            if(path.Count==2 && Math.Abs(path[0].X-path[1].X)<HalfWidth*2+70 &&
                Math.Abs(path[0].Y-path[1].Y)<HalfHeight*2+70)
            {
                var a=path[0];var b=path[1];
                foreach(int side in new[]{1,-1})
                {
                    var shift=new Point(side*(HalfWidth+46),0);
                    var candidate=new[]{a,a+shift,b+shift,b};bool clear=true;
                    for(int segment=1;segment<candidate.Length && clear;segment++)
                    {
                        if(candidate[segment].X<12 || candidate[segment].X>width-12){clear=false;break;}
                        for(int slot=0;slot<centers.Length;slot++)
                        {
                            if(slot==link.FirstSlot && segment==1 || slot==link.SecondSlot && segment==candidate.Length-1)continue;
                            if(Hits(candidate[segment-1],candidate[segment],centers[slot])){clear=false;break;}
                        }
                    }
                    if(clear){path=new List<Point>(candidate);break;}
                }
            }
            path[0]=Edge(path[0],path[1]);path[^1]=Edge(path[^1],path[^2]);
            var points=path.ToArray();routes.Add(new(link,points,Marker(points,centers,routes)));
        }
        return routes.ToArray();
    }
}