Collision.cpp

#include "Collision.h"
#include "Modules/DebugPrimitives/DebugPrimitives.h"
#include "Modules/Environment/Environment.h"
#include "Modules/Health/Health.h"
#include "Modules/Movement/Movement.h"
#include "Modules/Primitives/PrimitivesTypes.h"
#include "Modules/Transform/Transform.h"

namespace SE {

struct FColliderCircle {
    fvec2 Position;
    float Radius;
};
struct FColliderRect {
    TStaticArray<fvec2, 4> Polygon;
};
using FCollider = TVariant<FColliderCircle, FColliderRect>;


struct FSpatialHashCollider {
    FCollider Collider;
    entity_id EntityId;

//    inline bool operator==(const FSpatialHashCollider &Other) const {
//        return EntityId == Other.EntityId;
//    }
//    inline bool operator!=(const FSpatialHashCollider &Other) const {
//        return !operator==(Other);
//    }
    
    inline operator uint64() const {
        return EntityId;
    }
};

struct FSpatialHashColliderDynamic {
    FCollider Collider;
    fvec2 Velocity;
    entity_id EntityId;

//    inline bool operator==(const FSpatialHashColliderDynamic &Other) const {
//        return EntityId == Other.EntityId;
//    }
//    inline bool operator!=(const FSpatialHashColliderDynamic &Other) const {
//        return !operator==(Other);
//    }
    
    inline operator uint64() const {
        return EntityId;
    }
};

struct FSpatialHashCell {
    THeapArray<FSpatialHashCollider> StaticCollision;
    THeapArray<FSpatialHashColliderDynamic> DynamicCollision;
    THeapArray<FSpatialHashCollider> TriggerCollision;
    fvec2 CellPosition;
};

struct FSpatialHashQueryResult {
    TFrameArray<const FSpatialHashCollider *> StaticCollision;
    TFrameArray<const FSpatialHashColliderDynamic *> DynamicCollision;
    TFrameArray<const FSpatialHashCollider *> TriggerCollision;
};
struct FSpatialHashQueryFilter {
    bool AllowStaticCollision = true;
    bool AllowDynamicCollision = true;
    bool AllowTriggerCollision = true;
    TFrameArray<entity_id> RequiredComponents;
};

//

struct CDisplacement {
    fvec2 Displacement = {0.0f, 0.0f};
};

enum class EColliderCacheCollisionCategory {
    None,
    Static,
    Dynamic,
    Trigger
};

struct Reflection(NoSerialize, NoCopy) CColliderCache {
    THeapArray<ivec2> Cells;
    EColliderCacheCollisionCategory CollisionCategory = EColliderCacheCollisionCategory::None;
};

// Compound collision is just multiple children with CCircleCollision and CCollisionRedirector to their parent

// Use circle at CWorldTransform's position as collider.
struct CColliderCircle {
    float Radius = 50.0f;
};

struct CColliderRect {
    fvec2 Size = {100.0f, 100.0f};
};

struct CColliderRectFromSize {
};

struct CStaticCollision {
};

struct CDynamicCollision {
    float Mass = 0.0f;
};

struct CRVOAvoidance {
    fvec2 DesiredVelocity = {0.0f, 0.0f};
};

namespace {

struct FORCAObstaclePoint {
    fvec2 Position;
    fvec2 Direction;
    bool Convex;
};

struct FCollisionStorage {
    THashSet<uint64, THasherBypass> ProcessedEntities;
    THashSet<FSpatialHashCollider, THasherBypass, uint64> PotentialStaticCollisions;
    THashSet<FSpatialHashColliderDynamic, THasherBypass, uint64> PotentialDynamicCollisions;
    THeapArray<FORCALine> ORCALines;
    byte Padding0[Meta::MaxCacheLineSize];
};
byte Padding0[Meta::MaxCacheLineSize];
TStaticArray<FCollisionStorage, SE::Impl::MaxThreads> AllCollisionStorages;

constexpr int32 CellSize = 60;
constexpr float CellSizeFloat = (float)CellSize;
constexpr float DebugVisualizationRange = 400.0f;
// Careful with changing this, too high or too low makes behavior strange.
constexpr float RVOTimeHorizon = 10.0f;
constexpr float RVOTimeHorizonInverted = 1.0f / RVOTimeHorizon;
// Careful with changing this, too high or too low makes behavior strange.
constexpr float RVOTimeHorizonObstacle = 10.0f;
constexpr float RVOTimeHorizonObstacleInverted = 1.0f / RVOTimeHorizonObstacle;
// This is not a part of the algorithm, but it makes dead-end scenarios like circles resolve much-much faster.
constexpr float RVORadiusCoef = 1.1f;
constexpr float RVOAvoidanceRadiusMultiplier = 15.0f;
constexpr float RVOAvoidanceObstacleRadiusMultiplier = 1.5f;
constexpr float RVOEpsilon = 0.0001f;
constexpr float DisplacementPower = 0.7f;
constexpr float DisplacementConst = 5.0f;
const float DisplacementConstReversePowered = Math::Pow(DisplacementConst, 1.0f / DisplacementPower);

THeapArray<ivec2> CellsRemain;
THeapArray<ivec2> CellsAdded;
THeapArray<ivec2> CellsRemoved;

// 50% load factor for better performance.
THashMap<uint64, FSpatialHashCell, THasherBypass, uint64, 5u> SpatialHash;

struct FSpatialProjectionResult {
    ivec2 Start;
    ivec2 End;
};

void GenerateObstacleORCALines(THeapArray<FORCALine> &ORCALines, fvec2 Position, float Radius, fvec2 Velocity, TArrayView<fvec2> Polygon);
void GenerateObstacleORCALine(THeapArray<FORCALine> &ORCALines, fvec2 Position, float Radius, fvec2 Velocity, TArrayView<FORCAObstaclePoint> Points);
void GenerateEntityORCALine(
    THeapArray<FORCALine> &ORCALines, fvec2 Delta, float Radius, fvec2 Velocity, const FSpatialHashColliderDynamic &ColliderDynamic);
uint64 AssembleKey(ivec2 Cell);
uint64 AssembleKey(fvec2 Position);
FSpatialProjectionResult Project(const FCollider &Collider);
void ProcessCollider(
    entity Entity, const FCollider &Collider, const CStaticCollision *StaticCollision, const CDynamicCollision *DynamicCollision,
    const CWorldTransform &WorldTransform, const CWorldTransformPreviousPosition &WorldTransformPreviousPosition,
    const CMovementVelocity *MovementVelocity, CColliderCache &ColliderCache, const CDebugRenderSettings &DebugRenderSettings,
    const CCamera2 &Camera);
bool DoCollide(const FCollider &ColliderA, const FCollider &ColliderB);

}  // namespace

MCollisionComponents::MCollisionComponents(ecs &ECS) {
    Register<CDisplacement>(ECS);
    Register<CStaticCollision>(ECS);
    Register<CDynamicCollision>(ECS);
    RegisterWith<CDynamicCollision, CDisplacement>(ECS);
    Register<CColliderCache>(ECS);
    Register<CColliderCircle>(ECS);
    RegisterWith<CColliderCircle, CColliderCache>(ECS);
    RegisterWith<CColliderCircle, CWorldTransformPreviousPosition>(ECS);
    Register<CColliderRect>(ECS);
    RegisterWith<CColliderRect, CColliderCache>(ECS);
    RegisterWith<CColliderRect, CWorldTransformPreviousPosition>(ECS);
    Register<CColliderRectFromSize>(ECS);
    RegisterWith<CColliderRectFromSize, CColliderRect>(ECS);
    Register<CRVOAvoidance>(ECS);
    SpatialHash = {};
}

MCollisionColliderSystemsMT::MCollisionColliderSystemsMT(ecs &ECS) {
    MultiThreadedSystem<
        const CColliderRectFromSize, CColliderRect, const CWorldTransform, const CUINode *, const CTextSize *, const CShapeSize *,
        const CScaleBySpriteFrameSize *, const CSpriteFrameSize *, const CScaleByTextureSize *, const CTextureSize *, const CScaleByCustomSize *,
        const CCustomSize *>(
        ECS, "Collision|Collider",
        [](entity Entity, CColliderRect &ColliderRect, const CWorldTransform &WorldTransform, const CUINode *Node, const CTextSize *TextSize,
           const CShapeSize *ShapeSize, const CScaleBySpriteFrameSize *ScaleBySpriteFrameSize, const CSpriteFrameSize *SpriteFrameSize,
           const CScaleByTextureSize *ScaleByTextureSize, const CTextureSize *TextureSize, const CScaleByCustomSize *ScaleByCustomSize,
           const CCustomSize *CustomSize) {
            var ScaleAndSize = Transform::ResolveScaleAndSize(
                &WorldTransform, Node, TextSize, ShapeSize, ScaleBySpriteFrameSize, SpriteFrameSize, ScaleByTextureSize, TextureSize,
                ScaleByCustomSize, CustomSize);
            ColliderRect.Size = ScaleAndSize.Size;
        });
}

void MCollisionGatherSystemsST(ecs &ECS) {
    QueryIteration<
        const CColliderCircle, const CStaticCollision *, const CDynamicCollision *, const CWorldTransform, const CWorldTransformPreviousPosition,
        const CMovementVelocity *, CColliderCache, const CDebugRenderSettings &, const CCamera2 &>(
        ECS, "Collision|Gather",
        [](entity Entity, const CColliderCircle &CircleCollision, const CStaticCollision *StaticCollision, const CDynamicCollision *DynamicCollision,
           const CWorldTransform &WorldTransform, const CWorldTransformPreviousPosition &WorldTransformPreviousPosition,
           const CMovementVelocity *MovementVelocity, CColliderCache &ColliderCache, const CDebugRenderSettings &DebugRenderSettings,
           const CCamera2 &Camera) {
            FColliderCircle Circle = {WorldTransform.Position, CircleCollision.Radius};
            ProcessCollider(
                Entity, Circle, StaticCollision, DynamicCollision, WorldTransform, WorldTransformPreviousPosition, MovementVelocity, ColliderCache,
                DebugRenderSettings, Camera);
        });
    QueryIteration<
        const CColliderRect, const CStaticCollision *, const CDynamicCollision *, const CWorldTransform, const CWorldTransformPreviousPosition,
        const CMovementVelocity *, CColliderCache, const CDebugRenderSettings &, const CCamera2 &>(
        ECS, "Collision|Gather",
        [](entity Entity, const CColliderRect &ColliderRect, const CStaticCollision *StaticCollision, const CDynamicCollision *DynamicCollision,
           const CWorldTransform &WorldTransform, const CWorldTransformPreviousPosition &WorldTransformPreviousPosition,
           const CMovementVelocity *MovementVelocity, CColliderCache &ColliderCache, const CDebugRenderSettings &DebugRenderSettings,
           const CCamera2 &Camera) {
            FColliderRect Rect;
            var HalfSize = ColliderRect.Size * 0.5f;
            Rect.Polygon[0] = WorldTransform.Position + Math::Rotate(fvec2{-HalfSize.X, +HalfSize.Y}, WorldTransform.SinCos);
            Rect.Polygon[1] = WorldTransform.Position + Math::Rotate(fvec2{+HalfSize.X, +HalfSize.Y}, WorldTransform.SinCos);
            Rect.Polygon[2] = WorldTransform.Position + Math::Rotate(fvec2{+HalfSize.X, -HalfSize.Y}, WorldTransform.SinCos);
            Rect.Polygon[3] = WorldTransform.Position + Math::Rotate(fvec2{-HalfSize.X, -HalfSize.Y}, WorldTransform.SinCos);
            ProcessCollider(
                Entity, Rect, StaticCollision, DynamicCollision, WorldTransform, WorldTransformPreviousPosition, MovementVelocity, ColliderCache,
                DebugRenderSettings, Camera);
        });
    Profiled("Collision|Debug", [&]() {
        ref DebugRenderSettings = Ref<CDebugRenderSettings>(ECS);
        if(DebugRenderSettings.DebugRender) {
            ref Camera2 = Ref<const CCamera2>(ECS);

            var Projection = Project(FColliderCircle{Camera2.Position, DebugVisualizationRange});
            for(var X = Projection.Start.X; X <= Projection.End.X; ++X) {
                for(var Y = Projection.Start.Y; Y <= Projection.End.Y; ++Y) {
                    var Key = AssembleKey(ivec2{X, Y});
                    var StaticCount = 0u;
                    var DynamicCount = 0u;
                    var NoCount = 0u;
                    if(var Existing = SpatialHash.Find(Key)) {
                        StaticCount = Existing->StaticCollision.GetSize();
                        DynamicCount = Existing->DynamicCollision.GetSize();
                        NoCount = Existing->TriggerCollision.GetSize();
                    }
                    var RedStrength = Math::Sqrt(0.5f - 1.0f / (float)(DynamicCount + 2u));
                    var GreenStrength = Math::Sqrt(0.5f - 1.0f / (float)(StaticCount + 2u));
                    var BlueStrength = Math::Sqrt(0.5f - 1.0f / (float)(NoCount + 2u));
                    var Color = fcolor4{
                        RedStrength, GreenStrength, BlueStrength,
                        Math::Sqrt(RedStrength * 0.33f + GreenStrength * 0.33f + BlueStrength * 0.33f) * 1.0f};
                    if(!Math::IsAlmostZero(Color.A)) {
                        Debug::DebugFilledRect(
                            ECS, fvec2{((float)X + 0.5f) * CellSizeFloat, ((float)Y + 0.5f) * CellSizeFloat}, 0.0f,
                            fvec2{CellSizeFloat, CellSizeFloat} * 0.95f, Color, 0.0f, false);
                    }
                }
            }
        }
    });
}

void MCollisionDestructSystemsST(ecs &ECS) {
    QueryIteration<const CStaticCollision *, const CDynamicCollision *, CColliderCache, const CBeingDestructed>(
        ECS, "Collision|Gather",
        [](entity Entity, const CStaticCollision *StaticCollision, const CDynamicCollision *DynamicCollision, CColliderCache &ColliderCache) {
            var EntityId = Entity.id();
            for(var Cell: ColliderCache.Cells) {
                var Key = AssembleKey(Cell);
                var Bucket = SpatialHash.ComputeBucket(Key);
                FSpatialHashCell *SpatialHashCell = &SpatialHash.Get(Key, Bucket);
                if(StaticCollision) {
                    Array::RemoveSwap(SpatialHashCell->StaticCollision, [EntityId](const FSpatialHashCollider &Collider) {
                        return Collider.EntityId == EntityId;
                    });
                } else if(DynamicCollision) {
                    Array::RemoveSwap(SpatialHashCell->DynamicCollision, [EntityId](const FSpatialHashColliderDynamic &Collider) {
                        return Collider.EntityId == EntityId;
                    });
                } else {
                    Array::RemoveSwap(SpatialHashCell->TriggerCollision, [EntityId](const FSpatialHashCollider &Collider) {
                        return Collider.EntityId == EntityId;
                    });
                }
            }
        });
}

MCollisionDisplacementResolveSystemsMT::MCollisionDisplacementResolveSystemsMT(ecs &ECS) {
    SkipDuringPause([&]() {
        MultiThreadedSystem<CLocalTransform, CWorldTransform, CMovementVelocity *, CDisplacement>(
            ECS, "Collision|DisplacementResolve",
            [](entity Entity, CLocalTransform &LocalTransform, CWorldTransform &WorldTransform, CMovementVelocity *MovementVelocity,
               CDisplacement &Displacement) {
                //            var SlowDownFactor = Math::Min(Math::Length(Displacement.Displacement) / Math::Length(MovementVelocity.Velocity), 1.0f);
                //            MovementVelocity.Velocity *= 1.0f - SlowDownFactor;
                if(MovementVelocity) {
                    MovementVelocity->Velocity += Displacement.Displacement * 0.25f;
                }
                //            Debugf("Displacing %s by %.3f %.3f", *EntityName(Entity), Displacement.Displacement.X, Displacement.Displacement.Y);
                WorldTransform.Position += Displacement.Displacement * 0.5f;
                Check(!Math::IsNan(WorldTransform.Position));
                LocalTransform.SetOverridenByWorldTransform();
                Displacement.Displacement = {0.0f, 0.0f};
            });
    });
}

MCollisionUpdateSystemsMT::MCollisionUpdateSystemsMT(ecs &ECS) {
    SkipDuringPause([&]() {
        MultiThreadedSystem<
            const CColliderCircle, const CDynamicCollision, const CWorldTransform, CDisplacement, CMovementVelocity *, const CMovementMaximumSpeed *,
            CMovementPreferredVelocity *, const CAIMovementToEntity *, CRVOAvoidance *, const CDebugRenderSettings &>(
            ECS, "Collision|Update&Debug",
            [](entity Entity, const CColliderCircle &ColliderCircle, const CWorldTransform &WorldTransform, CDisplacement &Displacement,
               CMovementVelocity *Velocity, const CMovementMaximumSpeed *MaximumSpeed, CMovementPreferredVelocity *PreferredVelocity,
               const CAIMovementToEntity *AIMovementToEntity, CRVOAvoidance *RVOAvoidance, const CDebugRenderSettings &DebugRenderSettings) {
                var EntityId = Entity.id();
                //            Debugf("%s", *EntityName(Entity));
                var ECS = Entity.world();
                ref Storage = AllCollisionStorages[Impl::ThisThreadIndex];
                Storage.PotentialStaticCollisions.Clear();
                Storage.PotentialDynamicCollisions.Clear();
                Displacement.Displacement = {0.0f, 0.0f};
                var ProjectionRadius = ColliderCircle.Radius;
                if(RVOAvoidance) {
                    ProjectionRadius = Math::Max(ProjectionRadius, ColliderCircle.Radius * RVOAvoidanceRadiusMultiplier);
                }
                var Projection = Project(FColliderCircle{WorldTransform.Position, ProjectionRadius});
                for(var X = Projection.Start.X; X <= Projection.End.X; ++X) {
                    for(var Y = Projection.Start.Y; Y <= Projection.End.Y; ++Y) {
                        var Key = AssembleKey(ivec2{X, Y});
                        if(var Existing = SpatialHash.Find(Key)) {
                            for(ref ColliderStatic: Existing->StaticCollision) {
                                if(ColliderStatic.EntityId != EntityId) {
                                    Storage.PotentialStaticCollisions.TryAdd(ColliderStatic);
                                }
                            }
                        }
                        if(var Existing = SpatialHash.Find(Key)) {
                            for(ref ColliderDynamic: Existing->DynamicCollision) {
                                if(ColliderDynamic.EntityId != EntityId) {
                                    Storage.PotentialDynamicCollisions.TryAdd(ColliderDynamic);
                                }
                            }
                        }
                    }
                }

                if(RVOAvoidance) {
                    Storage.ORCALines.Clear();
                }

                for(ref PotentialStaticCollision: Storage.PotentialStaticCollisions) {
                    FColliderCircle Collider = PotentialStaticCollision.Collider;
                    var ColliderPosition = Collider.Position;
                    var Delta = WorldTransform.Position - ColliderPosition;
                    var Distance = Math::Length(Delta);
                    var DisplacementAmount = (ColliderCircle.Radius + Collider.Radius) - Distance;
                    var Collision = DisplacementAmount > 0.0f;
                    if(Collision) {
                        var Direction = Math::SafeDivision(Delta, Distance, fvec2{1.0f, 0.0f});
                        Displacement.Displacement +=
                            Direction * (Math::Pow(DisplacementAmount + DisplacementConstReversePowered, DisplacementPower) - DisplacementConst);
                        //                    Displacement.Displacement += Direction * DisplacementAmount;
                    }

                    if(RVOAvoidance) {
                        var Radius = Collider.Radius * RVOAvoidanceObstacleRadiusMultiplier;
                        var Polygon = Geom::CreateCircle<FFrameAllocator>(ColliderPosition, Radius, 15.0f);
                        GenerateObstacleORCALines(
                            Storage.ORCALines, WorldTransform.Position, ColliderCircle.Radius, Velocity->Velocity, View(Polygon));
                    }
                }
                var ObstacleCount = Storage.ORCALines.GetSize();
                for(ref PotentialDynamicCollision: Storage.PotentialDynamicCollisions) {
                    //                var PotentialDynamicCollisionEntity = ECS.entity(PotentialDynamicCollision.EntityId);
                    FColliderCircle Collider = PotentialDynamicCollision.Collider;
                    var ColliderPosition = Collider.Position;
                    var Delta = WorldTransform.Position - ColliderPosition;
                    var Distance = Math::Length(Delta);
                    var DisplacementAmount = (ColliderCircle.Radius + Collider.Radius) - Distance;
                    var Collision = DisplacementAmount > 0.0f;
                    if(Collision) {
                        var Direction = Math::SafeDivision(Delta, Distance, fvec2{1.0f, 0.0f});
                        Displacement.Displacement +=
                            Direction * (Math::Pow(DisplacementAmount + DisplacementConstReversePowered, DisplacementPower) - DisplacementConst);
                        Check(!Math::IsNan(Displacement.Displacement));
                    }

                    if(RVOAvoidance) {
                        if(!(AIMovementToEntity && AIMovementToEntity->Target.entity().id() == PotentialDynamicCollision.EntityId)) {
                            var CollisionEntity = ECS.entity(PotentialDynamicCollision.EntityId);
                            //                        GenerateEntityORCALine(Delta, ColliderCircle.Radius, Velocity->Velocity, PotentialDynamicCollision);
                            // Only expect from living entities to move.
                            if(CollisionEntity && Alive(CollisionEntity) && Has<CRVOAvoidance>(CollisionEntity)) {
                                GenerateEntityORCALine(
                                    Storage.ORCALines, Delta, ColliderCircle.Radius, Velocity->Velocity, PotentialDynamicCollision);
                            } else {
                                // Interpret non-rvo agents as static obstacles.
                                var Radius = Collider.Radius * RVOAvoidanceObstacleRadiusMultiplier;
                                var Polygon = Geom::CreateCircle<FFrameAllocator>(ColliderPosition, Radius, 15.0f);
                                GenerateObstacleORCALines(
                                    Storage.ORCALines, WorldTransform.Position, ColliderCircle.Radius, Velocity->Velocity, View(Polygon));
                            }
                        }
                    }
                }

                if(RVOAvoidance) {
                    fvec2 NewVelocity;
                    var LineFail =
                        RVO::LinearProgram2(View(Storage.ORCALines), MaximumSpeed->Speed, PreferredVelocity->PreferredVelocity, false, NewVelocity);

                    Check(!Math::IsNan(NewVelocity));
                    if(LineFail < Storage.ORCALines.GetSize()) {
                        RVO::LinearProgram3(View(Storage.ORCALines), ObstacleCount, LineFail, MaximumSpeed->Speed, NewVelocity);
                    }
                    RVOAvoidance->DesiredVelocity = NewVelocity;
                    Check(!Math::IsNan(NewVelocity));
                }
            });
    });
}

namespace Collision {

// Gather is single-threaded, so we don't need locks.
FSpatialHashQueryResult Query(ecs &ECS, const FCollider &InCollider, const FSpatialHashQueryFilter &Filter) {
    ref Storage = AllCollisionStorages[Impl::ThisThreadIndex];
    Storage.ProcessedEntities.Clear();
    FSpatialHashQueryResult Result;
    var Projection = Project(InCollider);

    var ConsiderCollider = [&](const FSpatialHashCollider &Collider) {
        var Bucket = Storage.ProcessedEntities.ComputeBucket(Collider.EntityId);
        if(Storage.ProcessedEntities.Contains(Collider.EntityId, Bucket)) {
            return false;
        }
        Storage.ProcessedEntities.Add(Collider.EntityId, Bucket);
        var Entity = ECS.entity(Collider.EntityId);
        if(!Entity) {
            return false;
        }
        for(var Component: Filter.RequiredComponents) {
            if(!Entity.has(Component)) {
                return false;
            }
        }
        if(!DoCollide(InCollider, Collider.Collider)) {
            return false;
        }
        return true;
    };
    var ConsiderColliderDynamic = [&](const FSpatialHashColliderDynamic &Collider) {
        var Bucket = Storage.ProcessedEntities.ComputeBucket(Collider.EntityId);
        if(Storage.ProcessedEntities.Contains(Collider.EntityId, Bucket)) {
            return false;
        }
        Storage.ProcessedEntities.Add(Collider.EntityId, Bucket);
        var Entity = ECS.entity(Collider.EntityId);
        if(!Entity) {
            return false;
        }
        for(var Component: Filter.RequiredComponents) {
            if(!Entity.has(Component)) {
                return false;
            }
        }
        if(!DoCollide(InCollider, Collider.Collider)) {
            return false;
        }
        return true;
    };

    for(var X = Projection.Start.X; X <= Projection.End.X; ++X) {
        for(var Y = Projection.Start.Y; Y <= Projection.End.Y; ++Y) {
            var Key = AssembleKey(ivec2{X, Y});

            if(var Existing = SpatialHash.Find(Key)) {
                if(Filter.AllowStaticCollision) {
                    for(ref StaticCollision: Existing->StaticCollision) {
                        if(ConsiderCollider(StaticCollision)) {
                            Result.StaticCollision.Add(&StaticCollision);
                        }
                    }
                }
                if(Filter.AllowDynamicCollision) {
                    for(ref DynamicCollision: Existing->DynamicCollision) {
                        if(ConsiderColliderDynamic(DynamicCollision)) {
                            Result.DynamicCollision.Add(&DynamicCollision);
                        }
                    }
                }
                if(Filter.AllowTriggerCollision) {
                    for(ref TriggerCollision: Existing->TriggerCollision) {
                        if(ConsiderCollider(TriggerCollision)) {
                            Result.TriggerCollision.Add(&TriggerCollision);
                        }
                    }
                }
            }
        }
    }
    return Result;
}

}  // namespace Collision

namespace {

bool DoCollide(const FCollider &ColliderA, const FCollider &ColliderB) {
    if(const FColliderCircle *CircleA = ColliderA) {
        if(const FColliderCircle *CircleB = ColliderB) {
            return Math::DistanceSquared(CircleA->Position, CircleB->Position) <= Math::Square(CircleA->Radius + CircleB->Radius);
        }
        if(const FColliderRect *RectB = ColliderB) {
            for(var Index = 0u; Index < 3u; ++Index) {
                if(Math::OverlapsSegmentToCircle(RectB->Polygon[Index + 0u], RectB->Polygon[Index + 1u], CircleA->Position, CircleA->Radius)) {
                    return true;
                }
            }
            if(Math::OverlapsSegmentToCircle(RectB->Polygon[3u], RectB->Polygon[0u], CircleA->Position, CircleA->Radius)) {
                return true;
            }
            if(Math::IsInsideConvexPolygon(CircleA->Position, View(RectB->Polygon))) {
                return true;
            }
        }
    }
    if(const FColliderRect *RectA = ColliderA) {
        if(const FColliderCircle *CircleB = ColliderB) {
            for(var Index = 0u; Index < 3u; ++Index) {
                if(Math::OverlapsSegmentToCircle(RectA->Polygon[Index + 0u], RectA->Polygon[Index + 1u], CircleB->Position, CircleB->Radius)) {
                    return true;
                }
            }
            if(Math::OverlapsSegmentToCircle(RectA->Polygon[3u], RectA->Polygon[0u], CircleB->Position, CircleB->Radius)) {
                return true;
            }
            if(Math::IsInsideConvexPolygon(CircleB->Position, View(RectA->Polygon))) {
                return true;
            }
        }
        if(const FColliderRect *RectB = ColliderB) {
            return Math::ContainsOrOverlapsConvex(View(RectA->Polygon), View(RectB->Polygon));
        }
    }
    return false;
}

void GenerateObstacleORCALines(THeapArray<FORCALine> &ORCALines, fvec2 Position, float Radius, fvec2 Velocity, TArrayView<fvec2> Polygon) {
    Check(Polygon.GetSize() >= 3u);
    var SizeMinusOne = Polygon.GetSize() - 1u;
    TFrameArray<FORCAObstaclePoint> Points;
    Points.EnsureMaxSize(Polygon.GetSize());
    for(var Index = 0u; Index < Polygon.GetSize(); ++Index) {
        fvec2 Current = Polygon[Index];
        fvec2 Next = (Index == SizeMinusOne ? Polygon.First() : Polygon[Index + 1u]);
        FORCAObstaclePoint Point;
        Point.Position = Current;
        Point.Direction = Math::Normalized(Next - Current);
        Point.Convex = true;
        Points.Add(Point);
    }
    for(var Index = 0u; Index < Points.GetSize(); ++Index) {
        TStaticArray<FORCAObstaclePoint, 3> InnerPoints;
        InnerPoints[0] = Index == 0u ? Points.Last() : Points[Index - 1u];
        InnerPoints[1] = Points[Index];
        InnerPoints[2] = Index == SizeMinusOne ? Points.First() : Points[Index + 1u];
        GenerateObstacleORCALine(ORCALines, Position, Radius, Velocity, View(InnerPoints));
    }
}

void GenerateObstacleORCALine(THeapArray<FORCALine> &ORCALines, fvec2 Position, float Radius, fvec2 Velocity, TArrayView<FORCAObstaclePoint> Points) {
    var Obstacle1 = Points[1].Position;
    var Obstacle2 = Points[2].Position;
    var Direction0 = Points[0].Direction;
    var Direction1 = Points[1].Direction;
    var Direction2 = Points[2].Direction;
    var Convex1 = Points[1].Convex;
    var Convex2 = Points[2].Convex;

    fvec2 relativePosition1 = Obstacle1 - Position;
    fvec2 relativePosition2 = Obstacle2 - Position;

    /* Check if velocity obstacle of obstacle is already taken care of by
     * previously constructed obstacle ORCA lines. */
    for(var j = 0u; j < ORCALines.GetSize(); ++j) {
        if(Math::Cross(RVOTimeHorizonObstacleInverted * relativePosition1 - ORCALines[j].Position, ORCALines[j].Direction)
                   - RVOTimeHorizonObstacleInverted * Radius
               >= -RVOEpsilon
           && Math::Cross(RVOTimeHorizonObstacleInverted * relativePosition2 - ORCALines[j].Position, ORCALines[j].Direction)
                      - RVOTimeHorizonObstacleInverted * Radius
                  >= -RVOEpsilon) {
            return;
        }
    }

    /* Not yet covered. Check for collisions. */
    float distSq1 = Math::LengthSquared(relativePosition1);
    float distSq2 = Math::LengthSquared(relativePosition2);

    float radiusSq = Radius * Radius;

    fvec2 obstacleVector = Obstacle2 - Obstacle1;
    float s = (Math::Dot(-relativePosition1, obstacleVector)) / Math::LengthSquared(obstacleVector);
    float distSqLine = Math::LengthSquared(-relativePosition1 - s * obstacleVector);

    FORCALine line;

    if(s < 0.0F && distSq1 <= radiusSq) {
        /* Collision with left vertex. Ignore if non-convex. */
        if(Convex1) {
            line.Position = fvec2{0.0f, 0.0f};
            line.Direction = Math::Normalized(fvec2{-relativePosition1.Y, relativePosition1.X});
            Check(!Math::IsNan(line.Direction));
            ORCALines.Add(line);
        }

        return;
    }

    if(s > 1.0F && distSq2 <= radiusSq) {
        /* Collision with right vertex. Ignore if non-convex or if it will be
       * taken care of by neighoring obstace */
        if(Convex2 && Math::Cross(relativePosition2, Direction2) >= 0.0F) {
            line.Position = fvec2{0.0f, 0.0f};
            line.Direction = Math::Normalized(fvec2{-relativePosition2.Y, relativePosition2.X});
            Check(!Math::IsNan(line.Direction));
            ORCALines.Add(line);
        }

        return;
    }

    if(s >= 0.0F && s <= 1.0F && distSqLine <= radiusSq) {
        /* Collision with obstacle segment. */
        line.Position = fvec2{0.0f, 0.0f};
        line.Direction = -Direction1;
        Check(!Math::IsNan(line.Direction));
        ORCALines.Add(line);
        return;
    }

    /* No collision. Compute legs. When obliquely viewed, both legs can come
     * from a single vertex. Legs extend cut-off line when nonconvex vertex. */
    fvec2 leftLegDirection;
    fvec2 rightLegDirection;

    if(s < 0.0F && distSqLine <= radiusSq) {
        /* Obstacle viewed obliquely so that left vertex defines velocity
       * obstacle. */
        if(!Convex1) {
            /* Ignore obstacle. */
            return;
        }

        Obstacle2 = Obstacle1;

        float leg1 = Math::Sqrt(distSq1 - radiusSq);
        leftLegDirection =
            fvec2{relativePosition1.X * leg1 - relativePosition1.Y * Radius, relativePosition1.X * Radius + relativePosition1.Y * leg1} / distSq1;
        rightLegDirection =
            fvec2{relativePosition1.X * leg1 + relativePosition1.Y * Radius, -relativePosition1.X * Radius + relativePosition1.Y * leg1} / distSq1;
    } else if(s > 1.0F && distSqLine <= radiusSq) {
        /* Obstacle viewed obliquely so that right vertex defines velocity
       * obstacle. */
        if(!Convex2) {
            /* Ignore obstacle. */
            return;
        }

        Obstacle1 = Obstacle2;

        float leg2 = Math::Sqrt(distSq2 - radiusSq);
        leftLegDirection =
            fvec2{relativePosition2.X * leg2 - relativePosition2.Y * Radius, relativePosition2.X * Radius + relativePosition2.Y * leg2} / distSq2;
        rightLegDirection =
            fvec2{relativePosition2.X * leg2 + relativePosition2.Y * Radius, -relativePosition2.X * Radius + relativePosition2.Y * leg2} / distSq2;
    } else {
        /* Usual situation. */
        if(Convex1) {
            float leg1 = Math::Sqrt(distSq1 - radiusSq);
            leftLegDirection =
                fvec2{relativePosition1.X * leg1 - relativePosition1.Y * Radius, relativePosition1.X * Radius + relativePosition1.Y * leg1} / distSq1;
        } else {
            /* Left vertex non-convex; left leg extends cut-off line. */
            leftLegDirection = -Direction1;
        }

        if(Convex2) {
            float leg2 = Math::Sqrt(distSq2 - radiusSq);
            rightLegDirection =
                fvec2{relativePosition2.X * leg2 + relativePosition2.Y * Radius, -relativePosition2.X * Radius + relativePosition2.Y * leg2}
                / distSq2;
        } else {
            /* Right vertex non-convex; right leg extends cut-off line. */
            rightLegDirection = Direction1;
        }
    }

    /* Legs can never point into neighboring edge when convex vertex, take
     * cutoff-line of neighboring edge instead. If velocity projected on
     * "foreign" leg, no constraint is added. */

    bool isLeftLegForeign = false;
    bool isRightLegForeign = false;

    if(Convex1 && Math::Cross(leftLegDirection, -Direction0) >= 0.0F) {
        /* Left leg points into obstacle. */
        leftLegDirection = -Direction0;
        isLeftLegForeign = true;
    }

    if(Convex2 && Math::Cross(rightLegDirection, Direction2) <= 0.0F) {
        /* Right leg points into obstacle. */
        rightLegDirection = Direction2;
        isRightLegForeign = true;
    }

    /* Compute cut-off centers. */
    fvec2 leftCutoff = RVOTimeHorizonObstacleInverted * (Obstacle1 - Position);
    fvec2 rightCutoff = RVOTimeHorizonObstacleInverted * (Obstacle2 - Position);
    fvec2 cutoffVec = rightCutoff - leftCutoff;

    /* Project current velocity on velocity obstacle. */

    /* Check if current velocity is projected on cutoff circles. */
    float t = Obstacle1 == Obstacle2 ? 0.5F : Math::Dot((Velocity - leftCutoff), cutoffVec) / Math::LengthSquared(cutoffVec);
    float tLeft = Math::Dot((Velocity - leftCutoff), leftLegDirection);
    float tRight = Math::Dot((Velocity - rightCutoff), rightLegDirection);

    if((t < 0.0F && tLeft < 0.0F) || (Obstacle1 == Obstacle2 && tLeft < 0.0F && tRight < 0.0F)) {
        /* Project on left cut-off circle. */
        fvec2 unitW = Math::Normalized(Velocity - leftCutoff);

        line.Direction = fvec2{unitW.Y, -unitW.X};
        Check(!Math::IsNan(line.Direction));
        line.Position = leftCutoff + Radius * RVOTimeHorizonObstacleInverted * unitW;
        ORCALines.Add(line);
        return;
    }

    if(t > 1.0F && tRight < 0.0F) {
        /* Project on right cut-off circle. */
        fvec2 unitW = Math::Normalized(Velocity - rightCutoff);

        line.Direction = fvec2{unitW.Y, -unitW.X};
        Check(!Math::IsNan(line.Direction));
        line.Position = rightCutoff + Radius * RVOTimeHorizonObstacleInverted * unitW;
        ORCALines.Add(line);
        return;
    }

    /* Project on left leg, right leg, or cut-off line, whichever is closest to
     * velocity. */
    float distSqCutoff = (t < 0.0F || t > 1.0F || Obstacle1 == Obstacle2) ? std::numeric_limits<float>::infinity()
                                                                          : Math::LengthSquared(Velocity - (leftCutoff + t * cutoffVec));
    float distSqLeft =
        tLeft < 0.0F ? std::numeric_limits<float>::infinity() : Math::LengthSquared(Velocity - (leftCutoff + tLeft * leftLegDirection));
    float distSqRight =
        tRight < 0.0F ? std::numeric_limits<float>::infinity() : Math::LengthSquared(Velocity - (rightCutoff + tRight * rightLegDirection));

    if(distSqCutoff <= distSqLeft && distSqCutoff <= distSqRight) {
        /* Project on cut-off line. */
        line.Direction = -Direction1;
        line.Position = leftCutoff + Radius * RVOTimeHorizonObstacleInverted * fvec2{-line.Direction.Y, line.Direction.X};
        ORCALines.Add(line);
        return;
    }

    if(distSqLeft <= distSqRight) {
        /* Project on left leg. */
        if(isLeftLegForeign) {
            return;
        }

        line.Direction = leftLegDirection;
        Check(!Math::IsNan(line.Direction));
        line.Position = leftCutoff + Radius * RVOTimeHorizonObstacleInverted * fvec2{-line.Direction.Y, line.Direction.X};
        ORCALines.Add(line);
        return;
    }

    /* Project on right leg. */
    if(isRightLegForeign) {
        return;
    }

    line.Direction = -rightLegDirection;
    Check(!Math::IsNan(line.Direction));
    line.Position = rightCutoff + Radius * RVOTimeHorizonObstacleInverted * fvec2{-line.Direction.Y, line.Direction.X};
    ORCALines.Add(line);
}

void GenerateEntityORCALine(
    THeapArray<FORCALine> &ORCALines, fvec2 Delta, float Radius, fvec2 Velocity, const FSpatialHashColliderDynamic &ColliderDynamic) {
    fvec2 relativePosition = -Delta;
    fvec2 relativeVelocity = Velocity - ColliderDynamic.Velocity;
    float distSq = Math::LengthSquared(relativePosition);
    FColliderCircle Collider = ColliderDynamic.Collider;
    float combinedRadius = (Radius + Collider.Radius) * RVORadiusCoef;
    float combinedRadiusSq = combinedRadius * combinedRadius;

    FORCALine line;
    fvec2 u;

    if(distSq > combinedRadiusSq) {
        /* No collision. */
        fvec2 w = relativeVelocity - RVOTimeHorizonInverted * relativePosition;
        /* Vector from cutoff center to relative velocity. */
        float wLengthSq = Math::LengthSquared(w);

        float dotProduct1 = Math::Dot(w, relativePosition);

        if(dotProduct1 < 0.0F && dotProduct1 * dotProduct1 > combinedRadiusSq * wLengthSq) {
            /* Project on cut-off circle. */
            float wLength = Math::Sqrt(wLengthSq);
            fvec2 unitW = w / wLength;

            line.Direction = fvec2{unitW.Y, -unitW.X};
            Check(!Math::IsNan(line.Direction));
            u = (combinedRadius * RVOTimeHorizonInverted - wLength) * unitW;
        } else {
            /* Project on legs. */
            float leg = Math::Sqrt(distSq - combinedRadiusSq);

            if(Math::Cross(relativePosition, w) > 0.0F) {
                /* Project on left leg. */
                line.Direction =
                    fvec2{
                        relativePosition.X * leg - relativePosition.Y * combinedRadius,
                        relativePosition.X * combinedRadius + relativePosition.Y * leg}
                    / distSq;
                Check(!Math::IsNan(line.Direction));
            } else {
                /* Project on right leg. */
                line.Direction =
                    -fvec2{
                        relativePosition.X * leg + relativePosition.Y * combinedRadius,
                        -relativePosition.X * combinedRadius + relativePosition.Y * leg}
                    / distSq;
                Check(!Math::IsNan(line.Direction));
            }

            float dotProduct2 = Math::Dot(relativeVelocity, line.Direction);

            u = dotProduct2 * line.Direction - relativeVelocity;
        }
    } else {
        /* Collision. Project on cut-off circle of time timeStep. */
        var invTimeStep = (float)Time::TicksPerSecond;

        /* Vector from cutoff center to relative velocity. */
        fvec2 w = relativeVelocity - invTimeStep * relativePosition;

        float wLength = Math::Length(w);
        fvec2 unitW = w / wLength;

        line.Direction = fvec2{unitW.Y, -unitW.X};
        Check(!Math::IsNan(line.Direction));
        u = (combinedRadius * invTimeStep - wLength) * unitW;
    }

    line.Position = Velocity + 0.5F * u;
    ORCALines.Add(line);
}

void ProcessCollider(
    entity Entity, const FCollider &Collider, const CStaticCollision *StaticCollision, const CDynamicCollision *DynamicCollision,
    const CWorldTransform &WorldTransform, const CWorldTransformPreviousPosition &WorldTransformPreviousPosition,
    const CMovementVelocity *MovementVelocity, CColliderCache &ColliderCache, const CDebugRenderSettings &DebugRenderSettings,
    const CCamera2 &Camera) {
    // TODO: Support runtime transitions (removing CStaticCollision and adding CDynamicCollision) through CColliderCache::WasStatic/WasDynamic.
    var EntityId = Entity.id();
    var ECS = Entity.world();

    if(DebugRenderSettings.DebugRender) {
        if(Math::DistanceSquared(WorldTransform.Position, Camera.Position) < Math::Square(DebugVisualizationRange)) {
            if(const FColliderCircle *Circle = Collider) {
                Debug::DebugCircle(ECS, Circle->Position, 0.0f, Circle->Radius, {0.0f, 0.0f, 1.0f, 0.6f}, 0.0f, 1.0f, false);
            }
            if(const FColliderRect *Rect = Collider) {
                for(var Index = 0u; Index < 3u; ++Index) {
                    Debug::DebugLine(ECS, Rect->Polygon[Index + 0u], Rect->Polygon[Index + 1u], {0.0f, 0.0f, 1.0f, 0.6f}, 0.0f, 1.0f, false);
                }
                Debug::DebugLine(ECS, Rect->Polygon[3u], Rect->Polygon[0u], {0.0f, 0.0f, 1.0f, 0.6f}, 0.0f, 1.0f, false);
            }
        }
    }

    if(!IsPaused()) {
        EColliderCacheCollisionCategory CollisionCategory;
        if(StaticCollision) {
            CollisionCategory = EColliderCacheCollisionCategory::Static;
        } else if(DynamicCollision) {
            CollisionCategory = EColliderCacheCollisionCategory::Dynamic;
        } else {
            CollisionCategory = EColliderCacheCollisionCategory::Trigger;
        }
        var SameCategory = ColliderCache.CollisionCategory == CollisionCategory;
        var Dirty = !SameCategory || WorldTransform.Position != WorldTransformPreviousPosition.Position;
        if(!Dirty && !DynamicCollision) {
            return;
        }
        CellsRemain.Clear();
        CellsAdded.Clear();
        CellsRemoved.Clear();
        TArrayView<ivec2> CellsRemainView;

        if(Dirty) {
            CellsRemoved = ColliderCache.Cells;
            var Projection = Project(Collider);
            for(var X = Projection.Start.X; X <= Projection.End.X; ++X) {
                for(var Y = Projection.Start.Y; Y <= Projection.End.Y; ++Y) {
                    var Cell = ivec2{X, Y};
                    var Index = Array::Find(CellsRemoved, Cell);
                    if(Index != Array::NotFound) {
                        CellsRemoved.RemoveSwap(Index);
                        CellsRemain.Add(Cell);
                    } else {
                        CellsAdded.Add(Cell);
                    }
                }
            }
            if(!CellsRemoved.IsEmpty()) {
                ColliderCache.Cells.Clear();
                ColliderCache.Cells.Add(CellsRemain);
            }
            ColliderCache.Cells.Add(CellsAdded);
            CellsRemainView = View(CellsRemain);
        } else {
            CellsRemainView = View(ColliderCache.Cells);
        }
        ref CellsAddedView = CellsAdded;
        ref CellsRemovedView = CellsRemoved;

        // First remove from cells, to search less entries.
        for(var Cell: CellsRemovedView) {
            var Key = AssembleKey(Cell);
            var Bucket = SpatialHash.ComputeBucket(Key);
            FSpatialHashCell *SpatialHashCell = &SpatialHash.Get(Key, Bucket);
            if(ColliderCache.CollisionCategory == EColliderCacheCollisionCategory::Static) {
                Array::RemoveSwap(SpatialHashCell->StaticCollision, [EntityId](const FSpatialHashCollider &Collider) {
                    return Collider.EntityId == EntityId;
                });
            } else if(ColliderCache.CollisionCategory == EColliderCacheCollisionCategory::Dynamic) {
                Array::RemoveSwap(SpatialHashCell->DynamicCollision, [EntityId](const FSpatialHashColliderDynamic &Collider) {
                    return Collider.EntityId == EntityId;
                });
            } else if(ColliderCache.CollisionCategory == EColliderCacheCollisionCategory::Trigger) {
                Array::RemoveSwap(SpatialHashCell->TriggerCollision, [EntityId](const FSpatialHashCollider &Collider) {
                    return Collider.EntityId == EntityId;
                });
            }
        }

        var Velocity = MovementVelocity ? MovementVelocity->Velocity
                                        : (Math::IsNan(WorldTransformPreviousPosition.Position)
                                               ? fvec2{0.0f, 0.0f}
                                               : WorldTransform.Position - WorldTransformPreviousPosition.Position);

        if(SameCategory) {
            if(DynamicCollision) {
                for(var Cell: CellsRemainView) {
                    var Key = AssembleKey(Cell);
                    ref Dynamic = SpatialHash[Key].DynamicCollision;
                    var Index = Array::Find(Dynamic, [EntityId](const FSpatialHashColliderDynamic &Collider) {
                        return Collider.EntityId == EntityId;
                    });
                    ref ColliderDynamic = Dynamic[Index];
                    ColliderDynamic.Velocity = Velocity;
                    if(FColliderCircle *ColliderCircle = ColliderDynamic.Collider) {
                        ColliderCircle->Position = WorldTransform.Position;
                    } else {
                        Prevent();
                    }
                }
            }
        } else {
            // Category changed, we have to move the Collider between storages of each cell.
            for(var Cell: CellsRemainView) {
                var Key = AssembleKey(Cell);

                // Remove from old (if any).
                if(ColliderCache.CollisionCategory == EColliderCacheCollisionCategory::Static) {
                    ref Static = SpatialHash[Key].StaticCollision;
                    var Index = Array::Find(Static, [EntityId](const FSpatialHashCollider &Collider) {
                        return Collider.EntityId == EntityId;
                    });
                    Static.RemoveSwap(Index);
                } else if(ColliderCache.CollisionCategory == EColliderCacheCollisionCategory::Dynamic) {
                    ref Dynamic = SpatialHash[Key].DynamicCollision;
                    var Index = Array::Find(Dynamic, [EntityId](const FSpatialHashColliderDynamic &Collider) {
                        return Collider.EntityId == EntityId;
                    });
                    Dynamic.RemoveSwap(Index);
                } else if(ColliderCache.CollisionCategory == EColliderCacheCollisionCategory::Trigger) {
                    ref Trigger = SpatialHash[Key].TriggerCollision;
                    var Index = Array::Find(Trigger, [EntityId](const FSpatialHashCollider &Collider) {
                        return Collider.EntityId == EntityId;
                    });
                    Trigger.RemoveSwap(Index);
                }

                // Add to new (if any).
                if(CollisionCategory == EColliderCacheCollisionCategory::Static) {
                    SpatialHash[Key].StaticCollision.Add({Collider, Entity.id()});
                } else if(CollisionCategory == EColliderCacheCollisionCategory::Dynamic) {
                    SpatialHash[Key].DynamicCollision.Add({Collider, Velocity, Entity.id()});
                } else if(CollisionCategory == EColliderCacheCollisionCategory::Trigger) {
                    SpatialHash[Key].TriggerCollision.Add({Collider, Entity.id()});
                }
            }
        }

        for(var Cell: CellsAddedView) {
            var Key = AssembleKey(Cell);
            var Bucket = SpatialHash.ComputeBucket(Key);
            FSpatialHashCell *SpatialHashCell;
            if(var Existing = SpatialHash.Find(Key, Bucket)) {
                SpatialHashCell = Existing;
            } else {
                SpatialHashCell = &SpatialHash.GetOrCreate(Key, Bucket);
                SpatialHashCell->CellPosition = fvec2{((float)Cell.X + 0.5f) * CellSizeFloat, ((float)Cell.Y + 0.5f) * CellSizeFloat};
            }
            if(CollisionCategory == EColliderCacheCollisionCategory::Static) {
                SpatialHashCell->StaticCollision.Add({Collider, Entity.id()});
            } else if(CollisionCategory == EColliderCacheCollisionCategory::Dynamic) {
                SpatialHashCell->DynamicCollision.Add({Collider, Velocity, Entity.id()});
            } else if(CollisionCategory == EColliderCacheCollisionCategory::Trigger) {
                SpatialHashCell->TriggerCollision.Add({Collider, Entity.id()});
            }
        }

        ColliderCache.CollisionCategory = CollisionCategory;
    }
}

uint64 AssembleKey(ivec2 Cell) {
    return *(const uint64 *)&Cell;
}

uint64 AssembleKey(fvec2 Position) {
    ivec2 Cell;
    Cell.X = (int32)Position.X / CellSize;
    Cell.Y = (int32)Position.Y / CellSize;
    return AssembleKey(Cell);
}

FSpatialProjectionResult Project(const FCollider &Collider) {
    FSpatialProjectionResult Result;
    if(const FColliderCircle *Circle = Collider) {
        Result.Start = {(int32)(Circle->Position.X - Circle->Radius), (int32)(Circle->Position.Y - Circle->Radius)};
        Result.End = {(int32)(Circle->Position.X + Circle->Radius), (int32)(Circle->Position.Y + Circle->Radius)};
    } else if(const FColliderRect *Rect = Collider) {
        ref Polygon = Rect->Polygon;
        Result.Start = Result.End = {(int32)Polygon[0].X, (int32)Polygon[0].Y};
        for(var Index = 1u; Index < 4u; ++Index) {
            var Point = ivec2{(int32)Polygon[Index].X, (int32)Polygon[Index].Y};
            Result.Start.X = Math::Min(Result.Start.X, Point.X);
            Result.Start.Y = Math::Min(Result.Start.Y, Point.Y);
            Result.End.X = Math::Max(Result.End.X, Point.X);
            Result.End.Y = Math::Max(Result.End.Y, Point.Y);
        }
    } else {
        Prevent();
    }

    if(Result.Start.X < 0) {
        Result.Start.X -= CellSize;
    }
    if(Result.End.X < 0) {
        Result.End.X -= CellSize;
    }
    if(Result.Start.Y < 0) {
        Result.Start.Y -= CellSize;
    }
    if(Result.End.Y < 0) {
        Result.End.Y -= CellSize;
    }
    Result.Start /= CellSize;
    Result.End /= CellSize;

    return Result;
}

}  // namespace

}  // namespace SE