|
|
In explaining the problem, Harabor pointed out that, "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. 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."
In getting around this problem, developers would create approximate paths for the characters to take within the game, but this always seemed to create clunky, unrealistic movement.
"This is a common approach," said Harabor. "The character doesn't find the shortest path, but they find one that is pretty good. 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."
This is where the fruits of his work come in. "Jump Point Search tries to efficiently speed up the process of finding the shortest path," he says. "Many paths look the same, but these alternatives cannot, logically, be better than the shortest. Our method eliminates the other paths from consideration. There are methods that are faster, but they use a lot more memory. They can also spend many minutes or even hours pre-processing. No other method we know of is as fast and has the same advantages."
In addition to games research, Harabor notes, "We are trying to identify real-world applications that are analogous to the computer games environment." With that in mind, he has already identified the problem of efficient path-finding in roads networks as an analogous problem. Presumably the developers of GPS systems may be interested in this research.
But what about the near-term use of this research?
