I have started rewriting my game engine, and I’ve just written a de-collision algorithm for objects. It runs purely through brute-force, using no space-partitioning. In my opinion, this is a good demonstration of what’s possible through DoD and modern C++. The code for the decollision algorithm will be presented at the end, but here is the associated video: ( The black boxes at the begining are lighting issues which resolve shortly)
When the video starts, the 5000 objects are alll intersecting multiple other objects, and they slowly vibrate outward until settling and causing no further collisions.
Normally in a game, you want things to collide as little as possible, using pathing and collision-avoidance methods. When things colliide and intersect, you must undo this and that tends to propagate a wave of decollision through crowds, which is observable in the video. This is the worst-case scenario. In the past, this problem is mitigated using some sort of space-partitioning method to reduce the amount of collision comparisons in addition to avoidance methods. In this example, however, there is no such space partitioning and it is entirely brute-forced using mutlithreading and some Data Oriented concepts.There are further improvements that could be made still to this simple method. The de-collision routine works in real time mostly, and the performance problems in the video have more to do with the 5k lights.
Using a collision-avoidance algorithm of some sort is far more performant than using a dumb decollision algorithm like the one used in this video. That is easy to do, too, since the objects ultimately will be managed by AI and other systems, they should only rarely collide if ever.
The code in the decollision routine is very simple and compares all 5000 objects to all other 5000 objects and modifies their position each time a collision is detected. It is implemented fairly simply using DOD and modern c++. I am going to present this code as a snippit to go with the video but will not describe it much as it is still being developed. The main things that you may notice are the parallel for loops, and in them, looping over *iota (misspelled in code atm) indexes which is a DOD design I’m trying out. I am going to try using a mutex rather than an atomic since atomic seems to be problematic in this algorithm.
void RtsObjectManager::decollide() {
std::vector< AtomicWrapper<Ogre::Vector2> > collisions; collisions.resize(mObjects.size());
std::for_each(std::execution::par_unseq, mAtoiIndexes.begin(), mAtoiIndexes.end(), [&](auto& ai) {
auto& p = mObjects[ai].mPosition;
collisions[ai]._a = { p.x, p.z };
});
std::for_each(std::execution::par_unseq, mAtoiIndexes.begin(), mAtoiIndexes.end(), [&](auto& ai) {
auto& a = mObjects[ai];
Ogre::Vector2 ap = collisions[ai]._a.load();
Ogre::Real ar = a.mTemplate->m2DRadius;
std::for_each(std::execution::par_unseq, mAtoiIndexes.begin(), mAtoiIndexes.end(), [&](auto& bi) {
if (ai == bi) return;
auto& b = mObjects[bi];
Ogre::Vector2 bp = collisions[bi]._a.load();
Ogre::Real br = b.mTemplate->m2DRadius;
Ogre::Real dist = ap.distance(bp);
if (dist < ar + br) {
//collision
//push each away
Ogre::Vector2 dir;
if (dist == 0) {
dir = { 1.0, 0 };
dist = 1.0;
}
else
dir = (ap - bp);
dir.normalise();
dir *= dist;
ap.x += dir.x; ap.y += dir.y;
collisions[ai]._a = ap;
bp.x -= dir.x; bp.y -= dir.y;
collisions[bi]._a = bp;
}
});
});
std::for_each(std::execution::par_unseq, mAtoiIndexes.begin(), mAtoiIndexes.end(), [&](auto& ai) {
auto& a = mObjects[ai];
Ogre::Vector2 p = collisions[ai]._a.load() ;
a.mPosition.x = p.x;
a.mPosition.z = p.y;
});
}
Spot C++ 