Gaming - step by step

March 19, 2010 By Ileiren Poon, University of Alberta

( -- For one University of Alberta professor, making the move from California to Edmonton turned out to be the first step in becoming involved with an award-winning video game.

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 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."

Explore further: Degree offered in computer game design

Related Stories

Students Launch Audiball, an Xbox Community Game

January 16, 2009

( -- Most students like to play video games, but Georgia Tech students Holden Link, Cory Johnson and Ian Guthridge have built and are selling their own. Their game, Audiball, was launched during the first week ...

Video games shown to improve vision

March 15, 2007

According to a new study from the University of Rochester, playing action video games sharpens vision. In tests of visual acuity that assess the ability to see objects accurately in a cluttered space, game players scored ...

Leveling the gaming field

May 13, 2008

A new computer game developed by MIT and Singaporean students makes it possible for visually impaired people to play the game on a level field with their sighted friends.

Computer games can teach schools some lessons

February 19, 2010

Some parents might see video games as an impediment to children keeping up with their schoolwork. James Gee, however, thinks video games are some of the best learning environments around. He says that if schools adopted some ...

Recommended for you

What do you get when you cross an airplane with a submarine?

February 15, 2018

Researchers from North Carolina State University have developed the first unmanned, fixed-wing aircraft that is capable of traveling both through the air and under the water – transitioning repeatedly between sky and sea. ...


Adjust slider to filter visible comments by rank

Display comments: newest first

1 / 5 (1) Mar 20, 2010
I may be in a minority but I think DAO is a steaming heap. It's heavy on talk, light on action and a closed world that you can't explore. No problem with path finding because you are on rails. This must be the new kind of game for the illiterates who want their stories in the game because they don't know what a book is. For myself, when I want a good story I'll read a book or watch a movie. Games like this are a sign of the end of literacy.
1 / 5 (1) Mar 22, 2010
Unfortunately, many people who are playing games are using them to fill in "stories" for them. All the actual gamers I know, tend not to read. I'm a reader, and I tend not to game. Once again this is a sad thing but I think you're right fourthrocker. They should make all games now like the old school legend of zelda's etc, where you have to READ the story right from the screen. But I suppose that is taking a step back and will never happen.
not rated yet Mar 22, 2010
I'm an avid reader. I also happen to be a hardcore gamer and am about 75 hours into DAO. I can tell you that I have done enough reading in this game to fill two or three novels. The real meat and potatoes of the story here is in the codex entries. If you stop and read every codex entry (which provides most of the lore and back-story for the game) it amounts to a lot of reading. And to royale, The old Zelda games were pretty light on text compared to true RPGs like Final Fantasy and the Dragon Quest games, or one of the old text RPGs like Zork which is still an extremely entertaining game.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.