I'm new to game development, and I'm trying to write a kinematic character controller that handles the movement of my character.
I‘m having some problems working on the behaviour when the character hits a wall or other obstacles. My expected behaviour is simply illustrated below:
So when the character moves along the green arrow and hit the wall, it will be redirected to a reflection direction indicated by the red arrow, which is roughly parallel to the wall surface.
With a flat and smooth wall surface, I got the expected behaviour, the problem is whenever the character encounters bumpy surface or arrives at the corner of the wall, the reflection direction results tend to bounce between the surfaces for a short period of time and cause the character to jitter. The unstable reflection directions look something like this:
I'm guessing this kind of problem should be quite common for character movement, not only for walls but for uneven ground as well? So I wonder how the game engines handle this problem, is there any classic solution or smoothing algorithms that can reduce the jittering artefact?
Any tips would be appreciated, many thanks in advance.
So first I'm assuming by your picture you are sweeping a sphere, capsule or ellipse. If you are doing this some other way I can't answer.
I had a similar problem. What I ended up doing is implementing the concept of “touching” a surface. For the purposes of this explanation, I'm going to assume you are using a sphere, but it works the same with a capsule. So, in addition to the collision sphere, I have a slightly larger sphere that defines when you are simply touching geometry. When you are touching something, I add it to a list of touching objects. This list is cleared when you move. After a collision I move collision geometry from the collision list to the touching list. You also check this list just before you move since you can't move into the geometry.
So now let's say you reach a corner. You hit one plane (line or vertex) and then get pushed into another, like with a little valley or something. Since each plane is pushing you into the other you would be at a deadlock, even though technically you should still be able to move. In this case I take pairs of planes in both lists (touching and collision) and do cross products to find a new way I can go. There will normally be only one combination, but technically with complex geometry there could be more. I check these verses the original direction I'm trying to move and flip the result of the cross product if necessary, so I don't move backwards. If there is more than one valid combination, I take the one closest to the way I'm trying to go. I now have my new travel vector which doesn't collide with either plane, so there is no jittering or deadlock.
Edit: I wrote dot product before when I meat cross product. It's fixed now.
zzaustin said: So when the character moves along the green arrow and hit the wall, it will be redirected to a reflection direction indicated by the red arrow, which is roughly parallel to the wall surface.
I would argue the resolved direction should be exactly parallel, otherwise you risk to move into another wall, increasing the chance of jitter.
So basically you project to the surface. The red (resolved) line can be shortened to get a friction effect, but it should not be longer than the projection, to avoid adding energy.
To avoid drifting deeper into a narrowing corner, i've had success by summing up all simultaneous projections, which could work like this:
The red and green vectors project to the colliding face. Their summed average gives the short black vector. Applying this as displacement at the averaged contact point will not guarantee a state without penetration, but it should converge towards that after multiple frames. Drift into solid space or jitter should not happen.
Another method which is more precise is to resolve collisions in order:
Here we can just bounce the ray around until we get the same length as the intended but cut trajectory. For multiple dynamic bodies such method becomes too expensive very quickly, but for static geometry it's fine.
A related, useful concept is to use Minchowsky Sums, so you can treat the character as a simple point moving along a ray. To achieve this, you extrude the static geometry by the shape of the player, which is simple if it's just a sphere for example:
A related, useful concept is to use Minchowsky Sums, so you can treat the character as a simple point moving along a ray. To achieve this, you extrude the static geometry by the shape of the player, which is simple if it's just a sphere for example:
I think in general this is what you are doing anyway with basic sweeping. You move the planes out, edges turn into cylinders and points turn into spheres.
@Gnollrunner Thanks a lot for taking time to answer the question, a little bit of following up question on this part:
Gnollrunner said: In this case I take pairs of planes in both lists (touching and collision) and do cross products to find a new way I can go
I'm not sure what is the detail of implementation on your side, like which vectors do you take to do cross products and such, but does it basically revolve around averaging out info based on surface normals, and try by all means to find a middle direction along which you will less likely to collide with both walls? Maybe something similar to what JoeJ proposed in his answer about “summing all simultaneous projections”?
@JoeJ Thank you very much for such variety of tips!
JoeJ said: A related, useful concept is to use Minchowsky Sums, so you can treat the character as a simple point moving along a ray.
I'm afraid I'm not quite following up with this concept, I kind of get that once we extruded the static geometry by the CCT shape, then the character shape is sort of reduced to a point, but what do we do afterwards? Do we still do sweeps with the shape, or do we switch to raycast in some way? And how all these is related to the jittering situation?
Can you elaborate on this a little bit? Really appreciate it.
I'm not sure what is the detail of implementation on your side, like which vectors do you take to do cross products and such, but does it basically revolve around averaging out info based on surface normals, and try by all means to find a middle direction along which you will less likely to collide with both walls? Maybe something similar to what JoeJ proposed in his answer about “summing all simultaneous projections”?
Sorry, I missed a few details. Yes it's the cross product of the surface normals. However, in the case of edges and vertexes you don't have surface normals. So again, when colliding with a sphere, what you use is a normalized vector from the contact point of said sphere to its center. For a face this turns out to be the same as the surface normal. But this way also gives you collision vectors for the other geometry.
As for being “less likely to collide with both walls” (or other geometry), it is in fact “guaranteed” not to collide with them. This assumes no rounding errors. In practice you should put some slop in the calculations. One way to do this is add a small bounce in the response vector. You'll have to play around with it and see if you need it.
Also keep in mind that you can't just do collisions with faces (perhaps you already know this). If a face collision fails, you may need to check its edges and if that fails you need to check its vertexes. Since edges and vertexes are shared between faces, if you want to optimize you can keep track of which ones you have already checked so you don't check them again. This may or may not be worth it depending on if you are using multiple threads.
zzaustin said: I'm afraid I'm not quite following up with this concept, I kind of get that once we extruded the static geometry by the CCT shape, then the character shape is sort of reduced to a point, but what do we do afterwards? Do we still do sweeps with the shape, or do we switch to raycast in some way? And how all these is related to the jittering situation? Can you elaborate on this a little bit? Really appreciate it.
The Minkowsky Sum approach would be useful for example in a Billiard game. All balls have the same radius, so you could precompute the extruded geometry of the table by the radus. After that the sweeping collision tests become much easier, because the balls become just points. Simple raytracing is guaranteed to find all collisions during a timestep in order. Contrary, if you use the real table geometry and spheres for the balls, raytracing is not enough. You would need to cast the sphere against the faces, which is hard if the ball is in motion. You could bound the trajectory with a capsule to find potential collisions, but then it is still hard to find the exact time of collision. So yeah, this is more useful for continuous collision detection where the goal is to prevent tunneling of fast objects to walls.
Jitter is another problem, more noticeable at low speed or at rest. The reason is usually a forth and back bouncing caused by multiple contacts. We resolve penetration with the left wall, but this resolve increases penetration with the right wall. We resolve the right, only to penetrate the left again, and so forth. That's your problem i guess. The solution is to resolve all penetrations at once, e.g. by summing them up and applying them as a single displacement, which then will minimize all penetrations with all walls. It might not resolve penetration completely, but it is enough to minimize it. A little bit of penetration is not problem, while a little bit of jitter is.
Another useful tool to reduce jitter is damping. So you can just resolve some percentage of penetration per step, which usually helps.
Here again a picture, but this time using a sphere not a point:
You calculate the displacements to project the sphere out of each wall (red and green arrows), then sum them up (black arrow), and apply this sum (times a damping factor of say 0.9) to displace the sphere. You can imagine it will take quite a lot of steps until the sphere seems out of the corner, and the behavior is somehow soft, but this might be what you want to feel good, stable and robust, and if softness is a problem you can do multiple iterations to make it more rigid.
To look at it differently, our goal is to move the sphere out of the corner with minimal displacement. So for the solution the ball will touch both walls, but not penetrate them. But with complex geometry this becomes a very hard problem to solve precisely and in one step. So my proposal is to solve it in a simple but iterative way, and we do not necessarily get the solution within one frame. We just need to generate more pushing back then the player can push into the corner.
The method behaves well even if we would put our ball into a room that is smaller than the ball. In this case, the ball will converge to a state where the penetrations with all walls have the same size.
The solution is to resolve all penetrations at once, e.g. by summing them up and applying them as a single displacement, which then will minimize all penetrations with all walls. It might not resolve penetration completely, but it is enough to minimize it. A little bit of penetration is not problem, while a little bit of jitter is.
Another useful tool to reduce jitter is damping. So you can just resolve some percentage of penetration per step, which usually helps.
Here again a picture, but this time using a sphere not a point:
We are apparently giving advice about two different algorithms. I have never worked on an actual “physics engine”, but I have read that you do in fact have penetration and then resolve it afterwards. That's not the case with the sweeping algorithm used in many character controllers. You should never get into the geometry at all. In fact, it's a bug if you do. One cool thing about sweeping is you can move as fast as you like, and you can never move through thin geometry. The downside is it's generally not for multiple moving objects colliding with each other, although you can handle basic character collision.
To the OP: If you are doing something more akin to a physics engine you should probably ignore my posts. However, sweeping spheres and/or capsules does work very well for a character controller and it's very smooth once you get the bugs out.
