namespace Machines.Race;

/// <summary>
/// Bakes the optimal line from scene splines, chaining them into a loop and bridging gaps.
/// </summary>
public sealed class SplinePathBaker
{
	private readonly RacingPath _path;
	private Scene Scene => _path.Scene;
	private readonly GapBridger _bridger;

	public SplinePathBaker( RacingPath path, GapBridger bridger )
	{
		_path = path;
		_bridger = bridger;
	}

	/// <summary>
	/// Point-index range for one contiguous section (source spline or gap bridge).
	/// </summary>
	public sealed class Section
	{
		public int StartIndex;
		public int EndIndex;
		public SplineType Type;
		public bool IsGap;
		public string Label;
	}

	/// <summary>
	/// Successful bake result: chained points, section metadata, and contributing spline count.
	/// </summary>
	public sealed class Result
	{
		public List<Vector3> Points;
		public List<Section> Sections;
		public int SplineCount;
	}

	/// <summary>
	/// Intermediate struct holding a sampled spline polyline with its type metadata.
	/// </summary>
	private struct SplineSegment
	{
		public List<Vector3> Points;
		public SplineType Type;
		public string Label;
		// Source component, so authored Next links can be resolved during ordering.
		public SplineComponent Source;
	}

	/// <summary>
	/// Try to bake from scene splines; returns false when none contribute so the caller can fall back.
	/// </summary>
	public bool TryBake( out Result result )
	{
		result = null;

		var splines = Scene.GetAll<SplineComponent>()
			.Where( s => s.Active
				&& s.Spline != null
				&& s.Spline.Length > 1f
				&& !s.GameObject.Tags.Has( RacingPath.NoPathTag )
				&& !s.GameObject.Tags.Has( RacingPath.ShortcutTag )
				// Custom-typed splines are markup/decoration, excluded from the path.
				&& s.GetComponent<SplineInfo>()?.Type != SplineType.Custom )
			.ToList();

		if ( splines.Count == 0 )
			return false;

		// Sample each contributing spline to a world-space polyline.
		var segments = new List<SplineSegment>();
		foreach ( var s in splines )
		{
			var poly = SampleSplineWorld( s, _path.SplineSampleSpacing );
			if ( poly.Count < 2 )
				continue;

			var info = s.GetComponent<SplineInfo>();
			segments.Add( new SplineSegment
			{
				Points = poly,
				Type = info?.Type ?? SplineType.Road,
				Label = info?.Label ?? s.GameObject.Name,
				Source = s
			} );
		}

		if ( segments.Count == 0 )
			return false;

		// Order multi-spline tracks into a loop via a junction graph: chains by directional continuity
		// (straightest-through at crossroads), not raw endpoint proximity, so intertwining splines and
		// intersections resolve correctly. Checkpoints seed the start and disambiguate genuine forks.
		var orderedSegments = segments;
		var preOrdered = false;
		if ( segments.Count > 1 )
		{
			var checkpoints = Scene.GetAll<Checkpoint>().OrderBy( c => c.Index ).ToList();
			var graphOrdered = OrderSegmentsByGraph( segments, checkpoints );

			if ( graphOrdered != null && graphOrdered.Count >= 2 )
			{
				orderedSegments = graphOrdered;
				preOrdered = true;
				if ( graphOrdered.Count < segments.Count )
					Log.Info( $"SplinePathBaker: junction graph used {graphOrdered.Count}/{segments.Count} splines (others aren't on the loop)." );
			}
			else
			{
				Log.Warning( "SplinePathBaker: junction-graph ordering failed; falling back to greedy nearest-endpoint." );
			}
		}

		// Chain into a continuous loop, bridging gaps via navmesh.
		var (points, segmentInfos) = ChainSegmentsWithMetadata( orderedSegments, preOrdered );
		if ( points.Count < 2 )
			return false;

		result = new Result
		{
			Points = points,
			Sections = segmentInfos,
			SplineCount = segments.Count
		};
		return true;
	}

	/// <summary>
	/// Order and orient segments into a loop by walking a junction graph: at each junction the next segment
	/// is the one that best continues the current heading (straightest-through), so crossroads and intertwining
	/// splines resolve by direction rather than ambiguous endpoint proximity. Checkpoints seed the start and
	/// gently bias genuine forks toward the authored lap order. Returns null if it can't even start.
	/// </summary>
	private List<SplineSegment> OrderSegmentsByGraph( List<SplineSegment> segments, List<Checkpoint> checkpoints )
	{
		var n = segments.Count;
		var ne = n * 2; // two endpoints per segment, encoded as endpointId = seg*2 + (tail ? 1 : 0)

		// Weld endpoints into junction nodes (3D, so a bridge endpoint above a road endpoint stays distinct).
		var radius = MathF.Max( _path.JunctionRadius, 1f );
		var r2 = radius * radius;
		var nodePos = new List<Vector3>();
		var nodeOf = new int[ne];
		for ( int endpointId = 0; endpointId < ne; endpointId++ )
		{
			var p = EndpointPos( segments, endpointId );
			int node = -1;
			for ( int j = 0; j < nodePos.Count; j++ )
			{
				if ( (nodePos[j] - p).LengthSquared <= r2 ) { node = j; break; }
			}
			if ( node < 0 ) { node = nodePos.Count; nodePos.Add( p ); }
			nodeOf[endpointId] = node;
		}

		// Endpoints incident to each node.
		var nodeEndpointIds = new List<List<int>>( nodePos.Count );
		for ( int j = 0; j < nodePos.Count; j++ )
			nodeEndpointIds.Add( new List<int>() );
		for ( int endpointId = 0; endpointId < ne; endpointId++ )
			nodeEndpointIds[nodeOf[endpointId]].Add( endpointId );

		var hasCps = checkpoints != null && checkpoints.Count >= 1;

		// Map each source spline to its segment index so authored Next links resolve during the walk.
		var segIndexOf = new Dictionary<SplineComponent, int>();
		for ( int i = 0; i < n; i++ )
		{
			if ( segments[i].Source.IsValid() )
				segIndexOf[segments[i].Source] = i;
		}

		var used = new bool[n];
		var ordered = new List<SplineSegment>( n );

		// Choose the starting endpoint.
		int startEndpointId;
		int startNode;
		if ( hasCps )
		{
			// Start at the node nearest checkpoint 0, leaving along the endpoint that heads toward checkpoint 1.
			startNode = NearestNode( nodePos, checkpoints[0].WorldPosition );
			var seedDir = checkpoints.Count >= 2
				? (checkpoints[1].WorldPosition - nodePos[startNode]).WithZ( 0f ).Normal
				: Vector3.Zero;

			startEndpointId = -1;
			float startScore = float.MinValue;
			foreach ( var endpointId in nodeEndpointIds[startNode] )
			{
				var score = seedDir.LengthSquared > 0.001f
					? Vector3.Dot( DepartDir( segments, endpointId ).WithZ( 0f ).Normal, seedDir )
					: 0f;
				if ( score > startScore ) { startScore = score; startEndpointId = endpointId; }
			}
		}
		else
		{
			// No checkpoints: start at the head of an authored chain (a spline nothing links to),
			// oriented so the end leading to its Next becomes the tail. Falls back to segment 0.
			var startSeg = ChainHeadSegment( segments, segIndexOf );
			startEndpointId = OrientChainHead( segments, segIndexOf, startSeg );
			startNode = nodeOf[startEndpointId];
		}

		if ( startEndpointId < 0 )
			return null;

		AppendOriented( segments, ordered, startEndpointId );
		used[startEndpointId >> 1] = true;
		var arriveDir = ArriveDir( segments, startEndpointId );
		var exitNode = nodeOf[startEndpointId ^ 1];
		var appendedSeg = startEndpointId >> 1;
		var appendedFarEndpoint = startEndpointId ^ 1;
		var nextCp = 1;

		for ( int guard = 0; guard < n; guard++ )
		{
			if ( exitNode == startNode )
				break; // loop closed back to the start junction

			int bestEndpointId;

			// Authored link wins: follow the just-appended spline's Next across any gap (jumps, level changes).
			var authored = ResolveAuthoredNext( segments, segIndexOf, used, appendedSeg, arriveDir );
			if ( authored >= 0 )
			{
				bestEndpointId = authored;
			}
			else
			{
				// Pick the unused continuation at this junction that best continues our heading.
				bestEndpointId = -1;
				float bestScore = float.MinValue;
				foreach ( var endpointId in nodeEndpointIds[exitNode] )
				{
					if ( used[endpointId >> 1] )
						continue;

					var depart = DepartDir( segments, endpointId ).WithZ( 0f ).Normal;
					var score = Vector3.Dot( arriveDir.WithZ( 0f ).Normal, depart ); // straightest-through

					// Mild bias toward the next checkpoint to settle genuine forks.
					if ( hasCps )
					{
						var toCp = (checkpoints[nextCp % checkpoints.Count].WorldPosition - nodePos[exitNode]).WithZ( 0f ).Normal;
						score += _path.JunctionCheckpointBias * Vector3.Dot( depart, toCp );
					}

					if ( score > bestScore ) { bestScore = score; bestEndpointId = endpointId; }
				}

				// Graph dead-end (a real gap): jump to the nearest unused endpoint; the chainer bridges the gap.
				if ( bestEndpointId < 0 )
					bestEndpointId = NearestUnusedEndpoint( segments, used, nodePos[exitNode] );
			}

			if ( bestEndpointId < 0 )
				break;

			AppendOriented( segments, ordered, bestEndpointId );
			used[bestEndpointId >> 1] = true;
			arriveDir = ArriveDir( segments, bestEndpointId );
			appendedSeg = bestEndpointId >> 1;
			appendedFarEndpoint = bestEndpointId ^ 1;
			var farNode = nodeOf[bestEndpointId ^ 1];

			// Advance the checkpoint cursor once we reach near the one we were heading for.
			if ( hasCps && (nodePos[farNode] - checkpoints[nextCp % checkpoints.Count].WorldPosition).Length < 500f )
				nextCp++;

			exitNode = farNode;
		}

		return ordered;
	}

	/// <summary>
	/// Segment index that a segment's authored <see cref="SplineInfo.Next"/> points to, or -1 if none/unresolved.
	/// </summary>
	private static int AuthoredNextIndex( List<SplineSegment> segments, Dictionary<SplineComponent, int> segIndexOf, int seg )
	{
		var src = segments[seg].Source;
		if ( !src.IsValid() )
			return -1;
		var next = src.GetComponent<SplineInfo>()?.Next;
		if ( !next.IsValid() )
			return -1;
		return segIndexOf.TryGetValue( next, out var idx ) ? idx : -1;
	}

	/// <summary>
	/// True when <paramref name="from"/> authors a Next link to <paramref name="to"/> - i.e. the gap between
	/// them is a designer-declared jump, which should be bridged through the air rather than along the ground.
	/// </summary>
	private static bool IsAuthoredLink( SplineSegment from, SplineSegment to )
	{
		if ( !from.Source.IsValid() || !to.Source.IsValid() )
			return false;
		var next = from.Source.GetComponent<SplineInfo>()?.Next;
		return next.IsValid() && next == to.Source;
	}

	/// <summary>
	/// If the just-appended segment authors a Next link to an unused segment, return the endpoint to enter
	/// it from - the one that best continues our heading (straightest-through), not the nearest one. On a
	/// jump the nearest endpoint is often the wrong (low/backward) end; direction continuity picks the
	/// landing that lets us keep going forward. Otherwise -1, so the junction heuristic runs.
	/// </summary>
	private static int ResolveAuthoredNext( List<SplineSegment> segments, Dictionary<SplineComponent, int> segIndexOf, bool[] used, int appendedSeg, Vector3 arriveDir )
	{
		var nextSeg = AuthoredNextIndex( segments, segIndexOf, appendedSeg );
		if ( nextSeg < 0 || used[nextSeg] )
			return -1;

		var heading = arriveDir.WithZ( 0f ).Normal;
		var head = nextSeg * 2;
		var tail = nextSeg * 2 + 1;
		var sHead = Vector3.Dot( heading, DepartDir( segments, head ).WithZ( 0f ).Normal );
		var sTail = Vector3.Dot( heading, DepartDir( segments, tail ).WithZ( 0f ).Normal );
		return sHead >= sTail ? head : tail;
	}

	/// <summary>
	/// Head of an authored chain: a linked segment that no other segment's Next points to.
	/// Falls back to segment 0 when there are no links.
	/// </summary>
	private static int ChainHeadSegment( List<SplineSegment> segments, Dictionary<SplineComponent, int> segIndexOf )
	{
		var n = segments.Count;
		var referenced = new bool[n];
		var anyLink = false;
		for ( int i = 0; i < n; i++ )
		{
			var nx = AuthoredNextIndex( segments, segIndexOf, i );
			if ( nx >= 0 ) { referenced[nx] = true; anyLink = true; }
		}
		if ( anyLink )
		{
			for ( int i = 0; i < n; i++ )
			{
				if ( !referenced[i] && AuthoredNextIndex( segments, segIndexOf, i ) >= 0 )
					return i;
			}
		}
		return 0;
	}

	/// <summary>
	/// Endpoint to enter a chain-head segment from, so the end leading to its Next becomes the tail.
	/// </summary>
	private static int OrientChainHead( List<SplineSegment> segments, Dictionary<SplineComponent, int> segIndexOf, int seg )
	{
		var nextSeg = AuthoredNextIndex( segments, segIndexOf, seg );
		if ( nextSeg < 0 )
			return seg * 2; // no link: enter head-first

		var nextHead = EndpointPos( segments, nextSeg * 2 );
		var nextTail = EndpointPos( segments, nextSeg * 2 + 1 );
		var head = EndpointPos( segments, seg * 2 );
		var tail = EndpointPos( segments, seg * 2 + 1 );
		var dHead = MathF.Min( (head - nextHead).LengthSquared, (head - nextTail).LengthSquared );
		var dTail = MathF.Min( (tail - nextHead).LengthSquared, (tail - nextTail).LengthSquared );
		// Enter from the farther end so the nearer end (leading into Next) becomes the tail.
		return dHead >= dTail ? seg * 2 : seg * 2 + 1;
	}

	/// <summary>
	/// World position of an endpoint (endpointId = seg*2 + tailBit).
	/// </summary>
	private static Vector3 EndpointPos( List<SplineSegment> segments, int endpointId )
	{
		var pts = segments[endpointId >> 1].Points;
		return (endpointId & 1) == 1 ? pts[^1] : pts[0];
	}

	/// <summary>
	/// Index of the node nearest a world position.
	/// </summary>
	private static int NearestNode( List<Vector3> nodePos, Vector3 p )
	{
		int best = -1;
		float bestSq = float.MaxValue;
		for ( int j = 0; j < nodePos.Count; j++ )
		{
			var sq = (nodePos[j] - p).LengthSquared;
			if ( sq < bestSq ) { bestSq = sq; best = j; }
		}
		return best;
	}

	/// <summary>
	/// Endpoint of an unused segment nearest a world position (gap fallback).
	/// </summary>
	private static int NearestUnusedEndpoint( List<SplineSegment> segments, bool[] used, Vector3 p )
	{
		int best = -1;
		float bestSq = float.MaxValue;
		for ( int endpointId = 0; endpointId < segments.Count * 2; endpointId++ )
		{
			if ( used[endpointId >> 1] )
				continue;
			var sq = (EndpointPos( segments, endpointId ) - p).LengthSquared;
			if ( sq < bestSq ) { bestSq = sq; best = endpointId; }
		}
		return best;
	}

	/// <summary>
	/// Direction leaving the node into the segment when entered from endpoint endpointId.
	/// </summary>
	private static Vector3 DepartDir( List<SplineSegment> segments, int endpointId )
	{
		var pts = segments[endpointId >> 1].Points;
		var c = pts.Count;
		var step = Math.Min( 3, c - 1 );
		var dir = (endpointId & 1) == 1 ? (pts[c - 1 - step] - pts[c - 1]) : (pts[step] - pts[0]);
		return dir.Normal;
	}

	/// <summary>
	/// Heading into the far node after entering the segment from endpoint endpointId.
	/// </summary>
	private static Vector3 ArriveDir( List<SplineSegment> segments, int endpointId )
	{
		var f = endpointId ^ 1; // far endpoint
		var pts = segments[f >> 1].Points;
		var c = pts.Count;
		var step = Math.Min( 3, c - 1 );
		var dir = (f & 1) == 1 ? (pts[c - 1] - pts[c - 1 - step]) : (pts[0] - pts[step]);
		return dir.Normal;
	}

	/// <summary>
	/// Append a segment to the ordered list, reversed if entered from its tail.
	/// </summary>
	private static void AppendOriented( List<SplineSegment> segments, List<SplineSegment> ordered, int endpointId )
	{
		var seg = segments[endpointId >> 1];
		if ( (endpointId & 1) == 1 )
		{
			var rev = new List<Vector3>( seg.Points );
			rev.Reverse();
			ordered.Add( new SplineSegment { Points = rev, Type = seg.Type, Label = seg.Label, Source = seg.Source } );
		}
		else
		{
			ordered.Add( seg );
		}
	}

	/// <summary>
	/// Connect segments into a continuous loop (nearest endpoints), bridging gaps via navmesh.
	/// </summary>
	private (List<Vector3> Points, List<Section> Segments) ChainSegmentsWithMetadata( List<SplineSegment> segments, bool preOrdered = false )
	{
		if ( segments.Count == 1 )
		{
			var pts = segments[0].Points;

			// The spline is authored to run past its own start (so the visual mesh tiles seamlessly).
			// Trim that overlapping overflow so the loop closes at the real start, instead of doubling
			// back over the overlap - which jogs the racing line and reads as a corner to the bots.
			TrimStartOvershoot( pts );

			var info = new Section
			{
				StartIndex = 0,
				EndIndex = pts.Count,
				Type = segments[0].Type,
				IsGap = false,
				Label = segments[0].Label
			};
			return (pts, new List<Section> { info });
		}

		var chain = new List<Vector3>( segments[0].Points );
		var segmentInfos = new List<Section>();

		// First spline section.
		segmentInfos.Add( new Section
		{
			StartIndex = 0,
			EndIndex = chain.Count,
			Type = segments[0].Type,
			IsGap = false,
			Label = segments[0].Label
		} );

		// Start index of the last spline section in the chain, so overshoot trims only scan it.
		var lastSplineStart = 0;

		for ( int placed = 1; placed < segments.Count; placed++ )
		{
			List<Vector3> next;
			SplineType nextType;
			string nextLabel;

			if ( preOrdered )
			{
				// Already ordered and oriented by checkpoint sorting.
				next = segments[placed].Points;
				nextType = segments[placed].Type;
				nextLabel = segments[placed].Label;
			}
			else
			{
				// Greedy nearest-endpoint (fallback when no checkpoints).
				var tail = chain[^1];
				int best = -1;
				bool reverse = false;
				float bestDist = float.MaxValue;

				for ( int i = placed; i < segments.Count; i++ )
				{
					var seg = segments[i].Points;
					var dStart = (seg[0] - tail).LengthSquared;
					var dEnd = (seg[^1] - tail).LengthSquared;

					if ( dStart < bestDist ) { bestDist = dStart; best = i; reverse = false; }
					if ( dEnd < bestDist ) { bestDist = dEnd; best = i; reverse = true; }
				}

				if ( best < 0 )
					break;

				// Swap best into position so remaining segments stay available.
				(segments[placed], segments[best]) = (segments[best], segments[placed]);

				next = segments[placed].Points;
				nextType = segments[placed].Type;
				nextLabel = segments[placed].Label;
				if ( reverse )
				{
					next = new List<Vector3>( next );
					next.Reverse();
				}
			}

			// Collapse any overlap at this join to the mutual closest point, so neither the previous
			// spline's tail nor the next spline's head doubles back over the other (splines are often
			// authored to overshoot the junction for seamless mesh tiling).
			TrimJoinOverlap( chain, lastSplineStart, next );
			segmentInfos[^1].EndIndex = chain.Count;

			var gapStart = chain[^1];
			var gapEnd = next[0];
			var gapDistance = (gapEnd - gapStart).Length;

			// Bridge non-coincident endpoints. An authored link is a jump: arc through the air.
			if ( gapDistance > _path.GapThreshold )
			{
				var startTangent = GapBridger.GetChainTailTangent( chain );
				var endTangent = GapBridger.GetSegmentHeadTangent( next );
				var authoredJump = preOrdered && IsAuthoredLink( segments[placed - 1], segments[placed] );

				var gapStartIdx = chain.Count;
				var bridgePoints = _bridger.BridgeGap( gapStart, gapEnd, startTangent, endTangent, authoredJump );
				chain.AddRange( bridgePoints );

				segmentInfos.Add( new Section
				{
					StartIndex = gapStartIdx,
					EndIndex = chain.Count,
					Type = SplineType.Road,
					IsGap = true,
					Label = "Gap"
				} );
			}

			// Append next spline (skip coincident join point).
			var splineStartIdx = chain.Count;
			if ( (next[0] - chain[^1]).Length < 1f )
				chain.AddRange( next.Skip( 1 ) );
			else
				chain.AddRange( next );

			segmentInfos.Add( new Section
			{
				StartIndex = splineStartIdx,
				EndIndex = chain.Count,
				Type = nextType,
				IsGap = false,
				Label = nextLabel
			} );
			lastSplineStart = splineStartIdx;
		}

		// Trim overflow where the last spline runs past the loop start before closing back to it.
		TrimTailToTarget( chain, chain[0], lastSplineStart );
		segmentInfos[^1].EndIndex = chain.Count;

		// Bridge the closing gap (last -> first) if the loop doesn't close.
		var closingGap = (chain[0] - chain[^1]).Length;
		if ( closingGap > _path.GapThreshold )
		{
			var closingStartTangent = GapBridger.GetChainTailTangent( chain );
			var closingEndTangent = (chain.Count > 1 ? (chain[1] - chain[0]).Normal : Vector3.Forward);
			var closingAuthored = preOrdered && IsAuthoredLink( segments[^1], segments[0] );

			var gapStartIdx = chain.Count;
			var bridgePoints = _bridger.BridgeGap( chain[^1], chain[0], closingStartTangent, closingEndTangent, closingAuthored );
			chain.AddRange( bridgePoints );

			segmentInfos.Add( new Section
			{
				StartIndex = gapStartIdx,
				EndIndex = chain.Count,
				Type = SplineType.Road,
				IsGap = true,
				Label = "Closing Gap"
			} );
		}

		return (chain, segmentInfos);
	}

	/// <summary>
	/// Trim a spline that overshoots its own start (authored so the visual mesh joins seamlessly).
	/// Finds where the tail returns closest to the start and drops that point plus the overflow after it,
	/// so the loop closes with a forward segment into the start rather than a backtrack over the overlap.
	/// </summary>
	private void TrimStartOvershoot( List<Vector3> points )
	{
		var count = points.Count;
		if ( count < 8 )
			return;

		var start = points[0];

		// Closest approach to the start in the back half: where the spline returns to (and passes) it.
		var from = count / 2;
		var bestK = -1;
		var bestSq = float.MaxValue;
		for ( int i = from; i < count; i++ )
		{
			var sq = (points[i] - start).LengthSquared;
			if ( sq < bestSq )
			{
				bestSq = sq;
				bestK = i;
			}
		}

		// Only trim a genuine overshoot: the tail returns near the start with overflow points past it.
		var threshold = _path.SplineSampleSpacing * 2f;
		var returnsToStart = bestSq <= threshold * threshold;
		if ( returnsToStart && bestK > from && bestK < count - 1 )
			points.RemoveRange( bestK, count - bestK );
	}

	/// <summary>
	/// Collapse the overlap at a two-spline join to the mutual closest point: find the closest pair between
	/// the previous spline's tail (back half of the last chain section) and the next spline's head (its front
	/// half), then drop the chain's overflow past it and the next spline's overflow before it. This kills the
	/// backtrack whichever side overshoots - the previous end running past the join, the next start running
	/// back past it, or both - independent of how far either was authored to overshoot.
	/// </summary>
	private static void TrimJoinOverlap( List<Vector3> chain, int chainSectionStart, List<Vector3> next )
	{
		var cCount = chain.Count;
		var nCount = next.Count;
		// Scan the whole previous section - it should end at the junction, so trimming any of its tail back
		// to the closest approach is always safe and catches overshoots longer than half its length. The
		// next spline's head only overshoots backward a little, so its front half is enough (and bounds how
		// much of it we could ever remove).
		var cFrom = chainSectionStart;
		var nTo = nCount / 2;
		if ( cCount - cFrom < 2 || nTo < 2 )
			return;

		var bestI = cCount - 1;
		var bestJ = 0;
		var bestSq = float.MaxValue;
		for ( int i = cFrom; i < cCount; i++ )
		{
			for ( int j = 0; j < nTo; j++ )
			{
				var sq = (chain[i] - next[j]).LengthSquared;
				if ( sq < bestSq ) { bestSq = sq; bestI = i; bestJ = j; }
			}
		}

		// Drop the chain's overflow after the junction, then the next spline's overflow before it.
		if ( bestI < cCount - 1 )
			chain.RemoveRange( bestI + 1, cCount - bestI - 1 );
		if ( bestJ > 0 )
			next.RemoveRange( 0, bestJ );
	}

	/// <summary>
	/// Trim points off the tail of <paramref name="chain"/> that overshoot <paramref name="target"/> - where
	/// the last spline section runs past a join (or the loop start) and would double back over the overlap.
	/// Scans only the back half of the last section (from <paramref name="sectionStart"/>). The test is
	/// magnitude-independent: if some interior point gets closer to the target than the section's end does,
	/// the end has turned away from the join - a backtrack - so everything past that closest approach is
	/// overflow and gets dropped, no matter how far the spline was authored to overshoot.
	/// </summary>
	private static void TrimTailToTarget( List<Vector3> chain, Vector3 target, int sectionStart )
	{
		var count = chain.Count;
		// Scan the whole last section so overshoots longer than half its length are still caught.
		var from = sectionStart;
		if ( count - from < 3 )
			return;

		var bestK = -1;
		var bestSq = float.MaxValue;
		for ( int i = from; i < count; i++ )
		{
			var sq = (chain[i] - target).LengthSquared;
			if ( sq < bestSq ) { bestSq = sq; bestK = i; }
		}

		// End is the closest -> monotonic approach, no overshoot. Otherwise the end turned back: trim overflow.
		var endSq = (chain[^1] - target).LengthSquared;
		if ( bestK >= from && bestK < count - 1 && endSq > bestSq + 1f )
			chain.RemoveRange( bestK + 1, count - bestK - 1 );
	}

	/// <summary>
	/// Sample a spline into world-space points at fixed arc-length spacing.
	/// </summary>
	private List<Vector3> SampleSplineWorld( SplineComponent sc, float spacing )
	{
		var result = new List<Vector3>();
		var spline = sc.Spline;
		var length = spline.Length;
		if ( length < 0.001f )
			return result;

		var tx = sc.WorldTransform;
		spacing = MathF.Max( spacing, 1f );
		var up = Vector3.Up * _path.UpOffset;

		for ( float d = 0f; d < length; d += spacing )
			result.Add( tx.PointToWorld( spline.SampleAtDistance( d ).Position ) + up );

		if ( !spline.IsLoop )
			result.Add( tx.PointToWorld( spline.SampleAtDistance( length ).Position ) + up );

		return result;
	}
}