namespace AdvancedMappingTools;

/// <summary>
/// One road as the solver sees it, in world space.
/// </summary>
public sealed record RoadInput( PathTrack Track, RoadSection Section, RoadEnd Start, RoadEnd Finish, float TurningRadius, bool Connects );

/// <summary>
/// What a junction wants from the roads around it.
/// </summary>
public sealed record JunctionWish( JunctionStyle Style, float CornerRadius, float OuterRadius );

/// <summary>
/// A road where it stops at a junction. It runs on along <see cref="Forward"/>.
/// </summary>
public sealed record RoadCut( int Road, float Along, bool Forward );

public sealed class SolvedJunction
{
	public Vector3 Center { get; set; }
	public List<RoadCut> Cuts { get; } = [];
	public JunctionWish Wish { get; set; }
}

public sealed class SolvedRoad
{
	public List<RoadStretch> Stretches { get; } = [];
}

/// <summary>
/// Works out how roads meet, from nothing but their lines and widths. Where the end of a road
/// lies on another road, where ends meet at an angle and where two roads cross on the same
/// level, there is a junction. Every road then stops where its curbs start to bend, far
/// enough away for the corners to fit. Roads are never merged: this says where each of them ends.
/// </summary>
public static class RoadNetwork
{
	/// <summary>
	/// Roads further apart in height than this do not meet: one runs over the other.
	/// </summary>
	public const float Clearance = 96.0f;

	const float EndMatch = 8.0f;
	const float Straight = 0.97f;
	const float WidthMatch = 1.0f;
	const float MinStretch = 48.0f;
	const float MaxTangent = 3.0f;
	const float FarAngle = 170.0f;
	const float MinArmLength = 8.0f;
	const float RoundaboutApproach = 128.0f;
	const float ParallelShare = 0.002f;
	const float CurvedEndRoom = 1.1f;
	const float CornerClearance = 24.0f;

	sealed class Line
	{
		public RoadInput Input;
		public Vector2[] Center;
		public float[] Along;
		public float[] Height;
		public float Length;
		public bool Closed => Input.Track.Closed;
		public float Half => Input.Section.Half;
	}

	sealed class Touch
	{
		public int Road;
		public float Along;
		public Vector2 Point;
		public float Height;
	}

	sealed class Node
	{
		public List<Touch> Touches = [];
		public Vector3 Center;
		public JunctionWish Wish;
		public List<Arm> Arms = [];
		public bool Dropped;
	}

	sealed class Arm
	{
		public int Road;
		public float Along;
		public bool Forward;
		public Vector2 Direction;
		public float Half;
		public float LeftSide;
		public float RightSide;
		public float Trim;

		public float Cut => Forward ? Along + Trim : Along - Trim;

		/// <summary>
		/// Where the road stops. On a closed road that may be past its seam.
		/// </summary>
		public float CutOn( Line line ) => line.Closed ? (Cut % line.Length + line.Length) % line.Length : Cut;
	}

	static Vector2 Flat( Vector3 v ) => new( v.x, v.y );

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

	static Line Prepare( RoadInput input )
	{
		var frames = input.Track.Frames;

		return new Line
		{
			Input = input,
			Center = [.. frames.Select( x => Flat( x.Position ) )],
			Along = [.. frames.Select( x => x.Distance )],
			Height = [.. frames.Select( x => x.Position.z )],
			Length = input.Track.Length
		};
	}

	static (Vector2 Point, float Height) At( Line line, float along )
	{
		var (index, t) = line.Input.Track.Locate( along );

		return (Vector2.Lerp( line.Center[index], line.Center[index + 1], t ), line.Height[index] + (line.Height[index + 1] - line.Height[index]) * t);
	}

	static (float Distance, float Along, Vector2 Point, float Height) Closest( Line line, Vector2 point )
	{
		var best = (Distance: float.MaxValue, Along: 0.0f, Point: Vector2.Zero, Height: 0.0f);

		for ( var i = 0; i + 1 < line.Center.Length; i++ )
		{
			var a = line.Center[i];
			var d = line.Center[i + 1] - a;
			var t = d.LengthSquared > 0.0f ? Math.Clamp( (point - a).Dot( d ) / d.LengthSquared, 0.0f, 1.0f ) : 0.0f;
			var on = a + d * t;
			var distance = on.Distance( point );

			if ( distance < best.Distance )
				best = (distance, line.Along[i] + (line.Along[i + 1] - line.Along[i]) * t, on, line.Height[i] + (line.Height[i + 1] - line.Height[i]) * t);
		}

		return best;
	}

	/// <summary>
	/// <paramref name="wishes"/> gives what a junction at a point wants, the existing one there or a new one.
	/// </summary>
	public static (List<SolvedRoad> Roads, List<SolvedJunction> Junctions) Solve( IReadOnlyList<RoadInput> inputs, Func<Vector3, IReadOnlyList<int>, JunctionWish> wishes )
	{
		var lines = inputs.Select( Prepare ).ToList();
		var touches = new List<(Touch A, Touch B)>();

		for ( var a = 0; a < lines.Count; a++ )
		{
			if ( !lines[a].Input.Connects ) continue;

			for ( var b = a; b < lines.Count; b++ )
			{
				if ( !lines[b].Input.Connects ) continue;

				if ( a != b )
				{
					EndsOn( lines, a, b, touches );
					EndsOn( lines, b, a, touches );
				}

				Crossings( lines, a, b, touches );
			}
		}

		var nodes = Group( lines, touches );

		for ( var pass = 0; pass < 4; pass++ )
		{
			foreach ( var node in nodes )
				Measure( lines, node, wishes );

			if ( !MergeClose( lines, nodes ) ) break;

			nodes = [.. nodes.Where( x => !x.Dropped )];
		}

		foreach ( var node in nodes )
			Measure( lines, node, wishes );

		nodes = [.. nodes.Where( x => !x.Dropped )];

		AddTurningCircles( lines, nodes, wishes );

		return (Stretches( lines, nodes ), [.. nodes.Select( node =>
		{
			var solved = new SolvedJunction { Center = node.Center, Wish = node.Wish };

			solved.Cuts.AddRange( node.Arms.Select( x => new RoadCut( x.Road, x.CutOn( lines[x.Road] ), x.Forward ) ) );

			return solved;
		} )]);
	}

	/// <summary>
	/// An end of one road on the other one, or on the end of it.
	/// </summary>
	static void EndsOn( List<Line> lines, int road, int other, List<(Touch, Touch)> touches )
	{
		var line = lines[road];
		var target = lines[other];

		if ( line.Closed ) return;

		foreach ( var along in new[] { 0.0f, line.Length } )
		{
			var (point, height) = At( line, along );
			var (distance, on, spot, level) = Closest( target, point );

			if ( distance > target.Half + EndMatch || MathF.Abs( level - height ) > Clearance ) continue;

			touches.Add( (new Touch { Road = road, Along = along, Point = point, Height = height }, new Touch { Road = other, Along = on, Point = spot, Height = level }) );
		}
	}

	/// <summary>
	/// Two lines crossing on the same level. A road may cross itself as well.
	/// </summary>
	static void Crossings( List<Line> lines, int first, int second, List<(Touch, Touch)> touches )
	{
		var a = lines[first];
		var b = lines[second];

		for ( var i = 0; i + 1 < a.Center.Length; i++ )
		{
			var p = a.Center[i];
			var r = a.Center[i + 1] - p;

			for ( var j = first == second ? i + 2 : 0; j + 1 < b.Center.Length; j++ )
			{
				var q = b.Center[j];
				var s = b.Center[j + 1] - q;
				var d = Cross( r, s );

				// As a share of their lengths: two pieces in one line are parallel at any angle to the axes.
				if ( MathF.Abs( d ) < ParallelShare * r.Length * s.Length ) continue;

				var t = Cross( q - p, s ) / d;
				var u = Cross( q - p, r ) / d;

				if ( t < 0.0f || t > 1.0f || u < 0.0f || u > 1.0f ) continue;

				var alongA = a.Along[i] + (a.Along[i + 1] - a.Along[i]) * t;
				var alongB = b.Along[j] + (b.Along[j + 1] - b.Along[j]) * u;

				// Near each other on the line of one road, that is no crossing but a tight bend.
				if ( first == second )
				{
					var apart = MathF.Abs( alongA - alongB );

					if ( a.Closed ) apart = MathF.Min( apart, a.Length - apart );
					if ( apart < a.Half * 4.0f ) continue;
				}

				var heightA = a.Height[i] + (a.Height[i + 1] - a.Height[i]) * t;
				var heightB = b.Height[j] + (b.Height[j + 1] - b.Height[j]) * u;

				if ( MathF.Abs( heightA - heightB ) > Clearance ) continue;

				var point = p + r * t;

				touches.Add( (new Touch { Road = first, Along = alongA, Point = point, Height = heightA }, new Touch { Road = second, Along = alongB, Point = point, Height = heightB }) );
			}
		}
	}

	/// <summary>
	/// Touches close to each other are one junction.
	/// </summary>
	static List<Node> Group( List<Line> lines, List<(Touch A, Touch B)> touches )
	{
		var nodes = new List<Node>();

		foreach ( var (a, b) in touches )
		{
			var reach = MathF.Max( lines[a.Road].Half, lines[b.Road].Half );
			var near = nodes.Where( n => n.Touches.Any( x => x.Point.Distance( a.Point ) < reach || x.Point.Distance( b.Point ) < reach ) ).ToList();
			var node = near.FirstOrDefault() ?? new Node();

			if ( near.Count == 0 ) nodes.Add( node );

			foreach ( var other in near.Skip( 1 ) )
			{
				node.Touches.AddRange( other.Touches );
				nodes.Remove( other );
			}

			node.Touches.Add( a );
			node.Touches.Add( b );
		}

		return nodes;
	}

	/// <summary>
	/// Where the roads of a junction stop. A road running through a junction counts as two ends.
	/// </summary>
	static void Measure( List<Line> lines, Node node, Func<Vector3, IReadOnlyList<int>, JunctionWish> wishes )
	{
		// The junction sits on the road that runs through it, the ends only come to it.
		var through = node.Touches.Where( x => !IsEnd( lines[x.Road], x.Along ) ).ToList();
		var anchors = through.Count > 0 ? through : node.Touches;
		var center = Vector2.Zero;
		var height = 0.0f;

		foreach ( var touch in anchors )
		{
			center += touch.Point;
			height += touch.Height;
		}

		center /= anchors.Count;
		height /= anchors.Count;

		node.Center = new Vector3( center.x, center.y, height );
		node.Arms.Clear();

		foreach ( var group in node.Touches.GroupBy( x => x.Road ) )
		{
			var line = lines[group.Key];
			var spots = new List<(float Low, float High)>();

			foreach ( var along in group.Select( x => x.Along ).OrderBy( x => x ) )
			{
				if ( spots.Count > 0 && along - spots[^1].High < line.Half * 4.0f ) spots[^1] = (spots[^1].Low, along);
				else spots.Add( (along, along) );
			}

			foreach ( var (low, high) in spots )
			{
				if ( line.Closed || high < line.Length - 1.0f ) node.Arms.Add( NewArm( lines, group.Key, high, true, center ) );
				if ( line.Closed || low > 1.0f ) node.Arms.Add( NewArm( lines, group.Key, low, false, center ) );
			}
		}

		// Roads shorter than the junction is wide lie inside it, nothing leaves it.
		if ( node.Arms.Count == 0 )
		{
			node.Dropped = true;
			return;
		}

		// Two ends in one line and of one width simply carry on, that is no junction.
		if ( node.Arms.Count == 2 && IsContinuation( lines, node.Arms[0], node.Arms[1] ) )
		{
			node.Dropped = true;
			return;
		}

		node.Wish = wishes( node.Center, [.. node.Arms.Select( x => x.Road )] );

		SetTrims( lines, node );
	}

	static bool IsEnd( Line line, float along ) => !line.Closed && (along < 1.0f || along > line.Length - 1.0f);

	static Arm NewArm( List<Line> lines, int road, float along, bool forward, Vector2 center )
	{
		var line = lines[road];
		var probe = MathF.Max( line.Half * 2.0f, 96.0f );
		var target = forward ? along + probe : along - probe;

		target = line.Closed ? (target % line.Length + line.Length) % line.Length : Math.Clamp( target, 0.0f, line.Length );

		var (point, _) = At( line, target );
		var section = line.Input.Section;

		return new Arm
		{
			Road = road,
			Along = along,
			Forward = forward,
			Direction = (point - center).Normal,
			Half = line.Half,
			LeftSide = forward ? section.Left.Width : section.Right.Width,
			RightSide = forward ? section.Right.Width : section.Left.Width
		};
	}

	static bool IsContinuation( List<Line> lines, Arm a, Arm b ) =>
		a.Direction.Dot( b.Direction ) < -Straight
		&& MathF.Abs( a.Half - b.Half ) < WidthMatch
		&& a.Road != b.Road
		&& IsEnd( lines[a.Road], a.Along ) && IsEnd( lines[b.Road], b.Along );

	/// <summary>
	/// Each road stops where the corners on both of its sides have room.
	/// </summary>
	static void SetTrims( List<Line> lines, Node node )
	{
		var wish = node.Wish;
		var arms = node.Arms.OrderBy( x => MathF.Atan2( x.Direction.y, x.Direction.x ) ).ToList();
		var far = FarAngle.DegreeToRadian();

		foreach ( var arm in arms )
			arm.Trim = 0.0f;

		if ( wish.Style != JunctionStyle.Open )
		{
			var radius = MathF.Max( wish.CornerRadius, 8.0f );

			// A roundabout leaves room in front of it, for the island that splits the lanes of each road.
			var approach = wish.Style == JunctionStyle.Roundabout ? RoundaboutApproach : 0.0f;

			foreach ( var arm in arms )
				arm.Trim = JunctionGenerator.EntryLength( arm.Half, wish.OuterRadius, radius ) + approach;
		}
		else
		{
			for ( var i = 0; i < arms.Count; i++ )
			{
				var a = arms[i];
				var b = arms[(i + 1) % arms.Count];
				var angle = MathF.Atan2( Cross( a.Direction, b.Direction ), a.Direction.Dot( b.Direction ) );

				if ( angle <= 0.0f ) angle += MathF.PI * 2.0f;

				if ( angle >= far ) continue;

				var sin = MathF.Sin( angle );
				var cos = MathF.Cos( angle );
				var tangent = MathF.Min( wish.CornerRadius / MathF.Tan( angle * 0.5f ), MaxTangent * (a.Half + b.Half) );

				// A road also stops clear of the sidewalk of its neighbour: that one turns the corner in front of it.
				var strips = MathF.Max( a.LeftSide, b.RightSide );

				a.Trim = MathF.Max( a.Trim, MathF.Max( (b.Half + a.Half * cos) / sin + tangent, strips > 0.0f ? (b.Half + strips + a.Half * cos) / sin + CornerClearance : 0.0f ) );
				b.Trim = MathF.Max( b.Trim, MathF.Max( (a.Half + b.Half * cos) / sin + tangent, strips > 0.0f ? (a.Half + strips + b.Half * cos) / sin + CornerClearance : 0.0f ) );
			}
		}

		foreach ( var arm in arms )
		{
			var line = lines[arm.Road];

			// What is left of the road may be short, but something has to meet the junction.
			if ( !line.Closed )
			{
				var room = arm.Forward ? line.Length - arm.Along : arm.Along;

				arm.Trim = MathF.Min( arm.Trim, MathF.Max( room - MinArmLength, 0.0f ) );
			}

			// A corner needs the edges of a road beside it, even with nothing to fit around.
			arm.Trim = MathF.Max( arm.Trim, 1.0f );
		}
	}

	/// <summary>
	/// Two junctions that leave too little road between them become one.
	/// </summary>
	static bool MergeClose( List<Line> lines, List<Node> nodes )
	{
		for ( var a = 0; a < nodes.Count; a++ )
		{
			for ( var b = a + 1; b < nodes.Count; b++ )
			{
				if ( nodes[a].Dropped || nodes[b].Dropped ) continue;

				foreach ( var first in nodes[a].Arms )
				{
					foreach ( var second in nodes[b].Arms.Where( x => x.Road == first.Road && x.Forward != first.Forward ) )
					{
						var (low, high) = first.Forward ? (first, second) : (second, first);
						var gap = high.Along - low.Along;

						if ( gap <= 0.0f || gap - low.Trim - high.Trim >= MinStretch ) continue;

						nodes[a].Touches.AddRange( nodes[b].Touches );
						nodes[b].Dropped = true;

						return true;
					}
				}
			}
		}

		return false;
	}

	/// <summary>
	/// A free end of a road that asks for a turning circle gets a junction with one arm.
	/// </summary>
	static void AddTurningCircles( List<Line> lines, List<Node> nodes, Func<Vector3, IReadOnlyList<int>, JunctionWish> wishes )
	{
		for ( var r = 0; r < lines.Count; r++ )
		{
			var line = lines[r];

			if ( line.Closed ) continue;

			foreach ( var (along, style, forward) in new[] { (0.0f, line.Input.Start, true), (line.Length, line.Input.Finish, false) } )
			{
				if ( style != RoadEnd.TurningCircle ) continue;
				if ( nodes.Any( x => x.Arms.Any( a => a.Road == r && MathF.Abs( a.Along - along ) < 1.0f ) ) ) continue;

				var (point, height) = At( line, along );
				var center = new Vector3( point.x, point.y, height );
				var wish = wishes( center, [r] );
				var circle = wish with { Style = JunctionStyle.TurningCircle, OuterRadius = line.Input.TurningRadius };
				var arm = NewArm( lines, r, along, forward, point );
				var node = new Node { Center = center, Wish = circle };

				// A road that bends into its circle comes closer to the middle than its length says.
				var strips = MathF.Max( arm.LeftSide, arm.RightSide );

				arm.Trim = MathF.Min( JunctionGenerator.EntryLength( line.Half, circle.OuterRadius, MathF.Max( circle.CornerRadius, 8.0f ) ) * CurvedEndRoom + strips, line.Length - MinArmLength );

				node.Arms.Add( arm );
				nodes.Add( node );
			}
		}
	}

	/// <summary>
	/// What is left of each road between the junctions on it.
	/// </summary>
	static List<SolvedRoad> Stretches( List<Line> lines, List<Node> nodes )
	{
		var result = new List<SolvedRoad>();

		for ( var r = 0; r < lines.Count; r++ )
		{
			var line = lines[r];
			var cuts = nodes.SelectMany( n => n.Arms.Where( x => x.Road == r ).Select( x => (Cut: x.CutOn( line ), x.Forward, Style: n.Wish.Style) ) ).OrderBy( x => x.Cut ).ToList();
			var solved = new SolvedRoad();

			result.Add( solved );

			if ( cuts.Count == 0 ) continue;

			// Forward arms start a stretch, backward arms end one. On a closed road the stretch over
			// the seam stays two pieces, which is all the seam ever is: the end of one section.
			var open = !line.Closed || !cuts[0].Forward;
			var start = new RoadStretch { From = 0.0f, To = line.Length };

			foreach ( var (cut, forward, style) in cuts )
			{
				// The end of a road carries nothing painted: nothing crosses a turning circle.
				if ( forward )
				{
					start = new RoadStretch { From = cut, To = line.Length, FromJunction = style != JunctionStyle.TurningCircle, FromYield = style == JunctionStyle.Roundabout };
					open = true;
				}
				else if ( open )
				{
					start.To = cut;
					start.ToJunction = style != JunctionStyle.TurningCircle;
					start.ToYield = style == JunctionStyle.Roundabout;

					if ( start.To - start.From > 0.5f ) solved.Stretches.Add( start );

					open = false;
				}
			}

			if ( open && start.To - start.From > 0.5f ) solved.Stretches.Add( start );
		}

		return result;
	}
}

/// <summary>
/// Keeps the roads of a scene connected. Roads and junctions stay objects of their own, a
/// change only touches settings and each of them then regenerates itself.
/// </summary>
public static class RoadLinker
{
	const float SameJunction = 192.0f;
	const float RampTurn = 4.0f;

	static readonly JunctionGenerator Generator = new();
	static readonly Dictionary<GameObject, (string Settings, Transform World, float Half, PathTrack Line)> Lines = [];

	static List<GameObject> Find( Scene scene, string generator ) =>
		[.. scene.GetAllComponents<AmtPart>()
			.Where( x => PartReconciler.IsAlive( x ) && x.Generator == generator && !string.IsNullOrEmpty( x.Settings ) )
			.Select( x => x.GameObject )];

	public static List<GameObject> Roads( Scene scene ) => Find( scene, RoadGenerator.GeneratorId );

	public static List<GameObject> Junctions( Scene scene ) => Find( scene, JunctionGenerator.GeneratorId );

	/// <summary>
	/// Everything a change to one road may touch. For undo.
	/// </summary>
	public static List<GameObject> Network( Scene scene ) => [.. Roads( scene ), .. Junctions( scene )];

	static RoadSettings ReadRoad( GameObject road ) => (RoadSettings)PartService.Read( road ).Settings;

	static JunctionSettings ReadJunction( GameObject junction ) => (JunctionSettings)PartService.Read( junction ).Settings;

	static Vector3 ToWorld( Transform world, Vector3 direction ) => world.Rotation * direction;

	/// <summary>
	/// The line of a road in the world, without its junctions.
	/// </summary>
	static PathTrack WorldLine( GameObject road, RoadSettings s ) => InWorld( road, RoadShape.Line( s ) );

	static PathTrack InWorld( GameObject root, PathTrack line )
	{
		var world = root.WorldTransform;

		var frames = line.Frames.Select( x => x with
		{
			Position = world.PointToWorld( x.Position ),
			Forward = ToWorld( world, x.Forward ),
			Left = ToWorld( world, x.Left ),
			Up = ToWorld( world, x.Up )
		} ).ToList();

		return new PathTrack( frames, line.Closed );
	}

	/// <summary>
	/// What the roads of a scene come to, with roads that are about to be added.
	/// </summary>
	sealed class Layout
	{
		public List<GameObject> Roads;
		public List<RoadSettings> Settings;
		public List<RoadInput> Inputs;
		public List<SolvedRoad> SolvedRoads;
		public List<SolvedJunction> SolvedJunctions;
		public Dictionary<SolvedJunction, GameObject> Kept = [];
		public List<GameObject> Unused = [];
	}

	static RoadInput InputOf( RoadSettings s, PathTrack track ) =>
		new( track, RoadShape.SectionOn( s, track ), s.StartEnd, s.FinishEnd, s.TurningRadius, s.Connect );

	static Layout Plan( Scene scene, IReadOnlyList<RoadSettings> adding = null )
	{
		var roads = Roads( scene ).OrderBy( x => x.Id ).ToList();
		var settings = roads.Select( ReadRoad ).ToList();
		var known = Junctions( scene ).OrderBy( x => x.Id ).Select( x => (Object: x, Settings: ReadJunction( x ), Center: x.WorldPosition) ).ToList();
		var inputs = roads.Select( ( road, i ) => InputOf( settings[i], WorldLine( road, settings[i] ) ) ).ToList();
		var all = settings.Concat( adding ?? [] ).ToList();

		inputs.AddRange( (adding ?? []).Select( x => InputOf( x, RoadShape.Line( x ) ) ) );

		JunctionWish Wish( Vector3 center, IReadOnlyList<int> arms )
		{
			var (found, junction, _) = known.Where( x => x.Center.Distance( center ) < SameJunction ).OrderBy( x => x.Center.Distance( center ) ).FirstOrDefault();

			return found.IsValid() ? new JunctionWish( junction.Style, junction.CornerRadius, junction.OuterRadius ) : NewWish( all, arms );
		}

		var (solvedRoads, solvedJunctions) = RoadNetwork.Solve( inputs, Wish );
		var layout = new Layout { Roads = roads, Settings = settings, Inputs = inputs, SolvedRoads = solvedRoads, SolvedJunctions = solvedJunctions };
		var used = new HashSet<GameObject>();

		foreach ( var solved in solvedJunctions )
		{
			var match = known.Where( x => !used.Contains( x.Object ) && x.Center.Distance( solved.Center ) < SameJunction ).OrderBy( x => x.Center.Distance( solved.Center ) ).Select( x => x.Object ).FirstOrDefault();

			if ( !match.IsValid() ) continue;

			used.Add( match );
			layout.Kept[solved] = match;
		}

		layout.Unused = [.. known.Select( x => x.Object ).Where( x => !used.Contains( x ) )];

		return layout;
	}

	/// <summary>
	/// The junctions a change would take away. Undo has to know them before they are gone.
	/// </summary>
	public static List<GameObject> Removed( Scene scene, IReadOnlyList<RoadSettings> adding = null ) => Plan( scene, adding ).Unused;

	/// <summary>
	/// The stretches roads about to be added will have once they are part of the network. Placed with
	/// these, a new road is built once instead of once without and once again with its junctions.
	/// </summary>
	public static List<List<RoadStretch>> StretchesFor( Scene scene, IReadOnlyList<RoadSettings> adding )
	{
		var layout = Plan( scene, adding );

		return [.. Enumerable.Range( layout.Roads.Count, adding.Count ).Select( i => layout.SolvedRoads[i].Stretches.ToList() )];
	}

	/// <summary>
	/// Work out all junctions again. Roads whose ends did not change are not rebuilt at all, and parts
	/// changed by hand keep their changes. A junction stays the same object with its own
	/// settings as long as there still are roads meeting at its place.
	/// </summary>
	public static List<GameObject> Reconnect( Scene scene )
	{
		var layout = Plan( scene );
		var changed = new List<GameObject>();

		for ( var i = 0; i < layout.Roads.Count; i++ )
		{
			var s = layout.Settings[i];
			var before = System.Text.Json.JsonSerializer.Serialize( s.Stretches );

			s.Stretches = layout.SolvedRoads[i].Stretches;

			if ( before == System.Text.Json.JsonSerializer.Serialize( s.Stretches ) ) continue;

			PartService.Regenerate( layout.Roads[i], RegenerationOptions.Everything, true, s );
			changed.Add( layout.Roads[i] );
		}

		foreach ( var solved in layout.SolvedJunctions )
		{
			layout.Kept.TryGetValue( solved, out var match );

			var s = match.IsValid() ? ReadJunction( match ) : NewJunction( solved.Wish );
			var world = new Transform( solved.Center, Rotation.Identity );

			s.Style = solved.Wish.Style;
			s.OuterRadius = solved.Wish.OuterRadius;
			s.Height = Arms( s, solved, layout.Inputs, world );

			if ( match.IsValid() )
			{
				var moved = !match.WorldPosition.AlmostEqual( solved.Center, 0.01f );

				match.WorldTransform = world;

				var report = PartService.Regenerate( match, RegenerationOptions.Everything, true, s );

				if ( moved || report.HasChanges ) changed.Add( match );
			}
			else
			{
				changed.Add( PartService.Create( Generator, s, world ) );
			}
		}

		foreach ( var junction in layout.Unused )
		{
			junction.Destroy();
			changed.Add( junction );
		}

		scene.ProcessDeletes();

		return changed;
	}

	/// <summary>
	/// What a junction that does not exist yet wants, from the roads that meet there.
	/// </summary>
	static JunctionWish NewWish( IReadOnlyList<RoadSettings> roads, IReadOnlyList<int> arms )
	{
		var style = arms.Any( x => roads[x].Roundabouts ) ? JunctionStyle.Roundabout : JunctionStyle.Open;

		return new JunctionWish( style, arms.Min( x => roads[x].CornerRadius ), MathF.Max( new JunctionSettings().OuterRadius, arms.Max( x => roads[x].Half ) * 2.5f ) );
	}

	static JunctionSettings NewJunction( JunctionWish wish ) => new()
	{
		CornerRadius = wish.CornerRadius,
		OuterRadius = wish.OuterRadius,
		IslandRadius = wish.OuterRadius * 0.5f
	};

	/// <summary>
	/// What roads that are not in the scene yet will look like with their junctions. Roads already
	/// there play no part: this is for showing a tool at work, it has to be quick.
	/// </summary>
	public static PolygonMesh Preview( RoadGenerator generator, IReadOnlyList<RoadSettings> roads )
	{
		var inputs = roads.Select( x => InputOf( x, RoadShape.Line( x ) ) ).ToList();
		var (solvedRoads, solvedJunctions) = RoadNetwork.Solve( inputs, ( _, arms ) => NewWish( roads, arms ) );
		var result = new PolygonMesh();

		void Add( PolygonMesh mesh ) => result.MergeMesh( mesh, Transform.Zero, out _, out _, out _ );

		for ( var i = 0; i < roads.Count; i++ )
		{
			roads[i].Stretches = solvedRoads[i].Stretches;
			Add( PartService.Plan( generator, roads[i] ).Flatten( new Transform( Vector3.Zero, Rotation.Identity ) ) );
		}

		foreach ( var solved in solvedJunctions )
		{
			var s = NewJunction( solved.Wish );
			var world = new Transform( solved.Center, Rotation.Identity );

			s.Style = solved.Wish.Style;
			s.Height = Arms( s, solved, inputs, world );

			Add( PartService.Plan( Generator, s ).Flatten( world ) );
		}

		return result;
	}

	/// <summary>
	/// Fill in the roads of a junction and give back the height of its middle.
	/// </summary>
	static float Arms( JunctionSettings s, SolvedJunction solved, List<RoadInput> inputs, Transform world )
	{
		s.Arms = [];

		var height = 0.0f;

		foreach ( var cut in solved.Cuts )
		{
			var input = inputs[cut.Road];
			var frame = RoadShape.Between( input.Track, cut.Along );
			var section = cut.Forward ? input.Section : input.Section.Mirrored();
			var sign = cut.Forward ? 1.0f : -1.0f;

			if ( frame.Width != 1.0f ) section = Scaled( section, frame.Width );

			s.Arms.Add( new JunctionArm
			{
				Middle = world.PointToLocal( frame.Position ),
				Forward = (frame.Forward * sign).WithZ( 0.0f ).Normal,
				Left = (frame.Left * sign).WithZ( 0.0f ).Normal,
				Up = frame.Up,
				Section = section
			} );

			height += world.PointToLocal( frame.Position ).z + section.Height( 0.0f );
		}

		return height / MathF.Max( solved.Cuts.Count, 1 );
	}

	static RoadSection Scaled( RoadSection section, float width )
	{
		var copy = section.Mirrored().Mirrored();

		copy.Half *= width;

		return copy;
	}

	/// <summary>
	/// A road and its line, worked out once. Snapping asks for them on every frame.
	/// </summary>
	static (float Half, PathTrack Line) Known( GameObject root )
	{
		var settings = PartReconciler.RootPart( root ).Settings;
		var world = root.WorldTransform;

		if ( Lines.TryGetValue( root, out var known ) && (object)known.Settings == settings && known.World == world )
			return (known.Half, known.Line);

		var (half, line) = PartService.Read( root ).Settings switch
		{
			RoadSettings road => (road.Half, RoadShape.Line( road )),
			CurvedRampSettings ramp => (ramp.Width * 0.5f, ramp.Path.Track( ramp.PathDetail, FrameMode.Upright, RampTurn, ramp.Path.Closed ? 0.0f : ramp.Rise, ramp.EaseEnds )),
			_ => (0.0f, null)
		};

		if ( line is not null ) line = InWorld( root, line );

		foreach ( var gone in Lines.Keys.Where( x => !x.IsValid() ).ToList() )
			Lines.Remove( gone );

		Lines[root] = (settings, world, half, line);

		return (half, line);
	}

	/// <summary>
	/// The end of a line, where something can carry on from it.
	/// </summary>
	static void SnapToEnds( PathTrack line, Vector3 flat, float reach, ref float best, ref Vector3 result, ref bool snapped )
	{
		var last = line.Closed ? line.Count - 1 : line.Count;

		foreach ( var i in new[] { 0, last - 1 } )
		{
			var end = line.Frames[i].Position;
			var distance = end.WithZ( 0.0f ).Distance( flat );

			if ( distance > reach || distance * 0.25f >= best ) continue;

			best = distance * 0.25f;
			result = end;
			snapped = true;
		}
	}

	/// <summary>
	/// Put a point on the line of a road near it, on an end if one is close. That is what makes
	/// a new road connect: it starts or ends on the old one, at the height of the old one.
	/// </summary>
	public static Vector3 Snap( Scene scene, Vector3 point, float radius, out bool snapped )
	{
		var flat = point.WithZ( 0.0f );
		var best = float.MaxValue;
		var result = point;

		snapped = false;

		// A road carries on from the end of a ramp as well, at the height the ramp reached.
		foreach ( var ramp in Find( scene, "curvedramp" ) )
		{
			var (half, line) = Known( ramp );

			if ( line is not null ) SnapToEnds( line, flat, radius + half, ref best, ref result, ref snapped );
		}

		foreach ( var road in Roads( scene ) )
		{
			var (half, line) = Known( road );
			var reach = radius + half;

			// Ends win over the side of a road, they are what a road carries on from.
			SnapToEnds( line, flat, reach, ref best, ref result, ref snapped );

			for ( var i = 0; i + 1 < line.Count; i++ )
			{
				var a = line.Frames[i].Position;
				var b = line.Frames[i + 1].Position;
				var d = (b - a).WithZ( 0.0f );
				var t = d.LengthSquared > 0.0f ? Math.Clamp( (flat - a.WithZ( 0.0f )).Dot( d ) / d.LengthSquared, 0.0f, 1.0f ) : 0.0f;
				var on = Vector3.Lerp( a, b, t );
				var distance = on.WithZ( 0.0f ).Distance( flat );

				if ( distance > reach || distance >= best ) continue;

				best = distance;
				result = on;
				snapped = true;
			}
		}

		return result;
	}
}