I've gotten many simple games up and running, and now I'm in the process of making a bigger one. In my smaller games, I would simply check if 2 objects were colliding in the game loop, for example, in Pong:

if(paddle.collides(ball)) {
  ball.bounce();
}

But now that I'm starting to upscale, it seems that I need a better, more flexible solution. I assumed this would be a common problem, but when I looked up “Collision engine”, I mostly got results on how to implement real life physics. The problem with this is that some objects colliding will have no effect, but the collision engines check all the objects against each other.

For example, one method that I've seen is to add every entity to a Quadtree. Then when the collision system detects a collision, it sends an event to another system to handle it. However, if you have 1000 bullets which can't collide with each other, the collision system checking in between them seems like a waste of cycles.

Another thing that I'm confused about is how the collision system should handle the collisions themselves. I'm using an Entity Component System structure, so right now I'm using a system that loops through all entities with a BoundsComponent, and checking them against all the other ones. But there are many different types of entities, some that do damage (bullets), some that have health (player), and some that are static (rocks). How should the collision system handle this?

Also, just another side question: If I'm using a Quadtree, should there be one for each type of entity, or one for all of them?

Sorry if I'm missing something here, I'm just really confused on how most games handle this.

Thanks!

One Quadtree. Let bullets collide. If you have a Quadtree you do not do 1000² checks.

Do you OOP with inheritance?

@arnero

arnero said:
Do you OOP with inheritance?

I'm using an Entity Component System.

arnero said:
Let bullets collide

Wouldn't it be better to use collision groups/masks? I've been looking around for a couple of hours and found this https://gamedev.stackexchange.com/a/20343/120515.

Bitmasks is one option, callbacks is another allowing to implement filtering in game code.
This can become pretty detailed, e.g. having a bounding box intersection callback from broad phase, and having a second callback in narrow phase when collision is known to happen.
Broad phase has the advantage to skip over expensive exact collision tests. Ofc. this can be done using bitmasks and no callbacks at all as well, or supporting both options.
Callbacks are also useful to generate sound effects, modify contact velocities for something like a conveyor belt, etc.
(Using ECS there should be be a nicer alternative to callbacks i guess.)

For bullets it may be more efficient to not insert them to quadtree, but only use the quadtree to check if they hit something.
This would save both insertion and bullet-bullet-collision costs.
If they move fast, raytracing their moved trajectory in a frame might be necessary, which is easier than requiring full continuous collision support for anything that might end up in the quadtree.

I would tend to use BVH over loose quadtree, because it gives the option to refit branches of the tree instead a full rebuild per frame.
I think BVH is also easier to implement, and ofc. you can still use 4 children like you are used to do with quadtrees.

@JoeJ Thanks for your reply!

JoeJ said:
Bitmasks is one option, callbacks

Is there any reason not to use both?

JoeJ said:
(Using ECS there should be be a nicer alternative to callbacks i guess.)

I think I'm going to create a CollisionComponent and a system that resolves it.

JoeJ said:
BVH

By BVH do you mean a Bounding volume hierarchy? I haven't really heard of it before, is it similar to a Quadtree?

hs12503 said:
Is there any reason not to use both?

Not really. I would implement both because callbacks cause some overhead.

hs12503 said:
By BVH do you mean a Bounding volume hierarchy? I haven't really heard of it before, is it similar to a Quadtree?

Yes. It seems BVH became more popular over time than quad/octree for both raytracing and collision detection.

The difference in implementation is small. Think of it as a quadtree, but instead splitting at the center of each node (causing a grid structure fixed in world space), you can pick the splitting point freely (giving options for better balanced / more efficient tree but mainly refitting).

I'll list major differences between to two:

Quadtree can work without storing bounding boxes for each node. This saves BW and memory and probably is the biggest advantage over BVH. But it disappears if you use bounds anyways to reduce the number of potential colliding pairs.

BVH will have overlapping child bounds, so you need to traverse multiple children. But the same is true for loose quadtree which you might want to use to avoid storing one object in multiple nodes (causing a need for variable sized lists per node).

BVH is very flexible. E.g. for structures like ragdolls or a moving ship you can keep the hierarchy static and only traverse once to update the bounds, which is cheaper than rebuilding the whole tree from scratch.
DXR / RTX is an example for this: It uses bottom level structures for dynamic objects, and a top level structure which is a tree over those few objects. Only the top level structure needs a full rebuild each frame.
Physics engines often use the same mechanism.
In case you do not require parent bounds to bound child bounds exactly (usually the case), even refitting might not be necessary, and just transforming the bottom levels is good enough. Just make bounds large enough so the objects stay within under any orientation (at the price of having less tight fitting bounds ofc.).

So it is this flexibility that makes BVH often the better choice.
But just to let you know - if you do not have super large numbers of stuff it should not matter much.

Or you could hard code this:

track which bullet position, see what it should collide? Maybe players only, and only enemy's. Track that position, player enemy.

If bullet ins in the same position (-area of character) lets say is only z +50 for character size and you hit the character.

On same position: trigger function.

ANd you have a costume collider.

Probably will work the same as collider, way because colliders are boxes cube, so they don't mimic character shape unless you have some more complex like physical box for the character or something. Don't know if games like FPS have only boxes or some kind of modular thing to the body. Since they need more precision.

Forget the walls, you also need to get their center position + size.

On hit function destroy bullet.

for world like sky, maybe add a life time, destroy on life time. A life should have the speed + world size. Should get life time like 20 secs.

Ground : don't know, if you need a grenade. Also need function for ground.

The effect should be added to the last grenade or bullet position, since the wall position is very big. in that case you adjust the size if it was -50 or +50 for effect add only +25 or - 25.

bullet.obj
bullet_position
enemy_position
wall_position
ground_position

function_add effect
function_hit enemy
function_hit wall → add effect, destroy grenade, bullet
function_life time
function_ground → add effect, destroy grenade, bullet

wall.obj
function_add effect

for complex graphics you could also add, another effect to the wall, using projectile last position also.

If you like this style pass the projectile position to function effect(projectile position), then tweek inside the function best angle.

This style is very similar to engine code. In my projects only use procedural style.

@JoeJ Ok, I'll start trying to implementing this myself now. Thanks for all your help!