January 04, 2004
Sentient Beings in a Digital Landscape
Recently film enthusiasts have flocked to movie theaters to enjoy the climax of the Lord of the Rings Trilogy - The Return of the King. A major scene in the film is the ultimate battle that wages humanity against the monstrous forces that would dominate Middle Earth, the Ringwraiths.
The battle represents a milestone in computer-generated filmmaking. Combat scenes have traditionally been one of the most challenging because of the complexity. There is a mix of chaos and purposeful action that plays out when soldiers clash in large numbers. 
If you increase the number of characters to the thousands and make each fighter appear autonomous onscreen, the level of programming intricacy increases dramatically. Needless to say, new technology was required.
According to Karl Sims, a former MIT researcher whose 1994 paper, "Evolving Virtual Creatures,"human (and humanoid) forms represent the highest order of computer graphic simulation because audiences are trained since birth to track human movement in all its complexity. So far, Sims says, filmmakers have done better with smaller creatures: "Even swarms of insects are easier to simulate than humans."
Previous simulations of digitally created physical interactions in crowds were relatively simple. Using basic rules governing attraction and repulsion, designers aimed single points called particles at each other. Each particle represents a different individual, and when a satisfactory mix is achieved to portray the movements of a group or crowd, animation is added: The particle is rendered as a digital human or creature. The result is not always natural-looking movement in two-dimensional space. The movement of real people, especially in battle over rough terrain, is a hugely more complex challenge for the programmer.
New Zealander, Stephen Regelous, wrote a software program called Massive. It generates crowds whose interaction is based not on particle dynamics but on unique and unpredictable choices made by individual characters within a scene. Rather than concentrating on duplicating mechanical actions, Massive endows each character with a digital brain and gives it the power to act completely on its own. In an AI sense, the characters fighting in Helm's Deep are actually fighting. 
Massive characters, or "agents," function as complex beings subject to physical forces, with specific body attributes that range from the biological (short, good eyesight, dark skin) to the behavioral (aggressive). These features govern a Massive character's ability to generate credible motion. Each character is assigned a host of potential actions, as many as 350, each about a second long (sword up, sword down, step forward, step back). How these actions play out is determined by the character's brain, a tangled web of anywhere from 100 to 8,000 behavioral logic nodes, which provide the rules that allow each character to perceive, interpret and respond to what's happening around it: to make decisions and act. These nodes group into rule collections which control aggression, fighting style, movement across varied terrain, and a dozen other factors.
Fuzzy logic is needed to support the random and variable events that introduce the element of the unpredictable into digital scenes and make the result much more human. A Massive archer doesn't just hit or miss his target. He adjusts his aim as each arrow follows a slightly different and random trajectory. Success or failure is based on many complex and sometimes interrelated factors, including the skill level he's been programmed with, the weather, and even his mood at the time; but, as in the real world, there's no way to know whether any single shot will be on the mark.
And behavior changes. Massive-generated characters are convincing in part because their inputs come from the digital landscape around them; each has eyes and ears on which it must rely to navigate through battle.
Once created, Massive characters are inserted into unpopulated scenes. The characters are then left to do what they've been created to do, and a battle scene assembles itself. This can take minutes, or overnight, depending on the size and complexity of the scene. Beyond general tendencies, the filmmaker does not know precisely what a character will do, since each is an autonomous and, within the confines of the digital landscape, sentient being.
Adapted from Popular Science, Dec 2003
Digital Horses Quicktime Video
Posted by rsk at January 4, 2004 10:37 PM