-
Notifications
You must be signed in to change notification settings - Fork 3
General Information
Without talking about Godot's specific things, the goal of Motion Matching is to analyze your animations, and at runtime playing the most accurate portion of your animation that match your current situation. However, what you analyze, how you save it and how you search for the best match is what this implementation is trying to help.
In other words, this is a classification problem, where the poses of our animations are what we analyze and we are trying to find the closest pose that match our trajectory. A good general-use data structure with good performance for this kind of problem is the kdtree with nearest neighbors search. As such, we use a kdtree to represent all our animations important features and do a search of a closest match with some weighted adjustement to give more importance to some features over others.
The problem become how to build the kdtree in the editor and query it at runtime. Let's go over some terms that we will use.
A poses is just a moment in an animation. For example, "Walk_Forward" at time 0.6s. To simplify, we only examining poses at 0.1s interval.
A data structure constructed from a 2D array of floats. The rows are the poses of our animations, and the dimension ( columns ) is each features serialized. The MotionMatcher node contains the kdtree and everything required to build and interact with it.
Since the kdtree only see floats, we must translate this all the information to an array of float. For example, if the feature we want is the root velocity and a bone position and velocity, then we have three Vector3 and it will be translated to an array of 9 float, or 9 dimensions like this : [rv.x,rv.y,rv.z,bp.x,bp.y,bp.z,bv.x,bv.y,bv.z].
A feature is a series of adjacent columns in the kdtree. For two features, one using a Vector3 and the other containing a Vector3 and a float, then the first feature use 3 columns and the other 4, for a total of 7. The kdtree isn't aware of the features, but it give use a good abstraction that help organizing our data. As such, each features must communicate the numbers of columns it contains, and being able to serialize information from animation tracks and, if required, being able to serialize the information for the querying.
This is the process of extracting information from animations and serializing it for each poses. The algorithm is quite simple
Array2D array
For(auto& anim : animations_list)
for (float time = 0.1f; time < animation.duration; time += 0.1f)
for(auto& f : features)
array.append_array(f.bake_animation(anim,time))
We then feed this array to the kdtree. We aim to provide help inside the editor to simplify how you trigger this operation.
To call a nearest neighbors search in a kdtree of k dimensions, we must provide an array of size k. We fill this array with the current informations, let's say the current velocity from the character's point of view with the position of a few important bones, serialize it, and search the kdtree.
The problem with serialization is that position and velocity and both Vector3, but doesn't share the same units. As such, as solution is to save the mean and variance for each dimensions, and save the result as `Dn = (Dn - Mean_n)/Variance_n. If our animations covert the problem space sufficiently well, we now have numbers that are around 0 and follow somewhat of a normal curve. However, this is extremely annoying so the process of normalizing both the data in the kdtree and the query is handled by the MotionMatcher, and the user shouldn't do it.
I repeat, do not normalize your data in either the baking nor the query.
To give some feature more importance over others, for example the trajectory is usually more important than the exact bone positions, we provide a way to weight the dimensions. We expect users to tweak those number a lot.
Even with properly adjusted weights, motion matching remains difficult to control. For example, I wanted my character to use the snaking animation when turning, but my strafing animations was always a better fit. While I'm sure adjusting weights would have been a good solution, an easier fix is to remove the strafing animations from the possibilities when the character isn't strafing. As such, you can categories your animations thought a bitfield ( or bitmask ) in an animation tracks and the query let you chooses which category you want to include, and which you want to exclude. We only reserve the bit no.31 of the bitfield to a special "Do not use" category that the MotionMatcher simply ignore when baking the data. Poses in the "Do not use" category aren't saved in the kdtree.