Gaming - step by step

Mar 19, 2010 By Ileiren Poon

(PhysOrg.com) -- 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: A new kind of data-driven predictive methodology

add to favorites email to friend print save as pdf

Related Stories

Students Launch Audiball, an Xbox Community Game

Jan 16, 2009

(PhysOrg.com) -- 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

Mar 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

Feb 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

New frontier in error-correcting codes

10 hours ago

Error-correcting codes are one of the glories of the information age: They're what guarantee the flawless transmission of digital information over the airwaves or through copper wire, even in the presence of the corrupting ...

Five ways the superintelligence revolution might happen

Sep 26, 2014

Biological brains are unlikely to be the final stage of intelligence. Machines already have superhuman strength, speed and stamina – and one day they will have superhuman intelligence. This is of course ...

User comments : 3

Adjust slider to filter visible comments by rank

Display comments: newest first

fourthrocker
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.
Royale
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.
rhuarch
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.