Aug 26

Written by:
Thursday, August 26, 2010 

 

Yet another blog post about character controllers for 3D games, and this time we will talk about the actual implementation.

Kinematic Character Controller Using Discrete Collision Detection

Here is how the character controller in our Character Controller Example works:

Capsule Shape

The character is represented as a an upright capsule that does not rotate:

A capsule shape has the advantage that the lower spherical cap smooths up/down movement when it moves over small obstacles or over stairs. Still, an additional smoothing is desirable in many cases (which is not supported in our character controller example).

The ingredients of our character controller are the routines Slide(), StepUp() and StepDown().

Slide()

The basic routine in our character controller is called a slide. It takes a desired position and computes a valid, non-penetrating position near the desired position like this:

The capsule is set to the desired positions and we detect all intersections. The collision detection returns all contacts at the desired position, including contact positions, contact normal vectors and penetration depths. Each contact indicates that we have moved into a solid object - we have reached a limit of the allowed movement space.

For each contact found we store a bounding plane that represents that movement limit. If the capsule touches a wall, the bounding plane is parallel to the wall surface. If the capsule touches an object like a sphere, the bounding plane is parallel to the tangential plane at the contact point.
All bounding planes together limit the allowed space in which the capsule can move.

Now, that we have a description of the allowed space in which the character can move, we compute the allowed position closest to the desired position. We do this by a simple iterative process: If we have no bounding planes or the desired position is in front of all bounding planes, we are done. If the desired position is behind a bounding plane, we project the position onto the surface of the bounding plane. The new position is checked against the next plane. If it is behind the plane it is projected onto the surface. The new position is checked against the other planes, and so forth.

This is done in a loop until we have found an allowed position in front of all bounding planes.

Once, we have found the new position, we set the capsule to the new position and detect all intersections. It is possible that we find new bounding planes that we add to the set of existing bounding planes. We repeat the process above until we have a new position that does not violate any bounding plane.

(Side note: The above problem is very similar to Linear Programming. The bounding planes describe the convex polytope of the feasible space and our objective is to find an allowed position near the desired position.)

StepUp()

The StepUp() temporarily changes the current capsule position: The step height is added and the capsule is moved forward by the half capsule width. If there are forbidden contacts at this position, the temporary position changes are undone. If there are no forbidden contacts, the up-stepping was successful: The new capsule position is the old capsule position plus the step height.

StepDown()

Down stepping is like a slide to the current position minus the step height - but the movement is only committed if the movement stops at a position with a bottom contact. If the capsule does not find a ground contact within the step height, then StepDown() does nothing because the character is simply falling.

Move()

CharacterController.Move() is the public method that is called each frame. It combines all previous methods like this:

First, we Slide() to the first obstacle. At this new position we try a StepUp(). If the StepUp() was not successful we finish the Slide() to the desired position. At the end we try StepDown(). And done.

This is a very coarse description of the process. More details, including the handling of gravity, jumping and slope limits can be found in the example code (contained in the DigitalRune Geometry package in the Download Area).

Kinematic Character Controller Using Continuous Collision Detection

The current public version of DigitalRune Geometry (v1.1) does not support Continuous Collision Detection (CCD). So our Character Controller Example does not use CCD. The new DigitalRune Geometry (v1.2, not yet released) supports CCD. CCD computes the first time of impact of an object that moves from position A to position B.

With CCD we can make a few modifications to Slide() and StepDown(). We compute a bounding box that includes all possible end positions of the character and get all objects in this bounding box. Then we compute the first time of impact and move the capsule to this position. We get the contact normal at the first time of impact and project the desired position onto the tangential plane of the contact. Next, we continue to slide to the new desired position or the first time of impact, and so on.

I think the PhysX character controller operates like this - which you could check if you are an Nvidia PhysX developer because the PhysX SDK contains the character controller source code. Or you can check it here, for example:

http://www.assembla.com/code/pxcode/subversion/nodes/PhysX/SDKs/NxCharacter/src?rev=8
(Is it allowed to make code of the PhysX SDK public like this!?)

Dynamic Character Controller

Well, we prefer kinematic character controller, so our dynamic character controller experience is limited. We have experience with one third party dynamic character controller using ODE and it demonstrated horrible stability. Maybe that was bad luck because we have heard from other developers that they have implemented dynamic character controllers with great success.

Usually following steps are involved:

• Create a rigid body with a capsule shape.
• Make sure the capsule stays upright with any of these methods:
  • Set the correct values of the inertia tensor to infinity if this is supported by your physics engine.
  • Some physics engines have a feature to lock rotations of a body.
  • Use a constraint, e.g. an angular motor, that keeps the capsule upright.
• Cast a ray from the bottom of the capsule to the ground to find the height above the ground.
• Apply a force to keep the capsule floating above the ground.
• ...

I remember several discussions in the ODE mailing list. If you are interested, you can search the mailing list archives.

Related Posts

• 3D XNA Character Controller Example,
• Character Controller Requirements
• Kinematic vs. Dynamic Character Controllers

We hope this information is helpful. If you have any questions or improvement ideas, please let us know in the comments.