using UnityEngine;
using UnityEngine.UI;
using System.Collections.Generic;

public class UntangleGameManager : MonoBehaviour
{
    public GameObject pointPrefab;
    public LineRenderer linePrefab;
    public Text statusText;
    public int pointCount = 10;
    public Button newGameButton, solveButton;

    private List<Point> points = new List<Point>();
    public List<Connection> connections = new List<Connection>();
    private Vector3[] solutionPositions;

    void Start()
    {
        newGameButton.onClick.AddListener(GenerateRandomGame);
        solveButton.onClick.AddListener(AutoSolve);
        GenerateRandomGame();
    }

    void GenerateRandomGame()
    {
        ClearOldGame();
        statusText.text = "";
        points.Clear();
        connections.Clear();
        solutionPositions = new Vector3[pointCount];

        // Step 1: Place points randomly (solution layout)
        for (int i = 0; i < pointCount; i++)
        {
            Vector2 pos;
            int tries = 0;
            do
            {
                pos = Random.insideUnitCircle * 4f;
                tries++;
                if (tries > 1000) break;
            }
            while (IsTooClose(pos));

            GameObject obj = Instantiate(pointPrefab, pos, Quaternion.identity);
            Point p = obj.GetComponent<Point>();
            p.id = i;
            p.manager = this;
            points.Add(p);
            solutionPositions[i] = pos;
        }

        // Step 2: Create a Minimum Spanning Tree (MST)
        List<(int, int, float)> edges = new List<(int, int, float)>();
        for (int i = 0; i < pointCount; i++)
        {
            for (int j = i + 1; j < pointCount; j++)
            {
                float dist = Vector2.Distance(points[i].transform.position, points[j].transform.position);
                edges.Add((i, j, dist));
            }
        }
        edges.Sort((a, b) => a.Item3.CompareTo(b.Item3));

        int[] parent = new int[pointCount];
        for (int i = 0; i < pointCount; i++) parent[i] = i;
        int Find(int x) => parent[x] == x ? x : parent[x] = Find(parent[x]);
        void Union(int x, int y) => parent[Find(x)] = Find(y);

        int edgeCount = 0;
        foreach (var (a, b, _) in edges)
        {
            if (Find(a) != Find(b))
            {
                Union(a, b);
                AddConnection(a, b);
                edgeCount++;
                if (edgeCount == pointCount - 1) break;
            }
        }

        // Step 3: Ensure every point has at least degree 2
        int[] degrees = new int[pointCount];
        foreach (var c in connections)
        {
            degrees[c.a.id]++;
            degrees[c.b.id]++;
        }

        for (int i = 0; i < pointCount; i++)
        {
            while (degrees[i] < 2)
            {
                bool added = false;

                // Try to add a non-crossing edge
                for (int j = 0; j < pointCount; j++)
                {
                    if (i == j || IsConnected(i, j)) continue;

                    Connection temp = new Connection { a = points[i], b = points[j] };
                    if (DoesIntersectAny(temp)) continue;

                    AddConnection(i, j);
                    degrees[i]++;
                    degrees[j]++;
                    added = true;
                    break;
                }

                // If no valid non-crossing edge found, allow one forced connection (rare case)
                if (!added)
                {
                    for (int j = 0; j < pointCount; j++)
                    {
                        if (i == j || IsConnected(i, j)) continue;

                        AddConnection(i, j);
                        degrees[i]++;
                        degrees[j]++;
                        break;
                    }
                }
            }
        }

        // Step 4: Shuffle point positions to create the puzzle
        foreach (var p in points)
        {
            p.transform.position = Random.insideUnitCircle * 4f;
        }

        foreach (var c in connections)
            c.UpdateLine();
    }

    void AddConnection(int a, int b)
    {
        Connection c = new Connection();
        c.a = points[a];
        c.b = points[b];
        c.line = Instantiate(linePrefab);
        c.UpdateLine();
        connections.Add(c);
    }

    bool IsConnected(int a, int b)
    {
        foreach (var c in connections)
        {
            if ((c.a.id == a && c.b.id == b) || (c.a.id == b && c.b.id == a))
                return true;
        }
        return false;
    }

    bool DoesIntersectAny(Connection newC)
    {
        foreach (var c in connections)
        {
            if (newC.SharesPointWith(c)) continue;
            if (LinesIntersect(newC, c)) return true;
        }
        return false;
    }

    bool IsTooClose(Vector2 pos)
    {
        foreach (var p in points)
        {
            if (Vector2.Distance(p.transform.position, pos) < 0.5f)
                return true;
        }
        return false;
    }

    public void CheckIfSolved()
    {
        foreach (var c1 in connections)
        {
            foreach (var c2 in connections)
            {
                if (c1 == c2 || c1.SharesPointWith(c2)) continue;
                if (LinesIntersect(c1, c2))
                {
                    statusText.text = "";
                    return;
                }
            }
        }
        statusText.text = "Completed!";
    }

    void AutoSolve()
    {
        for (int i = 0; i < points.Count; i++)
        {
            points[i].transform.position = solutionPositions[i];
        }

        foreach (var c in connections)
            c.UpdateLine();

        CheckIfSolved();
    }

    void ClearOldGame()
    {
        foreach (var p in points) Destroy(p.gameObject);
        foreach (var c in connections) Destroy(c.line.gameObject);
    }

    bool LinesIntersect(Connection c1, Connection c2)
    {
        Vector2 p1 = c1.a.transform.position;
        Vector2 q1 = c1.b.transform.position;
        Vector2 p2 = c2.a.transform.position;
        Vector2 q2 = c2.b.transform.position;
        return DoIntersect(p1, q1, p2, q2);
    }

    bool DoIntersect(Vector2 p1, Vector2 q1, Vector2 p2, Vector2 q2)
    {
        int o1 = Orientation(p1, q1, p2);
        int o2 = Orientation(p1, q1, q2);
        int o3 = Orientation(p2, q2, p1);
        int o4 = Orientation(p2, q2, q1);
        return (o1 != o2 && o3 != o4);
    }

    int Orientation(Vector2 a, Vector2 b, Vector2 c)
    {
        float val = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
        if (Mathf.Abs(val) < 0.0001f) return 0;
        return (val > 0) ? 1 : 2;
    }
}