// The clipping audit, implementation: counts enemies passing through geometry, in seconds on screen.
// Log-only; it never changes the game.
// Shared by BYOK Games under the MIT License
// eng17: the clipping audit. See SPNoclip.h.
#include "SPNoclip.h"
#include "SPDirector.h"
#include "SPEnemy.h"
#include "SPWurst.h"
#include "Components/SkinnedMeshComponent.h"
#include "SPTypes.h"
#include "EngineUtils.h"
#include "Engine/World.h"
#include "Engine/StaticMesh.h"
#include "Engine/OverlapResult.h"
#include "Engine/HitResult.h"
#include "Components/PrimitiveComponent.h"
#include "Components/StaticMeshComponent.h"
#include "GameFramework/PlayerController.h"
#include "Camera/PlayerCameraManager.h"
#include "Misc/CommandLine.h"
#include "Misc/Parse.h"
#include "Components/InstancedStaticMeshComponent.h"

namespace
{
	FString Describe(const UPrimitiveComponent* C)
	{
		FString M;
		if (const UStaticMeshComponent* S = Cast<UStaticMeshComponent>(C)) M = GetNameSafe(S->GetStaticMesh());
		return FString::Printf(TEXT("%s/%s/%s"), *GetNameSafe(C->GetOwner()), *C->GetName(), *M);
	}
}

// most kit meshes here have no collision (the physics overlap finds nothing on the cutting floor), so the audit also tests each
// enemy box against every world mesh's oriented box (its mesh bounds through its transform; ISMs per instance): face axes only
static bool BoxVsObb(const FVector& C1, const FVector& E1, const FTransform& X, const FBox& Lb, float& OutDepth, FVector& OutAxis)
{
	const FVector C2 = X.TransformPosition(Lb.GetCenter());
	const FVector S = X.GetScale3D().GetAbs();
	const FVector E2 = Lb.GetExtent() * S;
	const FQuat Q = X.GetRotation();
	const FVector B[3] = { Q.GetAxisX(), Q.GetAxisY(), Q.GetAxisZ() };
	const FVector A[3] = { FVector::XAxisVector, FVector::YAxisVector, FVector::ZAxisVector };
	const FVector D = C2 - C1;
	float Best = BIG_NUMBER; FVector BestAx = FVector::ZeroVector;
	for (int32 k = 0; k < 6; ++k)
	{
		const FVector L = k < 3 ? A[k] : B[k - 3];
		const float R1 = FMath::Abs(L.X) * E1.X + FMath::Abs(L.Y) * E1.Y + FMath::Abs(L.Z) * E1.Z;
		const float R2 = FMath::Abs(FVector::DotProduct(L, B[0])) * E2.X + FMath::Abs(FVector::DotProduct(L, B[1])) * E2.Y + FMath::Abs(FVector::DotProduct(L, B[2])) * E2.Z;
		const float Dd = R1 + R2 - FMath::Abs(FVector::DotProduct(L, D));
		if (Dd <= 0.f) return false;
		if (Dd < Best) { Best = Dd; BestAx = L; }
	}
	OutDepth = Best; OutAxis = BestAx;
	return true;
}

// the segment A..B crosses a mesh's oriented box (slab test in the mesh's space)
static bool SegVsObb(const FVector& A, const FVector& B, const FTransform& X, const FBox& Lb)
{
	const FVector La = X.InverseTransformPosition(A), Lc = X.InverseTransformPosition(B);
	const FVector D = Lc - La;
	float T0 = 0.f, T1 = 1.f;
	for (int32 k = 0; k < 3; ++k)
	{
		if (FMath::Abs(D[k]) < 1e-4f) { if (La[k] < Lb.Min[k] || La[k] > Lb.Max[k]) return false; continue; }
		float Ta = (Lb.Min[k] - La[k]) / D[k], Tb = (Lb.Max[k] - La[k]) / D[k];
		if (Ta > Tb) Swap(Ta, Tb);
		T0 = FMath::Max(T0, Ta); T1 = FMath::Min(T1, Tb);
		if (T0 > T1) return false;
	}
	return T1 > 0.02f && T0 < 0.98f;
}

bool USPNoclip::ShouldCreateSubsystem(UObject* Outer) const
{
	if (!Super::ShouldCreateSubsystem(Outer)) return false;
	const UWorld* Wd = Cast<UWorld>(Outer);
	return Wd && Wd->IsGameWorld() && FParse::Param(FCommandLine::Get(), TEXT("SPNoclipAudit"));
}

TStatId USPNoclip::GetStatId() const { RETURN_QUICK_DECLARE_CYCLE_STAT(USPNoclip, STATGROUP_Tickables); }

void USPNoclip::Close(FPen& P)
{
	const float Dur = P.Last - P.T0;
	if (P.bLogged || Dur <= 0.2f || P.Depth <= 8.f || P.OnScreen <= 0.f) return;
	P.bLogged = true;
	++Events;
	SPL("NOCLIP pen area=%s t0=%.2f dur=%.2f onscreen=%.2f enemy=%s uid=%d through=%s depth=%.0f", *P.Area, P.T0, Dur, P.OnScreen, *P.Enemy, P.Uid, *P.Through, P.Depth);
}

void USPNoclip::Tick(float Dt)
{
	UWorld* World = GetWorld();
	if (!Director) { for (TActorIterator<ASPDirector> It(World); It; ++It) { Director = *It; break; } if (!Director) return; }
	const float Now = Director->Now();
	if (Now < Next) return;
	const float Step = 0.1f;
	Next = Now + Step;
	APlayerController* Pc = World->GetFirstPlayerController();
	if (!Pc || !Pc->PlayerCameraManager) return;
	const FVector Cam = Pc->PlayerCameraManager->GetCameraLocation();
	const FVector Fwd = Pc->PlayerCameraManager->GetCameraRotation().Vector();
	const float HalfH = FMath::DegreesToRadians(Pc->PlayerCameraManager->GetFOVAngle() * 0.5f);
	const float HalfV = FMath::Atan(FMath::Tan(HalfH) * 9.f / 16.f);
	const FRotator CamR = Pc->PlayerCameraManager->GetCameraRotation();
	auto InView = [&](const FVector& P, float MaxDist) -> bool
	{
		const FVector To = P - Cam;
		const float D = To.Size();
		if (D > MaxDist || D < 1.f) return false;
		const FVector L = CamR.UnrotateVector(To);
		if (L.X <= 0.f) return false;
		return FMath::Abs(FMath::Atan2(L.Y, L.X)) <= HalfH && FMath::Abs(FMath::Atan2(L.Z, L.X)) <= HalfV;
	};
	FCollisionObjectQueryParams Obj;
	Obj.AddObjectTypesToQuery(ECC_WorldStatic);
	Obj.AddObjectTypesToQuery(ECC_WorldDynamic);
	FCollisionQueryParams Qp(SCENE_QUERY_STAT(SPNoclip), false);
	for (const ASPTarget* T : Director->GetTargets()) if (T) Qp.AddIgnoredActor(T);
	if (Pc->GetPawn()) Qp.AddIgnoredActor(Pc->GetPawn());
	const FString Area = Director->AreaName;
	if (Area != MeshArea || Now >= MeshNext)
	{
		MeshArea = Area; MeshNext = Now + 15.f;
		Meshes.Reset();
		for (TActorIterator<AActor> It(World); It; ++It)
		{
			if (Cast<ASPTarget>(*It) || *It == Pc->GetPawn()) continue;
			TArray<UStaticMeshComponent*> Sm;
			It->GetComponents<UStaticMeshComponent>(Sm);
			for (UStaticMeshComponent* C : Sm)
			{
				if (!C || !C->IsVisible() || !C->GetStaticMesh() || !C->IsRegistered()) continue;
				if (FVector::Dist(C->Bounds.Origin, Cam) > 6000.f + C->Bounds.SphereRadius) continue;
				const FBox Lb = C->GetStaticMesh()->GetBoundingBox();
				if (UInstancedStaticMeshComponent* I = Cast<UInstancedStaticMeshComponent>(C))
				{
					for (int32 n = 0; n < I->GetInstanceCount() && n < 4000; ++n)
					{
						FTransform Xi; if (!I->GetInstanceTransform(n, Xi, true)) continue;
						FMesh M; M.C = C; M.X = Xi; M.Lb = Lb; M.R = Lb.GetExtent().Size() * Xi.GetScale3D().GetAbsMax(); M.O = Xi.TransformPosition(Lb.GetCenter());
						Meshes.Add(M);
					}
				}
				else { FMesh M; M.C = C; M.X = C->GetComponentTransform(); M.Lb = Lb; M.R = C->Bounds.SphereRadius; M.O = C->Bounds.Origin; Meshes.Add(M); }
			}
		}
		SPL("NOCLIP meshes area=%s n=%d t=%.2f", *Area, Meshes.Num(), Now);
	}
	// a mesh that holds the camera and is thick every way is a room shell or volume, not a thing to walk through
	auto IsShell = [&](const FMesh& M) { const FVector E = M.Lb.GetExtent() * M.X.GetScale3D().GetAbs(); if (E.GetMin() < 150.f) return false; const FVector L = M.X.InverseTransformPosition(Cam) - M.Lb.GetCenter(); const FVector Le = M.Lb.GetExtent(); return FMath::Abs(L.X) < Le.X && FMath::Abs(L.Y) < Le.Y && FMath::Abs(L.Z) < Le.Z; };

	// is there collision at all here (once every 10 s): what a 3 m sphere at the camera touches
	if (Now >= WorldNext)
	{
		WorldNext = Now + 10.f;
		TArray<FOverlapResult> Ov;
		World->OverlapMultiByObjectType(Ov, Cam, FQuat::Identity, Obj, FCollisionShape::MakeSphere(300.f), Qp);
		SPL("NOCLIP world area=%s comps_within_3m=%d t=%.2f", *Area, Ov.Num(), Now);
	}

	// the camera's near plane inside a mesh
	{
		TArray<FOverlapResult> Ov;
		const FCollisionShape S = FCollisionShape::MakeSphere(12.f);
		float Best = 0.f; FString What;
		if (World->OverlapMultiByObjectType(Ov, Cam, FQuat::Identity, Obj, S, Qp))
			for (const FOverlapResult& O : Ov)
			{
				UPrimitiveComponent* C = O.GetComponent();
				if (!C || !(C->IsA<UStaticMeshComponent>() || C->IsA<USkinnedMeshComponent>()) || !C->IsVisible()) continue;   // meshes only, not trigger volumes
				FMTDResult M;
				if (C->ComputePenetration(M, S, Cam, FQuat::Identity) && M.Distance > Best) { Best = M.Distance; What = Describe(C); }
			}
		for (const FMesh& Mm : Meshes)
		{
			if (FVector::DistSquared(Mm.O, Cam) > FMath::Square(Mm.R + 12.f) || IsShell(Mm)) continue;
			if ((Mm.Lb.GetExtent() * Mm.X.GetScale3D().GetAbs()).GetMin() >= 40.f) continue;   // only thin solid things (walls, posts, doors, panels): a box round the cage or a rack is hollow
			float Dp; FVector Ax;
			if (BoxVsObb(Cam, FVector(12.f), Mm.X, Mm.Lb, Dp, Ax) && Dp > Best && Dp > 4.f && FMath::Abs(Ax.Z) < 0.7f)
			{
				Best = Dp; What = FString::Printf(TEXT("%s/%s/%s"), *GetNameSafe(Mm.C->GetOwner()), *Mm.C->GetName(), *GetNameSafe(Mm.C->GetStaticMesh()));
			}
		}
		if (Best > 2.f) { if (CamT0 < 0.f) { CamT0 = Now; CamWhat = What; } CamDepth = FMath::Max(CamDepth, Best); }
		else if (CamT0 >= 0.f)
		{
			if (Now - CamT0 > 0.15f) { ++Events; SPL("NOCLIP cam area=%s t0=%.2f dur=%.2f through=%s depth=%.0f", *Area, CamT0, Now - CamT0, *CamWhat, CamDepth); }
			CamT0 = -1.f; CamDepth = 0.f;
		}
	}

	TSet<FString> Touched;
	for (const ASPTarget* T : Director->GetTargets())
	{
		const ASPEnemy* E = Cast<ASPEnemy>(T);
		if (!E || E->bDead || E->IsHidden()) continue;
		FString Kind = E->KindName();
		if (E->Kind == ESPKind::Chunk)
		{
			// which part of a chunk's life, and how near the body's feet (a chunk joining the body is meant to sink in)
			const ASPWurst* Wb = Director->GetWurst();
			const float Hd = Wb ? FVector::Dist2D(E->GetActorLocation(), Wb->FeetPos()) : -1.f;
			Kind = FString::Printf(TEXT("chunk_s%d_%s"), (int32)E->State, Hd >= 0.f && Hd < (Wb->HomeRadius() + 300.f) ? TEXT("home") : TEXT("away"));
		}
		// a new enemy inside the view within 12 m with nothing between it and the lens
		if (!Seen.Contains(E->Uid))
		{
			Seen.Add(E->Uid);
			const FVector P = E->GetActorLocation() + FVector(0, 0, 60.f);
			// not counted: chunks blasted off the Wurst and spiders it sheds (they come off the body in view by design)
			const bool bOffBody = E->Kind == ESPKind::Chunk || (Director->GetWurst() && FVector::Dist(Director->GetWurst()->GetActorLocation(), P) < 900.f);
			if (!E->IsProjectile() && !bOffBody && InView(P, 1200.f))
			{
				FHitResult H;
				FCollisionQueryParams Lq = Qp;
				bool bBlocked = World->LineTraceSingleByChannel(H, Cam, P, ECC_Visibility, Lq);
				// the kit mostly has no collision: also any mesh box on the line counts as cover
				for (int32 m = 0; m < Meshes.Num() && !bBlocked; ++m)
				{
					const FMesh& Mm = Meshes[m];
					if (FMath::PointDistToSegment(Mm.O, Cam, P) > Mm.R) continue;
					const FVector Lc = Mm.X.InverseTransformPosition(Cam);
					if (Mm.Lb.ExpandBy(10.f).IsInside(Lc)) continue;   // the cage or room round the lens is not cover
					if (SegVsObb(Cam, P, Mm.X, Mm.Lb)) bBlocked = true;
				}
				if (!bBlocked) { ++Events; SPL("NOCLIP spawn_in_view area=%s t=%.2f enemy=%s uid=%d dist=%.1f", *Area, Now, *Kind, E->Uid, (P - Cam).Size() / 100.f); }
			}
		}
		// intended contacts
		if (E->IsClinging() || E->State == ASPEnemy::S_Ceiling || (E->Kind == ESPKind::Hanger && E->State == ASPEnemy::S_Idle)) continue;
		TArray<UPrimitiveComponent*> Comps;
		E->GetComponents<UPrimitiveComponent>(Comps);
		for (UPrimitiveComponent* C : Comps)
		{
			if (!C || !C->IsVisible() || !C->IsRegistered()) continue;
			const FBoxSphereBounds B = C->Bounds;
			if (B.SphereRadius < 3.f || B.SphereRadius > 600.f) continue;
			const FCollisionShape S = FCollisionShape::MakeBox(B.BoxExtent * 0.85f);
			const FVector E1 = B.BoxExtent * 0.85f;
			for (const FMesh& Mm : Meshes)
			{
				if (FVector::DistSquared(Mm.O, B.Origin) > FMath::Square(Mm.R + B.SphereRadius)) continue;
				float Dp; FVector Ax;
				if (!BoxVsObb(B.Origin, E1, Mm.X, Mm.Lb, Dp, Ax)) continue;
				if (FMath::Abs(Ax.Z) > 0.7f || Dp <= 8.f || IsShell(Mm)) continue;
				const FString D = FString::Printf(TEXT("%s/%s/%s"), *GetNameSafe(Mm.C->GetOwner()), *Mm.C->GetName(), *GetNameSafe(Mm.C->GetStaticMesh()));
				if (D.Contains(TEXT("Tray")) || D.Contains(TEXT("Floor")) || D.Contains(TEXT("Grate")) || D.Contains(TEXT("Sky"))) continue;
				// intended contacts: meat on meat (frank piles), a hung carcass on its rail, a spider on its wall, door or frame
				if (D.Contains(TEXT("frank")) || D.Contains(TEXT("Frank"))) continue;
				if ((E->Kind == ESPKind::Valve || E->Kind == ESPKind::Hanger) && (D.Contains(TEXT("HookRail")) || D.Contains(TEXT("Trolley")))) continue;
				if (E->Kind == ESPKind::Spider && (D.Contains(TEXT("Door")) || D.Contains(TEXT("Wall")) || D.Contains(TEXT("Frame")))) continue;
				const FString Key = FString::Printf(TEXT("%d|%s"), E->Uid, *D);
				Touched.Add(Key);
				FPen& P = Open.FindOrAdd(Key);
				if (P.T0 <= 0.f && P.Last <= 0.f) { P.T0 = Now; P.Enemy = Kind; P.Uid = E->Uid; P.Through = D; P.Area = Area; }
				P.Last = Now;
				P.Depth = FMath::Max(P.Depth, FMath::Min(Dp, B.BoxExtent.GetMin() * 2.f));
				if (InView(B.Origin, 1500.f)) P.OnScreen += Step;
			}
			TArray<FOverlapResult> Ov;
			if (!World->OverlapMultiByObjectType(Ov, B.Origin, FQuat::Identity, Obj, S, Qp)) continue;
			for (const FOverlapResult& O : Ov)
			{
				UPrimitiveComponent* W = O.GetComponent();
				if (!W) continue;
				const FString D = Describe(W);
				if (D.Contains(TEXT("Tray"))) continue;   // franks in trays
				FMTDResult M;
				if (!W->ComputePenetration(M, S, B.Origin, FQuat::Identity)) continue;
				if (FMath::Abs(M.Direction.Z) > 0.7f) continue;   // standing on the floor, or under a ceiling
				if (M.Distance <= 8.f) continue;
				const FString Key = FString::Printf(TEXT("%d|%s"), E->Uid, *D);
				Touched.Add(Key);
				FPen& P = Open.FindOrAdd(Key);
				if (P.T0 <= 0.f && P.Last <= 0.f) { P.T0 = Now; P.Enemy = Kind; P.Uid = E->Uid; P.Through = D; P.Area = Area; }
				P.Last = Now;
				P.Depth = FMath::Max(P.Depth, M.Distance);
				if (InView(B.Origin, 1500.f)) P.OnScreen += Step;
			}
		}
	}
	for (auto It = Open.CreateIterator(); It; ++It)
	{
		if (Touched.Contains(It.Key())) continue;
		Close(It.Value());
		It.RemoveCurrent();
	}
}

// ---------------------------------------------------------------- the keep-out (see SPNoclip.h)

bool USPKeepOut::ShouldCreateSubsystem(UObject* Outer) const
{
	if (!Super::ShouldCreateSubsystem(Outer)) return false;
	const UWorld* Wd = Cast<UWorld>(Outer);
	return Wd && Wd->IsGameWorld() && FParse::Param(FCommandLine::Get(), TEXT("SPKeepOut"));
}

TStatId USPKeepOut::GetStatId() const { RETURN_QUICK_DECLARE_CYCLE_STAT(USPKeepOut, STATGROUP_Tickables); }

void USPKeepOut::Gather()
{
	Meshes.Reset(); Grid.Reset();
	UWorld* World = GetWorld();
	const FVector Cart = Director->CartPos();
	for (TActorIterator<AActor> It(World); It; ++It)
	{
		if (Cast<ASPTarget>(*It)) continue;
		TArray<UStaticMeshComponent*> Sm;
		It->GetComponents<UStaticMeshComponent>(Sm);
		for (UStaticMeshComponent* C : Sm)
		{
			if (!C || !C->IsVisible() || !C->GetStaticMesh() || Cast<UInstancedStaticMeshComponent>(C)) continue;
			if (FVector::Dist(C->Bounds.Origin, Cart) > 8000.f + C->Bounds.SphereRadius) continue;
			const FString N = GetNameSafe(C->GetStaticMesh());
			if (N.Contains(TEXT("Floor")) || N.Contains(TEXT("Grate")) || N.Contains(TEXT("Ceiling")) || N.Contains(TEXT("Wall")) || N.Contains(TEXT("frank")) || N.Contains(TEXT("Frank"))) continue;
			FMesh M; M.X = C->GetComponentTransform(); M.Lb = C->GetStaticMesh()->GetBoundingBox(); M.O = C->Bounds.Origin; M.R = C->Bounds.SphereRadius;
			const FBox Wb = C->Bounds.GetBox();
			M.Top = Wb.Max.Z; M.Height = Wb.Max.Z - Wb.Min.Z;
			const FVector E = M.Lb.GetExtent() * M.X.GetScale3D().GetAbs();
			if (E.GetMin() > 400.f || M.Height < 25.f || M.R > 1500.f) continue;   // rooms, rugs and whole-floor pieces
			const int32 Ix = Meshes.Add(M);
			for (int32 x = FMath::FloorToInt((Wb.Min.X) / 400.f); x <= FMath::FloorToInt(Wb.Max.X / 400.f); ++x)
				for (int32 y = FMath::FloorToInt((Wb.Min.Y) / 400.f); y <= FMath::FloorToInt(Wb.Max.Y / 400.f); ++y) Grid.Add(FIntPoint(x, y), Ix);
		}
	}
	SPL("KEEPOUT area=%s meshes=%d t=%.2f", *Director->AreaName, Meshes.Num(), Director->Now());
}

void USPKeepOut::Tick(float Dt)
{
	UWorld* World = GetWorld();
	if (!Director) { for (TActorIterator<ASPDirector> It(World); It; ++It) { Director = *It; break; } if (!Director) return; }
	if (Director->AreaName != MeshArea) { MeshArea = Director->AreaName; Gather(); }
	const ASPWurst* W = Director->GetWurst();
	const FVector Feet = W ? W->FeetPos() : FVector(BIG_NUMBER);
	for (ASPTarget* T : Director->GetTargets())
	{
		ASPEnemy* E = Cast<ASPEnemy>(T);
		if (!E || E->bDead || E->Kind != ESPKind::Chunk || E->State != ASPEnemy::S_Crawl) continue;
		float& Secs = Pushed.FindOrAdd(E->Uid);
		if (Secs > 2.f) continue;
		FVector P = E->GetActorLocation();
		const FVector C1 = P + FVector(0, 0, 25.f), E1(28.f, 28.f, 22.f);
		TArray<int32> Near;
		Grid.MultiFind(FIntPoint(FMath::FloorToInt(P.X / 400.f), FMath::FloorToInt(P.Y / 400.f)), Near);
		bool bAny = false;
		for (int32 Ix : Near)
		{
			const FMesh& M = Meshes[Ix];
			if (FVector::DistSquared(M.O, C1) > FMath::Square(M.R + 45.f)) continue;
			if (M.Lb.ExpandBy(30.f).IsInside(M.X.InverseTransformPosition(Feet))) continue;   // where the body stands: it has to get there
			float Dp; FVector Ax;
			if (!BoxVsObb(C1, E1, M.X, M.Lb, Dp, Ax) || Dp < 4.f) continue;
			if (M.Height < 120.f && M.Top - P.Z < 130.f) P.Z = FMath::Max(P.Z, M.Top);   // low: it climbs over
			else
			{
				FVector N(Ax.X, Ax.Y, 0.f);
				if (N.SizeSquared() < 0.01f) continue;
				N.Normalize();
				if (FVector::DotProduct(N, C1 - M.X.TransformPosition(M.Lb.GetCenter())) < 0.f) N = -N;
				P += N * FMath::Min(Dp, 40.f);   // tall: it slides along the face
			}
			bAny = true;
		}
		if (bAny) { E->SetActorLocation(P); Secs += Dt; ++Pushes; }
	}
	if (Director->Now() >= LogNext) { LogNext = Director->Now() + 10.f; if (Pushes) SPL("KEEPOUT pushes=%d t=%.2f", Pushes, Director->Now()); Pushes = 0; }
}

// ---------------------------------------------------------------- the chunks' hop lines (see SPNoclip.h)

namespace
{
	struct FHopMesh { FTransform X; FBox Lb; FVector O; float R = 0.f; float Top = 0.f; };
	TArray<FHopMesh> GHop;
	TMultiMap<FIntPoint, int32> GHopGrid;
	TWeakObjectPtr<UWorld> GHopWorld;
	FString GHopArea;
	FIntPoint HopCell(const FVector& P) { return FIntPoint(FMath::FloorToInt(P.X / 400.f), FMath::FloorToInt(P.Y / 400.f)); }

	void HopGather(UWorld* World, const FString& Area, const FVector& Near)
	{
		GHop.Reset(); GHopGrid.Reset(); GHopWorld = World; GHopArea = Area;
		for (TActorIterator<AActor> It(World); It; ++It)
		{
			if (Cast<ASPTarget>(*It)) continue;
			TArray<UStaticMeshComponent*> Sm;
			It->GetComponents<UStaticMeshComponent>(Sm);
			for (UStaticMeshComponent* C : Sm)
			{
				if (!C || !C->IsVisible() || !C->GetStaticMesh() || Cast<UInstancedStaticMeshComponent>(C)) continue;
				if (FVector::Dist2D(C->Bounds.Origin, Near) > 7000.f + C->Bounds.SphereRadius) continue;
				const FString N = GetNameSafe(C->GetStaticMesh());
				if (N.Contains(TEXT("Floor")) || N.Contains(TEXT("Grate")) || N.Contains(TEXT("Ceiling")) || N.Contains(TEXT("Sky")) || N.Contains(TEXT("frank")) || N.Contains(TEXT("Frank"))) continue;
				FHopMesh M; M.X = C->GetComponentTransform(); M.Lb = C->GetStaticMesh()->GetBoundingBox(); M.O = C->Bounds.Origin; M.R = C->Bounds.SphereRadius;
				const FBox Wb = C->Bounds.GetBox();
				M.Top = Wb.Max.Z;
				const FVector E = M.Lb.GetExtent() * M.X.GetScale3D().GetAbs();
				if (E.GetMin() > 400.f || Wb.Max.Z - Wb.Min.Z < 20.f || M.R > 2500.f) continue;
				const int32 Ix = GHop.Add(M);
				for (int32 x = FMath::FloorToInt(Wb.Min.X / 400.f); x <= FMath::FloorToInt(Wb.Max.X / 400.f); ++x)
					for (int32 y = FMath::FloorToInt(Wb.Min.Y / 400.f); y <= FMath::FloorToInt(Wb.Max.Y / 400.f); ++y) GHopGrid.Add(FIntPoint(x, y), Ix);
			}
		}
		SPL("CHUNKLEAP boxes area=%s n=%d", *Area, GHop.Num());
	}
}

bool SPHopLine(UWorld* World, const FString& Area, const FVector& A, const FVector& B, float FloorZ, const FVector& Goal, float& OutTop, bool& bOutWall)
{
	OutTop = FloorZ; bOutWall = false;
	if (!World) return false;
	if (GHopWorld.Get() != World || GHopArea != Area) HopGather(World, Area, A);
	const FVector A1(A.X, A.Y, FloorZ + 35.f), B1(B.X, B.Y, FloorZ + 35.f);
	TSet<int32> Done;
	const int32 Steps = FMath::Max(1, FMath::CeilToInt(FVector::Dist2D(A1, B1) / 200.f));
	for (int32 s = 0; s <= Steps; ++s)
	{
		TArray<int32> Ix;
		GHopGrid.MultiFind(HopCell(FMath::Lerp(A1, B1, s / (float)Steps)), Ix);
		for (int32 i : Ix)
		{
			if (Done.Contains(i)) continue;
			Done.Add(i);
			const FHopMesh& M = GHop[i];
			if (FMath::PointDistToSegment(M.O, A1, B1) > M.R + 40.f) continue;
			// a fat line (40 cm either side): the chunk is not a point
			const FVector Side = FVector::CrossProduct((B1 - A1).GetSafeNormal2D(), FVector::UpVector) * 40.f;
			if (!SegVsObb(A1, B1, M.X, M.Lb) && !SegVsObb(A1 + Side, B1 + Side, M.X, M.Lb) && !SegVsObb(A1 - Side, B1 - Side, M.X, M.Lb)) continue;
			OutTop = FMath::Max(OutTop, M.Top);
			if (M.Top - FloorZ > 280.f && !M.Lb.ExpandBy(40.f).IsInside(M.X.InverseTransformPosition(Goal))) bOutWall = true;
		}
	}
	return true;
}

bool SPHopFreeSpot(UWorld* World, const FString& Area, const FVector& P, float FloorZ, FVector& Out)
{
	Out = P;
	if (!World) return false;
	if (GHopWorld.Get() != World || GHopArea != Area) HopGather(World, Area, P);
	auto Blocked = [&](const FVector& Q) -> bool
	{
		const FVector C(Q.X, Q.Y, FloorZ + 35.f);
		TArray<int32> Ix;
		GHopGrid.MultiFind(HopCell(C), Ix);
		for (int32 i : Ix)
		{
			const FHopMesh& M = GHop[i];
			if (FVector::DistSquared(M.O, C) > FMath::Square(M.R + 60.f)) continue;
			float Dp; FVector Ax;
			if (BoxVsObb(C, FVector(50.f, 50.f, 30.f), M.X, M.Lb, Dp, Ax) && FMath::Abs(Ax.Z) < 0.7f) return true;
		}
		return false;
	};
	if (!Blocked(P)) return false;
	for (float R = 100.f; R <= 600.f; R += 100.f)
		for (int32 k = 0; k < 8; ++k)
		{
			const FVector Q = P + FVector(FMath::Cos(k * PI / 4.f), FMath::Sin(k * PI / 4.f), 0.f) * R;
			if (!Blocked(Q)) { Out = FVector(Q.X, Q.Y, P.Z); return true; }
		}
	return false;
}

float SPHopTopAt(UWorld* World, const FString& Area, const FVector& P, float FloorZ)
{
	if (!World) return P.Z;
	if (GHopWorld.Get() != World || GHopArea != Area) HopGather(World, Area, P);
	float Top = P.Z;
	TArray<int32> Ix;
	GHopGrid.MultiFind(HopCell(P), Ix);
	for (int32 i : Ix)
	{
		const FHopMesh& M = GHop[i];
		if (FVector::DistSquared(M.O, P) > FMath::Square(M.R + 60.f) || M.Top - FloorZ > 400.f) continue;   // not out of a column or a wall
		float Dp; FVector Ax;
		if (BoxVsObb(P, FVector(40.f), M.X, M.Lb, Dp, Ax)) Top = FMath::Max(Top, M.Top + 30.f);
	}
	return Top;
}

