Incorporating walls, though seemingly simple, presents a few challenges.
Detecting that a character is colliding with the environment is simply a matter of checking for intersection with the triangle geometry. The next step is determining how to resolve each collision.
The typical approach to collision resolution is to iteratively push out a collider until it is no longer intersecting. We choose the triangle with which there is the most overlap and shift the character out along the shortest vector, or penetration vector, such that the character is no longer intersecting.
The direction of this vector will be the normal vector formed by the character position and the closest point on the intersecting triangle. The magnitude of this vector will be the penetration distance plus a small offset.
An offset is required to account for floating point precision error. Our offset should also be such that it allows us to reason something about the pushed out location. For instance, it’d be useful to ascertain that the location is within at most some small contactDistance of the intersecting triangle. We can choose an offset that’s half the contactDistance to guarantee this.
We evaluate and resolve intersections in this way until we eventually converge on a location where there is no more intersection. It’s worth noting that while this method will often converge, it is not guaranteed to. Therefore, we put a cap on the maximum number of iterations we make each tick.
If the method does not converge it can mean one of two things. One is that the max iteration cap per tick is set too low to converge. The other is that the character has moved into a location where they are boxed in and have no obvious way to exit. How you treat the latter scenario will depend on your particular game.
If a character was grounded prior to moving, snapping up or down should take higher precedence over penetration resolution. To illustrate why, consider a character moving in a set direction on some sloped ground. If the normal of the slope points towards left or right of the intended direction, the shortest-normal resolution would result in the character moving some unintended distance laterally.
As each iteration in a collision resolution loop may result in a change in the lateral location of a character, we should check whether the character can snap up or down to a grounded location at the start of each iteration. Only when there is no valid snapping result should we then use penetration resolution.
Directly applying the push-out method as described above may result in some undesirable behavior when the character intersects with walls that are not vertical.
Consider walls that slant upwards. If a character is grounded and moves into that wall, the upward component of the penetration vector will cause them to shift upwards and become not grounded. Over several game ticks this results in the character flipping quickly between grounded and not grounded states. Another issue occurs if a character is jumping and moving upwards. Over several game ticks the vertical component of the penetration vector will add up, ultimately resulting in the character reaching a higher jump peak than they would have had they not hit any walls.
All this is to say that the closest non-intersecting location may not be the one we want when implementing movement. What we may want is to find an intersection resolution which minimizes vertical oscillation.
One way to adjust for this is to keep iterating beyond the initial converged result. For example, if the result location after collision resolution is vertically above the target’s location, shift the result location down by some distance and run another set of collision resolution steps. By doing so, each repetition may result in a location with less of a vertical delta from the original target.