Gaming - step by step

Nathan Sturtevant came to the U of A from the University of California, Los Angeles, where his work focused on artificial intelligence programming for multiplayer games like hearts or Chinese checkers. During a conference in Edmonton, he met U of A vice-provost (information technology) Jonathan Shaeffer, whose games work Sturtevant was familiar with

"The U of A is well known for work in games and artificial intelligence," Sturtevant said. "I knew that there are really great people to work with here and I was very happy to come up and be part of the group."

Then, in 2005, Edmonton game developer BioWare approached the U of A computing science department, looking for help with a "pathfinding" challenge in their game Dragon Age: Origins.

Pathfinding is a major element in most modern video games, but not one many gamers think about unless things goes wrong. The ability to click a computer mouse to set digital characters in motion perhaps seems like it should be intuitive in this day of blockbuster games, but getting around or navigating in a complex and crowded game environment can make the journey slow and frustrating, the exact opposite of what video games are expected to deliver. Pathfinding allows the game programming to break the planning process into components, one following the other, so the program doesn't have to tackle all the planning at once.

"If you go back to [earlier] BioWare games you find that essentially what's going on is your character is trying to find an entire path of how to get to their destination before anything else happens," said Sturtevant, a professor in the Department of Computing Science. "There are many cases where that can be really difficult and unnecessarily slow the game down. If you can imagine a [game scenario] with a lot of things going on, or a lot of barriers to get around-in that type of situation the pathfinding program would just fail.

"In the game Dragon Age, BioWare was running exactly into that problem, and they have even more complicated environments than the one I described, and they needed some way for the characters to solve things a little faster," he explains.

Make it faster with fewer resources

So, faced with the challenges of creating pathfinding programming able to navigate complicated environments while minimizing the amount of overhead in terms of memory needed, Sturtevant chose to break the decision-making process into separate levels, leaving the computer to calculate the steps needed by the character.

"In a lot of games when you say 'go do something,' the character sort of sits there for a while as the program is planning and then they take off," he said. "What we did then is you get this very high-level path that says 'You're going this way' and then we can then cut it down into small pieces. You don't need to figure out how to get all the way to your goal, you just need to figure out how to get to the next step along this path."

Sturtevant says he wanted players to be able to trust that a character is going to get where they're going. "One of the things I really wanted to see was that if a character is standing on one side of the game map, would it be possible to mouse click on the farthest point away and watch your character then walk for 10, 20, 30, 40 seconds and get to where you wanted them to go?" he said. That turned out to be the case, which allows players to attend to other characters or decisions within the game as the pathfinding command is being carried out.

Working on Dragon Age was an exciting opportunity, said Sturtevant. "I get to be here in academia at the U of A and work on all these problems, but to be a part of something that millions of people are playing and enjoying, that's pretty thrilling."

Provided by University of Alberta (news : web)