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:
All of my bounding volumes are 3D AABBs
Tunneling may not be a concern, if significant performance can be gained by ignoring it
Need to support sliding (e.g. running diagonally into a wall)
Need to support colliding with things that are also moving on the same frame
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:
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.
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:
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.
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 its 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.
Alright, I've gone on a vision quest to try and understand what you all were telling me, and I think I get it!
Note to future people: the discrete algorithm (e.g. the overlap-based approach from the video I linked above) is nice in 2D, since you can come up with some heuristic for determining which axis to reject along (in the video, “use the previous overlap”). In 3D though, there doesn't seem to be a nice heuristic that leads to reasonable collision, so the swept approach seems to be more necessary. My original mistake was assuming that swept was only useful to avoid tunneling.
I've been implementing the swept approach from the gamedev article, and I was struggling to understand the algorithm until I found this comment that explained it in simple terms. Now that I understand the algorithm, I don't understand how the code from the gamedev article is implementing it.
The algorithm is:
For each axis, compute the time interval (entry and exit) where the boxes are intersecting.
If those intervals overlap and are within the 0 - 1 range, use the earliest time as your time of collision.
#1 is done clearly in the article, but #2 relies on this check:
// find the earliest/latest times of collisionfloat
entryTime = std::max(xEntry, yEntry);
float exitTime = std::min(xExit, yExit);
// if there was no collision
if (entryTime > exitTime || xEntry < 0.0f && yEntry < 0.0f || xEntry > 1.0f || yEntry > 1.0f)
{
normalx = 0.0f;
normaly = 0.0f;
return 1.0f;
}
This tests that the entry times are within the 0 - 1 range, but doesn't seem to actually check if the intervals are all overlapping. There's a note in one of the comments with a potential solution:
if (entryX < 0.0f) {
// Check that the bounding box started overlapped or not.
if (s.max.x < t.min.x || s.min.x > t.max.x) return 1.0f;
}
if (entryY < 0.0f) {
// Check that the bounding box started overlapped or not.
if (s.max.y < t.min.y || s.min.y > t.max.y) return 1.0f;
}
but it seems like a bit of a bandaid. Is the condition from the article + this bandaid the best way to do this, or is there a more straightforward way to test for step #2 from the algorithm?
Net_ said: Note to future people: the discrete algorithm (e.g. the overlap-based approach from the video I linked above) is nice in 2D, since you can come up with some heuristic for determining which axis to reject along (in the video, “use the previous overlap”). In 3D though, there doesn't seem to be a nice heuristic that leads to reasonable collision, so the swept approach seems to be more necessary. My original mistake was assuming that swept was only useful to avoid tunneling.
I think there is the same heuristic in 3D, but instead of tracking which previous dimensions overlap was greater zero, we would track which dimension had the largest overlap.
Using velocity instead previous states, the same decision can be made, but it feels easier to understand imo: E.g. we have a velocity of (2,-3,1), and there now is an overlap. The largest absolute velocity dimension is y, so we will resolve along y. Because the velocity is negative, we will resolve in the positive y direction.
I assume this would give the same result as the linked video, but avoiding a need to track previous states.
Net_ said: This tests that the entry times are within the 0 - 1 range, but doesn't seem to actually check if the intervals are all overlapping.
Some time ago i made a simple shortest distance collision code example for somebody else, and i have now added the code from the tutorial as well. It seems working, but i can imagine some special cases need more work. I have also added the raytracing method for comparison, showing it has the lowest complexity of all methods, assuming we need a ray - box intersection method anyway, which isn't complex either. Result is the same for most, but my method just finds the projected collision and does not care if the player would stop it's current movement before that. So even if you like the raytracing method, you have to work out the special cases there as well. (Which is no fun, so i did not do it for the example : )
(showing equal results from swept and RT methods)
static bool visBoxCollison = 1; ImGui::Checkbox("visBoxCollison", &visBoxCollison);
if (visBoxCollison)
{
static vec playerPos (3.9,0,0); ImGui::DragFloat3("playerPos", (float*)&playerPos, 0.01f);
static vec playerSize(2,4,1); ImGui::DragFloat3("playerSize", (float*)&playerSize, 0.01f);
static vec playerVelocity (2,0,1); ImGui::DragFloat3("playerVelocity", (float*)&playerVelocity, 0.01f);
static vec obstaclePos (4,0,0); ImGui::DragFloat3("obstaclePos", (float*)&obstaclePos, 0.01f);
static vec obstacleSize(1,4,1.3f); ImGui::DragFloat3("obstacleSize", (float*)&obstacleSize, 0.01f);
auto Print = [&](char *desc, vec v)
{
ImGui::Text("%s: (%f,%f,%f)", desc, v[0],v[1],v[2]);
};
auto Visualize = [&](vec pos, vec size, float r=1, float g=1, float b=1, float scale = 1)
{
MeshProcessing::AABox box;
box.minmax[0] = pos - size * .5f * scale;
box.minmax[1] = pos + size * .5f * scale;
RenderAABBox (box.minmax[0], box.minmax[1], r,g,b);
};
Visualize (obstaclePos, obstacleSize, 1,1,1);
Visualize (playerPos, playerSize, 1,0,0);
RenderArrow (playerPos, playerVelocity, 0.1f, 1,1,1);
static bool ResolveAlongShortestDistance = 1; ImGui::Checkbox("ResolveAlongShortestDistance", &ResolveAlongShortestDistance);
if (ResolveAlongShortestDistance) // ignoring previous states, velocity, and tunnelling
{
// calculate overlaps
vec overlap (0,0,0);
{
vec diff = playerPos - obstaclePos;
vec halfSizeSum = (playerSize + obstacleSize) * .5f;
Print("diff", diff);
Print("halfSizeSum", halfSizeSum);
for (int i=0; i<3; i++)
{
if (diff[i] > 0)
{
if (diff[i] < halfSizeSum[i])
overlap[i] = diff[i] - halfSizeSum[i];
}
else
{
if (diff[i] > -halfSizeSum[i])
overlap[i] = diff[i] + halfSizeSum[i];
}
}
Print("overlap", overlap);
}
// select smallest overlap
{
vec absOvl (fabs(overlap[0]), fabs(overlap[1]), fabs(overlap[2]));
Print("absolute overlap", absOvl);
if (absOvl[0] > absOvl[1] || absOvl[0] > absOvl[2]) overlap[0] = 0;
if (absOvl[1] > absOvl[0] || absOvl[1] > absOvl[2]) overlap[1] = 0;
if (absOvl[2] > absOvl[0] || absOvl[2] > absOvl[1]) overlap[2] = 0;
Print("minimal overlap", overlap);
}
vec resolved = playerPos - overlap;
Print("resolved", resolved);
Visualize (resolved, playerSize, 0,1,0, 0.99f);
}
static bool ResolveAlongSweptVelocity = 1; ImGui::Checkbox("ResolveAlongSweptVelocity", &ResolveAlongSweptVelocity);
if (ResolveAlongSweptVelocity)
{
using AABox = MeshProcessing::AABox;
using Vec3 = vec;
AABox boxPlayer;
boxPlayer.minmax[0] = playerPos - playerSize * .5f;
boxPlayer.minmax[1] = playerPos + playerSize * .5f;
AABox boxObstacle;
boxObstacle.minmax[0] = obstaclePos - obstacleSize * .5f;
boxObstacle.minmax[1] = obstaclePos + obstacleSize * .5f;
// https://www.gamedev.net/tutorials/programming/general-and-gameplay-programming/swept-aabb-collision-detection-and-response-r3084/
auto SweptAABB = [](const AABox &b1, const Vec3 &b1Vel, const AABox &b2, Vec3 &normal)
{
// find the distance between the objects on the near and far sides
Vec3 InvEntry;
Vec3 InvExit;
for (int d=0; d<3; d++)
{
if (b1Vel[d] > 0.0f)
{
InvEntry[d] = b2.minmax[0][d] - b1.minmax[1][d];
InvExit[d] = b2.minmax[1][d] - b1.minmax[0][d];
}
else
{
InvEntry[d] = b2.minmax[1][d] - b1.minmax[0][d];
InvExit[d] = b2.minmax[0][d] - b1.minmax[1][d];
}
}
// find time of collision and time of leaving for each axis (if statement is to prevent divide by zero)
Vec3 Entry;
Vec3 Exit;
for (int d=0; d<3; d++)
{
if (fabs(b1Vel[d]) <= std::numeric_limits<float>::epsilon())
{
Entry[d] = -std::numeric_limits<float>::infinity();
Exit[d] = std::numeric_limits<float>::infinity();
}
else
{
Entry[d] = InvEntry[d] / b1Vel[d];
Exit[d] = InvExit[d] / b1Vel[d];
}
}
// find the earliest/latest times of collisionfloat
float entryTime = Entry.MaxElem();
float exitTime = Exit.MinElem();
// if there was no collision
if (entryTime > exitTime
|| (Entry[0]<0.f && Entry[1]<0.f && Entry[2]<0.f)
|| Entry[0]>1.f || Entry[1]>1.f || Entry[2]>1.f)
{
normal = Vec3(0.0f);
return 1.0f;
}
else // if there was a collision
{
// calculate normal of collided surface
int d = 2;
if (entryTime == Entry[0]) d = 0;
else if (entryTime == Entry[1]) d = 1;
normal = Vec3(0.0f);
normal[d] = (InvEntry[d] > 0.f ? 1.f : -1.f);
return entryTime;
}
};
Vec3 normal;
float timeOfImpact = SweptAABB(boxPlayer, playerVelocity, boxObstacle, normal);
ImGui::Text("timeOfImpact: %f", timeOfImpact);
Vec3 playerImpact = playerPos + playerVelocity * timeOfImpact;
Visualize (playerImpact, playerSize, 0.5f,1,0, 0.98f);
// raytracing method:
AABox boxMinkovskiSum;
boxMinkovskiSum.minmax[0] = obstaclePos - (obstacleSize + playerSize) * .5f;
boxMinkovskiSum.minmax[1] = obstaclePos + (obstacleSize + playerSize) * .5f;
Vec3 ray = playerVelocity;
float mag = ray.Length();
if (mag > FP_EPSILON)
{
ray /= mag;
Vec3 rayOrigin = playerPos;
float ffd, bfd;
Vec3 rayInvDirection (1.f / ray[0], 1.f / ray[1], 1.f / ray[2]);
boxMinkovskiSum.DistanceRayFrontAndBackface (ffd, bfd, playerPos, rayInvDirection);
Vec3 playerImpact = playerPos + ray * ffd;
Visualize (playerImpact, playerSize, 1,0.5f,0, 0.97f);
}
}
}
