namespace HorizonRP;

/// <summary>
/// La carte du GPS : passer d'une position du monde à un pixel de l'image (ui/gps/carte.jpg) et
/// retour, et tracer un itinéraire par les rues. Les deux viennent d'outils/gps (README du jeu) :
/// l'image est un rendu orthographique de la ville vue de haut, nord (+X) en haut, +Y à gauche ;
/// la grille (<see cref="Packed"/>, GpsData.cs) dit, par cellule de 48 pouces, où passe la
/// chaussée. Tout se calcule chez le joueur : l'itinéraire ne regarde que lui.
///
/// L'itinéraire est un A* sur la grille, huit voisins, et ne passe que par la chaussée, à pied
/// comme en voiture : sur Truenorth, les cellules dont le sol porte un matériau de route de la
/// map (outils/gps/gps_truenorth.py), un seul réseau d'un tenant. Tout le reste est
/// infranchissable : passer par les pelouses faisait couper à travers les parcs. Départ et arrivée
/// se raccrochent à la route la plus proche ; le tracé commence et finit par un trait droit
/// jusqu'au joueur et à la destination. (Le couloir 'c' venait des routes tracées à la main sur
/// Union : la grille de Truenorth n'en a plus, le code le lit encore.)
/// </summary>
public static partial class GpsMap
{
	const byte Blocked = 0, Road = 1, Walk = 2, Corridor = 3;

	static byte[] grid;
	// Les données d'où la grille a été décodée : un champ statique survit au rechargement à chaud,
	// la grille se redécode donc quand GpsData.cs change.
	static string gridSource;

	static byte[] Grid
	{
		get
		{
			if ( grid is not null && ReferenceEquals( gridSource, Packed ) )
				return grid;
			gridSource = Packed;
			grid = new byte[Rows * Columns];
			var rows = Packed.Split( '|' );
			for ( var i = 0; i < Rows && i < rows.Length; i++ )
			{
				var row = rows[i];
				var j = 0;
				var n = 0;
				foreach ( var c in row )
				{
					if ( char.IsDigit( c ) )
					{
						n = n * 10 + (c - '0');
						continue;
					}
					var value = c == 'r' ? Road : c == 'c' ? Corridor : c == '.' ? Walk : Blocked;
					for ( var k = 0; k < n && j < Columns; k++, j++ )
						grid[i * Columns + j] = value;
					n = 0;
				}
			}
			return grid;
		}
	}

	/// <summary>Le pixel de l'image (0 à <see cref="ImageSize"/>) d'une position du monde.</summary>
	public static Vector2 ToImage( Vector3 world ) =>
		new( ImageSize / 2f - (world.y - CenterY) / UnitsPerPixel, ImageSize / 2f - (world.x - CenterX) / UnitsPerPixel );

	/// <summary>La position du monde (au sol, z inconnu) d'un pixel de l'image.</summary>
	public static Vector3 ToWorld( Vector2 image ) =>
		new( CenterX + (ImageSize / 2f - image.y) * UnitsPerPixel, CenterY + (ImageSize / 2f - image.x) * UnitsPerPixel, 0 );

	/// <summary>Le cap d'une rotation sur la carte, en degrés dans le sens horaire depuis le haut (nord).</summary>
	public static float Heading( float yaw ) => -yaw;

	static int CellI( float x ) => (int)MathF.Floor( (x - MinX) / Cell );
	static int CellJ( float y ) => (int)MathF.Floor( (y - MinY) / Cell );
	static bool Inside( int i, int j ) => i >= 0 && j >= 0 && i < Rows && j < Columns;
	static Vector3 CellCenter( int i, int j ) => new( MinX + (i + 0.5f) * Cell, MinY + (j + 0.5f) * Cell, 0 );

	static bool OnRoute( byte v ) => v == Road || v == Corridor;

	/// <summary>La cellule de route la plus proche (à 60 cellules au plus, ~70 m), ou -1.</summary>
	static int Nearest( Vector3 at )
	{
		var g = Grid;
		int ci = CellI( at.x ), cj = CellJ( at.y );
		var best = -1;
		var bestDistance = int.MaxValue;
		for ( var r = 0; r < 60; r++ )
		{
			for ( var di = -r; di <= r; di++ )
				for ( var dj = -r; dj <= r; dj++ )
				{
					if ( Math.Max( Math.Abs( di ), Math.Abs( dj ) ) != r )
						continue;
					int i = ci + di, j = cj + dj;
					if ( !Inside( i, j ) || !OnRoute( g[i * Columns + j] ) )
						continue;
					var d = di * di + dj * dj;
					if ( d < bestDistance )
					{
						bestDistance = d;
						best = i * Columns + j;
					}
				}
			// Le carré parcouru contient désormais le plus proche à coup sûr.
			if ( best >= 0 && r * r >= bestDistance )
				return best;
		}
		return best;
	}

	/// <summary>
	/// L'itinéraire de <paramref name="from"/> à <paramref name="to"/> (positions du monde, z ignoré),
	/// simplifié en quelques points, ou null s'il n'y en a pas. <paramref name="driving"/> : rester
	/// sur la chaussée.
	/// </summary>
	public static List<Vector3> Route( Vector3 from, Vector3 to, bool driving )
	{
		var g = Grid;
		var start = Nearest( from );
		var goal = Nearest( to );
		if ( start < 0 || goal < 0 )
			return null;
		var count = Rows * Columns;
		var cost = new float[count];
		var came = new int[count];
		var closed = new bool[count];
		Array.Fill( cost, float.MaxValue );
		cost[start] = 0;
		came[start] = -1;

		int gi = goal / Columns, gj = goal % Columns;
		var open = new Heap();
		open.Push( start, 0 );
		var found = false;

		while ( open.Count > 0 )
		{
			var current = open.Pop();
			if ( closed[current] )
				continue;
			if ( current == goal )
			{
				found = true;
				break;
			}
			closed[current] = true;
			int i = current / Columns, j = current % Columns;

			for ( var di = -1; di <= 1; di++ )
				for ( var dj = -1; dj <= 1; dj++ )
				{
					if ( di == 0 && dj == 0 )
						continue;
					int ni = i + di, nj = j + dj;
					if ( !Inside( ni, nj ) )
						continue;
					var next = ni * Columns + nj;
					var v = g[next];
					if ( !OnRoute( v ) || closed[next] )
						continue;
					// Pas de diagonale qui coupe un angle hors de la route.
					if ( di != 0 && dj != 0 && (!OnRoute( g[i * Columns + nj] ) || !OnRoute( g[ni * Columns + j] )) )
						continue;
					var step = (di != 0 && dj != 0 ? 1.4142f : 1f) * (v == Road ? 1f : 1.6f);
					var c = cost[current] + step;
					if ( c >= cost[next] )
						continue;
					cost[next] = c;
					came[next] = current;
					// Octile : n'exagère jamais la distance restante (la route coûte 1).
					int dx = Math.Abs( ni - gi ), dy = Math.Abs( nj - gj );
					open.Push( next, c + Math.Max( dx, dy ) + 0.4142f * Math.Min( dx, dy ) );
				}
		}

		if ( !found )
			return null;

		var cells = new List<int>();
		for ( var c = goal; c >= 0; c = came[c] )
			cells.Add( c );
		cells.Reverse();

		var points = cells.Select( c => CellCenter( c / Columns, c % Columns ) ).ToList();
		points = Simplify( points, Cell * 0.9f );
		points.Insert( 0, from.WithZ( 0 ) );
		points.Add( to.WithZ( 0 ) );
		return points;
	}

	/// <summary>
	/// Des points répartis le long des routes (à plat, z inconnu), au moins <paramref name="spacing"/>
	/// unités l'un de l'autre : où poser l'éclairage public (DayNight).
	/// </summary>
	public static List<Vector3> RoadPoints( float spacing )
	{
		var g = Grid;
		var points = new List<Vector3>();
		var cell = Math.Max( 1, (int)(spacing / Cell) );
		var taken = new HashSet<(int, int)>();
		for ( var i = 0; i < Rows; i++ )
			for ( var j = 0; j < Columns; j++ )
			{
				if ( g[i * Columns + j] != Road )
					continue;
				int bi = i / cell, bj = j / cell;
				var near = false;
				for ( var di = -1; di <= 1 && !near; di++ )
					for ( var dj = -1; dj <= 1 && !near; dj++ )
						near = taken.Contains( (bi + di, bj + dj) ) && points.Any( p => p.Distance( CellCenter( i, j ) ) < spacing );
				if ( near )
					continue;
				taken.Add( (bi, bj) );
				points.Add( CellCenter( i, j ) );
			}
		return points;
	}

	/// <summary>Longueur d'un tracé, en unités du monde.</summary>
	public static float Length( IReadOnlyList<Vector3> points )
	{
		var total = 0f;
		for ( var k = 1; k < points.Count; k++ )
			total += points[k].Distance( points[k - 1] );
		return total;
	}

	/// <summary>Douglas-Peucker : on ne garde que les points où le tracé tourne vraiment.</summary>
	static List<Vector3> Simplify( List<Vector3> points, float tolerance )
	{
		if ( points.Count < 3 )
			return points;
		var keep = new bool[points.Count];
		keep[0] = keep[^1] = true;
		var stack = new Stack<(int, int)>();
		stack.Push( (0, points.Count - 1) );
		while ( stack.Count > 0 )
		{
			var (a, b) = stack.Pop();
			var worst = -1;
			var worstDistance = tolerance;
			for ( var k = a + 1; k < b; k++ )
			{
				var d = DistanceToSegment( points[k], points[a], points[b] );
				if ( d > worstDistance )
				{
					worst = k;
					worstDistance = d;
				}
			}
			if ( worst < 0 )
				continue;
			keep[worst] = true;
			stack.Push( (a, worst) );
			stack.Push( (worst, b) );
		}
		return points.Where( ( _, k ) => keep[k] ).ToList();
	}

	/// <summary>Distance (à plat) d'un point à un segment.</summary>
	public static float DistanceToSegment( Vector3 p, Vector3 a, Vector3 b )
	{
		var ab = (b - a).WithZ( 0 );
		var ap = (p - a).WithZ( 0 );
		var len = ab.LengthSquared;
		var t = len < 0.001f ? 0 : Math.Clamp( Vector3.Dot( ap, ab ) / len, 0, 1 );
		return (ap - ab * t).Length;
	}

	/// <summary>Un tas binaire minimal (cellule, priorité) : la file de l'A*.</summary>
	sealed class Heap
	{
		readonly List<(int Cell, float Priority)> items = new();

		public int Count => items.Count;

		public void Push( int cell, float priority )
		{
			items.Add( (cell, priority) );
			var k = items.Count - 1;
			while ( k > 0 )
			{
				var parent = (k - 1) / 2;
				if ( items[parent].Priority <= items[k].Priority )
					break;
				(items[parent], items[k]) = (items[k], items[parent]);
				k = parent;
			}
		}

		public int Pop()
		{
			var top = items[0].Cell;
			var last = items[^1];
			items.RemoveAt( items.Count - 1 );
			if ( items.Count == 0 )
				return top;
			items[0] = last;
			var k = 0;
			while ( true )
			{
				int l = k * 2 + 1, r = l + 1, m = k;
				if ( l < items.Count && items[l].Priority < items[m].Priority ) m = l;
				if ( r < items.Count && items[r].Priority < items[m].Priority ) m = r;
				if ( m == k )
					break;
				(items[m], items[k]) = (items[k], items[m]);
				k = m;
			}
			return top;
		}
	}
}