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.)

SM64 used 4 iterations in it's player character collision detection, and for normal play the four iterations were enough.

Net_ said:
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.

If you're always pushed back exactly in the direction you were trying to move, you won't have any sliding. You'll stick to walls. Imagine there's a large wall immediately below your character, and you move down and to the left into it, so your velocity is (-1,-1). You move from [0,0] to [-1,-1] and end up embedded into the wall, so the collision resolution uses your old velocity and pushes you back to [0,0]. You end up exactly where you started, even though where you want to slide along the wall to [-1, 0]. What you actually want, is to be pushed directly up out of the wall, not back from whence you came, so that you can slide along its surface.

There's also the problem that if you just reverse your last step, the character may be pushed back too far. If they start 0.2 units from colliding with the wall, and then overlap with it, when they get pushed back they'll end up 0.2 units away from the wall rather than touching the wall. That can feel bad for a reason that's difficult to express with words. You could collide with the wall and then change your angle of approach and move closer to it, which makes collision feel inconsistent.

Coil said:
What you actually want, is to be pushed directly up out of the wall, not back from whence you came, so that you can slide along its surface.

Yes, and i realize i did not really think about using velocity to go ‘backwards’.

One approach is to ignore velocity, but resolving the collision by moving along the ‘shortest distance’. Which does exactly what your image shows. The velocity would be used only to check if the player is still on the same side of the wall to prevent tunnelling.

Another approach is to go backwards in time to the point where the contact occurs, projecting velocity to the surface normal, and continue with that by the amount of left time:

Both methods would give the same blue box end result for the example.
The second option is more complicated, but more robust against tunnelling, and implementing friction can be easier. But if we had multiple moving bodies colliding with each other, it becomes very expensive to find the first collision and rolling back the entire collision to this point, then finding the next collision and repeating the process many times.
Another problem is: If we accidentally spawn a player to clip a wall, he has no velocity yet and the collision won't be resolved.

Not sure which method to recommend here. Both would work.

JoeJ said:
Not sure which method to recommend here. Both would work.

Personally i have used the shortest distance method when working on a physics engine or later in a mobile car game.

I have used the backtracking method only once, for a kind of breakout game. Maybe that's worth to mention.
The bricks and walls were all AABS. And the ball could go very fast, so tunnelling was an issue.
To keep it simple, i accepted to give the ball a collision shape of a box too. Borrowing from the Minkovski Sum idea, i have enlarged the bricks by the radius of the ball, and made the ball a point:

The blue box is extended by the radius to become the red box, so the ball can be treated as an arealess point. Then i can use simple ray tracing for the ball. If the ray hits a wall i just reflect it, but we could also project it to surface normal to get sliding. Repeat the ray tracing process until the ball traveled the same distance as the initial green velocity vector.
This was robust and quite simple to implement.

I guess following the quoted gamedev.net article would tend towards a similar solution, being a variant of the backtracking method.

Contrary, the Verlet paper i have posted is an example of the simpler ‘shortest distance’ method.