#include "World/DescentTerrainSubsystem.h"
#include "World/DescentOreSubsystem.h"
#include "World/DescentTerrainActor.h"
#include "World/DescentWorldDef.h"
#include "World/SurfaceNets.h"
#include "Core/DescentMath.h"
#include "Core/Tuning/DescentTune_World.h"
#include "Debug/DescentStateRegistry.h"
#include "TheDescent.h"
#include "DescentUnits.h"

#include "Async/ParallelFor.h"
#include "Engine/World.h"
#include "HAL/IConsoleManager.h"
#include "HAL/PlatformProcess.h"
#include "HAL/PlatformTime.h"
#include "Misc/Compression.h"
#include "Serialization/MemoryReader.h"
#include "Serialization/MemoryWriter.h"
#include "ProceduralMeshComponent.h"
#include "Tasks/Task.h"

namespace TTune = Descent::Tune::Terrain;
namespace WTune = Descent::Tune::World;
using namespace Descent::World;

static TAutoConsoleVariable<float> GTerrainCvarStreamRadius(
	TEXT("descent.Terrain.StreamRadius"), static_cast<float>(TTune::LoadRadiusM),
	TEXT("Radius in metres around the stream focus points that is loaded and meshed (unload radius = this + 40). Low preset: 120."));

namespace
{
	/** Floor division for negative numerators. */
	int32 TerrainFloorDiv(int32 A, int32 B)
	{
		int32 Q = A / B;
		if ((A % B != 0) && ((A < 0) != (B < 0))) { --Q; }
		return Q;
	}

	/** Index of local sample (I, J, K) in a padded chunk array. */
	FORCEINLINE int32 TerrainIdx(int32 I, int32 J, int32 K) { return I + J * TTune::P + K * TTune::P2; }
}

UDescentTerrainSubsystem* UDescentTerrainSubsystem::Get(const UWorld* World)
{
	return World ? World->GetSubsystem<UDescentTerrainSubsystem>() : nullptr;
}

void UDescentTerrainSubsystem::Initialize(FSubsystemCollectionBase& Collection)
{
	Super::Initialize(Collection);
	Collection.InitializeDependency<UDescentSimSubsystem>();
	Collection.InitializeDependency<UDescentStreamFocusSubsystem>();
	Collection.InitializeDependency<UDescentOreSubsystem>();
}

void UDescentTerrainSubsystem::OnWorldBeginPlay(UWorld& InWorld)
{
	Super::OnWorldBeginPlay(InWorld);
	if (UDescentSimSubsystem* Sim = UDescentSimSubsystem::Get(GetWorld()))
	{
		FDescentSimRegisterOptions Opt;
		Opt.Owner = TEXT("Terrain");
		StepHandle = Sim->RegisterStep(EDescentSimStep::Terrain, [this](const FDescentSimFrame& F) { Tick(F); }, Opt);
	}
}

void UDescentTerrainSubsystem::Deinitialize()
{
	if (UDescentSimSubsystem* Sim = UDescentSimSubsystem::Get(GetWorld()))
	{
		Sim->Unregister(StepHandle);
	}
	// Workers read only their own copies and the immortal world definition, but they push into our queue: wait for them.
	while (InFlight.load() > 0)
	{
		FPlatformProcess::Sleep(0.001f);
	}
	Chunks.Empty();
	Super::Deinitialize();
}

UDescentOreSubsystem* UDescentTerrainSubsystem::Ore()
{
	if (!OreSub.IsValid())
	{
		OreSub = UDescentOreSubsystem::Get(GetWorld());
	}
	return OreSub.Get();
}

double UDescentTerrainSubsystem::GetLoadRadiusM() const
{
	return GTerrainCvarStreamRadius.GetValueOnAnyThread();
}

FIntVector UDescentTerrainSubsystem::KeyOfPoint(const FVector& P)
{
	return FIntVector(FMath::FloorToInt(P.X / TTune::ChunkM), FMath::FloorToInt(P.Y / TTune::ChunkM), FMath::FloorToInt(P.Z / TTune::ChunkM));
}

// ---------------------------------------------------------------------------------------------------------
// Chunks
// ---------------------------------------------------------------------------------------------------------

FTerrainChunk* UDescentTerrainSubsystem::FindChunk(const FIntVector& Key)
{
	if (LastChunk && LastChunkKey == Key) { return LastChunk; }
	if (TSharedPtr<FTerrainChunk>* F = Chunks.Find(Key))
	{
		LastChunk = F->Get();
		LastChunkKey = Key;
		return LastChunk;
	}
	return nullptr;
}

FTerrainChunk* UDescentTerrainSubsystem::FindOrCreateChunk(const FIntVector& Key)
{
	if (FTerrainChunk* C = FindChunk(Key)) { return C; }
	TSharedPtr<FTerrainChunk> N = MakeShared<FTerrainChunk>();
	N->Key = Key;
	ClassifyChunk(*N);
	Chunks.Add(Key, N);
	LastChunk = N.Get();
	LastChunkKey = Key;
	return LastChunk;
}

void UDescentTerrainSubsystem::ClassifyChunk(FTerrainChunk& C)
{
	const FDescentWorldDef& Def = FDescentWorldDef::Get();
	const FVector Centre = C.CentreM();
	FPrimList L;
	Def.Sdf().Gather(Centre, TTune::ChunkM * TTune::GatherRadiusFactor + TTune::GatherRadiusBias, L);
	const double V = Def.Sdf().GenRaw(Centre, L);
	bool bSponge = false;
	for (const FSpongeZone& Z : Def.Sponges)
	{
		if (FDescentSDF::BoxSDF(Z.Box, Centre.X, Centre.Y, Centre.Z) < TTune::ChunkM * TTune::ClassifyFactor + TTune::SpongeCandidateGrow) { bSponge = true; }
	}
	if (!bSponge && FMath::Abs(V) > TTune::ChunkM * TTune::ClassifyFactor + TTune::ClassifyBias)
	{
		C.State = EChunkState::Uniform;
		C.UniformValue = V > 0.0 ? static_cast<float>(WTune::ClampD) : -static_cast<float>(WTune::ClampD);
	}
	else
	{
		C.State = EChunkState::Candidate;
	}
}

void UDescentTerrainSubsystem::RefreshDeposits(FTerrainChunk& C)
{
	if (C.bDepositsKnown) { return; }
	C.bDepositsKnown = true;
	C.Deposits.Reset();
	TArray<int32, TInlineAllocator<8>> Near;
	FDescentWorldDef::Get().DepositsNear(C.CentreM(), TTune::ChunkM + 4.0, Near);
	for (const int32 I : Near) { C.Deposits.Add(I); }
}

/** The fill: Gather + P^3 Gen samples. Static and thread-safe. Returns true if the field has both signs. */
static bool TerrainFillData(const FIntVector& Key, TArray<float>& OutData, TArray<uint8>& OutCut)
{
	const FDescentWorldDef& Def = FDescentWorldDef::Get();
	const FDescentSDF& Sdf = Def.Sdf();
	const FVector Centre = (FVector(Key) + FVector(0.5)) * TTune::ChunkM;
	FPrimList L;
	Sdf.Gather(Centre, TTune::ChunkM * TTune::GatherRadiusFactor + TTune::GatherRadiusBias, L);
	OutData.SetNumUninitialized(TTune::P3);
	OutCut.Init(0, TTune::P3);
	int32 Pos = 0, Neg = 0;
	const int32 Bx = Key.X * TTune::CoreN - TTune::Pad, By = Key.Y * TTune::CoreN - TTune::Pad, Bz = Key.Z * TTune::CoreN - TTune::Pad;
	for (int32 K = 0; K < TTune::P; ++K)
	{
		for (int32 J = 0; J < TTune::P; ++J)
		{
			for (int32 I = 0; I < TTune::P; ++I)
			{
				const FVector P((Bx + I) * TTune::VoxelM, (By + J) * TTune::VoxelM, (Bz + K) * TTune::VoxelM);
				const float V = static_cast<float>(Sdf.Gen(P, L));
				OutData[TerrainIdx(I, J, K)] = V;
				if (V > 0.f) { ++Pos; } else { ++Neg; }
			}
		}
	}
	return Pos > 0 && Neg > 0;
}

void UDescentTerrainSubsystem::FillChunkSync(FTerrainChunk& C)
{
	const double T0 = FPlatformTime::Seconds();
	TerrainFillData(C.Key, C.Data, C.Cut);
	FillMsSum += (FPlatformTime::Seconds() - T0) * 1000.0;
	++FillCount;
	C.State = EChunkState::Mixed;   // a chunk that is about to be edited keeps its data even if it has no surface
	++C.Version;                    // a job in flight for the old state is now stale
}

FTerrainChunk& UDescentTerrainSubsystem::EnsureData(FTerrainChunk& C)
{
	if (!C.HasData()) { FillChunkSync(C); }
	return C;
}

float UDescentTerrainSubsystem::GenQuickGen(const FVector& P)
{
	const FIntVector Cell(FMath::FloorToInt(P.X / WTune::GenQuickCell), FMath::FloorToInt(P.Y / WTune::GenQuickCell), FMath::FloorToInt(P.Z / WTune::GenQuickCell));
	TSharedPtr<FPrimList>* Found = QuickCache.Find(Cell);
	if (!Found)
	{
		if (QuickCache.Num() >= WTune::GenQuickCacheEntries) { QuickCache.Empty(WTune::GenQuickCacheEntries); }
		TSharedPtr<FPrimList> L = MakeShared<FPrimList>();
		const FVector C((Cell.X + 0.5) * WTune::GenQuickCell, (Cell.Y + 0.5) * WTune::GenQuickCell, (Cell.Z + 0.5) * WTune::GenQuickCell);
		FDescentWorldDef::Get().Sdf().Gather(C, WTune::GenQuickCell * 0.87 + 2.0, *L);
		Found = &QuickCache.Add(Cell, L);
	}
	return static_cast<float>(FDescentWorldDef::Get().Sdf().Gen(P, **Found));
}

// ---------------------------------------------------------------------------------------------------------
// Queries
// ---------------------------------------------------------------------------------------------------------

double UDescentTerrainSubsystem::Density(const FVector& P)
{
	FTerrainChunk* C = FindOrCreateChunk(KeyOfPoint(P));
	if (C->HasData())
	{
		const double Gx = P.X / TTune::VoxelM, Gy = P.Y / TTune::VoxelM, Gz = P.Z / TTune::VoxelM;
		const double Lx = Gx - C->Key.X * TTune::CoreN + TTune::Pad, Ly = Gy - C->Key.Y * TTune::CoreN + TTune::Pad, Lz = Gz - C->Key.Z * TTune::CoreN + TTune::Pad;
		const int32 Ix = FMath::Clamp(FMath::FloorToInt(Lx), 0, TTune::P - 2), Iy = FMath::Clamp(FMath::FloorToInt(Ly), 0, TTune::P - 2), Iz = FMath::Clamp(FMath::FloorToInt(Lz), 0, TTune::P - 2);
		const double Fx = Lx - Ix, Fy = Ly - Iy, Fz = Lz - Iz;
		const float* D = C->Data.GetData();
		const int32 B = TerrainIdx(Ix, Iy, Iz);
		const double C00 = D[B] + (D[B + 1] - D[B]) * Fx, C10 = D[B + TTune::P] + (D[B + TTune::P + 1] - D[B + TTune::P]) * Fx;
		const double C01 = D[B + TTune::P2] + (D[B + TTune::P2 + 1] - D[B + TTune::P2]) * Fx;
		const double C11 = D[B + TTune::P2 + TTune::P] + (D[B + TTune::P2 + TTune::P + 1] - D[B + TTune::P2 + TTune::P]) * Fx;
		const double C0 = C00 + (C10 - C00) * Fy, C1 = C01 + (C11 - C01) * Fy;
		return C0 + (C1 - C0) * Fz;
	}
	if (C->State == EChunkState::Uniform) { return C->UniformValue; }
	return GenQuickGen(P);
}

FVector UDescentTerrainSubsystem::Gradient(const FVector& P, double H)
{
	const FVector G(Density(P + FVector(H, 0, 0)) - Density(P - FVector(H, 0, 0)),
		Density(P + FVector(0, H, 0)) - Density(P - FVector(0, H, 0)),
		Density(P + FVector(0, 0, H)) - Density(P - FVector(0, 0, H)));
	const double L = G.Size();
	return L > 1e-6 ? G / L : FVector(0, 0, 1);
}

double UDescentTerrainSubsystem::Raycast(const FVector& O, const FVector& Dir, double MaxD, double MinStep)
{
	if (Density(O) > 0.0) { return 0.0; }
	double T = 0.0, PrevT = 0.0;
	while (T < MaxD)
	{
		const double V = Density(O + Dir * T);
		if (V > 0.0)
		{
			double A = PrevT, B = T;
			for (int32 I = 0; I < TTune::RaycastBisections; ++I)
			{
				const double M = 0.5 * (A + B);
				if (Density(O + Dir * M) > 0.0) { B = M; } else { A = M; }
			}
			return B;
		}
		PrevT = T;
		T += FMath::Max(MinStep, -V * TTune::RaycastStepFactor);
	}
	return -1.0;
}

bool UDescentTerrainSubsystem::PushOutSphere(FVector& C, double Radius, FVector* OutNormal)
{
	const double Pen = Radius + Density(C);
	if (Pen <= 0.0) { return false; }
	const FVector G = Gradient(C);
	C -= G * Pen;
	if (OutNormal) { *OutNormal = -G; }
	return true;
}

float UDescentTerrainSubsystem::GetSampleGlobal(int32 Gx, int32 Gy, int32 Gz)
{
	const FIntVector K(TerrainFloorDiv(Gx, TTune::CoreN), TerrainFloorDiv(Gy, TTune::CoreN), TerrainFloorDiv(Gz, TTune::CoreN));
	FTerrainChunk* C = FindOrCreateChunk(K);
	if (C->HasData())
	{
		return C->Data[TerrainIdx(Gx - K.X * TTune::CoreN + TTune::Pad, Gy - K.Y * TTune::CoreN + TTune::Pad, Gz - K.Z * TTune::CoreN + TTune::Pad)];
	}
	if (C->State == EChunkState::Uniform) { return C->UniformValue; }
	return GenQuickGen(FVector(Gx * TTune::VoxelM, Gy * TTune::VoxelM, Gz * TTune::VoxelM));
}

void UDescentTerrainSubsystem::SetSampleGlobal(int32 Gx, int32 Gy, int32 Gz, float V)
{
	// Every chunk that holds a copy of the sample (core or padding) is written, so neighbouring meshes keep identical borders.
	const int32 N = TTune::CoreN;
	for (int32 Cz = TerrainFloorDiv(Gz - N - 1, N); Cz <= TerrainFloorDiv(Gz + 2, N); ++Cz)
	{
		for (int32 Cy = TerrainFloorDiv(Gy - N - 1, N); Cy <= TerrainFloorDiv(Gy + 2, N); ++Cy)
		{
			for (int32 Cx = TerrainFloorDiv(Gx - N - 1, N); Cx <= TerrainFloorDiv(Gx + 2, N); ++Cx)
			{
				const int32 Lx = Gx - Cx * N + TTune::Pad, Ly = Gy - Cy * N + TTune::Pad, Lz = Gz - Cz * N + TTune::Pad;
				if (Lx < 0 || Ly < 0 || Lz < 0 || Lx >= TTune::P || Ly >= TTune::P || Lz >= TTune::P) { continue; }
				FTerrainChunk* C = FindOrCreateChunk(FIntVector(Cx, Cy, Cz));
				if (!C->HasData())
				{
					if (C->State == EChunkState::Uniform && (C->UniformValue > 0.f) == (V > 0.f)) { continue; }
					EnsureData(*C);
				}
				C->Data[TerrainIdx(Lx, Ly, Lz)] = V;
				C->bModified = true;
				C->bDirty = true;
				++C->Version;
				DirtySet.Add(C->Key);
			}
		}
	}
}

// ---------------------------------------------------------------------------------------------------------
// Carving (section 2.5; port of 04_terrain.js carve)
// ---------------------------------------------------------------------------------------------------------

int32 UDescentTerrainSubsystem::Carve(const FVector& Cm, double Rad, double Rate, double Dt, bool bIgnoreHardness)
{
	const FDescentWorldDef& Def = FDescentWorldDef::Get();
	const double Reach = Rad + TTune::CarveReachExtra;
	const int32 N = TTune::CoreN;
	const int32 G0x = FMath::FloorToInt((Cm.X - Reach) / TTune::VoxelM), G1x = FMath::CeilToInt((Cm.X + Reach) / TTune::VoxelM);
	const int32 G0y = FMath::FloorToInt((Cm.Y - Reach) / TTune::VoxelM), G1y = FMath::CeilToInt((Cm.Y + Reach) / TTune::VoxelM);
	const int32 G0z = FMath::FloorToInt((Cm.Z - Reach) / TTune::VoxelM), G1z = FMath::CeilToInt((Cm.Z + Reach) / TTune::VoxelM);
	int32 Removed = 0;
	UDescentOreSubsystem* OreSys = Ore();
	for (int32 Cz = TerrainFloorDiv(G0z - N - 1, N); Cz <= TerrainFloorDiv(G1z + 2, N); ++Cz)
	{
		for (int32 Cy = TerrainFloorDiv(G0y - N - 1, N); Cy <= TerrainFloorDiv(G1y + 2, N); ++Cy)
		{
			for (int32 Cx = TerrainFloorDiv(G0x - N - 1, N); Cx <= TerrainFloorDiv(G1x + 2, N); ++Cx)
			{
				FTerrainChunk* Ch = FindOrCreateChunk(FIntVector(Cx, Cy, Cz));
				if (!Ch->HasData())
				{
					if (Ch->State == EChunkState::Uniform && Ch->UniformValue < 0.f) { continue; }   // open water: nothing to remove
					EnsureData(*Ch);
				}
				const int32 Bx = Cx * N - TTune::Pad, By = Cy * N - TTune::Pad, Bz = Cz * N - TTune::Pad;
				const int32 I0 = FMath::Max(0, G0x - Bx), I1 = FMath::Min(TTune::P - 1, G1x - Bx);
				const int32 J0 = FMath::Max(0, G0y - By), J1 = FMath::Min(TTune::P - 1, G1y - By);
				const int32 K0 = FMath::Max(0, G0z - Bz), K1 = FMath::Min(TTune::P - 1, G1z - Bz);
				if (I0 > I1 || J0 > J1 || K0 > K1) { continue; }
				RefreshDeposits(*Ch);
				bool bTouched = false;
				float* D = Ch->Data.GetData();
				uint8* Cu = Ch->Cut.GetData();
				for (int32 K = K0; K <= K1; ++K)
				{
					for (int32 J = J0; J <= J1; ++J)
					{
						for (int32 I = I0; I <= I1; ++I)
						{
							const FVector W((Bx + I) * TTune::VoxelM, (By + J) * TTune::VoxelM, (Bz + K) * TTune::VoxelM);
							const double Dist = FVector::Dist(W, Cm);
							if (Dist > Rad + TTune::CarveReachExtra) { continue; }
							if (!bIgnoreHardness && FDescentWorldDef::ClaimDist(W) > WTune::BasaltRampM) { continue; }   // dense basalt: nothing cuts it (a debug carve ignores this too)
							const int32 Id = TerrainIdx(I, J, K);
							const double Old = D[Id];
							const double Target = Dist - Rad;
							double Nv = Descent::SMin(Old, Target, TTune::CarveBlendK);
							const double MaxDrop = Rate * Dt / (bIgnoreHardness ? 1.0 : FDescentWorldDef::HardnessAt(W));
							if (Nv < Old - MaxDrop) { Nv = Old - MaxDrop; }
							if (Nv < -WTune::ClampD) { Nv = -WTune::ClampD; }
							if (Nv >= Old) { continue; }
							D[Id] = static_cast<float>(Nv);
							bTouched = true;
							if (Dist < Rad + TTune::CarveCutRadiusExtra) { Cu[Id] = FMath::Max<uint8>(Cu[Id], TTune::CutValue); }
							const bool bCore = I >= TTune::Pad && I < N + TTune::Pad && J >= TTune::Pad && J < N + TTune::Pad && K >= TTune::Pad && K < N + TTune::Pad;
							if (bCore && Old > 0.0 && Nv <= 0.0)
							{
								++Removed;
								double Kd = 0.0;
								const int32 Dep = Ch->Deposits.Num() > 0 ? Def.DepositAt(W, Ch->Deposits, Kd) : -1;
								if (Dep >= 0 && OreSys) { OreSys->NoteSampleRemoved(Dep, W); }
							}
						}
					}
				}
				if (bTouched)
				{
					Ch->bModified = true;
					Ch->bDirty = true;
					++Ch->Version;
					DirtySet.Add(Ch->Key);
				}
			}
		}
	}
	LastRemoved = Removed;
	return Removed;
}

int32 UDescentTerrainSubsystem::CleanupFloating(const FVector& Cm, double Rad)
{
	const int32 R = FMath::CeilToInt((Rad + TTune::CleanupMargin) / TTune::VoxelM);
	const int32 Ox = FMath::RoundToInt(Cm.X / TTune::VoxelM) - R, Oy = FMath::RoundToInt(Cm.Y / TTune::VoxelM) - R, Oz = FMath::RoundToInt(Cm.Z / TTune::VoxelM) - R;
	const int32 S = 2 * R + 1, S2 = S * S, Tot = S * S2;
	TArray<uint8> Solid, Seen;
	Solid.SetNumZeroed(Tot);
	Seen.SetNumZeroed(Tot);
	for (int32 K = 0; K < S; ++K)
	{
		for (int32 J = 0; J < S; ++J)
		{
			for (int32 I = 0; I < S; ++I)
			{
				Solid[I + J * S + K * S2] = GetSampleGlobal(Ox + I, Oy + J, Oz + K) > 0.f ? 1 : 0;
			}
		}
	}
	TArray<int32> Stack;
	for (int32 K = 0; K < S; ++K)
	{
		for (int32 J = 0; J < S; ++J)
		{
			for (int32 I = 0; I < S; ++I)
			{
				if (!(I == 0 || J == 0 || K == 0 || I == S - 1 || J == S - 1 || K == S - 1)) { continue; }
				const int32 Id = I + J * S + K * S2;
				if (Solid[Id] && !Seen[Id]) { Seen[Id] = 1; Stack.Add(Id); }
			}
		}
	}
	while (Stack.Num() > 0)
	{
		const int32 Id = Stack.Pop(EAllowShrinking::No);
		const int32 I = Id % S, J = (Id / S) % S, K = Id / S2;
		const int32 Nb[6] = { I > 0 ? Id - 1 : -1, I < S - 1 ? Id + 1 : -1, J > 0 ? Id - S : -1, J < S - 1 ? Id + S : -1, K > 0 ? Id - S2 : -1, K < S - 1 ? Id + S2 : -1 };
		for (const int32 Nid : Nb)
		{
			if (Nid >= 0 && Solid[Nid] && !Seen[Nid]) { Seen[Nid] = 1; Stack.Add(Nid); }
		}
	}
	int32 Freed = 0;
	FVector Last = Cm;
	for (int32 Id = 0; Id < Tot; ++Id)
	{
		if (Solid[Id] && !Seen[Id])
		{
			const int32 I = Id % S, J = (Id / S) % S, K = Id / S2;
			SetSampleGlobal(Ox + I, Oy + J, Oz + K, static_cast<float>(TTune::CleanupFreedValue));
			++Freed;
			Last = FVector((Ox + I) * TTune::VoxelM, (Oy + J) * TTune::VoxelM, (Oz + K) * TTune::VoxelM);
		}
	}
	LastCleanupFreed = Freed;
	if (Freed > 0 && OnRockFreed) { OnRockFreed(Last, Freed); }
	// What is left unconnected in the same region (must be none).
	FloatingAfterCleanup = CountFloatingRock(Cm, Rad);
	return Freed;
}

int32 UDescentTerrainSubsystem::CountFloatingRock(const FVector& Cm, double Rad)
{
	const int32 R = FMath::CeilToInt((Rad + TTune::CleanupMargin) / TTune::VoxelM);
	const int32 Ox = FMath::RoundToInt(Cm.X / TTune::VoxelM) - R, Oy = FMath::RoundToInt(Cm.Y / TTune::VoxelM) - R, Oz = FMath::RoundToInt(Cm.Z / TTune::VoxelM) - R;
	const int32 S = 2 * R + 1, S2 = S * S, Tot = S * S2;
	TArray<uint8> Solid, Seen;
	Solid.SetNumZeroed(Tot);
	Seen.SetNumZeroed(Tot);
	for (int32 K = 0; K < S; ++K)
	{
		for (int32 J = 0; J < S; ++J)
		{
			for (int32 I = 0; I < S; ++I)
			{
				Solid[I + J * S + K * S2] = GetSampleGlobal(Ox + I, Oy + J, Oz + K) > 0.f ? 1 : 0;
			}
		}
	}
	TArray<int32> Stack;
	for (int32 K = 0; K < S; ++K)
	{
		for (int32 J = 0; J < S; ++J)
		{
			for (int32 I = 0; I < S; ++I)
			{
				if (!(I == 0 || J == 0 || K == 0 || I == S - 1 || J == S - 1 || K == S - 1)) { continue; }
				const int32 Id = I + J * S + K * S2;
				if (Solid[Id] && !Seen[Id]) { Seen[Id] = 1; Stack.Add(Id); }
			}
		}
	}
	while (Stack.Num() > 0)
	{
		const int32 Id = Stack.Pop(EAllowShrinking::No);
		const int32 I = Id % S, J = (Id / S) % S, K = Id / S2;
		const int32 Nb[6] = { I > 0 ? Id - 1 : -1, I < S - 1 ? Id + 1 : -1, J > 0 ? Id - S : -1, J < S - 1 ? Id + S : -1, K > 0 ? Id - S2 : -1, K < S - 1 ? Id + S2 : -1 };
		for (const int32 Nid : Nb)
		{
			if (Nid >= 0 && Solid[Nid] && !Seen[Nid]) { Seen[Nid] = 1; Stack.Add(Nid); }
		}
	}
	int32 Floating = 0;
	for (int32 Id = 0; Id < Tot; ++Id)
	{
		if (Solid[Id] && !Seen[Id]) { ++Floating; }
	}
	return Floating;
}

// ---------------------------------------------------------------------------------------------------------
// Jobs
// ---------------------------------------------------------------------------------------------------------

FTerrainJobResult UDescentTerrainSubsystem::RunJob(const FTerrainJobInput& In)
{
	FTerrainJobResult R;
	R.Key = In.Key;
	R.Version = In.Version;
	R.bWasFill = In.bFill;
	const FDescentWorldDef& Def = FDescentWorldDef::Get();
	TArray<float> LocalData;
	TArray<uint8> LocalCut;
	const float* Data = In.Data.GetData();
	const uint8* Cut = In.Cut.GetData();
	if (In.bFill)
	{
		const double T0 = FPlatformTime::Seconds();
		R.bMixed = TerrainFillData(In.Key, LocalData, LocalCut);
		R.FillMs = (FPlatformTime::Seconds() - T0) * 1000.0;
		if (!R.bMixed)
		{
			return R;   // no surface: nothing to mesh, the data is dropped
		}
		Data = LocalData.GetData();
		Cut = LocalCut.GetData();
	}
	const double T1 = FPlatformTime::Seconds();
	FSurfaceNetsInput Mi;
	Mi.Data = Data;
	Mi.Cut = Cut;
	Mi.Key = In.Key;
	Mi.Def = &Def;
	Mi.Deposits = In.Deposits;
	Mi.Exhausted = In.Exhausted;
	R.bHasSurface = FSurfaceNets::Mesh(Mi, R.Section, R.Triangles);
	R.MeshMs = (FPlatformTime::Seconds() - T1) * 1000.0;
	if (In.bFill)
	{
		R.Data = MoveTemp(LocalData);
		R.Cut = MoveTemp(LocalCut);
	}
	return R;
}

TSharedRef<FTerrainJobInput> UDescentTerrainSubsystem::MakeJobInput(FTerrainChunk& C, bool bCopyData)
{
	TSharedRef<FTerrainJobInput> In = MakeShared<FTerrainJobInput>();
	In->Key = C.Key;
	In->Version = C.Version;
	In->bFill = !bCopyData;
	RefreshDeposits(C);
	UDescentOreSubsystem* OreSys = Ore();
	for (const int32 D : C.Deposits)
	{
		In->Deposits.Add(D);
		In->Exhausted.Add(OreSys && OreSys->IsExhausted(D) ? 1 : 0);
	}
	if (bCopyData)
	{
		In->Data = C.Data;
		In->Cut = C.Cut;
	}
	return In;
}

void UDescentTerrainSubsystem::LaunchJobs()
{
	while (QueueHead < Queue.Num() && InFlight.load() < TTune::MaxJobsInFlight)
	{
		FTerrainChunk* C = FindChunk(Queue[QueueHead++].Key);
		if (!C || C->bMeshed || C->bJobInFlight) { continue; }
		if (C->State != EChunkState::Candidate && C->State != EChunkState::Mixed) { continue; }
		const bool bCopy = C->HasData();
		TSharedRef<FTerrainJobInput> In = MakeJobInput(*C, bCopy);
		C->bJobInFlight = true;
		InFlight.fetch_add(1);
		UE::Tasks::Launch(UE_SOURCE_LOCATION, [this, In]()
		{
			TUniquePtr<FTerrainJobResult> R = MakeUnique<FTerrainJobResult>(RunJob(*In));
			ResultsWaiting.fetch_add(1);
			Results.Enqueue(MoveTemp(R));
			InFlight.fetch_sub(1);
		});
	}
	if (QueueHead >= Queue.Num())
	{
		Queue.Reset();
		QueueHead = 0;
	}
}

void UDescentTerrainSubsystem::ApplyResults(double BudgetMs, bool bUnlimited)
{
	const double T0 = FPlatformTime::Seconds();
	TUniquePtr<FTerrainJobResult> R;
	while (Results.Dequeue(R))
	{
		ResultsWaiting.fetch_sub(1);
		ApplyResult(*R);
		if (!bUnlimited && (FPlatformTime::Seconds() - T0) * 1000.0 > BudgetMs) { break; }
	}
	ApplyMsLast = (FPlatformTime::Seconds() - T0) * 1000.0;
}

void UDescentTerrainSubsystem::ApplyResult(FTerrainJobResult& R)
{
	FTerrainChunk* C = FindChunk(R.Key);
	if (!C) { return; }
	C->bJobInFlight = false;
	++JobsDoneCount;
	if (R.bWasFill && R.FillMs > 0.0) { FillMsSum += R.FillMs; ++FillCount; }
	if (R.MeshMs > 0.0) { MeshMsSum += R.MeshMs; ++MeshCount; }
	if (R.Version != C->Version) { return; }   // edited while the job ran: the edit's own remesh is newer
	if (R.bWasFill)
	{
		if (!R.bMixed)
		{
			C->State = EChunkState::Empty;
			C->bMeshed = false;
			return;
		}
		C->Data = MoveTemp(R.Data);
		C->Cut = MoveTemp(R.Cut);
		C->State = EChunkState::Mixed;
	}
	SetMesh(*C, R.Section, R.Triangles, R.bHasSurface);
}

void UDescentTerrainSubsystem::SetMesh(FTerrainChunk& C, FProcMeshSection& Section, int32 Triangles, bool bHasSurface)
{
	TotalTriangles += Triangles - C.Triangles;
	C.Triangles = Triangles;
	C.bMeshed = true;
	MeshedSet.Add(C.Key);
	ADescentTerrainActor* Actor = TerrainActor.Get();
	if (!bHasSurface)
	{
		if (C.Comp && Actor) { Actor->ReleaseChunkComponent(C.Comp); }
		C.Comp = nullptr;
		return;
	}
	if (!Actor) { return; }
	if (!C.Comp) { C.Comp = Actor->AcquireChunkComponent(C.OriginM() * Descent::UUPerMetre); }
	C.Comp->SetProcMeshSection(0, Section);
}

void UDescentTerrainSubsystem::Unmesh(FTerrainChunk& C)
{
	if (C.Comp && TerrainActor.IsValid()) { TerrainActor->ReleaseChunkComponent(C.Comp); }
	C.Comp = nullptr;
	TotalTriangles -= C.Triangles;
	C.Triangles = 0;
	C.bMeshed = false;
	MeshedSet.Remove(C.Key);
	if (!C.bModified)
	{
		C.Data.Empty();
		C.Cut.Empty();
		if (C.State == EChunkState::Mixed) { C.State = EChunkState::Candidate; }
	}
}

void UDescentTerrainSubsystem::MeshChunkNow(FTerrainChunk& C)
{
	if (!C.HasData()) { return; }
	RefreshDeposits(C);
	TArray<uint8> Exhausted;
	UDescentOreSubsystem* OreSys = Ore();
	for (const int32 D : C.Deposits) { Exhausted.Add(OreSys && OreSys->IsExhausted(D) ? 1 : 0); }
	FSurfaceNetsInput Mi;
	Mi.Data = C.Data.GetData();
	Mi.Cut = C.Cut.GetData();
	Mi.Key = C.Key;
	Mi.Def = &FDescentWorldDef::Get();
	Mi.Deposits = TConstArrayView<int32>(C.Deposits.GetData(), C.Deposits.Num());
	Mi.Exhausted = Exhausted;
	FProcMeshSection Section;
	int32 Tris = 0;
	const double T0 = FPlatformTime::Seconds();
	const bool bHas = FSurfaceNets::Mesh(Mi, Section, Tris);
	MeshMsSum += (FPlatformTime::Seconds() - T0) * 1000.0;
	++MeshCount;
	SetMesh(C, Section, Tris, bHas);
	C.bDirty = false;
	C.LastRemeshFrame = FrameCounter;
}

void UDescentTerrainSubsystem::ProcessDirty(double BudgetMs)
{
	const double T0 = FPlatformTime::Seconds();
	RemeshMsLast = 0.0;
	if (DirtySet.Num() == 0) { return; }
	TArray<FDescentStreamPoint> Foci;
	if (UDescentStreamFocusSubsystem* SF = UDescentStreamFocusSubsystem::Get(GetWorld())) { SF->GetFocusPoints(Foci); }
	const double R = GetLoadRadiusM();
	TArray<FWanted> Order;
	for (const FIntVector& K : DirtySet)
	{
		FTerrainChunk* C = FindChunk(K);
		if (!C) { continue; }
		double Best = 1e30;
		bool bNear = false;
		for (const FDescentStreamPoint& F : Foci)
		{
			const double D = FVector::Dist(C->CentreM(), Descent::UUToMetres(F.LocationUU));
			Best = FMath::Min(Best, D);
			if (D < (F.RadiusM > 0.0 ? F.RadiusM : R)) { bNear = true; }
		}
		if (Foci.Num() == 0) { bNear = C->bMeshed; Best = 0.0; }
		Order.Add({ Best, K, });
		if (!(C->bMeshed || bNear)) { Order.Last().Dist = -1.0; }   // far and never meshed: drop it from the set below
	}
	Order.Sort([](const FWanted& A, const FWanted& B) { return A.Dist < B.Dist; });
	for (const FWanted& W : Order)
	{
		FTerrainChunk* C = FindChunk(W.Key);
		if (!C) { DirtySet.Remove(W.Key); continue; }
		if (W.Dist < 0.0)
		{
			// Not showing and not near anyone: it will mesh from its (modified, kept) data when it streams in.
			C->bDirty = false;
			DirtySet.Remove(W.Key);
			continue;
		}
		if (FrameCounter - C->LastRemeshFrame < TTune::RemeshMinFrames) { continue; }
		MeshChunkNow(*C);
		DirtySet.Remove(W.Key);
		if ((FPlatformTime::Seconds() - T0) * 1000.0 > BudgetMs) { break; }
	}
	RemeshMsLast = (FPlatformTime::Seconds() - T0) * 1000.0;
}

// ---------------------------------------------------------------------------------------------------------
// Streaming
// ---------------------------------------------------------------------------------------------------------

void UDescentTerrainSubsystem::PlanStream(const TArray<FDescentStreamPoint>& Foci)
{
	Queue.Reset();
	QueueHead = 0;
	TSet<FIntVector> Seen;
	const double DefaultR = GetLoadRadiusM();
	for (const FDescentStreamPoint& F : Foci)
	{
		const FVector Fm = Descent::UUToMetres(F.LocationUU);
		const double R = F.RadiusM > 0.0 ? F.RadiusM : DefaultR;
		const FIntVector Lo = KeyOfPoint(Fm - FVector(R)), Hi = KeyOfPoint(Fm + FVector(R));
		for (int32 Z = Lo.Z; Z <= Hi.Z; ++Z)
		{
			for (int32 Y = Lo.Y; Y <= Hi.Y; ++Y)
			{
				for (int32 X = Lo.X; X <= Hi.X; ++X)
				{
					const FIntVector K(X, Y, Z);
					const double Dist = FVector::Dist((FVector(K) + FVector(0.5)) * TTune::ChunkM, Fm);
					if (Dist > R) { continue; }
					FTerrainChunk* C = FindOrCreateChunk(K);
					if (C->State == EChunkState::Uniform || C->State == EChunkState::Empty || C->bMeshed || C->bJobInFlight) { continue; }
					if (Seen.Contains(K)) { continue; }
					Seen.Add(K);
					Queue.Add({ Dist, K });
				}
			}
		}
	}
	Queue.Sort([](const FWanted& A, const FWanted& B) { return A.Dist < B.Dist; });
}

void UDescentTerrainSubsystem::UnloadFar(const TArray<FDescentStreamPoint>& Foci)
{
	if (Foci.Num() == 0) { return; }
	const double Extra = TTune::UnloadExtraM;
	TArray<FIntVector> Drop;
	for (const FIntVector& K : MeshedSet)
	{
		FTerrainChunk* C = FindChunk(K);
		if (!C) { continue; }
		bool bNear = false;
		for (const FDescentStreamPoint& F : Foci)
		{
			const double R = (F.RadiusM > 0.0 ? F.RadiusM : GetLoadRadiusM()) + Extra;
			if (FVector::Dist(C->CentreM(), Descent::UUToMetres(F.LocationUU)) < R) { bNear = true; break; }
		}
		if (!bNear) { Drop.Add(K); }
	}
	for (const FIntVector& K : Drop)
	{
		if (FTerrainChunk* C = FindChunk(K)) { Unmesh(*C); }
	}
}

void UDescentTerrainSubsystem::Tick(const FDescentSimFrame& F)
{
	++FrameCounter;
	TimeSincePlan += F.Dt;
	TimeSinceUnload += F.Dt;
	ApplyMsLast = 0.0;
	if (bStreamingEnabled)
	{
		TArray<FDescentStreamPoint> Foci;
		if (UDescentStreamFocusSubsystem* SF = UDescentStreamFocusSubsystem::Get(GetWorld())) { SF->GetFocusPoints(Foci); }
		if (Foci.Num() > 0)
		{
			const FVector F0 = Descent::UUToMetres(Foci[0].LocationUU);
			if (bReplanNeeded || TimeSincePlan >= TTune::PlanIntervalSec || FVector::Dist(F0, PlanFocus0) > TTune::PlanMoveM)
			{
				PlanStream(Foci);
				PlanFocus0 = F0;
				TimeSincePlan = 0.0;
				bReplanNeeded = false;
			}
			if (TimeSinceUnload >= TTune::UnloadIntervalSec)
			{
				UnloadFar(Foci);
				TimeSinceUnload = 0.0;
			}
		}
		LaunchJobs();
	}
	ApplyResults(TTune::ApplyBudgetMs, false);
	ProcessDirty(TTune::RemeshBudgetMs);
}

bool UDescentTerrainSubsystem::IsStreamIdle() const
{
	return InFlight.load() == 0 && ResultsWaiting.load() == 0 && QueueHead >= Queue.Num() && DirtySet.Num() == 0 && !bReplanNeeded;
}

void UDescentTerrainSubsystem::FlushJobsSync()
{
	// Everything queued runs here, one after another, then is applied.
	for (; QueueHead < Queue.Num(); ++QueueHead)
	{
		FTerrainChunk* C = FindChunk(Queue[QueueHead].Key);
		if (!C || C->bMeshed || C->bJobInFlight) { continue; }
		if (C->State != EChunkState::Candidate && C->State != EChunkState::Mixed) { continue; }
		TSharedRef<FTerrainJobInput> In = MakeJobInput(*C, C->HasData());
		TUniquePtr<FTerrainJobResult> R = MakeUnique<FTerrainJobResult>(RunJob(*In));
		C->bJobInFlight = true;
		ApplyResult(*R);
	}
	Queue.Reset();
	QueueHead = 0;
	while (InFlight.load() > 0) { FPlatformProcess::Sleep(0.001f); }
	ApplyResults(0.0, true);
	ProcessDirty(1e9);
}

void UDescentTerrainSubsystem::StreamInitialBlocking(const FVector& FocusM, double RadiusM)
{
	FDescentStreamPoint P;
	P.LocationUU = Descent::MetresToUU(FocusM);
	P.RadiusM = RadiusM;
	P.Owner = TEXT("Initial");
	PlanStream({ P });
	// Pull everything planned into jobs run on all cores; results are applied here without a time budget.
	TArray<TSharedRef<FTerrainJobInput>> Inputs;
	TArray<FTerrainChunk*> Targets;
	for (const FWanted& W : Queue)
	{
		FTerrainChunk* C = FindChunk(W.Key);
		if (!C || C->bMeshed || C->bJobInFlight) { continue; }
		if (C->State != EChunkState::Candidate && C->State != EChunkState::Mixed) { continue; }
		Inputs.Add(MakeJobInput(*C, C->HasData()));
		Targets.Add(C);
		C->bJobInFlight = true;
	}
	Queue.Reset();
	QueueHead = 0;
	TArray<FTerrainJobResult> Out;
	Out.SetNum(Inputs.Num());
	ParallelFor(Inputs.Num(), [&](int32 I) { Out[I] = RunJob(*Inputs[I]); });
	for (FTerrainJobResult& R : Out)
	{
		ApplyResult(R);
	}
	bReplanNeeded = true;
}

UDescentTerrainSubsystem::FStats UDescentTerrainSubsystem::GetStats() const
{
	FStats S;
	S.ChunksKnown = Chunks.Num();
	for (const TPair<FIntVector, TSharedPtr<FTerrainChunk>>& P : Chunks)
	{
		if (P.Value->HasData()) { ++S.ChunksFilled; }
		if (P.Value->bModified) { ++S.ChunksModified; }
	}
	S.ChunksMeshed = MeshedSet.Num();
	S.Triangles = static_cast<int32>(TotalTriangles);
	S.PendingJobs = InFlight.load() + ResultsWaiting.load() + (Queue.Num() - QueueHead) + DirtySet.Num();
	S.ComponentsActive = TerrainActor.IsValid() ? TerrainActor->NumActive() : 0;
	S.ApplyMs = ApplyMsLast;
	S.RemeshMs = RemeshMsLast;
	S.FillMsAvg = FillCount > 0 ? FillMsSum / FillCount : 0.0;
	S.MeshMsAvg = MeshCount > 0 ? MeshMsSum / MeshCount : 0.0;
	S.JobsDone = JobsDoneCount;
	return S;
}

// ---------------------------------------------------------------------------------------------------------
// State section "terrain" (DESIGN_UE.md section 9.4)
// ---------------------------------------------------------------------------------------------------------

static FDescentStateProviderRegistrar GTerrainSection(TEXT("terrain"), [](UWorld* World, FJsonObject& Out)
{
	UDescentTerrainSubsystem* T = UDescentTerrainSubsystem::Get(World);
	Out.SetBoolField(TEXT("available"), T != nullptr);
	if (!T) { return; }
	const UDescentTerrainSubsystem::FStats S = T->GetStats();
	Out.SetNumberField(TEXT("chunks_known"), S.ChunksKnown);
	Out.SetNumberField(TEXT("chunks_filled"), S.ChunksFilled);
	Out.SetNumberField(TEXT("chunks_meshed"), S.ChunksMeshed);
	Out.SetNumberField(TEXT("chunks_modified"), S.ChunksModified);
	Out.SetNumberField(TEXT("triangles"), S.Triangles);
	Out.SetNumberField(TEXT("pending_jobs"), S.PendingJobs);
	Out.SetNumberField(TEXT("components_active"), S.ComponentsActive);
	Out.SetNumberField(TEXT("apply_ms"), Descent::Json::Round(S.ApplyMs));
	Out.SetNumberField(TEXT("remesh_ms"), Descent::Json::Round(S.RemeshMs));
	Out.SetNumberField(TEXT("fill_ms_avg"), Descent::Json::Round(S.FillMsAvg));
	Out.SetNumberField(TEXT("mesh_ms_avg"), Descent::Json::Round(S.MeshMsAvg));
	Out.SetNumberField(TEXT("jobs_done"), static_cast<double>(S.JobsDone));
	Out.SetNumberField(TEXT("last_density"), Descent::Json::Round(T->LastDensity));
	Out.SetNumberField(TEXT("last_removed"), T->LastRemoved);
	Out.SetNumberField(TEXT("floating_after_cleanup"), T->FloatingAfterCleanup);
	Out.SetNumberField(TEXT("last_cleanup_freed"), T->LastCleanupFreed);
	Out.SetNumberField(TEXT("load_radius_m"), T->GetLoadRadiusM());
});

void UDescentTerrainSubsystem::SetTerrainActor(ADescentTerrainActor* Actor)
{
	TerrainActor = Actor;
}

ADescentTerrainActor* UDescentTerrainSubsystem::GetTerrainActor() const
{
	return TerrainActor.Get();
}

// ---------------------------------------------------------------------------------------------------------
// Saving (DESIGN_UE.md section 6.12)
// ---------------------------------------------------------------------------------------------------------

void UDescentTerrainSubsystem::SaveModified(TArray<uint8>& OutCompressed, int32& OutRawSize)
{
	TArray<uint8> Raw;
	FMemoryWriter Ar(Raw);
	int32 Count = 0;
	for (const auto& P : Chunks) { if (P.Value->bModified && P.Value->HasData()) { ++Count; } }
	Ar << Count;
	TArray<FIntVector> Keys;
	for (const auto& P : Chunks) { if (P.Value->bModified && P.Value->HasData()) { Keys.Add(P.Key); } }
	Keys.Sort([](const FIntVector& A, const FIntVector& B) { return A.X != B.X ? A.X < B.X : (A.Y != B.Y ? A.Y < B.Y : A.Z < B.Z); });
	for (const FIntVector& K : Keys)
	{
		FTerrainChunk& C = *Chunks[K];
		FIntVector Key = K;
		Ar << Key;
		TArray<int16> Q;
		Q.SetNumUninitialized(C.Data.Num());
		for (int32 I = 0; I < C.Data.Num(); ++I) { Q[I] = static_cast<int16>(FMath::Clamp(FMath::RoundToInt(C.Data[I] / 4.f * 32767.f), -32767, 32767)); }
		Ar << Q;
		Ar << C.Cut;
	}
	OutRawSize = Raw.Num();
	int32 Size = FCompression::CompressMemoryBound(NAME_Zlib, Raw.Num());
	OutCompressed.SetNumUninitialized(Size);
	if (!FCompression::CompressMemory(NAME_Zlib, OutCompressed.GetData(), Size, Raw.GetData(), Raw.Num())) { Size = 0; }
	OutCompressed.SetNum(Size);
}

bool UDescentTerrainSubsystem::LoadModified(const TArray<uint8>& Compressed, int32 RawSize)
{
	TArray<uint8> Raw;
	Raw.SetNumUninitialized(RawSize);
	if (RawSize <= 0 || !FCompression::UncompressMemory(NAME_Zlib, Raw.GetData(), RawSize, Compressed.GetData(), Compressed.Num())) { return false; }
	FlushJobsSync();
	FMemoryReader Ar(Raw);
	int32 Count = 0;
	Ar << Count;
	TSet<FIntVector> Saved;
	for (int32 N = 0; N < Count; ++N)
	{
		FIntVector Key;
		TArray<int16> Q;
		TArray<uint8> Cut;
		Ar << Key;
		Ar << Q;
		Ar << Cut;
		FTerrainChunk* C = FindOrCreateChunk(Key);
		if (!C || Q.Num() != TTune::P3) { continue; }
		C->Data.SetNumUninitialized(TTune::P3);
		for (int32 I = 0; I < TTune::P3; ++I) { C->Data[I] = Q[I] * 4.f / 32767.f; }
		C->Cut = MoveTemp(Cut);
		C->State = EChunkState::Mixed;
		C->bModified = true;
		C->bDirty = true;
		++C->Version;
		DirtySet.Add(Key);
		Saved.Add(Key);
	}
	// carved after the save: back to the generated rock
	for (const auto& P : Chunks)
	{
		FTerrainChunk& C = *P.Value;
		if (C.bModified && !Saved.Contains(P.Key))
		{
			C.bModified = false;
			FillChunkSync(C);
			C.bDirty = true;
			DirtySet.Add(P.Key);
		}
	}
	return true;
}