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

namespace RedSnail.WaterTool2;

/// <summary>
/// Which of a lake's water its rings may draw, as a grid over the lake's bounds.
/// <para>
/// A lake's water is drawn by rings round the camera, and the only places the built mesh is still needed are where
/// rivers open into it: there the surface has to meet the river's rows vertex for vertex, so the built mesh keeps a
/// cap round each mouth and the rings fill everything else. Both are drawn in full and each throws away the pixels
/// the other owns, so neither has to be cut to the other's shape.
/// </para>
/// </summary>
internal sealed class LakeMask
{
	/// <summary>
	/// Roughly how many cells across the mask is, whatever the lake's size: a pond and a lake a kilometre across cost
	/// the same to store and to read. It also sets how sharp a corner of the shore can stay - the distance field
	/// rounds them off at about a cell.
	/// </summary>
	private const int TargetCells = 384;

	public readonly Vector2 Origin;
	public readonly float CellSize;
	public readonly int Width;
	public readonly int Height;

	/// <summary>
	/// Row after row, two distances in world units: x, how far the cell is from the shore, positive inside the lake
	/// and negative outside it; y, how far it is from the nearest river mouth.
	/// <para>
	/// Both are read between the cells rather than from the nearest one, which is what keeps the two lines they draw
	/// smooth: a contour of a value that only changes at cell edges is a staircase of them. The shore distance is a
	/// true signed field and runs across the shore unbroken, so interpolating it is safe anywhere, and its zero
	/// contour follows the outline to well under a cell.
	/// </para>
	/// </summary>
	public readonly Vector2[] Cells;



	private LakeMask(Vector2 _Origin, float _CellSize, int _Width, int _Height)
	{
		Origin = _Origin;
		CellSize = _CellSize;
		Width = _Width;
		Height = _Height;
		Cells = new Vector2[_Width * _Height];
	}



	/// <summary>
	/// Measures a lake: how far every cell is from its shore, and how far from the nearest point where a river meets
	/// it.
	/// </summary>
	/// <param name="_Mouths">
	/// The outline's fixed points - the river rows. A lake with none of them is drawn by its rings alone.
	/// </param>
	public static LakeMask Build(IReadOnlyList<Vector2> _Outline, IReadOnlyList<Vector2> _Mouths)
	{
		int count = _Outline?.Count ?? 0;

		if (count < 3)
			return null;

		float minX = float.MaxValue, minY = float.MaxValue, maxX = float.MinValue, maxY = float.MinValue;

		for (int i = 0; i < count; i++)
		{
			minX = MathF.Min(minX, _Outline[i].x);
			minY = MathF.Min(minY, _Outline[i].y);
			maxX = MathF.Max(maxX, _Outline[i].x);
			maxY = MathF.Max(maxY, _Outline[i].y);
		}

		float span = MathF.Max(maxX - minX, maxY - minY);

		if (span <= 0.0f)
			return null;

		float cellSize = MathF.Max(span / TargetCells, 1.0f);

		// A cell either side, so the edge of the mask is never the edge of the lake.
		var origin = new Vector2(minX - cellSize, minY - cellSize);

		int width = (int)MathF.Ceiling((maxX - minX) / cellSize) + 3;
		int height = (int)MathF.Ceiling((maxY - minY) / cellSize) + 3;

		var mask = new LakeMask(origin, cellSize, width, height);

		var inside = mask.FillInside(_Outline);
		var shore = mask.Chamfer(mask.SeedOutline(_Outline));
		var mouth = mask.Chamfer(mask.SeedPoints(_Mouths));

		for (int i = 0; i < mask.Cells.Length; i++)
			mask.Cells[i] = new Vector2(inside[i] ? shore[i] : -shore[i], mouth[i]);

		return mask;
	}



	/// <summary>
	/// How far inside the shore a point is, in world units; negative outside it.
	/// <para>
	/// Read between the cells exactly as the shader reads it, so where the water can be swum in is where it is drawn.
	/// With rings on, a lake is only meshed round its river mouths, and this is all there is to answer with anywhere
	/// else.
	/// </para>
	/// </summary>
	public float ShoreDistance(Vector2 _Point)
	{
		float localX = (_Point.x - Origin.x) / CellSize - 0.5f;
		float localY = (_Point.y - Origin.y) / CellSize - 0.5f;

		int column = (int)MathF.Floor(localX);
		int row = (int)MathF.Floor(localY);

		float alongX = localX - column;
		float alongY = localY - row;

		float low = Shore(column, row) + (Shore(column + 1, row) - Shore(column, row)) * alongX;
		float high = Shore(column, row + 1) + (Shore(column + 1, row + 1) - Shore(column, row + 1)) * alongX;

		return low + (high - low) * alongY;
	}



	private float Shore(int _Column, int _Row)
	{
		int column = Math.Clamp(_Column, 0, Width - 1);
		int row = Math.Clamp(_Row, 0, Height - 1);

		return Cells[row * Width + column].x;
	}



	/// <summary>
	/// Scanline fill: along each row the outline is crossed in pairs, and the water is between them.
	/// </summary>
	private bool[] FillInside(IReadOnlyList<Vector2> _Outline)
	{
		int count = _Outline.Count;

		var inside = new bool[Width * Height];
		var crossings = new List<float>();

		for (int row = 0; row < Height; row++)
		{
			float y = Origin.y + (row + 0.5f) * CellSize;

			crossings.Clear();

			for (int i = 0; i < count; i++)
			{
				var a = _Outline[i];
				var b = _Outline[(i + 1) % count];

				if ((a.y > y) == (b.y > y))
					continue;

				crossings.Add(a.x + (y - a.y) * (b.x - a.x) / (b.y - a.y));
			}

			if (crossings.Count < 2)
				continue;

			crossings.Sort();

			for (int c = 0; c + 1 < crossings.Count; c += 2)
			{
				int from = (int)MathF.Ceiling((crossings[c] - Origin.x) / CellSize - 0.5f);
				int to = (int)MathF.Floor((crossings[c + 1] - Origin.x) / CellSize - 0.5f);

				from = Math.Max(from, 0);
				to = Math.Min(to, Width - 1);

				for (int column = from; column <= to; column++)
					inside[row * Width + column] = true;
			}
		}

		return inside;
	}



	/// <summary>
	/// A field with nothing in it yet: every cell further away than any route across the grid could be.
	/// </summary>
	private float[] Filled()
	{
		var field = new float[Width * Height];
		float far = (Width + Height) * 2.0f;

		for (int i = 0; i < field.Length; i++)
			field[i] = far;

		return field;
	}



	/// <summary>
	/// Lays the outline into a field, walking each edge in half cells so none of the cells it passes through is
	/// stepped over.
	/// </summary>
	private float[] SeedOutline(IReadOnlyList<Vector2> _Outline)
	{
		var field = Filled();
		int count = _Outline.Count;

		for (int i = 0; i < count; i++)
		{
			var a = _Outline[i];
			var b = _Outline[(i + 1) % count];

			int steps = Math.Max((int)MathF.Ceiling((b - a).Length / (CellSize * 0.5f)), 1);

			for (int s = 0; s <= steps; s++)
				Seed(field, a + (b - a) * (s / (float)steps));
		}

		return field;
	}



	private float[] SeedPoints(IReadOnlyList<Vector2> _Points)
	{
		var field = Filled();
		int count = _Points?.Count ?? 0;

		for (int i = 0; i < count; i++)
			Seed(field, _Points[i]);

		return field;
	}



	/// <summary>
	/// Writes how far a point is into the cell holding it and the eight round it, keeping whichever was nearer.
	/// <para>
	/// The true distance rather than a flat zero, because the handover follows the zero contour of this field and a
	/// field seeded flat puts that contour half a cell off, wherever the point sits inside its cell.
	/// </para>
	/// </summary>
	private void Seed(float[] _Field, Vector2 _Point)
	{
		int column = (int)MathF.Floor((_Point.x - Origin.x) / CellSize);
		int row = (int)MathF.Floor((_Point.y - Origin.y) / CellSize);

		for (int y = row - 1; y <= row + 1; y++)
		{
			if (y < 0 || y >= Height)
				continue;

			for (int x = column - 1; x <= column + 1; x++)
			{
				if (x < 0 || x >= Width)
					continue;

				var centre = new Vector2(Origin.x + (x + 0.5f) * CellSize, Origin.y + (y + 0.5f) * CellSize);
				float away = (centre - _Point).Length / CellSize;

				int index = y * Width + x;

				if (away < _Field[index])
					_Field[index] = away;
			}
		}
	}



	/// <summary>
	/// Spreads a field outwards from whatever was seeded into it, as a chamfer distance: two sweeps carrying the
	/// cheapest route back to a seed, a step costing 1 straight and √2 diagonally. The result is in world units.
	/// <para>
	/// Spreading it a layer at a time is easier but gives a chessboard distance, whose contours are diamonds. Both of
	/// these fields are read as contours, so a blocky distance is a blocky, stepped line however finely it is sampled.
	/// </para>
	/// </summary>
	private float[] Chamfer(float[] _Field)
	{
		const float Straight = 1.0f;
		float diagonal = MathF.Sqrt(2.0f);

		// Down and right, so every cell sees the best route from what is already settled behind it.
		for (int row = 0; row < Height; row++)
		{
			for (int column = 0; column < Width; column++)
			{
				int index = row * Width + column;
				float best = _Field[index];

				if (column > 0) best = MathF.Min(best, _Field[index - 1] + Straight);
				if (row > 0) best = MathF.Min(best, _Field[index - Width] + Straight);
				if (column > 0 && row > 0) best = MathF.Min(best, _Field[index - Width - 1] + diagonal);
				if (column < Width - 1 && row > 0) best = MathF.Min(best, _Field[index - Width + 1] + diagonal);

				_Field[index] = best;
			}
		}

		// And back up and left for the routes the first sweep could not see.
		for (int row = Height - 1; row >= 0; row--)
		{
			for (int column = Width - 1; column >= 0; column--)
			{
				int index = row * Width + column;
				float best = _Field[index];

				if (column < Width - 1) best = MathF.Min(best, _Field[index + 1] + Straight);
				if (row < Height - 1) best = MathF.Min(best, _Field[index + Width] + Straight);
				if (column < Width - 1 && row < Height - 1) best = MathF.Min(best, _Field[index + Width + 1] + diagonal);
				if (column > 0 && row < Height - 1) best = MathF.Min(best, _Field[index + Width - 1] + diagonal);

				_Field[index] = best;
			}
		}

		for (int i = 0; i < _Field.Length; i++)
			_Field[i] *= CellSize;

		return _Field;
	}
}