Motion Matching

For twenty years, character locomotion was built like a subway map. Animators authored a blend tree and state machine: an idle state, a walk state, a run state, a turn-left state, and a thicket of hand-tuned transitions wiring them together. Every new move — a sharp pivot, a stumble, a 180° spin — meant a new node and new edges, and the graph grew into an unmaintainable tangle. Then in 2016, Simon Clavet and Michael Büttner shipped Ubisoft's For Honor with a startling idea: throw the graph away.

Their replacement, motion matching, keeps no states and no transitions at all. It keeps only a big pile of motion-capture clips — unstructured, unlabelled, un-cut — and a very simple loop: a few times a second, look at what the player is asking for, search the entire database for the single frame that best fits, jump there, and play forward. Repeat forever. The animation is never authored; it is found, frame by frame, out of raw data.

The idea in one loop

Strip motion matching down and it is a search running on a clock. Every N frames (typically every 5–10, so several times a second) the system does four things:

Describe the goal. Build a query feature vector from the player's desired future path — where the character should be and which way it should face a few tenths of a second ahead — plus the character's current pose and foot state.
Search the database. Over every candidate frame in the mocap database, compute a matching cost — how far that frame's stored feature vector is from the query — and keep the cheapest.
Jump and play. If the best match is somewhere better than where we already are, blend to it and start playing the clip forward from that frame.
Repeat. A few frames later, query again. Frequent re-querying is what makes the character feel responsive — a new stick input is honoured within a fraction of a second.

There is no notion of "being in the walk state". The character is only ever at a frame of raw data, and the search is free to leap to any other frame — inside the same clip or a completely different one — the instant a better match exists. The database's job is to be rich enough that some frame always fits; the search's job is to find it fast.

The feature vector: what "best match" means

Everything hinges on the feature vector — the handful of numbers that summarise a frame for comparison. Compare full skeletons (dozens of joint angles) and the search is both slow and wrong-headed; matching should care about the things a player feels. So the feature vector blends three ingredients:

Desired future root trajectory — the character's root position and facing direction sampled at a few points ahead (e.g. 20, 40 and 60 frames into the future). This is the steering: it is what the player input controls, and matching it is what makes the character go where you point.
Current pose — key joint positions (and sometimes velocities), so the frame we jump to continues the body we already have rather than teleporting the limbs.
Foot state — foot positions and velocities, because feet planted on the ground must stay planted: matching them is the main defence against foot sliding.

These live in different units — metres, metres-per-second, radians — so they cannot simply be thrown into one distance. Each block gets a weight, and the matching cost is a weighted squared distance (a weighted L^2 norm) between the query feature vector q and a database frame's feature vector f_i:

\text{cost}(q, f_i) \;=\; \sum_{k} w_k \,\bigl(q_k - f_{i,k}\bigr)^2 .

The chosen frame is simply the cheapest one, a nearest-neighbour query in feature space:

i^\star \;=\; \arg\min_{i}\; \text{cost}(q, f_i).

Crank up the trajectory weights and the character becomes twitchy and hyper-responsive but may snap between poses; crank up the pose and foot weights and it moves smoothly but lags behind the stick. Those weights are the tuning dials of the whole system.

Picturing the search

Here the player is holding "turn left while running". The dashed path is the desired future trajectory — the query — a few sample points curving up and to the left of the character's current position. Around it sit three candidate database trajectories, each stored with some frame of mocap. The search scores each by how well its sample points line up with the desired ones (plus pose and foot terms we can't draw); the best match, candidate B, is highlighted. That is the frame we jump to.

Notice the search compares trajectories, not just endpoints: candidate C ends near the goal but bends the wrong way through the middle, so its per-point cost is high. Candidate A barely turns at all. Only B curves left through every sample, so it minimises the summed cost.

Worked example: a tiny feature vector

Let's compute a match by hand with a deliberately small feature vector. We'll use two future trajectory points and two foot positions, all in a flat 2-D world (units in metres), and drop the pose term for clarity. The query — "turn left while running" — is

q = \bigl(\underbrace{(1.0,\,0.6),\,(1.4,\,1.5)}_{\text{future points}},\; \underbrace{(-0.1,\,0.0),\,(0.1,\,0.2)}_{\text{feet}}\bigr).

We weight the trajectory block by w_t = 1.0 and the foot block by w_f = 3.0 (feet matter a lot — sliding is ugly). Two candidate frames:

Frame	traj pt 1	traj pt 2	foot 1	foot 2
A (gentle left)	(1.1, 0.5)	(1.5, 1.3)	(-0.1, 0.0)	(0.0, 0.3)
B (hard right)	(1.0, -0.6)	(1.4, -1.5)	(-0.1, 0.0)	(0.1, 0.2)

Frame A. Trajectory squared error: (1.0-1.1)^2+(0.6-0.5)^2+(1.4-1.5)^2+(1.5-1.3)^2 = 0.01+0.01+0.01+0.04 = 0.07. Foot squared error: 0+0+(0.1-0.0)^2+(0.2-0.3)^2 = 0.02. Cost = 1.0(0.07) + 3.0(0.02) = 0.13.

Frame B. Its feet match perfectly, but it turns the wrong way. Trajectory squared error: (0.6+0.6)^2+(1.5+1.5)^2 = 1.44 + 9.0 = 10.44 (the x terms cancel). Cost = 1.0(10.44) + 3.0(0.0) = 10.44.

Frame A wins by a mile (0.13 \ll 10.44) — exactly what we want, since A actually turns left. The search picks A, we blend to it and play forward, and a few frames later we query again. Note how the heavy foot weight couldn't rescue B: matching feet is worthless if the character is running the wrong direction, which is why the trajectory block usually dominates the cost when the two conflict.

A shipping locomotion database can hold tens or hundreds of thousands of candidate frames, and we re-query several times a second, so a naive scan sounds ruinous. Two things save it. First, the feature vector is tiny — a couple of dozen floats — so scoring one frame is a handful of multiply-adds, and even a brute-force sweep of the whole database is cheap on modern hardware (it vectorises beautifully). Second, when the database gets big you swap the brute-force scan for a spatial index — a KD-tree or other approximate nearest-neighbour structure — which finds the closest feature vector in roughly O(\log n) instead of O(n). The elegant part is that the whole problem has been reduced to a generic nearest-neighbour query, so decades of NN acceleration research apply directly.

The obvious cost of motion matching is memory: you ship the raw mocap. In 2020 Daniel Holden, Oussama Kanoun and colleagues introduced Learned Motion Matching, which trains small neural networks to reproduce the behaviour of the search and the clips without storing them. One network compresses the pose data; another predicts the next feature vector given the current one (a learned "stepper"); a third decompresses features back into full poses. The result matches the quality of classic motion matching at a fraction of the memory — a few megabytes of network weights instead of hundreds of megabytes of animation — while keeping the same responsive, search-driven feel. It is the bridge from the data-driven era to the learned-motion era.

Motion matching feels like magic, but it has no imagination — it can only ever return a frame that is already in the database, scored by the weights you chose. Two failure modes follow directly, and both look like the character behaving badly:

Coverage gaps. If the player asks for a sharp 180° pivot and no clip in the database contains one, the search returns the least-bad frame it has — which might be a wide loping turn. The character does something plausible-ish but wrong, and no amount of tuning fixes a motion that simply isn't there. The cure is capturing more coverage, not tweaking code.
Bad weights. If the foot weight is too low, the search happily snaps to frames whose feet are in the wrong place, and you get foot sliding (skating). If the trajectory weight is too low, the character ignores the stick and wanders. If the pose weight is too low, limbs jump discontinuously on each match.

The slogan: motion matching is only as good as your database coverage and your feature weights. Debugging it is usually asking "is the right motion in the data?" and "are the weights sane?" — before touching the search itself.

Weighing it up

Pros. High animation quality straight from mocap; very little manual authoring (no hand-built state machine); highly responsive, because re-querying often lets input change the motion within a fraction of a second.
Cons. Large memory footprint (you ship the raw database); a search cost on every update (mitigated by acceleration structures); and sensitive tuning of the per-block feature weights.

Set against the sprawling, hand-wired graphs it replaced, motion matching trades authoring labour for data and compute — a bargain that got better every year as memory grew cheaper, and better still once Learned Motion Matching shrank the memory cost too.