using Sandbox;
using System;
using System.Collections.Generic;
using System.Linq;

namespace NZombies;

/// <summary>
/// Turns a drawn footprint into a solid barrier — mesh and collision.
///
/// ⛔ THE FOOTPRINT IS THE SHAPE, NOT A HINT AT ONE. Blocks used to be an
/// oriented BOX measured from the clicked corners, so four corners describing an
/// L, a wedge or any non-rectangle were flattened into the rectangle that
/// enclosed them. Reported as "it always makes a rectangle with the 2 furthest
/// from each other" — which is what an enclosing box looks like when the corners
/// were never meant to be one.
///
/// Now the polygon is extruded verbatically: top and bottom faces triangulated,
/// one quad per edge, and convex collision pieces per triangle.
///
/// ⚠️ CONCAVE IS SUPPORTED, which is why this triangulates by ear clipping
/// rather than fanning from a corner. A fan is two lines shorter and silently
/// fills in any dent the polygon has — the exact failure being fixed.
/// </summary>
public static class DebrisMesh
{
	/// <summary>
	/// Build a prism from a footprint.
	///
	/// <paramref name="local"/> is the footprint in the barrier's own space, XY,
	/// centred on its origin. The prism runs from z=0 up to <paramref name="height"/>.
	/// </summary>
	public static Model Build( IReadOnlyList<Vector2> local, float height, Material material )
	{
		if ( local is null || local.Count < 3 ) return null;

		// Ear clipping needs a known winding, and the caller has no reason to
		// guarantee one — corners get clicked whichever way round the player
		// walks. Normalise to counter-clockwise rather than demand it.
		var poly = local.ToList();
		if ( SignedArea( poly ) < 0f ) poly.Reverse();

		var tris = Triangulate( poly );
		if ( tris.Count == 0 ) return null;

		var verts = new List<Vertex>();
		var idx = new List<int>();

		AddCap( verts, idx, poly, tris, height, top: true );
		AddCap( verts, idx, poly, tris, 0f, top: false );
		AddWalls( verts, idx, poly, height );

		// ⛔ BOUNDS ARE NOT DERIVED FROM THE VERTEX BUFFER — THEY MUST BE SET.
		//
		// `Mesh.Bounds` is documented as "Sets AABB bounds for this mesh", and
		// `ModelBuilder.WithViewBounds` as "if not set, the bounds are calculated
		// from the model's meshes" — so leaving the mesh's bounds empty leaves the
		// MODEL's bounds empty, and the renderer frustum-culls against an empty
		// box at the origin. The barrier then renders only when that one point
		// happens to be on screen, which from the outside is "the debris is
		// sometimes invisible depending on my distance to it or angle".
		//
		// ⚠️ Nothing about this fails loudly. There is no warning, no pink error
		// model, and the mesh is perfectly correct — it is simply not submitted.
		// Any runtime-built mesh in this project needs this.
		var lo = new Vector3( float.MaxValue );
		var hi = new Vector3( float.MinValue );

		foreach ( var p in poly )
		{
			lo = Vector3.Min( lo, new Vector3( p.x, p.y, 0f ) );
			hi = Vector3.Max( hi, new Vector3( p.x, p.y, height ) );
		}

		var bounds = new BBox( lo, hi );

		var mesh = new Mesh( material );
		mesh.CreateVertexBuffer( verts.Count, verts );
		mesh.CreateIndexBuffer( idx.Count, idx );

		// After the buffers, not before — creating a buffer is exactly the kind of
		// call that would recompute or clear whatever was set beforehand.
		mesh.Bounds = bounds;

		var builder = Model.Builder.AddMesh( mesh );

		// ⚠️ ONE CONVEX HULL PER TRIANGLE, NOT ONE FOR THE WHOLE SHAPE. A single
		// hull over every point is the convex hull — for a concave footprint that
		// is exactly the over-filled box this class exists to avoid, just with
		// more steps. Per-triangle prisms are individually convex, so together
		// they match the drawn shape however dented it is.
		foreach ( var t in tris )
		{
			builder.AddCollisionHull( new List<Vector3>
			{
				new( poly[t.a].x, poly[t.a].y, 0f ),
				new( poly[t.b].x, poly[t.b].y, 0f ),
				new( poly[t.c].x, poly[t.c].y, 0f ),
				new( poly[t.a].x, poly[t.a].y, height ),
				new( poly[t.b].x, poly[t.b].y, height ),
				new( poly[t.c].x, poly[t.c].y, height ),
			}, null, null );
		}

		// ⚠️ STATED ON THE MODEL TOO, not left to be derived from the mesh above.
		// These are the documented overrides — view bounds drive visibility, hull
		// bounds drive "physics and gameplay queries", which includes the traces
		// the tool aims with and the reach check that decides whether a barrier
		// can be bought. Saying both outright costs two lines and removes the
		// whole class of bug where a barrier is there but nothing can see or
		// find it.
		builder.WithViewBounds( bounds );
		builder.WithHullBounds( bounds );

		return builder.Create();
	}

	/// <summary>
	/// Does the outline cross over itself?
	///
	/// ⚠️ CHECKED BEFORE STORING A FOOTPRINT, not after. Corners are used in the
	/// order they were CLICKED — that is what makes "the shape I draw" the shape
	/// you get — but clicking the four corners of a doorway diagonally gives a
	/// bowtie, which has no interior and no valid ear to clip. Triangulate() only
	/// bails out silently; this lets the caller say what went wrong and how to fix
	/// it, which is the difference between a confusing result and a typo.
	/// </summary>
	public static bool IsSimple( IReadOnlyList<Vector2> p )
	{
		if ( p is null || p.Count < 3 ) return false;

		for ( int i = 0; i < p.Count; i++ )
		{
			var a1 = p[i];
			var a2 = p[(i + 1) % p.Count];

			for ( int j = i + 1; j < p.Count; j++ )
			{
				// Edges that share a corner always "touch" — only edges with no
				// corner in common can cross.
				if ( (j + 1) % p.Count == i ) continue;
				if ( j == (i + 1) % p.Count ) continue;

				if ( Crosses( a1, a2, p[j], p[(j + 1) % p.Count] ) )
					return false;
			}
		}

		return true;
	}

	static bool Crosses( Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2 )
	{
		float d1 = Cross( b2 - b1, a1 - b1 );
		float d2 = Cross( b2 - b1, a2 - b1 );
		float d3 = Cross( a2 - a1, b1 - a1 );
		float d4 = Cross( a2 - a1, b2 - a1 );

		return ((d1 > 0f) != (d2 > 0f)) && ((d3 > 0f) != (d4 > 0f));
	}

	static float Cross( Vector2 a, Vector2 b ) => (a.x * b.y) - (a.y * b.x);

	/// <summary>
	/// Does the outline turn the same way at every corner?
	///
	/// Only asked so the tool can warn about the one place the drawn shape and
	/// the barrier's behaviour still disagree: the nav block is a box, so a
	/// concave shape blocks pathing through its own notch. Convex shapes have no
	/// notch, so nothing to warn about.
	/// </summary>
	public static bool IsConvex( IReadOnlyList<Vector2> p )
	{
		if ( p is null || p.Count < 4 ) return true;

		bool neg = false, pos = false;

		for ( int i = 0; i < p.Count; i++ )
		{
			var a = p[i];
			var b = p[(i + 1) % p.Count];
			var c = p[(i + 2) % p.Count];

			float turn = Cross( b - a, c - b );

			// Three points in a line turn neither way — a corner clicked onto an
			// edge is not a dent, and counting it as one would warn on shapes that
			// are perfectly convex.
			if ( turn > 0.01f ) pos = true;
			else if ( turn < -0.01f ) neg = true;

			if ( neg && pos ) return false;
		}

		return true;
	}

	readonly record struct Tri( int a, int b, int c );

	/// <summary>Positive for counter-clockwise. Also the area, which is why a
	/// degenerate footprint can be spotted with the same number.</summary>
	static float SignedArea( IReadOnlyList<Vector2> p )
	{
		float sum = 0f;
		for ( int i = 0; i < p.Count; i++ )
		{
			var a = p[i];
			var b = p[(i + 1) % p.Count];
			sum += (a.x * b.y) - (b.x * a.y);
		}
		return sum * 0.5f;
	}

	/// <summary>
	/// Ear clipping. O(n²), which for a footprint someone clicked out by hand is
	/// nothing — the alternative algorithms only start paying at hundreds of
	/// points.
	/// </summary>
	static List<Tri> Triangulate( List<Vector2> p )
	{
		var tris = new List<Tri>();
		var live = Enumerable.Range( 0, p.Count ).ToList();

		// ⚠️ GUARDED AGAINST NEVER FINDING AN EAR. A self-intersecting footprint
		// — two clicks that cross the shape over itself — has no valid ear, and
		// without this the loop would spin forever and hang the editor on a
		// misclick. Bail out and let the caller fall back to a box.
		int guard = p.Count * p.Count + 8;

		while ( live.Count > 3 && guard-- > 0 )
		{
			bool clipped = false;

			for ( int i = 0; i < live.Count; i++ )
			{
				int i0 = live[(i - 1 + live.Count) % live.Count];
				int i1 = live[i];
				int i2 = live[(i + 1) % live.Count];

				if ( !IsEar( p, live, i0, i1, i2 ) ) continue;

				tris.Add( new Tri( i0, i1, i2 ) );
				live.RemoveAt( i );
				clipped = true;
				break;
			}

			if ( !clipped ) break;
		}

		if ( live.Count == 3 )
			tris.Add( new Tri( live[0], live[1], live[2] ) );

		return tris;
	}

	static bool IsEar( List<Vector2> p, List<int> live, int i0, int i1, int i2 )
	{
		var a = p[i0];
		var b = p[i1];
		var c = p[i2];

		// Reflex corners are not ears. Cross <= 0 on a CCW polygon means the
		// corner points into the shape.
		float cross = ((b.x - a.x) * (c.y - a.y)) - ((b.y - a.y) * (c.x - a.x));
		if ( cross <= 0f ) return false;

		// And no other vertex may sit inside the candidate triangle, or clipping
		// it would cut across the polygon.
		foreach ( var k in live )
		{
			if ( k == i0 || k == i1 || k == i2 ) continue;
			if ( InTriangle( p[k], a, b, c ) ) return false;
		}

		return true;
	}

	static bool InTriangle( Vector2 pt, Vector2 a, Vector2 b, Vector2 c )
	{
		float d1 = Side( pt, a, b );
		float d2 = Side( pt, b, c );
		float d3 = Side( pt, c, a );

		bool neg = d1 < 0f || d2 < 0f || d3 < 0f;
		bool pos = d1 > 0f || d2 > 0f || d3 > 0f;

		return !(neg && pos);
	}

	static float Side( Vector2 p, Vector2 a, Vector2 b )
		=> ((p.x - b.x) * (a.y - b.y)) - ((a.x - b.x) * (p.y - b.y));

	/// <summary>Top or bottom face. The bottom is wound backwards so it faces
	/// down — a cap wound the same way both ends is invisible from below.</summary>
	static void AddCap( List<Vertex> verts, List<int> idx, List<Vector2> poly,
		List<Tri> tris, float z, bool top )
	{
		var normal = top ? Vector3.Up : Vector3.Down;
		var tangent = Vector3.Forward;
		int start = verts.Count;

		foreach ( var v in poly )
		{
			// UVs from world units so texture scale stays constant whatever size
			// the barrier is drawn at — 128 units per tile.
			verts.Add( new Vertex( new Vector3( v.x, v.y, z ), normal, tangent,
				new Vector4( v.x / 128f, v.y / 128f, 0f, 0f ) ) );
		}

		foreach ( var t in tris )
		{
			if ( top )
			{
				idx.Add( start + t.a ); idx.Add( start + t.b ); idx.Add( start + t.c );
			}
			else
			{
				idx.Add( start + t.c ); idx.Add( start + t.b ); idx.Add( start + t.a );
			}
		}
	}

	/// <summary>One quad per edge, each with its own vertices so the sides get a
	/// hard normal instead of being smoothed into the caps.</summary>
	static void AddWalls( List<Vertex> verts, List<int> idx, List<Vector2> poly, float height )
	{
		float run = 0f;

		for ( int i = 0; i < poly.Count; i++ )
		{
			var a = poly[i];
			var b = poly[(i + 1) % poly.Count];

			var edge = b - a;
			float len = edge.Length;
			if ( len < 0.01f ) continue;

			// Outward normal for a CCW polygon is the edge turned right.
			var n = new Vector3( edge.y, -edge.x, 0f ).Normal;
			var tangent = new Vector3( edge.x, edge.y, 0f ).Normal;

			int s = verts.Count;
			float u0 = run / 128f;
			float u1 = (run + len) / 128f;
			float v1 = height / 128f;

			verts.Add( new Vertex( new Vector3( a.x, a.y, 0f ), n, tangent, new Vector4( u0, 0f, 0f, 0f ) ) );
			verts.Add( new Vertex( new Vector3( b.x, b.y, 0f ), n, tangent, new Vector4( u1, 0f, 0f, 0f ) ) );
			verts.Add( new Vertex( new Vector3( b.x, b.y, height ), n, tangent, new Vector4( u1, v1, 0f, 0f ) ) );
			verts.Add( new Vertex( new Vector3( a.x, a.y, height ), n, tangent, new Vector4( u0, v1, 0f, 0f ) ) );

			idx.Add( s + 0 ); idx.Add( s + 1 ); idx.Add( s + 2 );
			idx.Add( s + 0 ); idx.Add( s + 2 ); idx.Add( s + 3 );

			run += len;
		}
	}
}