Advanced Character Controller Physics

Gamepro5 - 1/19/2023

Description

This paper is about the theory behind implementing a comprehensive, multi purpose, and low level character controller. It is considered low level because all it needs from a physics engine is a collision detection algorithm that reports collision normals. I will be using Godot 4's "move_and_collide()" function, a method native to the PhysicsBody3D class. Knowledge of vector algebra is required to understand this paper.

Chapter one: Lerping xz velocity towards the input direction

The first thing we must do each frame is figure out what the user wants the velocity to be. This is done by taking the input direction (sometimes called wishdir or dir) and comparing it to our current velocity. This comparison part is useful for deciding which linear interpolation (lerp) function we want to use and what weight the lerp function will have (acceleration). For instance, my movement system has less acceleration when the player has the “on_floor” flag set to false (from the previous frame) than when the player is on the floor. When on the floor, however, we need to make sure the player isn’t also on a wall nor that the dot product between the xz velocity and the wall collision normal is greater than or equal to zero. This prevents climbing up walls, because it will refuse to analyze player input if the direction is into the wall. The rest is just playing around with dot products of velocity and direction until you find something that feels right. The dot product helps you control things like air strafing sensitivity. You can also save the magnitude of the velocity before using lerp to only lerp the rotation.

Chapter two: On the ground or in the air?

Our second order of business is to do the mother of all collision tests. The "ground_check" This is a simple check that gives a general idea of if we could be on the floor, or if we are in the air. If ground_check ends up reporting that there is a collision, that's all we need to know to proceed with the "on ground" procedure. Note that "on ground" doesn't necessarily mean we are on the floor: we could be on a sloped wall that is too steep to be considered a floor. Once we have established that we could be on the floor, we do a more refined check called “snap_ground_check”. This check tests if moving ever so slightly in the down direction reports a collision. If this isn’t true, we actually (not a test) move down with a large magnitude. This will “snap” us onto the ground, and will not run if it doesn’t need to. Once that is resolved, we can proceed with analyzing the collision normals from this ”snap_ground_check”. Before we move on, however, it is important to note that this whole “ground_check” algorithm will not run if the “snap_vector” is (0,0,0) (aka does not exist). This is because when we are jumping, we apply an impulse of something (0, 7, 0) to our velocity and instantly set the snap vector to (0,0,0). That way, we won’t be snapped to the ground on the next frame when we are trying to jump. The “snap_vector” will only be set to (0,-1,0) inside the code that executes when we are not on the ground. If those simple movement collisions end up detecting a floor normal, we know we can set it to (0,-1,0).

Chapter three: Evaluating the floor normal

Assuming we are in the “ground_check = true” part of the master conditional statement, we must evaluate what floor normal we use. Our “snap_ground_check” will return anywhere from 1 to 3 collisions. Collisions are objects that contain a collision_normal. I’m going to assume you know what a normal is. It doesn’t mean the same thing as normalizing a vector. It is basically a line of magnitude (length) 1 that is perpendicular to the surface. This is vital. With this information, we can deduce if a surface is within the range we consider to be a floor and not a wall. We can simply find the angle between the normal and the up direction (0,1,0). If this angle is less than or equal to our max floor angle, the normal is representing a floor. If we find a normal that satisfies this, our job is easy and we can move on to the next step. If all the normals detected fail this (are considered walls), we have a bit more work to do.

Our first order of business for a situation like this is to sum up all the wall normals and normalize the result. Normalizing is setting the vector’s length (aka magnitude) to 1. With this strategy, we basically took the average direction of all the normals we are colliding with. This is useful for situations like this:

It’s important to note that I consider a slope that is too steep to be considered a floor to be a wall. Anyhow, as you can see, taking the average is important. If we are wedged in between two steep slopes, taking the average would give us an angle that represents a floor. That way we don’t get wedged and stuck in edge cases like this and can move about freely along the newly constructed interpreted floor normal.

Now what happens if one of the walls we are colliding with is perfectly vertical (the normal has no y component). What happens then? The code theoretically should work with that edge case, but the issue is the normal of that wall wouldn’t be reported because our snap_ground_check only checks in the (0,-1,0) direction. To fix this, we can add another case. If we don’t find a floor normal and we only have wall normals and the wall normals don’t average out to be a floor normal, we do one last check. We do a test move in the direction of the average wall normal that we found to be still too steep, but remove the y component. If this collides, we redo our average normal with the newly found wall normal and re-evaluate if the average normal defines a floor. At the end of all this, we can correctly evaluate if we are on the floor or should slide down a steep slope (aka wall).

Chapter four: Adjusting the velocity vector based on collision normals

We are nearing the end of our journey. This final step is where we adjust the velocity we inputted in chapter one. First, we do a test move in the direction we plan to move. If there are no collisions, we can proceed and actually move there. If there are any collisions, we must do a conditional statement chain. We first filter through all collisions that this frame detected using a for loop: We keep an average collision normal for ceilings, floors, and walls. We then go through them in a specific order and adjust velocity for each of them, given they exist. First we process ceiling, then wall, and finally, floor. Floor is considered here because if we collide with a slope that we consider to be a floor, we should treat that surface as a floor and travel up it.

For ceiling, since we know that floor_normal isn’t zero, we can simply take the cross product of the floor_normal and the average_ceiling_normal. If we take that resulting vector and multiply it by the dot product of our velocity and whatever that resulting vector was, we can get a signed tangential projection of our velocity along the floor with respect to the wall. This is necessary because the floor might not have a normal of (0,1,0); it might be a slope.

Walls are handled in the same way as ceilings, but with one additional step. If we are colliding with a wall, we need to check if that wall is the step of a staircase. We can do this just like Quake (1996). The paper describing this complex algorithm can be found here. If we resolve that we haven’t stepped up a stair, we can assume there isn’t a stair and that it is an ordinary wall. We proceed to do the same cross and dot product process as for ceilings, but with the average_ceiling_normal being replaced with average_wall_normal.

For floor, this one really depends. I like movement systems where slopes have zero effect on x and z velocity. Most games seem to agree. If you look at the upper corner of a slope and walk forward and backward, you should always be looking at the corner of that slope. To accomplish this, I adjust the y velocity based on the following:

vel.y = (-floor_normal.z*vel.z-floor_normal.x*vel.x)/floor_normal.y

This is the dot product formula moved around to isolate the y component of velocity. We don’t change the x or z component, and only move the player up or down based on the xz velocity components. It’s that simple! All we need to do it make sure that floor_normal.y is not 0. If the y component of a normal is 0, it means it’s a perfectly vertical wall. There is no possible way to adjust the y component of the velocity to keep x and z the same in this situation, because you would have to travel infinitely far. This is also called a divide by zero error, where the solution is infinity. Not good if you want to not be sent into the NaN coordinate shadowrealm. If your max floor angle is not 90 degrees, this would never happen. Just in case, though, a simple conditional statement should prevent your banishment into the shadowrealm.

Important Credits!

This paper is based off the advanced character controller I developed from scratch for my game. If you would like to see the code for it, here is a simple project that contains just the movement code. The linked paper implementing stair stepping was not made by me, and the entire tracing algorithm was simply ported from GDScript to GDScript 2.0 (the new GDScript for Godot 4.0) by me. The original author of that algorithm is Btan2. Certain simple vector math concepts were brainstormed with some help from various friends. Everything else was made 100% by me over the span of about two years.