Hand-made Character Controller w/ Capsule-based CCD

[trophyN4]

Hi everyone,

Mostly title, but it usess continuous collision detection (CCD) for capsule colliders (the pill shape in red). No shapecasts/raycasts/queries were used

Videos/Examples

This shows basic movement, jumping, and just general the acting of gravity + control

Here is colliding with a wall (and floor)

For better or for worse, it is a true capsule shape, so it has some interesting interactions with shapes

It works walking up slopes, I am still working on a way to reduce the “hopping” motion when going down though—any suggestions are welcome

Thanks to the capsule shape, it can work with stairs too

Here it traverses (more or less) complex geometry, aka walking across the monkey—still working towards making it less jarring though

Admittedly, it does need some work that I specified beneath a few of the examples. Beyond that, I went ahead and replaced the camera system and the inputs “just because” (I was reinventing the wheel, might as well make the whole car). Neither of those work extremely well. The camera doesn’t have a zoom feature yet (easy to solve) and doesn’t have collisions (difficult to solve). The movement doesn’t have acceleration or any really cool techniques like coyote time—but I’ll add all that in the future.

There will be a severe lack of visuals here on

How I made it

I used this paper for the idea: Continuous Collision Detection of General Convex Objects Under Translation by Gino van Bergen

To summarize, it says that you can “inflate” or “deflate” an object by another and still perform operations. It’s hard to make a capsule sweep through space, so we try to reduce that problem to be between a ray (position and direction in space) and an “inflated” environment

A bit longer, if I look for the intersection between shape A and shape B, I might set up an equation like A = B. I might want to move B to the other side, to make A - B = 0. To add or subtract shapes, you can use Minkowski addition - Wikipedia. This is the idea behind a discrete collision detection algorithm called GJK, that tries to find if A - B = 0 through optimization. In the context of Gino van Bergen’s algorithm, he has A + O + tD = B, where O + tD represent a raycast (which in our case is player velocity). He subtracts over O + tD = B - A, where A is the capsule (and also symmetrical, so -A = A). So we have O + tD = B + A. We can cache B + A assuming the capsule doesn’t change in shape for every shape B in the environment (since it is no longer what is moving, rather the “O” for origin of the ray).

Anyway, the search for t is just a raycasting problem, so after we “inflate” the environment (sum every shape and the components of the capsule together, notably ball and cylinder) we finally find the time of impact (TOI) between the capsule and whatever geometry. All of this is represented in code for exact precision (ex/ cylinder being a radius and two vertices, ball being a radius and point)

If anyone has any follow-up questions, feel free to ask

Details I found interesting

1. I used a basic grid architecture to find potentially colliding objects faster (aka the broad phase)
2. Uses buffers since there is a LOT of data that is unchanging (given I am working in a static environment)
3. Gives a lot of flexibility given on-demand collision detection. For example, giving the server authority to run its own calculations (A part of me died after I saw Roblox was coming out with server-authoritative characters, but surely their system is better than mine)
4. Having continuous collisions makes the character not susceptible to issues like tunneling (swept), and also has more accuracy in where it “finds” the collision). Admittedly, these are uncommon issues to have given the character isn’t often going mach 5
5. Has collide-and-slide built in, like you can see when the capsule collides with the wall in the second example it doesn’t just “stop.” (Even more primitively, it uses to walk across the floor since the floor counts as one collision already)
6. Again, uses capsules—I think Roblox uses boxes (don’t quote me on that)
7. While the monkey is represented by capsule-inflated-triangles (leading to some redundancy or balls/cylinders/faces hidden by others), primitives like the boxes are manually defined to ensure there are no hidden colliders. I might work on convex hulls w/ convex decomposition for more optimized complex geometry that needs less precision, but as it stands now thats low priority

Thanks for reading

TLDR: watch the videos, lmk what I could do to improve character movement

edit 1: i messed up notation

[Threejack (Chuddy)]

nice dude. i’ve been trying to make something like this for my arena fps game for years but could never figure it out, i just don’t have a good enough background in mathematics ig

[trigophi]

This is very interesting. Do you have any pointers for where I can learn more about applying mathematics like this?

[trophyN4]

Hi, thanks for reaching out! To learn about applying mathematics, I hate to give the cliché response but it’s a matter of practice. Despite that, for someone just getting into it I suggest:

For learning new math, I suggest blogs, youtube, and formal papers (in that order, but we all learn different). For example, Cool Algorithms: Spatial indexing with Quadtrees and Hilbert Curves - Nick’s Blog is an interesting one. Youtubers like 3Blue1Brown (his Essence of Linear Algebra is incredible), Reducible, and Sebastian Lague have stunning visuals and explain math in a programming setting that might ease following along. Past GDC presentations are also a gold mine. Papers are self-explanatory, but I find them often verbose and difficult to implement

For choosing practice problems, select those that are easily testable. I find that geometric problems (ones concerning 3D space) satisfy this best, since Roblox Studio works in a 3D environment so you can just model out points, shapes, lines, or triangles with sphereHandleAdornments, parts, lineHandleAdornments and editableMeshes in the environment to test results. For example, with my capsule collisions I need to compute the intersection of a ray and a plane. I was able to physically test edge cases by moving a part in the environment to see if it would work

A standard problem that I like is making a “pet” circle around your character (like in those simulator games). There are a few problems you can tackle with it, like whether the pet should orbit around you or stay in one spot, whether they should align themselves to your facing direction, how to evenly space out multiple pets, avoiding collisions with surrounding geometry, smooth interpolation when moving/rotating (LERP, SLERP), etc

[Threejack (Chuddy)]

https://streamable.com/wugskg

tried my hand at making my own capsule collider. it works okay but i get this jitter when i walk into a corner. i am using shapecasts which only return one collision point so im guessing thats probably why

[edenojack]

In order to let your capsule walk up and down slopes/stairs properly, much like ladders, you are going to need to start looking at the shape of the geometry and your direction on it.

Consider a ramp.
Going up, we are moving into the ramp, and from this collision, being pushed up. Ideally, the capsule has been moved into the position we would expect to be were we moving up a ramp. Seemingly, attached to the ramp itself.
Going down, however, we no longer benefit from this. Rather than moving into the ramp, colliding, and being pushed up, we are instead moving away from it and subsequently fall back onto it. So now it’s not just a collision, we’re looking at gravity and how long gravity will take to make you fall back on to touching the ramp.

One method, and will probably be the most effective, is to simply try and capture the next step in the direction of movement for the capsule. If we determine that the next step is on a slightly different height, rather than moving in the global 3D axis, adjust the axis so you are moving along a plane between those two points.

What does this mean?
It means that now, going up/down steps is going to feel a bit smoother. You are following a “natural” path along a slope, rather than continuously colliding or falling onto it. You should also notice that you’re able to traverse stairs without jittering up/down them, they will behave like a ramp.
Continuing along this, if you’re using this capsule purely for “part”-based geometry, you should be able to use this method to determine how to move about terrain properly.

Typically, a simple raycast would work here. If you really want to avoid doing rays, it might be worth finding a way to consider the current and next “surfaces” your capsule is and then will be standing on, then going from there to create a plane between those two points.

AFAIK, there are some games that have stairs that really just have invisible slopes in them because of how much of a faff this is to solve for.