You would think computers would be super smart — and infinitely better than humans — at figuring out how to get from Point A to Point B. Isn’t that why we use Google Maps and the like as navigational aids?
But it turns out that computers are not great at getting animated characters from one point to another. For long, this has posed a sticky problem for scientists and game developers. Consequently, on-screen personas are jumpy, awkward and plain inefficient — though these probably add a comic element to animated shows, in games the lapse can be critical to users, and certainly strain the resources of a computer.
Nevertheless, this is a serious problem that gripped software developers. The good news is: a breakthrough has been cited at NICTA.
Daniel Harabor, a PhD student with a fascination for artificial intelligence environment in video games, promises a future where animated characters in computer games move more efficiently, naturally and intelligently.
“In video games, characters don’t move around in an intelligent way – they take dead end routes, bump into things – and I was curious about how this could be addressed,” he says. “Once I started looking into it, it turned out that finding the shortest path between two points is a really difficult problem for scientists and games developers.”
Thus far, developers have addressed this problem by making “approximate paths” for their characters to take.
The leap forward
“This is a common approach. The character doesn’t find the shortest path, but they find one that is pretty good,” Harabor explained. However, “this can be costly in terms of memory and CPU, which is important because the bulk of available CPU and memory in computer games must be given over to rendering the environment to make the game viable. The less memory and CPU required getting your character from A to B, the better.”
Harabor’s “Jump Point Search” tries to efficiently speed up the process of finding the shortest path, by eliminating several less efficient routes. The technology identifies, on the fly, a large number of equivalent solutions but examines only those paths that are “fundamentally different,” eliminating redundant work.
“The algorithm is fast, requires no additional memory, zero pre-processing time, and always returns the shortest path,” says Harabor. “On maps taken from real computer games, the approach is 10-15 times faster, on average, than comparable industry standard techniques.”
“Daniel’s achievement is a tribute to his talent and hard work, and also to the collaborative research environment we foster here at NICTA, where students are supported and guided by some of the most accomplished ICT researchers in the world,” said NICTA CEO Hugh Durrant-Whyte. “He has a very bright future.”
Harabor’s Jump Start Search was “highly commended” at the Nasscom Student Innovation Awards presented earlier this month at the CeBIT. Harabor, who is studying for a doctorate in Computer Science at the Australian National University and NICTA, is evaluating if he can use the Jump Point Search algorithm to take a stab at real-world problems such as finding the most efficient route on a road network. He is also working on making the algorithm run even faster.
“We are trying to identify real-world applications that are analogous to the computer games environment.”
Harabor’s supervisors at NICTA are Phil Kilby, a NICTA Principal Researcher and joint winner of the ICT category of The Australian’s Innovation Challenge last year. He was also supervised by former NICTA Senior Researcher Adi Botea and NICTA Researcher Alban Grastien.
