Using character controller in v1 to be easily upgradeable to v2

Discuss any questions about BEPUphysics or problems encountered.
Post Reply
Frooxius
Posts: 12
Joined: Tue Aug 16, 2016 4:01 am

Using character controller in v1 to be easily upgradeable to v2

Post by Frooxius » Mon Dec 17, 2018 9:30 am

Hello!

I am currently using BEPUPhysics v1 in my project (it's one of the most awesome C# projects that I know!) and I'm working on an integration of the character controller. I have been looking at the changes in the v2 and noticed that it doesn't have one, because of some of the issues with the old one (such as the stepping up/down being velocity-less).

Eventually I'd like to upgrade to v2 in the future and also avoid some of the issues with the character controller in v1 currently. What would be the best way to approach this to ease the upgrade in the future (of the character controller in particular) and also avoid some of the issues it has.

Should I modify it in some way or ignore/reimplement certain features of it? Or would writing my own simpler variant be better approach?

Any advice is greatly appreciated!

Norbo
Site Admin
Posts: 4661
Joined: Tue Jul 04, 2006 4:45 am

Re: Using character controller in v1 to be easily upgradeable to v2

Post by Norbo » Tue Dec 18, 2018 12:31 am

I haven't fully decided what to do about the character controller situation in v2 yet, so things are still a little muddy.

One option would be to continue with a v1-ish approach, just without the explicit upstepping and downstepping. Walking up stairs and similar obstacles would be handled entirely by roundness of the character shape. This would imply some form of HorizontalMotionConstraint and VerticalMotionConstraint that are updated by contact data collected from contact callbacks.

This sort of thing is sufficiently simple that I will probably create a version of it in a demo in the not-terribly-distant future (post-v2.0 "RTW" though).

There's also the good old 'capsule on a (raycast) stick'. If your application happens to work with that, it would be pretty easy to reimplement the same idea in v2.

In my own projects, I plan to take a more physical approach to characters that doesn't rely on a single shape approximation. The final form of this is still a bit up in the air and I'm not sure if it will end up making sense as a general purpose thing, so it's unclear if I'll ever release a super heavy duty (i.e. a bunch of features beyond the above with the goal of being generally applicable) character controller for v2.

Frooxius
Posts: 12
Joined: Tue Aug 16, 2016 4:01 am

Re: Using character controller in v1 to be easily upgradeable to v2

Post by Frooxius » Wed Dec 26, 2018 6:59 pm

Thanks for the informative reply! I don't need too complex of a functionality right now, I don't mind starting with something simple and swapping it out later or rewriting for a better solution.

What exactly is the "capsule on a stick"? Is that using a custom velocity simulation (outside of the physics engine) and doing a convex sweep to check how far it can go along that direction?

I'm trying to understand what exactly does the character controller in v1 do and how much of it is needed for a simple approach.


I got one more question: How well in general will the character controller perform against instanced mesh (semi-complex or even more complex)? Convex sweeps against these are generally quite slow, but raycasts (with some extra optimizations) are significantly faster.

Ideally they shouldn't be used at all, but I do want to provide some basic physical locomotion on user imported content that doesn't have colliders setup (yet), so I was thinking of approximating some character controller with only raycasts against mesh colliders (rather than just going through them), even though it'll make it infinitely thin and bit wonky.

So I'm thinking about writing my own solution using the combination of the convex sweep against general colliders + raycasts against mesh ones, but I'm not entirely sure how much to take from the character controller in v1 for that so I don't have to reinvent the wheel.

Norbo
Site Admin
Posts: 4661
Joined: Tue Jul 04, 2006 4:45 am

Re: Using character controller in v1 to be easily upgradeable to v2

Post by Norbo » Fri Dec 28, 2018 12:01 am

What exactly is the "capsule on a stick"? Is that using a custom velocity simulation (outside of the physics engine) and doing a convex sweep to check how far it can go along that direction?
"Capsule on a stick" refers to a very simple form of character where the character's collision is represented by a capsule or similarly simple shape and it detects supports using a ray cast pointing straight down out of the bottom of the shape. The normal and location provided by the ray cast informs a velocity calculation to control the character's motion.

Usually there will be some form of relatively stiff spring-ish calculation to maintain a target vertical offset above the ground. Since there's a gap between the capsule shape and the support, this automatically supports a form of upstepping with no additional complexity- if the character moves over a higher surface, the vertical spring-thing will naturally push it up. Likewise, when a character walks off an edge, the ray can extend down to detect potential supports and pull the character down (if you want that behavior).

In games where the level design is suitable, this kind of character can work great. It can run into some issues with arbitrary geometry, though- the above design would happily attempt to step up into a space which is too small to stand up in, for example. And what happens if the character walks over a higher surface that is too steep to support traction? These issues all have sorta-solutions, but some of them can be gameplay specific or just pretty hacky.
I'm trying to understand what exactly does the character controller in v1 do and how much of it is needed for a simple approach.
The v1 controller can be broken into a few different chunks:
1) Support detection
2) Velocity control
3) Upstepping/downstepping
4) Stance changing

Going back through them in detail:
1) Support detection is based on the contacts generated with the character's collision shape. In v1, this was typically a cylinder with a large margin- halfway between a cylinder and a capsule. Any contacts with the environment with normals pointing up were classified as 'supports', and then a subset of those with sufficiently gentle slopes were considered 'traction supports'. When the character has traction, it enables full motion control. If supported but without traction, a more limited form of control is used.

The character also picks the most 'important' supporting object (based on some heuristics) to act as the representative for the purposes of applying forces. That is, if the character has contacts with multiple dynamic bodies, the character will try to pick the one that is more likely to be carrying the character's weight. It'll be pushed around as the character tries to move if it's dynamic.

Using contacts for this purpose is pretty simple since the engine's already done all the work, you just have to check for its results and reinterpret them.

2) Velocity control is the process of applying impulses to the character (and its dynamic support if it exists) to make it move in the desired way. In v1's character controller, this is accomplished by a pair of constraints, the HorizontalMotionConstraint and VerticalMotionConstraint. Conceptually, they're pretty simple- the horizontal motion constraint is just a solver-compatible implementation of 'try to reach a target velocity in the target movement direction', which you could implement in non-constraint form if you wanted. The VerticalMotionConstraint's job is also simple- it just tries to eliminate motion that would separate the character from the support surface (up to a limit). It works kind of like magnetized boots- not exactly physically correct in most cases, but in gamelike use cases you often are dealing with velocities that would launch your character into the sky if it didn't exist.

The only reason these are implemented as constraints rather than external velocity controls is that constraints have a more robust interaction with other constraints in the simulation. Pushing around dynamic bodies, for example, works better when the motion is controlled by a constraint rather than periodic external impulses.

3) Upstepping/downstepping involves a bunch of complex queries to identify alternative positions for the character. If the character has 'side' contacts (normals that are not pointing up or down relative to the character), it can check to see if there is space for the character to stand on top of the obstacle. If there is, it can teleport up.

Downstepping is similar- If the previous frame had traction and the current frame doesn't, it tries some positions down from the character's current position to see if it can regain traction.

About 80% of the character's total complexity is dedicated to getting stepping robust, and it can really hurt performance in pathological cases.

4) Stance changing is just changing the size of the character's shape in response to a desired state like standing or crouching. This is pretty simple, but there is one difficulty- going from a smaller shape to a larger shape requires queries to guarantee that the larger shape actually fits. This is like a mild version of upstepping and can be somewhat expensive. Notably, that effort is only required because the stance shift is instantaneous- if the stance changed smoothly, you could perform the tests incrementally.

Now, what parts are required for a simple version of v1's controller: just #1 and #2, and #2 could be simplified further by just using external velocity controls rather than constraints.

#3 can be handled implicitly by making the character a capsule and just using its rounded bottom plus the contact-based support finding to slide up/down obstacles rather than discontinuously teleporting up them. It can be completely disabled by commenting out the query in the CharacterController: https://github.com/bepu/bepuphysics1/bl ... er.cs#L611

#4 is sort of an optional feature and you could do query guards like v1's controller does, or you could do the smoother transition with incremental tests. You can also just ignore it and never change stance.
I got one more question: How well in general will the character controller perform against instanced mesh (semi-complex or even more complex)? Convex sweeps against these are generally quite slow, but raycasts (with some extra optimizations) are significantly faster.
Character controllers like the one in v1 rely on existing contacts rather than performing explicit queries (except in the case of stepping), so in the average case it's very fast. If you have an extremely complex environment where most characters are constantly performing some form of step query, that can get more expensive. Check out the CharacterStressTestDemo or CharacterStressierTestDemo in the BEPUphysicsDemos for examples of v1's full featured character performance- you can probably use 500-3000 in v1 depending on the target hardware, environmental complexity, and frame budget. (A contact-support based character in v2 without stepping would likely be 5-15x faster than v1, like everything else.)

Convex sweeps are indeed not superfast. A character that uses multiple sweeps every frame would probably end up an order of magnitude slower. Ray casts are faster, but still slower than not doing anything extra.
So I'm thinking about writing my own solution using the combination of the convex sweep against general colliders + raycasts against mesh ones, but I'm not entirely sure how much to take from the character controller in v1 for that so I don't have to reinvent the wheel.
I would hesitate to try to build something on top of sweeps and ray casts beyond something simple like the 'capsule on a stick' above- in general, if you can stick to contact-based support, it'll end up faster than more robust in the general case. That's not to say that it can't be done, but stuff can get complicated fast as you run into corner cases.

I've updated my plans for v2 a bit since my previous post a bit. In the next 3 weeks or so, I plan to create a character controller that is similar to v1's in terms of support finding and motion control, but without any discontinuous stepping or stance changing support. It'll just be a capsule with constraint-based motion. It'll be implemented outside of the library itself as a demo showing how to create custom constraint types as a side benefit. It wont have nearly as many features, but it's expected that users can take the relatively simple starting point and modify it as needed.

Frooxius
Posts: 12
Joined: Tue Aug 16, 2016 4:01 am

Re: Using character controller in v1 to be easily upgradeable to v2

Post by Frooxius » Fri Dec 28, 2018 3:45 pm

Wow, thanks for the really detailed answer, you're awesome! :D

This helps me a lot, I am going to be happy with just 1) and 2). I really don't want instant upstepping and downstepping anyway, since it's mainly for VR, so everything should be smooth. The stance change would probably need to be based on the actual player's height at the moment, which by its nature will be smooth and incremental. And I don't need it right from the start anyway.

One thing that I'm still not quite sure about are the instanced meshes. Is the contact support going to work with these as well and perform reasonably well with a single character? I'd like to provide at least some basic locomotion for these, even if it's going to be more janky to save some performance (it would be a motivation for them to optimize their experience), but I'm not sure about the performance characteristics of going with that solution.

Norbo
Site Admin
Posts: 4661
Joined: Tue Jul 04, 2006 4:45 am

Re: Using character controller in v1 to be easily upgradeable to v2

Post by Norbo » Fri Dec 28, 2018 8:35 pm

One thing that I'm still not quite sure about are the instanced meshes. Is the contact support going to work with these as well and perform reasonably well with a single character?
From a performance perspective, the difference between an InstancedMesh and a StaticMesh is near zero, and the character's functionality does not depend on what the supporting collision shape is. All it cares about is whether there are some contacts.

In other words, the character will only have performance problems on instanced meshes if any object colliding with them would have performance problems- so if they have hyperdense geometry such that every collision requires testing thousands of triangles, it could get slow, but otherwise you're going to be fine.

Notably, the CharacterStressTestDemo and CharacterStressierTestDemo both use InstancedMeshes. (Edit: and all meshes in v2 are "InstancedMeshes" in the v1 sense.)

Frooxius
Posts: 12
Joined: Tue Aug 16, 2016 4:01 am

Re: Using character controller in v1 to be easily upgradeable to v2

Post by Frooxius » Fri Dec 28, 2018 10:50 pm

Oh that's awesome! I was a little bit afraid of the performance with instanced meshes because I found that the convex sweeps against them can be really expensive, but this gives me a lot more confidence with it, as well as your plans for v2.

I've started integrating it with my project and got basic integration working already :D (I'm actually a bit further now, the video is from a few hours ago). Thank you so much again for all your help and detailed answers! (the heavy comments in the code help as well, but I was missing a bit of higher level overview).

https://www.youtube.com/watch?v=vf40L9QATNM (the framerate it s bit lower because it was running at 4K on my laptop, runs really smooth otherwise)

EDIT:

Got more things to work pretty well! :D It's turning out much easier than I thought, I needed to make it work well with the transform hierarchy and scaling in the scene: https://www.youtube.com/watch?v=hhf1FzjZbT0

What would be the best way to approximate scaling actually? Should I just scale all the forces (gravity, movement, jump) in addition to rescaling the height and radius and mass? It's not going to be something that's usually done continuously, but rather at points in time (players can scale themselves in the scene in certain modes) or once (a set scale level for an avatar or a world), so it's ok if it leads to some expensive-ish calculations.

Also I removed the checks whether crouching/prone height is lower than standing, because it was a bit painful updating them in the right order on scale change (and I only use the standing now anyway), I assume that as long as I update them all in one go and I only use standing it doesn't matter when crouching is momentarily higher than standing?

Norbo
Site Admin
Posts: 4661
Joined: Tue Jul 04, 2006 4:45 am

Re: Using character controller in v1 to be easily upgradeable to v2

Post by Norbo » Sat Dec 29, 2018 10:43 pm

Looking good 8)
What would be the best way to approximate scaling actually? Should I just scale all the forces (gravity, movement, jump) in addition to rescaling the height and radius and mass?
Pretty much, although you should be careful about mass. A 'correct' scaling would increase mass by the cube of the scaling factor, but that would result in enormous mass ratios would be extremely hard to solve whenever a heavy thing depends upon a light thing.
Also I removed the checks whether crouching/prone height is lower than standing, because it was a bit painful updating them in the right order on scale change (and I only use the standing now anyway), I assume that as long as I update them all in one go and I only use standing it doesn't matter when crouching is momentarily higher than standing?
Should be fine- or at least, I'd assume so until proven otherwise. I don't quite remember all the details off the top of my head :)

Norbo
Site Admin
Posts: 4661
Joined: Tue Jul 04, 2006 4:45 am

Re: Using character controller in v1 to be easily upgradeable to v2

Post by Norbo » Mon Jan 14, 2019 3:24 am

The v2 demos now contain a basic character controller system and a demo with a giant newt to run around on.

Post Reply

Who is online

Users browsing this forum: No registered users and 7 guests