Dragon Age pathfinding program put to the test

(Edmonton) 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. Once 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, a big presence in the video game industry, 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 most 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 doesnt 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 calculates 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 theyre 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.

Category:

Education

Tags:

• University
• of
• Alberta
• Edmonton
• Computing
• Science
• Dragon
• Age
• BioWare
• Nathan
• Sturtevant

[evfyiv]

Amaaaaaazing!

[eesogmo]

Amaaaaaazing!

[FGsGFdG2]

This is really impressive, but somehow path finding isn't nearly this good in the game.

[phthartic]

What I don't undestand is how your experience can be so opposite to mine, unless this is an ironic spoof. I literally can't click 5 steps away on open ground without my character running off in the wrong direction and finding a clump of grass to get stuck behind. I've tried the same sort of test and it hasn't worked yet even on much easier paths.

[krgrief]

1337 views.

[apfrezende]

Finding paths like a boss.