IA on AI

IA Information

Communication

Dave Mark's book,
"Behavioral Mathematics
for Game AI"
is available on Amazon.com!

Archives

IA on AI

Sunday, August 10, 2008

Fixing pathfinding a la Paul Tozour

My friend and colleague, Paul Tozour, has put up an excellent post at the internet blog he shares with some other big names, Game/AI. In it, he covers all sorts of stuff that is "wrong" with pathfinding and offers evidence as to why nav meshes are better than waypoint graphs. There's plenty of pretty images that he has created using real-world maps... er... maps from real-world games. Definately educational and thought-provoking.

Labels: nav meshes, pathfinding, Paul Tozour, waypoint graphs

Feedback and ratings:

View blog reactions

Friday, July 4, 2008

Damian Isla's 2005 AIIDE Slides

Got linked to this by Paul Tozour. Here are Damian Isla's (Bungie) slides from his 2005 AIIDE presentation on "spatial competence" entitled "Dude, where's my Warthog?" It includes info on a ton of the stuff he/they did in Halo 2. Included is information on pathfinding - especially with regard to how we (as people) process spatial information. It's nice to see someone else tapping into psychology as a source for potential solutions for game AI.

Fantastic stuff... and left me dying for the audio.

Labels: AIIDE, Bungie, Damian Isla, Halo, Halo 2, pathfinding, psychology, slides, using cover

Feedback and ratings:

View blog reactions

Tuesday, May 27, 2008

Why always the shortest path?

Christer Ericson, Director of Tools and Technology at Sony Santa Monica (the God of War team), has posted a teaser of sorts on his blog, realtimecollisiondetection.net. In Don't follow the shortest path!, he points out the near fanatical restriction to have the heuristic in A* be admissible, which is defined as not overestimating the theoretical path cost to the goal.

When the heuristic (h) is admissible, A* will return the shortest possible path. However, it also takes longer than when h is not admissible by the above definition. Even when not admissible, A* will find the path, but it may not necessarily be the shortest. His point is that we are spending a lot of calculation time achieving that shortest path when plenty of other paths would do.

When h(x) is admissible, meaning it doesn't overestimate the true cost of reaching a goal, A* is guaranteed to find a shortest path (if one exists). And herein lies the problem: 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. We can reduce search effort, sometimes drastically, by forfeiting the guarantee of an optimal shortest-path using nonadmissible heuristics.

He quotes a few other researchers in the column and makes a couple of other points. While I like the idea, I wish that he would have shown some examples of why this sort of fanaticism is unwarranted... or at least overrated. Thought-provoking read, however.

In my opinion, he's on the right track. In my weekly Developer Discussion column I have even made similar points about our addiction to exactness where it is not necessary and speed where it is not warranted. There are times when we are either simply not solving the right problem or we are approaching it with a level of granularity that significantly overshoots what it is we are trying to emulate. Christer makes that point briefly above when he points out that we humans rarely take the exact shortest path. When weighed against the diminishing returns of calculating it, is it worth it?

Labels: A*, Christer Ericson, pathfinding, RealTimeCollisionDetection.net

Feedback and ratings:

View blog reactions

Friday, February 29, 2008

Other coverage of GDC sessions

I have kinda entered a vortex of browsing through other people's GDC coverage - especially on the sessions that I could not attend. Note that I don't necessarily agree with everything that people have posted here - I'm just including them so people can have a broader picture. Here's a partial list of (loosely) AI-related stuff that I have found so far:

GDC: Storytelling in Bioshock (Not really AI, but interesting)
GDC: Rules of Engagement
GDC: Rules of Engagement Part 2
GDC: A Q&A With Sid Meier (Not really AI... but it's Sid!)
GDC: Creating a Character in Uncharted (animation AI)
GDC: Creating believable crowds in Assassin’s Creed (group behavior and many units)
GDC08 Notes - Streaming Open World Pathfinding (Obviously pathfinding)

A thread at Game/AI where Jeff Orkin (F.E.A.R. AI mastermind) asked what we all saw at GDC it made for an interesting AI discussion.

Labels: animation, Assasin's Creed, BioShock, crowd simulation, GDC, GDC 2008, group behavior, Jeff Orkin, pathfinding, Sid Meier

Feedback and ratings:

View blog reactions

Thursday, November 15, 2007

Autonomous Movement in a Hostile World

Movement in a dynamic world - especially with hostile entities and constantly changing safe and danger zones - is a dicey issue in game AI. AIGameDev.com has posted a great article about some work by Leslie Ikemoto from the University of Berkeley that I believe has some great future relevance to the game industry.