using System;
using System.Collections.Generic;
using IslaApocalypse.Core;

namespace IslaApocalypse.Tools
{
	/// <summary>
	/// ⭐⭐ FLOW-THROUGH ROUTING (rivers/05) — river → lake → over the spill → river → … → sea.
	///
	/// ═══ THE MODEL ═══
	///
	/// The reference routes a river to the FIRST terminus it can afford and stops. This replaces that with
	/// CHAINING THROUGH THE BASIN GRAPH (rivers/04): a promoted river runs down its erosion-carved stem to
	/// its terminal basin and from there follows the terrain's own overflow structure — into the lake or
	/// across the dry pan, over the basin's spill, into the next basin, over its spill — until it reaches
	/// the coast, walls at a real lake, or walls at a dry sink.
	///
	///   THE FIELD    one island-wide D8 direction per land cell on <c>Plan.FullFilled</c> (the overflow
	///                surface, rivers/04 §0.2: on it every basin's minimum is its spill, so descent leaves
	///                each basin over its spill into the next). Cap-independent; computed once per seed.
	///   THE WALK     a river FOLLOWS the field from its terminal. Each basin it enters is checked once:
	///                floor→spill climb (<c>BasinNode.SpillClimbM</c>, the fill-to-overtop metric, applied
	///                uniformly to lake and dry basins) ≤ cap → overflow, continue; > cap → walled, stop.
	///   DISPOSITION  reaches <c>OceanMask</c> → KEEP (flow-through to the sea); walls at an <c>IsLake</c>
	///                basin → KEEP (lake-terminal, feeds visible water); walls at a dry or puddle-only basin
	///                → DROP the river entirely (a river dead-ending in dry nowhere is worse than no river,
	///                and nothing is filled). Read through the CONFLUENCE ROOT: a river that joins a kept
	///                river is kept as its tributary, whatever its own chain would have done.
	///   CONFLUENCE   rivers/03b's, reused verbatim: biggest-first, true cell intersection, never proximity.
	///
	/// ═══ ⛔ THE RED LINE ═══
	///
	/// **Courses, a direction field, and data. No height written, no bed carved, no water created or
	/// filled.** The caller digests both height fields around this and refuses on any change.
	///
	/// ═══ ⚠ D-046 — which surface each step reads ═══
	///
	///   RENDER    the field (<c>FullFilled</c>), the climbs (<c>SpillClimbM</c>), the real-terrain descent into
	///             a lake (<c>Plan.Dir</c> on <c>Filled</c>), the lowground fallback (<c>RouteTo</c> on <c>p2.Height</c>).
	///   CLASSIFY  every terminus test: <c>OceanMask</c> for the sea, <c>IsLake</c> (≥ floor) for a lake, and
	///             "is this cell the basin's own water" for where a river enters a lake. No bare <c>h &lt; sea</c>.
	///
	/// ═══ ⭐ HOW A LAKE BASIN IS CROSSED (the one place the field is not simply followed) ═══
	///
	/// The field inside a basin is the flood's ulp-staircase — it points from anywhere in the basin straight
	/// at the spill, IGNORING the lake, because the flood never asked where the low water is. Water entering
	/// a lake basin does not skirt the lake to the spill; it runs down to the lake, fills it, and leaves at
	/// the spill. So inside an <c>IsLake</c> basin the course is: the REAL-TERRAIN descent from the entry
	/// point into the basin's own classify water (<c>Plan.Dir</c>; rivers/03c fix B's lowground route as the
	/// fallback when the descent pools short of the water), then the LAKE SPAN (water — recorded, not drawn),
	/// then the OUTLET: from the lake's lowest cell on <c>FullFilled</c> (its point nearest the spill in flood
	/// terms) along the field over the spill. A dry basin is crossed on the field as a visible line.
	/// </summary>
	public static class FlowThroughRouting
	{
		private static readonly int[] DX = { -1, -1, -1, 0, 0, 1, 1, 1 };
		private static readonly int[] DY = { -1, 0, 1, -1, 1, -1, 0, 1 };
		private static readonly float[] DIST = {
			1.41421356f, 1f, 1.41421356f, 1f, 1f, 1.41421356f, 1f, 1.41421356f };

		public const sbyte D_NONE = -1;

		public enum Terminus : byte
		{
			/// <summary>The chain reached <c>OceanMask</c>.</summary>
			Ocean,
			/// <summary>Walled at an <c>IsLake</c> basin — a significant lake.</summary>
			Lake,
			/// <summary>Walled at a dry (or puddle-only) basin.</summary>
			DrySink,
			/// <summary>The walk stuck with no lower neighbour outside any basin — an exact flat. Not expected.</summary>
			Closed,
		}

		/// <summary>One basin the chain entered.</summary>
		public sealed class Hop
		{
			public int BasinId;
			public bool IsLake;
			/// <summary>Floor→spill climb, metres, clamped at sea as <c>RouteTo</c> clamps — the cap metric.</summary>
			public float ClimbM;
			public bool Walled;
			public int EntryCell;
			/// <summary>The first cell outside the basin on the way out (-1 if walled).</summary>
			public int SpillCell = -1;
			/// <summary>⭐ The cell the river actually ENTERED the lake at (lake basins only; -1 otherwise).</summary>
			public int LakeEntryCell = -1;
			/// <summary>Cross-check: the field's exit from this basin lands where <c>BasinGraph</c>'s edge says.</summary>
			public bool EdgeAgreesWithGraph = true;
			/// <summary>The lake-entry descent had to fall back to the lowground route (the terminal pooled short of the water).</summary>
			public bool UsedLowgroundFallback;
		}

		/// <summary>One promoted river, walked, disposed, assembled.</summary>
		public sealed class FlowRiver
		{
			public RiverCandidate Candidate;
			public List<Hop> Chain = new();
			/// <summary>This river's OWN terminus, before confluence.</summary>
			public Terminus Terminus;
			public int TerminusBasinId;
			/// <summary>The ocean cell entered, the lake cell entered, or where a dry/closed chain ended.</summary>
			public int MouthCell = -1;
			/// <summary>Head → terminus: the upland stem then the lowland chain. Lake spans are straight jumps across water.</summary>
			public List<(float x, float y)> Course;
			/// <summary>Lake spans: (entry water cell, outlet water cell) — the parts of the course that are water, not channel.</summary>
			public List<(int from, int to)> WaterSpans = new();
			public float StemLenPx, LowlandLenPx;
			public float TotalLenPx => StemLenPx + LowlandLenPx;
			public float MaxHopClimbM, TotalClimbM;
			public int LakesPassed;
			/// <summary>The rivers/03b confluence wrapper — <c>Joined</c>, <c>ConfluenceParentRank</c>, <c>CellPath</c>, <c>OwnPath</c>, <c>StemCells</c>.</summary>
			public RiverRouting.RoutedRiver Routed;
			/// <summary>⭐ The disposition of record — read through the confluence root.</summary>
			public Terminus RootTerminus;
			public bool Dropped;
			public bool Trunk => Candidate.IsSea;
			public bool ReachesSea => !Dropped && RootTerminus == Terminus.Ocean;
			public string Why = "";
		}

		/// <summary>The cap-independent field: D8 on <c>FullFilled</c>, 0..7 or <see cref="D_NONE"/> (ocean, or no lower neighbour).</summary>
		public sealed class Field
		{
			public sbyte[] Dir;
			public int N;
			public int Target(int i)
			{
				sbyte d = Dir[i];
				if (d < 0) return -1;
				int cx = i / N, cy = i % N;
				return (cx + DX[d]) * N + (cy + DY[d]);
			}
		}

		/// <summary>Per-seed precomputation shared by every cap: each lake basin's water cells and outlet cell; every basin's fill volume.</summary>
		public sealed class Prep
		{
			public Dictionary<int, List<int>> LakeCells = new();
			/// <summary>
			/// ⭐ Per WATER BODY (an 8-connected component of a lake basin's own classify water): its cell with the lowest
			/// <c>FullFilled</c> — the body's point nearest the spill in flood terms, where its overflow leaves. Per body, not
			/// per basin: one basin can own several separate lakes (rivers/04 found `1063685222 #699` owning two), and a
			/// river that enters one must leave from THAT one, not jump across land to another.
			/// </summary>
			public Dictionary<int, int> BodyOut = new();
			/// <summary>Water cell → its body id (lake basins' own water only).</summary>
			public Dictionary<int, int> BodyOf = new();
			/// <summary>Per basin id: Σ (FullFilled − render) × metres, over its cells — the volume to fill it to its spill, in metre·cells.</summary>
			public Dictionary<int, double> FillVolumeMPx = new();
			public bool[] Scratch;   // one reusable target mask for the lowground fallback
		}

		public sealed class HeroLake
		{
			public int BasinId; public long LakeCells; public double FillVolumeMPx;
			public float RiverLenPx; public int RiverRank; public int RiversThrough;
			public double Score;
		}

		public sealed class Result
		{
			public float CapM;
			public List<FlowRiver> Rivers = new();
			public HashSet<int> WalledIds = new();
			public int Trunks, FlowThrough, LakeTerminal, DroppedDry, DroppedClosed, Joined, RescuedByConfluence, DroppedByConfluence;
			public int EdgeAgree, EdgeDisagree, LowgroundFallbacks;
			/// <summary>The field AT THIS CAP: the ∞ field with every walled basin's cells replaced by D8 on the real terrain, so flow into a walled basin ends there.</summary>
			public sbyte[] CappedDir;
			/// <summary>Flow accumulation on the capped field (Kahn), cells; 0 on ocean — the field's own drainage tree, for the data map.</summary>
			public int[] CappedAcc;
			public long LandCells, CellsToSea, CellsToWalledLake, CellsToWalledDry, CellsStuck;
			public List<HeroLake> HeroLakes = new();
		}

		// ═══ THE FIELD ══════════════════════════════════════════════════════════════════════════

		/// <summary>D8 on <c>FullFilled</c> for every non-ocean cell, the analysis's exact neighbour order and drop/DIST rule. Ocean cells are <see cref="D_NONE"/>.</summary>
		public static Field BuildField(DrainageAnalysis.Plan plan, int n, bool[] isOcean)
		{
			int total = n * n;
			var dir = new sbyte[total];
			float[] ff = plan.FullFilled;
			for (int i = 0; i < total; i++)
			{
				if (isOcean[i]) { dir[i] = D_NONE; continue; }
				int cx = i / n, cy = i % n;
				float best = 0f; int bestK = -1;
				for (int k = 0; k < 8; k++)
				{
					int nx = cx + DX[k], ny = cy + DY[k];
					if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
					float drop = (ff[i] - ff[nx * n + ny]) / DIST[k];
					if (drop > best) { best = drop; bestK = k; }
				}
				dir[i] = bestK < 0 ? D_NONE : (sbyte)bestK;
			}
			return new Field { Dir = dir, N = n };
		}

		public static Prep Prepare(DrainageAnalysis.Plan plan, BasinGraph graph, float[,] height, int n, bool[] isOcean, bool[] isClassifyWater)
		{
			int total = n * n;
			var p = new Prep { Scratch = new bool[total] };
			var isLake = new HashSet<int>();
			foreach (var b in graph.Nodes) if (b.IsLake) isLake.Add(b.Id);
			var outFF = new Dictionary<int, float>();
			for (int i = 0; i < total; i++)
			{
				int id = plan.BasinId[i];
				if (id == 0) continue;
				double d = WorldScale.MetresFromRaw(plan.FullFilled[i] - height[i / n, i % n]);
				p.FillVolumeMPx.TryGetValue(id, out double v); p.FillVolumeMPx[id] = v + d;
				if (!isLake.Contains(id) || !isClassifyWater[i] || isOcean[i]) continue;
				if (!p.LakeCells.TryGetValue(id, out var cells)) { cells = new List<int>(); p.LakeCells[id] = cells; }
				cells.Add(i);
			}
			// Label each lake basin's water into bodies (8-connected, fixed order) and find each body's outlet cell.
			int nextBody = 1;
			var stack = new Stack<int>();
			foreach (var kv in p.LakeCells)
			{
				var set = new HashSet<int>(kv.Value);
				foreach (int seed in kv.Value)
				{
					if (p.BodyOf.ContainsKey(seed)) continue;
					int body = nextBody++;
					p.BodyOf[seed] = body; stack.Push(seed);
					int outCell = seed; float outFFv = plan.FullFilled[seed];
					while (stack.Count > 0)
					{
						int c = stack.Pop();
						if (plan.FullFilled[c] < outFFv || (plan.FullFilled[c] == outFFv && c < outCell)) { outFFv = plan.FullFilled[c]; outCell = c; }
						int cx = c / n, cy = c % n;
						for (int k = 0; k < 8; k++)
						{
							int nx = cx + DX[k], ny = cy + DY[k];
							if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
							int ni = nx * n + ny;
							if (!set.Contains(ni) || p.BodyOf.ContainsKey(ni)) continue;
							p.BodyOf[ni] = body; stack.Push(ni);
						}
					}
					p.BodyOut[body] = outCell;
				}
			}
			return p;
		}

		/// <summary>The shortest 8-connected path THROUGH a body's water from one of its cells to another (BFS, fixed order). Water, not channel — recorded, never drawn.</summary>
		private static List<int> WaterPath(Prep prep, int from, int to, int n)
		{
			int body = prep.BodyOf[from];
			var parent = new Dictionary<int, int> { [from] = -1 };
			var q = new Queue<int>(); q.Enqueue(from);
			while (q.Count > 0)
			{
				int c = q.Dequeue();
				if (c == to) break;
				int cx = c / n, cy = c % n;
				for (int k = 0; k < 8; k++)
				{
					int nx = cx + DX[k], ny = cy + DY[k];
					if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
					int ni = nx * n + ny;
					if (parent.ContainsKey(ni) || !prep.BodyOf.TryGetValue(ni, out int b) || b != body) continue;
					parent[ni] = c; q.Enqueue(ni);
				}
			}
			var path = new List<int>();
			if (!parent.ContainsKey(to)) { path.Add(from); path.Add(to); return path; }
			for (int c = to; c >= 0; c = parent[c]) path.Add(c);
			path.Reverse();
			return path;
		}

		// ═══ THE WALKS ══════════════════════════════════════════════════════════════════════════

		public static Result Run(List<RiverCandidate> promoted, DrainageAnalysis.Plan plan, BasinGraph graph, Field field, Prep prep,
			float[,] height, int n, bool[] isOcean, bool[] isClassifyWater, float sea, float capM, Action<string> log, bool confluence = true)
		{
			var r = new Result { CapM = capM };
			foreach (var b in graph.LandNodes) if (b.SpillClimbM > capM) r.WalledIds.Add(b.Id);

			foreach (var c in promoted)
			{
				var fr = Walk(c, plan, graph, field, prep, height, n, isOcean, isClassifyWater, sea, capM, r);
				r.Rivers.Add(fr);
			}

			// ---- confluence (rivers/03b, reused) over EVERY river, kept or not — a river that meets a kept river's
			// channel before its own dead-end is that river's tributary, and its water reaches the sea through it.
			var wrappers = new List<RiverRouting.RoutedRiver>();
			foreach (var fr in r.Rivers)
			{
				fr.Routed = new RiverRouting.RoutedRiver
				{
					Candidate = fr.Candidate, Course = fr.Course,
					Class = fr.Trunk ? RiverRouting.RiverClass.OceanTrunk
						: fr.Terminus == Terminus.Ocean ? RiverRouting.RiverClass.RoutedGiant
						: fr.Terminus == Terminus.Lake ? RiverRouting.RiverClass.LakeEnder
						: RiverRouting.RiverClass.WalledOff,
				};
				wrappers.Add(fr.Routed);
			}
			if (confluence) RiverRouting.Confluence(wrappers, log);
			else foreach (var w in wrappers) w.OwnPath = w.Course;

			var byRank = new Dictionary<int, FlowRiver>();
			foreach (var fr in r.Rivers) byRank[fr.Candidate.Rank] = fr;
			foreach (var fr in r.Rivers)
			{
				var root = RiverRouting.Root(fr.Routed, wrappers);
				var rootFr = byRank[root.Candidate.Rank];
				fr.RootTerminus = rootFr.Terminus;
				fr.Dropped = fr.RootTerminus == Terminus.DrySink || fr.RootTerminus == Terminus.Closed;
				bool ownKept = fr.Terminus == Terminus.Ocean || fr.Terminus == Terminus.Lake;
				if (fr.Routed.Joined)
				{
					r.Joined++;
					if (!ownKept && !fr.Dropped) r.RescuedByConfluence++;
					if (ownKept && fr.Dropped) r.DroppedByConfluence++;
				}
				if (fr.Dropped) { if (fr.RootTerminus == Terminus.Closed) r.DroppedClosed++; else r.DroppedDry++; }
				else if (fr.Trunk) r.Trunks++;
				else if (fr.RootTerminus == Terminus.Ocean) r.FlowThrough++;
				else r.LakeTerminal++;
				foreach (var h in fr.Chain) { if (h.UsedLowgroundFallback) r.LowgroundFallbacks++; }
			}
			foreach (var fr in r.Rivers)
				for (int i = 0; i < fr.Chain.Count; i++)
					if (fr.Chain[i].SpillCell >= 0) { if (fr.Chain[i].EdgeAgreesWithGraph) r.EdgeAgree++; else r.EdgeDisagree++; }
			return r;
		}

		private static FlowRiver Walk(RiverCandidate c, DrainageAnalysis.Plan plan, BasinGraph graph, Field field, Prep prep,
			float[,] height, int n, bool[] isOcean, bool[] isClassifyWater, float sea, float capM, Result res)
		{
			var fr = new FlowRiver { Candidate = c };
			// The upland stem, head → terminal (the analysis's course is downstream-first, decimated ×4).
			fr.Course = new List<(float x, float y)>(c.Course);
			fr.Course.Reverse();
			fr.StemLenPx = PolyLen(fr.Course);

			if (c.IsSea)
			{
				fr.Terminus = Terminus.Ocean;
				fr.MouthCell = c.Cell;
				fr.Why = "natural ocean trunk — erosion already reaches the coast";
				return fr;
			}

			int cur = c.TermX * n + c.TermY;
			int basin = plan.BasinId[cur] != 0 ? plan.BasinId[cur] : c.BasinId;
			var visited = new HashSet<int>();
			var why = new System.Text.StringBuilder();

			for (int guard = 0; guard < 256; guard++)
			{
				var node = graph.Of(basin);
				if (node == null || !visited.Add(basin))
				{
					fr.Terminus = Terminus.Closed; fr.TerminusBasinId = basin; fr.MouthCell = cur;
					why.Append(node == null ? $" → basin #{basin} not in the graph (closed)" : $" → basin #{basin} revisited (closed)");
					break;
				}
				var hop = new Hop { BasinId = basin, IsLake = node.IsLake, ClimbM = node.SpillClimbM, Walled = node.SpillClimbM > capM, EntryCell = cur };
				fr.Chain.Add(hop);
				if (hop.ClimbM > fr.MaxHopClimbM) fr.MaxHopClimbM = hop.ClimbM;

				if (hop.Walled)
				{
					fr.TerminusBasinId = basin;
					if (node.IsLake)
					{
						var reach = DescendToWater(cur, basin, plan, prep, height, n, isOcean, isClassifyWater, sea, out bool fb);
						hop.UsedLowgroundFallback = fb;
						if (reach.Count > 1) AppendReach(fr, reach, n);
						hop.LakeEntryCell = reach[^1];
						fr.Terminus = Terminus.Lake; fr.MouthCell = reach[^1];
						why.Append($" → #{basin} LAKE, rim {hop.ClimbM:F1} m > cap {capM:F0} m: walls at the lake — LAKE-TERMINAL, kept");
					}
					else
					{
						fr.Terminus = Terminus.DrySink; fr.MouthCell = cur;
						why.Append($" → #{basin} DRY{(node.HasAnyLake ? " (puddle only)" : "")}, rim {hop.ClimbM:F1} m > cap {capM:F0} m: walls at a dry sink — DROPPED");
					}
					break;
				}

				fr.TotalClimbM += hop.ClimbM;
				int from = cur;
				if (node.IsLake)
				{
					var reach = DescendToWater(cur, basin, plan, prep, height, n, isOcean, isClassifyWater, sea, out bool fb);
					hop.UsedLowgroundFallback = fb;
					if (reach.Count > 1) AppendReach(fr, reach, n);
					int w = reach[^1];
					hop.LakeEntryCell = w;
					int lakeOut = prep.BodyOf.TryGetValue(w, out int body) && prep.BodyOut.TryGetValue(body, out int bo) ? bo : w;
					if (lakeOut != w)
					{
						// The lake span — through the water of the body the river entered, to that body's outlet.
						fr.WaterSpans.Add((w, lakeOut));
						var span = WaterPath(prep, w, lakeOut, n);
						for (int i = 1; i < span.Count; i++) fr.Course.Add((span[i] / n, span[i] % n));
					}
					fr.LakesPassed++;
					from = lakeOut;
					why.Append($" → #{basin} LAKE, rim {hop.ClimbM:F1} m ≤ cap: through the lake and over its spill");
				}
				else why.Append($" → #{basin} dry, rim {hop.ClimbM:F1} m ≤ cap: across the low ground and over its spill");

				var path = Follow(from, basin, field, plan, isOcean, n, out int status, out int spill);
				hop.SpillCell = spill;
				if (path.Count > 1) AppendReach(fr, path, n);
				int end = path[^1];

				if (status == 1)
				{
					fr.Terminus = Terminus.Ocean; fr.MouthCell = end;
					hop.EdgeAgreesWithGraph = node.Downstream == DownstreamKind.Ocean;
					why.Append(" → the SEA — flow-through, kept");
					break;
				}
				if (status == 0)
				{
					fr.Terminus = Terminus.Closed; fr.TerminusBasinId = 0; fr.MouthCell = end;
					hop.EdgeAgreesWithGraph = node.Downstream == DownstreamKind.None;
					why.Append(" → stuck on an exact flat outside any basin — CLOSED, dropped");
					break;
				}
				int next = plan.BasinId[end];
				hop.EdgeAgreesWithGraph = node.Downstream == DownstreamKind.Basin && node.DownstreamId == next;
				cur = end; basin = next;
			}
			fr.Why = $"terminal basin #{fr.Chain[0].BasinId}" + why;
			return fr;
		}

		/// <summary>
		/// Follow the ∞ field from a cell inside <paramref name="basin"/> until it reaches the ocean (status 1),
		/// enters another terminal basin (status 2), or sticks (status 0). <paramref name="spill"/> is the first
		/// cell outside the basin on the way.
		/// </summary>
		private static List<int> Follow(int start, int basin, Field field, DrainageAnalysis.Plan plan, bool[] isOcean, int n,
			out int status, out int spill)
		{
			var path = new List<int> { start };
			int c = start; spill = -1; status = 0;
			for (int guard = 0; guard < 8 * n; guard++)
			{
				int b = plan.BasinId[c];
				if (b != basin && spill < 0) spill = c;
				if (isOcean[c]) { status = 1; return path; }
				if (b != basin && b != 0) { status = 2; return path; }
				int t = field.Target(c);
				if (t < 0) { status = 0; return path; }
				c = t; path.Add(c);
			}
			return path;
		}

		/// <summary>
		/// The real-terrain descent from a point inside a lake basin to the basin's own classify water:
		/// <c>Plan.Dir</c> (D8 on <c>Filled</c>) until a water cell; if it pools short (the terminal is a D8
		/// sink by definition), rivers/03c fix B's lowground route to the basin's own water — same rule, same cost model.
		/// </summary>
		private static List<int> DescendToWater(int start, int basin, DrainageAnalysis.Plan plan, Prep prep, float[,] height, int n,
			bool[] isOcean, bool[] isClassifyWater, float sea, out bool usedFallback)
		{
			usedFallback = false;
			var path = new List<int> { start };
			int c = start;
			bool IsOwnWater(int i) => isClassifyWater[i] && !isOcean[i] && plan.BasinId[i] == basin;
			for (int guard = 0; guard < 8 * n; guard++)
			{
				if (IsOwnWater(c)) return path;
				sbyte d = plan.Dir[c];
				if (d < 0) break;
				int cx = c / n, cy = c % n;
				int t = (cx + DX[d]) * n + (cy + DY[d]);
				if (plan.BasinId[t] != basin) break;
				c = t; path.Add(c);
			}
			// Pooled short of the water — route the rest as rivers/03c does for a lake-ender.
			if (!prep.LakeCells.TryGetValue(basin, out var cells) || cells.Count == 0) return path;
			usedFallback = true;
			foreach (int i in cells) prep.Scratch[i] = true;
			var route = RiverRouting.RouteTo(height, n, prep.Scratch, start / n, start % n, RiverRouting.StyleLowground, sea);
			foreach (int i in cells) prep.Scratch[i] = false;
			if (!route.Reached) return path;
			var outp = new List<int>(route.Path.Count);
			foreach (var p in route.Path) outp.Add((int)p.x * n + (int)p.y);
			return outp;
		}

		/// <summary>Append a 1-px cell reach to the course, RDP+Chaikin-smoothed as rivers/03 smooths every lowland reach (endpoints pinned).</summary>
		private static void AppendReach(FlowRiver fr, List<int> cells, int n)
		{
			var pts = new List<(float x, float y)>(cells.Count);
			foreach (int i in cells) pts.Add((i / n, i % n));
			fr.LowlandLenPx += PolyLen(pts);
			var sm = RiverRouting.SmoothCourse(pts);
			int start = fr.Course.Count > 0 && fr.Course[^1].x == sm[0].x && fr.Course[^1].y == sm[0].y ? 1 : 0;
			for (int i = start; i < sm.Count; i++) fr.Course.Add(sm[i]);
		}

		private static float PolyLen(List<(float x, float y)> pts)
		{
			float L = 0f;
			for (int i = 1; i < pts.Count; i++)
			{
				float dx = pts[i].x - pts[i - 1].x, dy = pts[i].y - pts[i - 1].y;
				L += MathF.Sqrt(dx * dx + dy * dy);
			}
			return L;
		}

		// ═══ THE FIELD AT THE CAP — the artifact ════════════════════════════════════════════════

		/// <summary>
		/// The ∞ field with every WALLED basin's cells replaced by D8 on the real terrain (<c>Filled</c>), so
		/// flow that reaches a walled basin descends to its floor and ends there — "a cell whose downstream
		/// chain walls off drains to that wall, not past it". Then every land cell's destination, memoised.
		/// </summary>
		public static void BuildCappedField(Result r, DrainageAnalysis.Plan plan, BasinGraph graph, Field field, int n, bool[] isOcean)
		{
			int total = n * n;
			var dir = (sbyte[])field.Dir.Clone();
			float[] filled = plan.Filled;
			for (int i = 0; i < total; i++)
			{
				int id = plan.BasinId[i];
				if (id == 0 || !r.WalledIds.Contains(id) || isOcean[i]) continue;
				int cx = i / n, cy = i % n;
				float best = 0f; int bestK = -1;
				for (int k = 0; k < 8; k++)
				{
					int nx = cx + DX[k], ny = cy + DY[k];
					if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
					float drop = (filled[i] - filled[nx * n + ny]) / DIST[k];
					if (drop > best) { best = drop; bestK = k; }
				}
				dir[i] = bestK < 0 ? D_NONE : (sbyte)bestK;
			}
			r.CappedDir = dir;

			// Accumulation on the capped field — Kahn propagation, as the analysis does on its own field.
			{
				var acc = new int[total];
				var indeg = new byte[total];
				int Tgt(int i) { sbyte d = dir[i]; if (d < 0) return -1; int cx = i / n, cy = i % n; return (cx + DX[d]) * n + (cy + DY[d]); }
				for (int i = 0; i < total; i++) if (!isOcean[i] && dir[i] >= 0) { int t = Tgt(i); if (!isOcean[t]) indeg[t]++; }
				var q = new Queue<int>();
				for (int i = 0; i < total; i++) { if (isOcean[i]) continue; acc[i] = 1; if (indeg[i] == 0) q.Enqueue(i); }
				while (q.Count > 0)
				{
					int c = q.Dequeue();
					int t = Tgt(c);
					if (t < 0 || isOcean[t]) continue;
					acc[t] += acc[c];
					if (--indeg[t] == 0) q.Enqueue(t);
				}
				r.CappedAcc = acc;
			}

			// Destinations: -1 sea, >0 basin id (a sink), -2 stuck.
			var lakeIds = new HashSet<int>();
			foreach (var b in graph.Nodes) if (b.IsLake) lakeIds.Add(b.Id);
			var dest = new int[total];
			var path = new List<int>(4096);
			for (int i = 0; i < total; i++)
			{
				if (isOcean[i] || dest[i] != 0) continue;
				int c = i; path.Clear(); int result;
				while (true)
				{
					if (dest[c] != 0) { result = dest[c]; break; }
					path.Add(c);
					sbyte d = dir[c];
					if (d < 0) { result = plan.BasinId[c] != 0 ? plan.BasinId[c] : -2; break; }
					int cx = c / n, cy = c % n;
					int t = (cx + DX[d]) * n + (cy + DY[d]);
					if (isOcean[t]) { result = -1; break; }
					c = t;
				}
				foreach (int pc in path) dest[pc] = result;
			}
			for (int i = 0; i < total; i++)
			{
				if (isOcean[i]) continue;
				r.LandCells++;
				int d = dest[i];
				if (d == -1) r.CellsToSea++;
				else if (d > 0) { if (lakeIds.Contains(d)) r.CellsToWalledLake++; else r.CellsToWalledDry++; }
				else r.CellsStuck++;
			}
		}

		// ═══ THE HERO-LAKE CANDIDATE — data, not a fill ═════════════════════════════════════════

		/// <summary>
		/// Among lakes that a sea-reaching, un-joined river flows THROUGH, rank by the geometric mean of
		/// normalised fill volume and normalised attached river length. Recorded intent (procedural, executed
		/// post-water-render); nothing is filled here.
		/// </summary>
		public static void RankHeroLakes(Result r, BasinGraph graph, Prep prep)
		{
			var cand = new Dictionary<int, HeroLake>();
			foreach (var fr in r.Rivers)
			{
				if (fr.Dropped || fr.Trunk || fr.Routed.Joined || fr.Terminus != Terminus.Ocean) continue;
				foreach (var h in fr.Chain)
				{
					if (!h.IsLake || h.Walled) continue;
					if (!cand.TryGetValue(h.BasinId, out var hl))
					{
						var node = graph.Of(h.BasinId);
						hl = new HeroLake { BasinId = h.BasinId, LakeCells = node.LakeCells, FillVolumeMPx = prep.FillVolumeMPx.TryGetValue(h.BasinId, out double v) ? v : 0 };
						cand[h.BasinId] = hl;
					}
					hl.RiversThrough++;
					if (fr.TotalLenPx > hl.RiverLenPx) { hl.RiverLenPx = fr.TotalLenPx; hl.RiverRank = fr.Candidate.Rank; }
				}
			}
			double maxV = 1, maxL = 1;
			foreach (var hl in cand.Values) { if (hl.FillVolumeMPx > maxV) maxV = hl.FillVolumeMPx; if (hl.RiverLenPx > maxL) maxL = hl.RiverLenPx; }
			foreach (var hl in cand.Values) hl.Score = Math.Sqrt((hl.FillVolumeMPx / maxV) * (hl.RiverLenPx / maxL));
			r.HeroLakes = new List<HeroLake>(cand.Values);
			r.HeroLakes.Sort((a, b) => b.Score != a.Score ? b.Score.CompareTo(a.Score) : a.BasinId.CompareTo(b.BasinId));
		}

		public static string TerminusName(Terminus t) => t switch
		{
			Terminus.Ocean => "sea", Terminus.Lake => "lake", Terminus.DrySink => "dry-sink", _ => "closed",
		};

		public static string ClassName(FlowRiver fr) =>
			fr.Dropped ? "dropped" : fr.Trunk ? "trunk" : fr.RootTerminus == Terminus.Ocean ? "flow-through" : "lake-terminal";
	}
}