In the comments to last week’s column, Querying the Real Minds Behind the Artificial Minds…, Kevin Dill tossed out some things that have been on his mind lately that he would be interested in asking a gathering of top AI developers.. One of his ideas was something that I have actually seen before, yet I haven’t really seen a lot of discussion on the subject. He asked:
“How can we move from finding the shortest path to finding the best path? What does ‘best’ mean? For a dog? For a soldier?”
I find it strange to think that this hasn’t been hashed out more given that pathfinding is so completely ubiquitous in games and, despite that ubiquity, is something keeps garnering significant space in tomes of AI knowledge and learning. That is, while pathfinding may be “solved”, it is by no means “perfected.” How does the saying go…? “Five minutes to learn — a lifetime to master?”
However, what Kevin brought up was not fishing for how to “perfect” pathfinding in the objective sense. He was asking a more ephemeral question. How to “perfect” pathfinding in the subjective sense. Christer Ericson of RealtimeCollisionDetection.net recently touched on this problem in a blog post where he suggested that the extra clock cycles we burn to find the exact shortest path are perhaps a waste of time on what amounts to diminishing returns. He pointed out:
“…much too much effort is spent in games in finding the shortest paths! There is a near obsession with admissible heuristics, which is completely misguided! Who the heck cares about the shortest path?! In our everyday lives we rarely, if ever, take a shortest path. Instead, we often optimize for search effort, taking a path we’re familiar with (which we’ve chunked or otherwise memorized so as to require no search). Well, the same applies to games and the A* algorithm.”
Interestingly, I think Christer’s point solves Kevin’s question to an extent. In the search for extra clock cycles, Christer made the point that people are rarely perfectly efficient… and that’s what makes us look like… well… us. It would also be what makes a dog look like a dog, as Kevin asked for. A soldier is going to move a bit differently through an environment than is a layman. A tourist is going to move slightly differently than a businessman. Someone unfamiliar with their surroundings is going to path a bit different than someone on mental autopilot. Someone suspicious or frightened of the unknown will move differently than someone who is confident… or for that matter, differently than someone to be suspicious of. Some of the above can be accounted for with animation, of course. However, there is a layer of subtlety that can be achieved with the pathfinding itself.
So I guess I want to co-opt Kevin’s comment from last week and ask you folks a series of questions:
First, is there any benefit computationally to not calculating the best path and simply settling for something that looks “good enough?”
Second, is there any benefit from a design standpoint to going out of our way to intentionally tweak paths for different characters — or even types of characters?
Third, in doing number two… what sort of features — from a design standpoint — would this “best path” entail?
Fourth, in doing number two… what sort of challenges — from a technical standpoint — would this approach create?
(Of course, a conversation around that may amount to a whole new Pathfinding section in the next AI Game Programming Wisdom book!)
