Wednesday, December 19, 2007

Virtual Extras

Giving each member of a digital crowd its own personality could make animated mob scenes more realistic.

By Duncan Graham-Rowe

Places to go, people to see: Giving animated characters their own personalities could make computer-generated crowd scenes in movies and video games more realistic. Credit: W. Shao and D. Terzopoulos

Multimedia •  Track a single autonomous agent through a crowd scene. •  Watch virtual crowds stream through New York City’s Penn Station. •  See a simulation of the Great Temple of Petra, in Jordan.

The behavior of computer-generated crowds in movies and video games could soon appear much more realistic, thanks to new software that gives each character a complex personality of its own.

The software has been demonstrated in a simulation of Pennsylvania Station, in New York City, depicting more than 1,000 commuters, law-enforcement officers, entertainers, and tourists going about their business. Each individual demonstrates complex, rational behaviors that collectively create a much more lifelike representation of human activity, says Demetri Terzopoulos, a professor of computer science at the University of California, Los Angeles.

This sort of realism is important in games and motion pictures, says Norm Badler, director of the Center for Human Modeling and Simulation at the University of Pennsylvania. Even though simulated crowds tend to form part of the backdrop to the foreground action, they will stand out if their behavior is unrealistic, he says. "The whole animation should look plausible."

Until recently, crowd-animation algorithms have typically been based on some form of flocking activity, in which each character moves in a particular way depending upon how its neighbors move. This works fine for depictions of animal behavior, such as the well-known wildebeest stampede in Disney's The Lion King, says Terzopoulos. But in simulated humans that should evince some cognitive capacity, this sort of movement can appear aimless and random, says Badler.

The "autonomous pedestrians" designed by Terzopoulos and graduate student Wei Shao, on the other hand, are governed by three different layers of behavior. A motion layer handles basic movement, such as walking, running, standing, and sitting. On top of this sits a reactive layer, which allows the characters to respond to obstacles or other characters they encounter; it also enables them to perform simple behaviors that people normally take for granted, such as walking around a bench in order to sit on it.

But where the real complexity comes from is the top, cognitive layer. "This is where the agent is able to think ahead about what it's going to do in the future," says Terzopoulos. "It's a comprehensive cognitive model of people from the ground up."

For example, a character may be charged with the simple task of catching a train. But it knows that, in order to perform this task, it must carry out a number of subgoals, such as purchasing a ticket and finding the train platform. In fact, even these subgoals can have further subgoals, such as finding the ticket office and choosing the shortest ticket line to stand in.

This is a complex planning problem that can be exacerbated by a character's failure or success in meeting each of its subgoals, says Terzopoulos. "If you want to catch a train, but there are no tickets left, then you have to replan and maybe buy a ticket for a later train."

To make characters' behavior still richer, animators can also give them desires, which might make them stop off to buy a soda from a vending machine or pause to watch some street entertainers. Terzopoulos's software even manages to capture the way in which two crowds of people, moving through a narrow corridor, naturally form two opposing lanes.