Hello, I'm working on an MMO-y engine, with a large world and lots of players. I'm looking to upgrade my temporary collision algorithm to something more robust, and am getting lost in all of the different articles and options.

I need a solution that is as performant as possible (the more performant it is, the more players I can fit in a world). Here are my constraints:

1. All of my bounding volumes are 3D AABBs
2. Tunneling may not be a concern, if significant performance can be gained by ignoring it
3. Need to support sliding (e.g. running diagonally into a wall)
4. Need to support colliding with things that are also moving on the same frame
5. No need to support any complex physics, just simple collision detection and resolution

What would a good approach be for my situation? I've seen minkowski differences mentioned many times, as well as all sorts of “test each face”-style algorithms. I've also seen different approaches for e.g. how many times to iterate.

For future people, here are some relevant references:

https://web.archive.org/web/20220928164633/https://www.deengames.com/blog/2020/a-primer-on-aabb-collision-resolution.html​

https://www.gamedev.net/tutorials/programming/general-and-gameplay-programming/swept-aabb-collision-detection-and-response-r3084/​

https://blog.hamaluik.ca/posts/simple-aabb-collision-using-minkowski-difference/​

https://katyscode.wordpress.com/2013/01/18/2d-platform-games-collision-detection-for-dummies/​

Net_ said:
No need to support any complex physics, just simple collision detection and resolution

The problem is: Collisions across multiple, moving objects is complex physics.
But i see you can simplify quite a bit by ignoring the angular part and not having complex shapes.

Net_ said:
Need to support colliding with things that are also moving on the same frame

The linked gamedev article lists this as a limitation, because it can only handle dynamic vs. static.
But it's easy to use the same methods for two dynamic boxes, by treating one as static, and using the relative velocity for the other. Then you apply half of the computed collision displacement to both bodies (if they have the same mass). Seems a good article. I'd go with that.

Net_ said:
I've seen minkowski differences mentioned many times, as well as all sorts of “test each face”-style algorithms.

Introducing Minkowski difference just for AABBs is overcomplicated, and likely only good to explain the concept with a simple example.

Thinking about faces also is overcomplicated, since an AABB is just a range. Calculating overlap and the least displacement to separate is trivial, and we don't need vertices, edges or faces for that.

Net_ said:
Hello, I'm working on an MMO-y engine, with a large world and lots of players.

I see a potential problem: If many players from a crowd and bump into each other, the sharp corners of boxes cause an unpredictable discontinuity. As a player you can not see your corners, nor those of other players. But on collision, corners decide if things slide to the left or to the right. Not sure how bad this is, but think of it before you start the work.
It would be better to use capsules or cylinders for the players.

Net_ said:
Tunneling may not be a concern, if significant performance can be gained by ignoring it

That's irrelevant i would say.

To figure out if you need continuous collision detection or not, you need to know:
The maximum speed objects can have. (If you don't have a limit, you need CCD)
The minimal thickness of the walls in your game.

From that you can calculate if a player can tunnel through a wall in one frame or not.

Mostly CCD is necessary only for dynamic vs. static, but not for dynamic vs. dynamic.

JoeJ said:

I see a potential problem: If many players from a crowd and bump into each other, the sharp corners of boxes cause an unpredictable discontinuity. As a player you can not see your corners, nor those of other players. But on collision, corners decide if things slide to the left or to the right. Not sure how bad this is, but think of it before you start the work.
It would be better to use capsules or cylinders for the players.

Players won't be able to collide with other players, only the world geometry and any non-player entities that have been given collision. I'm thinking of simplifying that further and saying “if you move a non-player entity that has collision, weird things may happen”, reducing my scenarios to dynamic vs static in all cases.

It sounds like simple overlap and displacement is the way to go, thanks for clarifying that. I watched this video which is a primer for that approach, but it doesn't go fully into the math. I think I'll be able to figure it out though, I just have a few more questions:

1. When two boxes overlap, the video mentions using the last frame's overlap to determine the response. In my case, since only one box is dynamic, can I just use the inverse of that box's velocity to resolve the collision in 1 iteration? I assume there's some issue with that since none of these resources mention it.
2. Assuming I can't use the inverse velocity, in 3D do I need to do 3 iterations of each collision resolution process to be sure that the box is no longer colliding along any axis? If sliding is implemented, do I need to do more iterations?

Net_ said:
can I just use the inverse of that box's velocity to resolve the collision in 1 iteration? I assume there's some issue with that since none of these resources mention it.

Yes it should work. At least if the actual velocity does indeed tell where the object came from.
This is not necessarily the case, especially if we use some hacks. But i would be very optimistic.

Btw, there also is a simulation approach which does not use velocity. Instead it stores the last position and calculates velocities from that. It's likely to loose energy, which is better than raising energy, and it's pretty stable. I really liked it for it's simplicity: https://www.cs.cmu.edu/afs/cs/academic/class/15462-s13/www/lec_slides/Jakobsen.pdf​

Net_ said:
Assuming I can't use the inverse velocity, in 3D do I need to do 3 iterations of each collision resolution process to be sure that the box is no longer colliding along any axis? If sliding is implemented, do I need to do more iterations?

No. No matter how many dimensions, you only need one iteration to resolve collision between two objects.

But if more objects intersect each other, generally more iterations are needed.
However, as long as the overlap is minimized each frame, it's often good enough to resolve over time, instead resolving quickly using many iterations. In practice overlap is no problem as long as it does not ‘grow’.

You don't have multi body problems if players can't collide each other, so if you need iterations at all, it won'[t be many.

(Talked about that just recently at the bottom of the ‘obstacle avoidance using vector approach’ blog post, on top of the site.)