A live QuadTree visualiser built in UE5 C++. Hundreds of particles move each frame; the tree is rebuilt only when a particle has moved more than a 10-unit threshold since the last insert. Per-particle neighbour queries drive debug connection lines — demonstrating O(log n) proximity lookups versus O(n²) brute force.

What I Built

• Adaptive rebuild — 10-unit threshold — tree is not rebuilt every tick; a dirty flag is set only when any particle moves >10 units, preventing unnecessary O(n log n) rebuilds on stationary frames with 0 wasted work.
• Clear + reinsert — 1 pass — UpdateQuadtree() clears the tree then reinserts all particles in 1 linear pass, keeping root bounds stable across frames.
• Range query — 1 configurable radius — QueryPoints() called per particle with 1 configurable radius; O(log n) results drive per-particle debug line drawing.
• Debug visualisation — 2 tunable parameters — node boundaries rendered as coloured boxes; neighbour lines show query results live. 2 tunable parameters: max depth and capacity per node.
• 2-path benchmark toggle — 1 runtime toggle benchmarks the QuadTree path against a naive all-pairs check; 2 frame-time readouts printed live in the overlay.

Adaptive Rebuild + Neighbour Query

Only rebuilds when a particle exceeds the movement threshold. The query result feeds the debug draw call each tick.

void AParticleSystemActor::UpdateQuadtree()
{
    Quadtree->Clear();
    for (AParticleActor* P : Particles)
        Quadtree->Insert(P->GetActorLocation(), P);

    // Cache last-known positions for dirty checking
    LastPositions.Empty();
    for (AParticleActor* P : Particles)
        LastPositions.Add(P->GetActorLocation());
}

void AParticleSystemActor::Tick(float DeltaTime)
{
    Super::Tick(DeltaTime);

    // Rebuild only when any particle moved > 10 units
    bool bDirty = false;
    for (int32 i = 0; i < Particles.Num(); ++i)
    {
        if (FVector::Dist(Particles[i]->GetActorLocation(), LastPositions[i]) > 10.f)
            { bDirty = true; break; }
    }
    if (bDirty) UpdateQuadtree();

    // Per-particle neighbour query → debug lines
    for (AParticleActor* P : Particles)
    {
        TArray<AActor*> Neighbours;
        Quadtree->QueryPoints(P->GetActorLocation(), QueryRadius, Neighbours);
        for (AActor* N : Neighbours)
            DrawDebugLine(GetWorld(), P->GetActorLocation(),
                          N->GetActorLocation(), FColor::Cyan, false, -1.f, 0, 1.f);
    }
}