search

SPC-Some-Polish-Coders / PopHead

2D, zombie, action game made from scratch in C++
MIT License
116 stars 21 forks source link

Kinematic collisions broadphase #444

Open meyerzinn opened 4 years ago

meyerzinn commented 4 years ago

I was just looking through the code to see what sort of things I might be able to help optimize and I stumbled on the kinematic collision solver. It looks like it's performing a brute-force collision detection algorithm, which has a complexity of O(n^2).

Since all of the collision bodies are rectangles, it would be fairly trivial to integrate a broadphase algorithm to reduce the number of nearphase collision checks needed. This would become more important as you add increasingly sophisticated nearphase algorithms, i.e. detecting circle-on-rectangle (#443) or rectangle-on-polygon collisions.

PiotrGardocki commented 4 years ago

I was already thinking about collisions optimization and I have a plan to keep BodyRect pool sorted in some "chunks" to check only the limited amount of bodies. I will code that in a few days and check how much faster it is comparing to the current algorithm (it should be much better).

Another advantage that I want to take from specific components order is to make collisions calculations run concurrently.

meyerzinn commented 4 years ago

I'm going to try patching the collision detection systems to take advantage of EnTT's reactive systems. That could vastly cut down the number of entities processed without needing to change much code.

Czapa10 commented 4 years ago

@PiotrGardocki I think that we already have chunk collision optimalizations for static collisions. Don't Introduce this kind of optimalizations for kinematic collisions right now. You don't have enough information to make the right decision yet. So it would be premature optimalization and almost certainly waste of time.

Czapa10 commented 4 years ago

@20zinnm I don't know how Entt's reactive systems would help us in collision detection but if you think it will, you can give it a try.

meyerzinn commented 4 years ago

@Czapa10 I dug into it a bit. Though I think using the reactive systems would improve the performance, it alters the ECS paradigm and we'd probably see better gains by implementing a broadphase.

meyerzinn commented 4 years ago

Also, that particular EnTT API is undergoing rapid changes, so adding a code dependency there might become a headache later on if you try and upgrade the EnTT version.