godotengine / godot-proposals

Godot Improvement Proposals (GIPs)
MIT License
1.11k stars 69 forks source link

Implement Motion Matching #6122

Open Mikeysax opened 1 year ago

Mikeysax commented 1 year ago

Describe the project you are working on

A third person action adventure game

Describe the problem or limitation you are having in your project

I believe in order for animation systems in Godot to be closer to other engines, Motion Matching should be implemented. It seems as though there used to be a thread open before the Godot proposals existed and seems to have been lost as a result:

https://github.com/godotengine/godot/issues/20606

As a result, I'm resurrecting the thread here so it exists in some form and can be accounted for.

Describe the feature / enhancement and how it helps to overcome the problem or limitation

I think the original proposal by @reduz describes it well enough:

https://github.com/godotengine/godot/issues/20606#issue-345822669

Despite the big advances in the [animation system](https://godotengine.org/article/godot-gets-new-animation-tree-state-machine), there is a fairly recent technique called [motion matching](https://www.gdcvault.com/play/1023478/Animation-Bootcamp-Motion-Matching-The), which makes it easier to match 3D animation data with character motion.

The biggest advantage of this technique is that it's easier to simply move the character in a relatively physically correct way, and animation data will try to match it, making it hugely easier to animate.

This could be implemented as either a separate node, or most likely a node for use in the AnimationTree system that does all the work (and can still be blended with others).

If anyone would be interested in researching this, let me know and I can lend a hand.

Some Resources:

[Original GDC 2016 Presentation](https://www.gdcvault.com/play/1023478/Animation-Bootcamp-Motion-Matching-The) from Ubisoft.
[Link to Slides](https://twvideo01.ubm-us.net/o1/vault/gdc2016/Presentations/Clavet_Simon_MotionMatching.pdf)
[Open source implementation for UE4](https://github.com/Hethger/UE4_MotionMatching-)

If you know more resources, feel free to contribute them!

As an aside, I believe some of the work was done as part of the google summer of code but not fully completed and also likely has many regressions due to how old it is as well as some other implementations:

1) https://gist.github.com/mall1/cb626660619825cce09126eb06cc2314 2) https://github.com/theroeberry/Motion-Matching-For-Godot

Some other resources that describe how to implement a learned motion matching system:

https://montreal.ubisoft.com/en/introducing-learned-motion-matching/

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

As stated in the original proposal:

This could be implemented as either a separate node, or most likely a node for use in the AnimationTree system that does all the work (and can still be blended with others).

If this enhancement will not be used often, can it be worked around with a few lines of script?

I believe this needs to be worked into the core animation systems. I think some of the bigger blockers are the lack the newer Godot 4 IK system and potentially other animation changes in the works for Godot 4 or 4.*

Is there a reason why this should be core and not an add-on in the asset library?

I guess this could be an add-on but I don't believe it would be optimal or potentially as performant, in order to have full integration into the engine.

fire commented 1 year ago

See also https://github.com/godotengine/godot/pull/29892

fire commented 1 year ago

I was surprised to see that O3DE wrote a great article about their feature https://www.o3de.org/blog/posts/blog-motionmatching/.

https://github.com/o3de/o3de/pull/7232

Remi123 commented 1 year ago

After a month of trying to implemented this, I think I can add my input to this conversation.

First of all, this blog is all you need to implement MotionMatching by one of the animation team member working at Ubisoft that implemented it: https://theorangeduck.com/page/code-vs-data-driven-displacement. Quite frankly his blog is full of insight on animation it's a goldmine.

So on the topic of motion matching :

  1. What it is and how it work ( bunch of sources )
  2. Controller
  3. Choice of data structure
  4. Baking the animation data and features
  5. Searching the best poses at runtime ( with weights )
  6. Switching to the new pose. ( Inertialization )
  7. Editor tools

1. What it is and how it work ( bunch of sources )

For an explanation of what is is, please see this talk by Simon Clavet. However, the implementation he show is way too slow for practical purpose. Fortunately, he goes more into detail about a fast solution in this video on his personal channel. The first half is how it works, and the second half talks about a clever solution to integrate it into an engine and choosing features.

Once you understand that you create a big 2D array with your animation data, and quickly search inside this array for the pose with lowest cost, things start to make senses. In the context of the big array, the rows are the poses of your animations and the columns are your features. Each row is a timestamp of the animation, and each column is a features like rootbone velocity, left_feet velocity, etc, all serialized by float. For example, the rootbone velocity is three float instead of a vector3. One notable features is thing like future position, where you don't refer to the rows of the array corresponding to the delta, but instead add it to the list of features this pose have.

2. Controller.

Motion Matching is for matching what ? The goal is to match the character motion so we need things like the velocity, acceleration, angular velocity of the controller. Not too complex to implement. The blog use a Critically Damped Spring Controller, which let you quickly calculate the next velocity and calculate the next_position in X seconds.

More detail here.

3. Choice of data structure

Storing the 2d array only requires a simple PackedFloat32Array for easy serialization and engine integration. This is what I used when I baked all my animation data in the next section. However, once done, the array must be given (moved in c++ terms) to a kdtree.

The choice of kdtree implementation was important, as quality vary. I choose this implementation where I changed double to float for a few reasons :

4. Baking the animation data and features

The goal at this point is to store all useful information the data array. As long as you can interpolate the data from animation tracks, you can get velocities and all other interesting information from your animation. From the user point of view, it would be nice to have a function in animation that retrieve the position at time x of a given bone in model frame, but fortunately root bone is the normally the first and doesn't need to follow a transform hierarchy.

The only thing that must be followed is the order of the features, as it end up as a series of float, and we must construct the query in the same order for the kdtree search to make senses.

5. Searching the best poses at runtime ( with weights )

At this point I only it's only a matter of constructing the query in the same order as the features when baking data. So I take the character velocity, acceleration, left_foot position, etc... and store that in a std::vector of size k (dimension) and search for the best poses. I then use the void* in the resulting KdNode to retrieve the stored animation name, and the timestamp of the best pose in this animation.

You can take the N nearest neighbors and search from those which is the "best" for the current situation using a slower algorithm and then switch to it.

6. Switching to the new pose. ( Inertialization )

This is the last problem that remains to fix, as godot's animationtree isn't fit to handle the transition at this frequency. It's quite frequent to request a new timestamp/animation while a transition from the previous one is still going on. There is some tricks like forbidding the switch while we are transitioning, but it doesn't look good and it feels unresponsive.

The truth is that animationtree entire functionality is based around two animation blending together, and each transitions in statemachine or blendtree is a blend between the From animation, and the To animation in x seconds. Switching those two animations too fast and the blending is completely different, resulting in jumps in the skeleton. Basically, switching animation during transitions give unwanted result.

The solution is called inertialization, and there is a good talk about it from the Gears of War developers, as it allows to switch to a new animation while completely forgetting about the previous one. They said it's a more performant transitions and give more natural result. Now the inertialization formulae they give is more physically correct, OrangeDuck's implementation use a critically damped spring to approximate it faster with negligible overshoot.

A small but important detail, a pose in inertialization isn't the same as a pose in motionmatching. In Inertialization, each poses is the position,rotation,velocitiy, acceleration of EACH bones, while pose in motionmatching only contains thoses information for a few interestings bones if you need it.

I insist that this inertialization process is absolutely necessary for motion matching, all the rest is just data manipulation that can be done with code either at startup, or in editor with @tool. I used this MR https://github.com/godotengine/godot/pull/73656 for baking the data in Gdscript in editor, as I simply need to loop over a few animation library and construct a resource with a PackedFloat32Array. The rest was GdExtension to call kdtree constructor and functions and filling a query at runtime with the values of velocity, rotation, etc of all the features of my character.

Inertialization and blending isn't exclusive. You can for example transition from a pose to a blend of two poses, or vice versa. In term of memory we need to store all bones velocities, which is about an array of size max 206 for a human 😄

7. Editor tools

After reviewing this, I'll say that MotionMatching is close to being something that a gdextension could provide, or maybe a module. There is someone that did a inertialization animation system in godot and, although it's very barebone, it give an idea of what to do. Here the link.

Integrating this into godot is for sure 4.2, maybe 4.1 if we are really motivated. Once this is done it would be nice to add a tag system to the animation. Something like this implemented here https://theorangeduck.com/media/uploads/RangesDemo0.m4v. This would simplify the predicate of the KDTree, mentioned previously.

End

I think this is all knowledge and experience I gathered while trying to implement this. I'm open to questions.

@fire

GeorgeS2019 commented 1 year ago

Motion Matching as an addon

ywmaa commented 1 year ago

First of all Thanks to @Mikeysax and @Remi123 for providing very valuable info about the subject, Now are you @Remi123 still working on motion matching ? is there a repo that we/I can work on it ? Or should I start a new repo, I was initially thinking to do it all in GD script as an add-on, also with this PR https://github.com/godotengine/godot/pull/73656 I think it will make it work in GD script, though we may need to implement the KDTree and inertialization process in GD script, which I think isn't worth the effort because it will require a lot of time and reduce performance ? So I think I should at least start it as gd-extension addon ?

Edit : also I think we really need a demo project to experiment on it, and test the system while working on it.

The demo project should have 3 types of animations : 1- full motion captured animation 2- normal looping animations 3- motion captured animations separated into different actions (Run, Walk, Sprint)

So we can check that the system works on all/most types of the animation systems.

I think we can get 2 and 3 from mixamo, while I don't know how can we get 1.

Now I suggest that we use my project

https://github.com/ywmaa/Advanced-Movement-System-Godot

Because it has 3 main stuff that will help

1- normal looping animations 2- the movement system has acceleration, velocity, input_velocity, input_acceleration, so I think all of this data will help the motion matching system to pick the right stuff. 3-I use state machines which can help in the future test and implement tags system.

Another Edit : I would like to add too that I have a version of my project that uses RigidBody3D instead of kinematicBody3D

I think we should keep in mind supporting both.

GeorgeS2019 commented 1 year ago

@ywmaa

There are many good examples in c# from Unity, including one for people wearing VR headset and the motion matching predicts the rest of body and feet IK movements

https://github.com/GeorgeS2019/Godot4-3D-IK-Demo/issues/2

ywmaa commented 1 year ago

@GeorgeS2019 thank you for this resource too, I think it will help. Even though I don't prefer doing it in Godot in c# But at least I can understand how some code works from it and get into c++ or GD script.

Remi123 commented 1 year ago

@ywmaa @GeorgeS2019 I'm resuming working on this, as I need it for my project.

Since a month ago, I've discovered the project by theroeberry. Quite frankly if I knew this project existed I would have simply started from there. It isn't finished, and there is some issues with the direction of character and bone selection, but it's a very excellent starting point. It also implement inertialization, which to me is the most valuable part of the project.

However it's a godot 3 project, and since then the function Animation::transform_track_interpolate() has been replaced into Animation::position_track_interpolate,Animation::rotation_track_interpolate and and Animation::scale_track_interpolate. This is a problem since his logic has a association map from bone_id to track id, which now should be a association map from bone_id to (position_track, rotation_track,scale_track).

Nonetheless it's shouldn't be too hard to translate this code to godot 4, and since https://github.com/godotengine/godot/pull/73656 has been merged, the whole motion matching feature can now be a GdExtension instead of a module. At least if you compile the latest godot master branch.

GeorgeS2019 commented 1 year ago

@Remi123

Thanks for updating us on https://github.com/godotengine/godot/pull/73656

Not sure what approach [Motion-Matching-For-Godot](https://github.com/theroeberry/Motion-Matching-For-Godot) is taking with respect to those (Motion-Matching) which are under active research

Some of these come with trained data ready to be uploaded and also make it easy to integrate new or customized motion matching for e.g. picking up a box instead of standard walking etc.

I have not looked into the Godot approach simply I am not sure if it is up-to-date and how easy to integrate new movements

The godot approach could be the shortest path, in the end, you demo => yes => motion matching does work in Godot

Most Open source work I have seen are in Unity c#

However, the aim here is to stay with c++ and GDExtension

Ideally we need to evaluate what is out there, especially those with trained data, and modular for integrating new movement

Start with that design first before committing to a motion matching that could be out-of-date

This is just suggestion, I could be totally wrong, why we have open discussion

Remi123 commented 1 year ago

@GeorgeS2019

Learned MotionMatching is quite similar in interface to classic MotionMatching. You store data of your animations in blackbox, you tell the blackbox what is the current and desired state, and the blackbox return which animation to play and at what time.

Classic MotionMatching use a KdTree as the blackbox, or an AABB implementation that is slightly faster but I'm not familiar with how it work. Learned MotionMatching use an AI trained to the animations.

I consider Learned MotionMatching as slightly out-of-scope. We could provide an option to select the AI trained blackbox as a Resource, and in the code we query the AI instead of the KDTree. There is also the possibility that the AI wants to control the skeleton instead which animation to play at what time... In resume I think that if you already have a trained dataset, you can integrate it yourself since it's probably already very specialized.

Not exactly sure what the godot approach is, but my aim to is to simplify the usage of this technic. How in Editor we bake the data and at run time how we form the query. In code it's only floats array everywhere.

Here is the plan :

C++ GDExtension : Everything related to the KDTree at runtime. GDScript Editor Plugin : Baking the data in the KDtree can be done in Editor since we don't care about performance in the Editor. Forming the query can also be done in Gdscript as it's only a few virtual calls. In Game : The character should only need to form a query, and when the MotionMatching node send a signal to play a specific animation, then we send this info to the animationplayer/animationtree/Inertialization

Hellmett50 commented 1 year ago

Hi,

I have been working on the repo from theroeberry for some time to implement motion matching for a personal project in godot 4.0. Seeing this post, I told myself it could maybe interest somone. I could update it and compile it with godot 4.1 but I'm no expert and I still strugle to understand how to have it work smoothly on my project (my character just jiggles between 5/6 poses). Still here is the link.

Remi123 commented 1 year ago

MM_DEV.webm

I'm finallly having some good result from my WIP implementation. Walking is almost perfect but running has some bad animation that interact badly the system, but that's a fine-tuning job.

I've managed to create a plugin that ease the development, at least a little bit. Here is my current view in the editor :

image

Everything needs to be improved and clean up, but as a general proof of concept it do what I want. So here is a tour guide :

The node MotionPlayer is badly named, all it does is outputting the name of the best fitting animation and timing. I pass this info to an animationtree with a blendtree and you see the result. Not perfect as I would have prefered inertialization but it works great for demonstration.

Hellmett50 commented 1 year ago

@Hellmett50 please share gif of your work

Well there is really not much to see, especially compared to the impressive results of @Remi123 but for fun sake here it is : MMProject.webm

GeorgeS2019 commented 1 year ago

@Remi123 @Hellmett50

The big picture, godot users are making PROGRESS! I have seen Motion Matching in Unity and Unreal and NOW in GODOT, that is inspiring! Thank you

ywmaa commented 1 year ago

@Remi123 How is the performance with the plugin you are using ? Does the profiler notice any overhead on processing ?

Remi123 commented 1 year ago

@ywmaa

The crux of the performance is the kdtree. I'm monitoring the c++ side and it take about 70ms to 150ms in general to find the best pose. Of course I'm only searching the best poses every 200ms to compensate. While it sounds bad, this is mostly because I'm using the debugging symbol for now. The authors of the kdtree implementation specifically said that this would slow it down. I've tested with a much bigger dataset of random data and it was much faster so I'm not worried about that.

Once I know which animation to play next at which timestep, I ship this info to the animationtree with a small setup.

Remi123 commented 1 year ago

Updates

The development continues and is going well.

Update on performance : Turns out I'm an idiot. My timer was set up in microsecond, not millisecond ! So my previous statement was false, it was 70 us to 150 us.

I've added a category selector into the algorithm using a bitset, but didn't test it too much. Basically you add a track with a preselected name to some animations, and modify a bitset at key points. The bitset can be whatever you want, so "Locomotion", "Crouched","Male","Strafe", whatever. I add this info to the KDTree, and when searching I just check if the bitset match.

I am now using a library of motion captured animations that I found online. Around 50 animations, so 7700 possibles poses and I find the closest in around 500us.

june23.webm

Things to note on this video

The weights are not correctly set, so it tries to shift animation too often, especially when doing nothing or going forward. bigger competition for those poses I guess. But the true problem is that none of those new animation loop. So if the AnimationPlayer get to the end of an animation, it stop playing and most of the time the best pose in this state is the same poses as the one that get me into this state. What you saw in the video is my attempt where every animation is looping. It cause some other problem as you can see. However I think I have a solution.

OrangeDuck's solution was to transform those non-looping animations into looping ones using some math , but I've tried to add a method calls at the end of some animations to manually trigger an animation shift to a similar pose predetermined. It give surprisingly good result and I'll be attempting this on a larger scale. Fortunately the KdTree can be used to search for a pose similar to the current, so I can get the best 10 poses and chooses the one that will fit nicely.

Future plan

Now here is the interesting part. I plan to release the MotionMatching part of my project as a simple GDExtension in a few weeks. I need to extract it from my project and write a simple tutorial because it will be a v0.5 release. My Plugin UI is bad, make only sense for me, and the user needs to connect the MotionMatching node correctly .. But it's somewhat usable.

Basically I'm looking for more contributors.

fire commented 1 year ago

Let me know how to help. You have my discord I think. chibifire on discord.

ywmaa commented 1 year ago

@Remi123 I am interested and I would like to even use it in my multiplayer game, My username on discord is ywmaa Or using the old username ywmaa#4173

And I may even try to understand the code and improve it.

Remi123 commented 1 year ago

I've finally have all the features that I wanted.

I can now exclude or require some poses based their category using bitfields. This does so much work even if my weight aren't nearly as good and it still give good results. I'm using animation tracks to let the user setup the categories ( walk, run, strafe, etc ) so this part is already integrated into the editor's AnimationPlayer interface. Still tedious but I think it's good enough for a first pass.

Unfortunately this means that I now need to clean my code 😞. And write a proper ReadMe on how to use this thing because there is a lot ( maybe record a video? Might be easier to show things).

@ywmaa If you are interested in adopting this thing early, we can arrange something since I want to know where are the pain points while integrating and using this, or where I'm not clear explaining it. I've tried my best to make it as friendly as possible but there is still some tedious part. Didn't test it in a multiplayer setting but I have a idea on how to synchronize this.

@fire I think I may need some help in the CI/CD, as I'm not exactly sure how to generate the binaries for linux and macos. I also have some questions about Gdextension and a few functionalities that I want to add. There is also some questions about license with this kdtree implementation : https://github.com/cdalitz/kdtree-cpp . I'm sure it's very open and only want the license to stay in source and binary in order to credit them, but I want to be sure before release the code.

I have the next two weeks free before starting a new job, so progress will go faster.

Thank you all for your interest in the subject !

Edit : Added latest video. The weights aren't properly adjusted and I manually add a little bit of overshoot in the rotation, but it still give relatively good result.

july03.webm

fire commented 1 year ago

I read the license.

  • Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

Seems to require that the enduser developer display license information inside of their game (usually in a help screen)

fire commented 1 year ago

Let me know when I can start generating the binaries for Linux and Macos. I do need the source.

There's two examples:

The standard example.

https://github.com/paddy-exe/GDExtensionSummator/blob/main/.github/workflows/builds.yml

An example of doing both C++ modules and gdextension..

https://github.com/ashtonmeuser/godot-wasm/blob/master/.github/workflows/build-addon.yml

Calinou commented 1 year ago

Seems to require that the enduser developer display license information inside of their game (usually in a help screen)

That license is a standard 2-clause BSD license; it just uses unusual formatting. We use that license for third-party libraries in Godot already, so it's fine.

ywmaa commented 1 year ago

@Remi123 Yeah I am still interested.

About this :

Didn't test it in a multiplayer setting but I have a idea on how to synchronize this

In Godot Engine I sync animations by replicating/syncing character states like Gait : walk, run , sprint Stance : crouch, standing

Then let each client run its own animation tree and player based on these values.

I think the same can be done with motion matching.

This way is not 100% accurate, but it works for me most of the time and I don't care much about exactly accurate animations replicated between client.

fire commented 1 year ago

I updated the readme of kdtree upstream.

GeorgeS2019 commented 1 year ago

The original 2019 Google summer of code by Aditya Abhiram

msedge_0uT09ebiny

image

UI of the Godot Motion Matching Editor

AnimationNodeMotionMatch (1)

image

MotionMatchUI

GeorgeS2019 commented 1 year ago

I need feedback the advantages and disadvantages of implementing MotionMatching using

Remi123 commented 1 year ago

@GeorgeS2019

Excellent question !

In short, nothing. There is no advantage in doing it this way other than I'm a novice in godot development. In fact, transitioning my class to an AnimationNode is what I'm working on next. However, I was considering adding this step when I needed Inertialization ( aka a more performant and realist blending between poses) and I just needed my BlendTree hack for now.

The only part that would be harder for user when inheriting AnimationNodeRoot is passing information like future trajectory at runtime. I don't think it is too hard to get right but I might ask some question later.

I have release my code under alpha at this link. However everything is expected to change, like in the near future my motion player will be an animation node.

P.S. This is the latest inspector of the node MotionPlayer :

image

VicPrzz00 commented 2 months ago

soo is anyone still working on this by any chance? with motion matching getting even more popular now that unreal engine added it for free including animations, I think it would be an advantage to also have it on Godot

GeorgeS2019 commented 2 months ago

Done

@VicPrzz00 https://github.com/GuilhermeGSousa/godot-motion-matching/issues/2

Photos_jNY92D48L8

GuilhermeGSousa commented 3 weeks ago

Hey that's me! What @GeorgeS2019 posted above is a small side project of mine that I'll be improving as time allows, I've been working on motion matching professionally for some time now and I'd love to contribute in whatever way I can to bring this to godot. There's still a lot to be done, and @Remi123's work was essential to get a demo stood up. I'd actually recommend people checkout that repo first as it is more advanced than what I did in a lot of things.

GeorgeS2019 commented 3 weeks ago

@GuilhermeGSousa I assume very few have managed to get the @Remi123 version working since the beginning.

The Godot4 Skeleton3D modifier keeps improving.

However, what you have done, is a great contribution for us to start with something working.

GuilhermeGSousa commented 3 weeks ago

Oh thanks for letting me know about SkeletonModifier3D! My implementation is on 4.3 (or close enough) but I wasn't aware those existed, I'll need to update my code to use those.

As for deep learning, I'd argue that a simpler acceleration structure like KD Trees should yield a "good enough" selection for most use cases. Even the naive version works well for small datasets. There as some features that I think would be more useful to a wider range of users, stuff like:

There's probably a lot I forgot here, but these should be next up on my list of stuff to do!

GeorgeS2019 commented 3 weeks ago

@GuilhermeGSousa https://godotengine.org/article/design-of-the-skeleton-modifier-3d/

Remi123 commented 3 weeks ago

Hi @GuilhermeGSousa

I'm surprise someone looked at my code at was able to decipher it. Especially in the deplorable state that I left it in the main branch. I'm really happy it helped you get started.

I didn't had much time lately since the birth of my second child to make as much progress as I wanted,

I do have however a secret branch on my computer that I've kept working on in order to properly show a demo with editor plugin, GUI and other stuffs that would help. I'm not 100% happy with the API and one or two UI stuff, but if you are willing to help I'll be more than happy to look at any PR you would submit afterward. I'll share it this evening when the kids are asleep.

Things I added :

  1. Editor plugin UI to inspect animations, see features with gizmos on selected frames, see each values in a pose. see the coverage of the animations.
  2. Tag system to either mark a pose as Junk or any custom Category. Available in the Editor plugin UI.
  3. Methods to query parts of the data set. For example, only the Crouching poses are searched.
  4. Already added SkeletonModifier3D for Ik, look_at, and inertialization. The latter allows the AnimationTree to be used.
  5. MFfeatures written in GDScript. 4.3 allows virtual function that can be override in gdscript.
  6. MMAnimationLibrary search query with AABB acceleration with bias toward continuation.
  7. Custom Weights per query with a QueryOptions class.

If it isn't clear, I'm trying to recruit you to migrate to my codebase :P

If you say that you worked on Motion Matching professionally, I'm more than willing to learn from your experience.

I'm also glad that someone found my GETSET and BINDER_PROPERTY_PARAMS useful.

GuilhermeGSousa commented 3 weeks ago

That secret branch of yours does seem like it has a bunch of cool stuff I'd love to play around with ;)

I'll check out your branch soon to play with it locally, I noticed you also added a demo on your recent PR. If that works for you I'll send you a message on Discord to chat about what you're planning to work on next.