Bullet hit detection strategies & performance...

Unity Engine
, ,
1

I’m sure I’m not the only one wondering what the most performant and cleanest method for handling projectile collisions in ECS is. It’s an interesting topic. Lots of good guys with guns, lots of bad guys with guns, and LOTS of bullets!

For this analysis, we’re assuming the physics shapes are simple spheres, rectangles, or other primitives. We don’t care about hitting specific body parts - just that the bullet hits the primitive.

So far, here are the strategies I’ve encountered:

  1. Use Unity Physics triggers - Using ITriggerEventsJob and triggers, check all collisions and look for bullets hitting things. One good thing is that use of triggers means this code only gets executed when objects collide, but I suspect that unity physics has to a lot of extra collision handling under the hood. [(+)only runs whenever things collide, (-)the unity physics system has more work every frame]
    Examples:
    DOTS-Shmup3D-sample-master - DOTS-Shmup3D-sample/Assets/Scripts/BaseSystem/CollisionManager.cs at master · Unity-Technologies/DOTS-Shmup3D-sample · GitHub
    shaefsky - Handling collisions

  2. Make a system with a brute-force nested loop “for every target” and “for every bullet” and checks to see if they are close enough to a target. This appears computationally heavy, but then again, perhaps the other methods have to loop through the same number of entities anyway and it’s just hidden under the physics raycast/collision systems. Most of the examples I found using this method are from a couple of years ago - before unity.physics existed. [(-)runs every frame, (-)bullet * target iterations, (+)no extra work for unity physics]
    Examples:
    AngryDots - https://github.com/UnityTechnologies/AngryBots_ECS/blob/master/AngryDOTS/Assets/Scripts/ECS/Systems/CollisionSystem.cs
    IntroToECSFinal - Entity Component System for Unity: Getting Started | Kodeco
    Unity-Official-ECS-EntityComponentSystemSamples - Unity-Offical-ECS-EntityComponentSystemSamples/TwoStickShooter/Hybrid/Assets/GameCode/DamageSystem.cs at master · lkihk/Unity-Offical-ECS-EntityComponentSystemSamples · GitHub

  3. Make a system that loops through every bullet and does a forward raycast, while moving the bullet at the same time. I like this method since it kills two birds with one stone (movement and collision), and because raycasting supposedly pretty fast. If a raycast internally needs to check against everything in the scene, then this method would be the same speed as Method 2. It seems like this method is the most popular one at the moment, but maybe that’s because it’s easier (not necessarily faster), or perhaps it’s because the physics package is relatively new. [(-)runs every frame, (?)one raycast per bullet, (+)no extra loop for bullet movement required].
    Examples:
    DotsOfTheDead - DOTSoftheDead/Assets/_Project/Scripts/Systems/ProjectileHitDetectionSystem.cs at master · illogika-studio/DOTSoftheDead · GitHub
    Opeth001 - Collision Detection projectiles

  4. Visual Effects Graph - There are a couple of guys on Reddit talking about using VFX Graph with baked textures for bullets because apparently VFXG has some sort of physics collider capability that is separate from unity physics. The GPU does most of the work. This method looks fast, but for me personally, I don’t have enough details to reproduce what they’re talking about. I’m sure there are some shader gurus around who could figure it out. [(-)doesn’t work with unity colliders/shapes, (-)not many details on what they did, (+)runs fast even without ECS, (-)probably doesn’t work on older mobile platforms]
    Example: grvChA - Reddit - Dive into anything

For completeness, I also found couple of other projects with solutions that don’t really apply:
SpaceShooterECS used some sort of hash table voodoo… I have no idea what the heck is going on in that code.
SurvivalShooterECS just does an instant-hit raycast (no projectiles)

Unfortunately I don’t know enough about the internal workings of the physics package to make a determination about which one is best.

Any insights for performance pros/cons? Methods I missed? Has anyone done any performance testing to compare the methods or know of someone who has tested some of them?

4 Likes
2

the third approach is very fast (for my case) i have a maximum of 100 projectile per frame which is very low.
to create collision Events im using a commandBuffer within a bursted Job and for this low events count it fits my needs.

for my point of view the only problem this approach can have is the creation of thousands of Event Entities per frame.
so if you are concerned with this case you should take a look at @tertle 's Event System package.

1 Like
3

I don’t think anything involving physics (#1 and #3) does an O(N^2) lookup. For static meshes, they use a BVH/octree. If everything is moving, they probably use spatial hashing (and/or BIH) for the broad phase and only do the O(N^2) comparison for objects that are already close together.

1 Like
4

#3 except the normal flow is you track current/last position and raycast from current to last. You don’t know how far a bullet is going to travel in any single frame so forward can either hit before the bullet arrives or not hit at all.

1 Like
5

That’s good to know. I really like tertle’s event system. I’ll investigate a way to use his event system and batch create all bullets per frame.

6

Thanks for the info. I had a hunch the broad phase might be able to improve things and I didn’t know that physics uses tree pruning. I had to google spatial hashing just now and yes that definitely looks better than O(N^2). It’s nice to have all this confirmed by someone in-the-know!

7

That’s good to know… I hadn’t thought of that but it makes sense. The DotsOfTheDead example does what you stated - it raycasts from the current position to the previous position. I think Opeth001’s algorithm accounts for that too, except he’s doing the raycast from the current to the next predicted position to detect the collision before it has a chance to overshoot.

8

Unity uses two BVH structures, one for static objects and one for dynamic objects. These are true BVH structures and not some more primitive spatial hashing techniques. Now onto the different approaches:

  1. Pros: Logic already written by Unity. Code has been heavily optimized using the dual BVH structures. Cons: The filtering and processing of trigger events has to be done single-threaded.
  2. Pros: Easy to implement. Cons: Super slow and difficult to multithread.
  3. Pros: Cheaper than a trigger object. Heavy logic already written by Unity. Code has been heavily optimized using the dual BVH structures. Can order hits. Cons: Doesn’t work for large bullets.
  4. Pros: Highest throughput. Cons: Requires GPU compute support. Has on average a 3 frame latency to get the results back to the CPU.

While I doubt my solution is the fastest for your game, I wrote a solution that generates a CapsuleCollider scaled based on the movement every frame and queries the capsule collider against other objects it can collide against (I have big bullets). This is in a custom physics solution where colliders can be allocated in place (blobless) and instead of having two BVH structures, I can have an acceleration structure per type of object so I don’t have to do post-event filtering. It also allows safe processing of events in parallel.

Granted, a SphereCast solution that uses a ray vs Minkowski sum would be faster. Unity.Physics doesn’t use that technique for spherecasts, and I haven’t gotten around to implementing it myself yet.

4 Likes
9

In practice you have other concerns that will likely be more challenging then the physics. Like rendering. Every feature level package in DOTS has it’s own quirks that you really need to find before building out any one area too much. I would create a minimal yet complete end to end flow and use that as a base. As opposed to say putting a lot of time into optimizing the physics part before touching rendering. The transform systems has gotcha’s also like hierarchy with a lot of moving objects. You want to discover things like that early not late.

1 Like
10

Thanks - you brought up some good pro/con points. That’s pretty cool that you did a custom physics solution - that’s beyond my capabilities at this moment. At this point, I think I have enough info so tomorrow morning I’ll start implementing option 3 and see how it goes. I’m sure there’s a good joke in here somewhere about having big bullets :eyes:

11

That’s good advice, and I concur. I won’t get crazy with physics optimization, but I thought it was worth spending a day deciding on the best projectile strategy since it’s a big part of my game and it has repercussions on how some of the other systems interact.

12

Sorry to bump this subject but my query is for a number of bullets that need to hit static and dynamic colliders, but also function with prediction with dots netcode. Am I right in choosing method (3) above?

The bullets have a slower travel time and can be dodged.

As this topic is old, I want to see if any new information has come to light since before I implement it with Entities 0.50. Thanks!

13

I can share my bullets job I’ve used in this demo

There’s a bunch of stuff in there that I would do differently & more cleanly if I re-wrote it today, but overall my hit detection strategy would be the same as this. This is basically like approach 3, except you can specify a radius for your bullet collision. If radius is 0f, it does a raycast; otherwise it does a spherecast. It also shows how to do filtering on detected hits, in a way that’s more complex than simply relying on physics layers (useful for ignoring the specific gun that shot this bullet, or for going through surfaces based on the perpenticularity of the hit for example).

But as you can see, despite every single bullet doing raycasts every frame and despite checking every hit to see if the entity is ignored, it’s still extremely fast. The reason why I haven’t written this as a Entities.ForEach is because of the “TmpRaycastHits” and “TmpColliderCastHits” collections that need to be unique to every thread

It would be hard for me to recommend any other approach, because if you don’t do some form of raycast from prevPosition to currentPosition, you won’t have accurate hit point/normal info, and you’re gonna start missing collisions as soon as your projectile is somewhat fast-moving. At a fixedUpdate rate of 60 and a bullet radius of 0.05f, if your bullets move any faster than a speed of 6 units/sec, they are going to start being at risk of missing collisions if you don’t use a raycast approach (because that’s the speed at which they would advance by a distance equal to their whole sphere diameter in one fixedUpdate). Unity.Physics does use Continuous Collision Detection for rigidbodies moved with velocity, but for something that moves fast it’s gonna give you some very large imprecisions, and I’m fairly certain it would perform much worse

Code

[BurstCompile]
public struct ProjectileJob : IJobEntityBatchWithIndex
{
    public float DeltaTime;
    public EntityCommandBuffer.ParallelWriter DestructionCommandBuffer;
    public EntityCommandBuffer.ParallelWriter HitEventsCommandBuffer;
    [ReadOnly]
    public PhysicsWorld PhysicsWorld;

    [ReadOnly]
    public EntityTypeHandle EntityType;
    [ReadOnly]
    public ComponentTypeHandle<Projectile> ProjectileType;
    public ComponentTypeHandle<ProjectileMoving> ProjectileMovingType;
    public ComponentTypeHandle<Translation> TranslationType;
    public ComponentTypeHandle<Rotation> RotationType;
    [ReadOnly]
    public BufferTypeHandle<ProjectileIgnoredEntity> IgnoreEntityBuffer;
    [ReadOnly]
    public BufferFromEntity<HitEvent> HitEventsBufferFromEntity;

    [NativeDisableContainerSafetyRestriction]
    private NativeList<Unity.Physics.RaycastHit> TmpRaycastHits;
    [NativeDisableContainerSafetyRestriction]
    private NativeList<ColliderCastHit> TmpColliderCastHits;

    public unsafe void Execute(ArchetypeChunk batchInChunk, int batchIndex, int indexOfFirstEntityInQuery)
    {
        NativeArray<Entity> chunkEntities = batchInChunk.GetNativeArray(EntityType);
        NativeArray<Projectile> chunkProjectiles = batchInChunk.GetNativeArray(ProjectileType);
        NativeArray<ProjectileMoving> chunkProjectileMovings = batchInChunk.GetNativeArray(ProjectileMovingType);
        NativeArray<Translation> chunkTranslations = batchInChunk.GetNativeArray(TranslationType);
        NativeArray<Rotation> chunkRotations = batchInChunk.GetNativeArray(RotationType);
        BufferAccessor<ProjectileIgnoredEntity> ignoreEntityBufferAccessor = batchInChunk.GetBufferAccessor(IgnoreEntityBuffer);

        if (!TmpRaycastHits.IsCreated)
        {
            TmpRaycastHits = new NativeList<Unity.Physics.RaycastHit>(24, Allocator.Temp);
        }
        if (!TmpColliderCastHits.IsCreated)
        {
            TmpColliderCastHits = new NativeList<ColliderCastHit>(24, Allocator.Temp);
        }

        for (int i = 0; i < batchInChunk.Count; i++)
        {
            Entity entity = chunkEntities[i];
            Projectile projectile = chunkProjectiles[i];
            ProjectileMoving projectileMoving = chunkProjectileMovings[i];
            Translation translation = chunkTranslations[i];
            Rotation rotation = chunkRotations[i];
            DynamicBuffer<ProjectileIgnoredEntity> ignoredEntitiesBuffer = ignoreEntityBufferAccessor[i];

            // Init
            if (projectileMoving.LifetimeCounter == 0f)
            {
                translation.Value = projectile.StartPointSimulation.pos;
                rotation.Value = projectile.StartPointSimulation.rot;

                float3 moveDirection = math.mul(rotation.Value, math.forward());

                projectileMoving.Velocity = moveDirection * projectileMoving.Speed;
                projectileMoving.SimulationToVisualsPositionOffset = projectile.StartPointVisual.pos - projectile.StartPointSimulation.pos;
            }

            projectileMoving.LifetimeCounter += DeltaTime;

            float moveLength = math.length(projectileMoving.Velocity) * DeltaTime;
            if (projectileMoving.MaxRange > 0f)
            {
                moveLength = math.clamp(moveLength, 0f, projectileMoving.MaxRange - projectileMoving.DistanceTraveledCounter);
            }
            float3 movementDirection = math.normalizesafe(projectileMoving.Velocity);

            // Hit detection
            CommonCastHit commonHit = default;
            commonHit.Fraction = float.MaxValue;
            CollisionFilter filter = new CollisionFilter();
            filter.BelongsTo = projectileMoving.BelongsTo.Value;
            filter.CollidesWith = projectileMoving.CollidesWith.Value;
            if (projectileMoving.Radius > 0f)
            {
                TmpColliderCastHits.Clear();
                if (PhysicsWorld.SphereCastAll(translation.Value, projectileMoving.Radius, movementDirection, moveLength, ref TmpColliderCastHits, filter, QueryInteraction.IgnoreTriggers))
                {
                    for (int hitIndex = 0; hitIndex < TmpColliderCastHits.Length; hitIndex++)
                    {
                        ColliderCastHit hit = TmpColliderCastHits[hitIndex];
                        if (hit.Fraction < commonHit.Fraction)
                        {
                            bool hitValid = true;
                            for (int ignoreIndex = 0; ignoreIndex < ignoredEntitiesBuffer.Length; ignoreIndex++)
                            {
                                if (hit.Entity == ignoredEntitiesBuffer[ignoreIndex].Entity)
                                {
                                    hitValid = false;
                                }
                            }

                            if (hitValid)
                            {
                                commonHit = new CommonCastHit(hit);
                            }
                        }
                    }
                }
            }
            else
            {
                TmpRaycastHits.Clear();
                if (PhysicsUtilities.RaycastAll(in PhysicsWorld, translation.Value, movementDirection, moveLength, ref TmpRaycastHits, filter, true, true))
                {
                    for (int hitIndex = 0; hitIndex < TmpRaycastHits.Length; hitIndex++)
                    {
                        RaycastHit hit = TmpRaycastHits[hitIndex];
                        if (hit.Fraction < commonHit.Fraction)
                        {
                            bool hitValid = true;
                            for (int ignoreIndex = 0; ignoreIndex < ignoredEntitiesBuffer.Length; ignoreIndex++)
                            {
                                if (hit.Entity == ignoredEntitiesBuffer[ignoreIndex].Entity)
                                {
                                    hitValid = false;
                                }
                            }

                            if (hitValid)
                            {
                                commonHit = new CommonCastHit(hit);
                            }
                        }
                    }
                }
            }

            float hitDistance = moveLength;
            if (commonHit.Entity != Entity.Null)
            {
                hitDistance = commonHit.Fraction * moveLength;
                projectileMoving.Hit = commonHit;

                if (HitEventsBufferFromEntity.HasComponent(commonHit.Entity))
                {
                    HitEventsCommandBuffer.AppendToBuffer(batchIndex, commonHit.Entity, new HitEvent(projectileMoving.Damage));
                }
            }

            if (math.lengthsq(projectileMoving.Velocity) > 0f)
            {
                rotation.Value = Maths.CreateRotationPointingTo(projectileMoving.Velocity);
            }
            translation.Value += movementDirection * hitDistance;
            projectileMoving.DistanceTraveledThisFrame = hitDistance;
            projectileMoving.DistanceTraveledCounter += hitDistance;

            // todo; custom gravity?
            projectileMoving.Velocity += math.up() * -9.81f * projectileMoving.GravityFactor * DeltaTime;

            // Destruction (deferred)
            if (projectile.AutoDestroy)
            {
                if (commonHit.Entity != Entity.Null ||
                    projectileMoving.LifetimeCounter >= projectileMoving.MaxLifetime ||
                    projectileMoving.DistanceTraveledCounter >= projectileMoving.MaxRange)
                {
                    DestructionCommandBuffer.DestroyEntity(batchIndex, entity);
                }
            }

            chunkProjectileMovings[i] = projectileMoving;
            chunkTranslations[i] = translation;
            chunkRotations[i] = rotation;
        }
    }
}
6 Likes
14

Thank you! Digging through now and I can see the process, very helpful!

1 Like
15

I agree with PhilSA in that I haven’t found anything superior to Approach 3 as of yet and I wrote that way back in July 2020. I’m still using it today for my linear projectiles and I know a lot of other guys in these forums use the approach as well. As @burningmime said, this approach uses the physics system’s internal BHV/Oct-tree so it’s quite a bit faster than searching through every entity for every projectile.

Of course, the one gotcha is that you need to be using Unity.Physics already for that approach to work. If you’re already using it, perfect. Also using the physics calculate AABB is a super fast way of detecting nearby targets. However… I would not advise using unity.physics for the sole purpose of making your projectiles faster because the physics systems take a large amount of horsepower by themselves. I lost 20% of my frame-time just by including unity.physics and putting colliders on the things I want to track.

If I was not using unity.physics, I would probably use a home-grown quad tree to reduce the search space. There are several examples in these forums that work pretty well.

2 Likes
16

Do you mean you have colliders on your bullets?

But more generally, if that’s not already the case, you could try setting your PhysicsBody to “Kinematic” instead of “Static” for moving objects

17

No I don’t have colliders on the bullets. But in order for raycasting to work, all the things that a bullet can hit need colliders - moving enemies, props, buildings, terrain, etc.