IA Logo

IA Information

Dave Mark's books

IA on AI

Posts Tagged ‘pathfinding’

Lydia vs. the Gate: Will she ever learn?

Monday, November 21st, 2011

10 days in and I still have not played Skyrim. I’ve been too busy. However, that doesn’t stop me from seeing what other people have pointed out. Given that it is a PC-playable game, there are no shortage of YouTube videos out showing many of the plusses and minuses of it. (There seem to be plenty of both.) If I took the time to analyze each one that I saw, I would never get anything done and would have even less time to play it myself. That said, some things are too easy to pass up.

This video came to my attention via someone on Twitter and I thought it was worth a mention.


This is something that is so easily fixed that it is spectacular that this even occurs.

Obviously, our poor Lydia is having a difficult time with this gate trap. The problem is, she really shouldn’t. While we can understand Lydia getting whacked the first time (after all, that’s what traps are all about, right?) why is it that she persists in trying to go through the same area? This is something that is so easily fixed — even with likely existing tech and logic — that it is spectacular that this even occurs.

The short version of why this is happening can likely be summed up as follows:

  1. The pathfinding engine in Skyrim is a waypoint graph rather than a navmesh. The edge that she is trying to follow runs right through the middle of that gate and, therefore, right over the trap trigger.
  2. Even when knocked off the graph, her top movement priority is to get back on the path at the nearest node. This is why she moves to the center of the hall instead of just moving along the left (her left, our right) wall towards the player.
  3. She has no recollection of getting hit by the gate. Therefore, nothing about her processing is different in each iteration.
  4. Even if she recalled that the gate is the problem and was able to understand that the trigger stone was the issue, on a waypoint graph she has no way to really steer around the stone anyway.
  5. When she is stuck behind the gate against the wall, she has no realization that she is stuck… therefore, she keeps “running”.

As you can tell, this could be remedied fairly simply. First, for the pathfinding issue, a navmesh would be very helpful here. (For an excellent treatment on waypoint graphs vs. navmeshes, see Paul Tozour’s post on Game/AI, Fixing Pathfinding Once and for All.) That way, the stone could be created as a separate mesh polygon and, upon discovery, marked as as something to avoid.

Of course, the above is premised that the stone can be “discovered” in the first place. Certainly, Lydia managed to “discover” the stone when she got whacked the first time. What she failed to do was make a mental note (in an e- sort of way) of its existence. It is at this point that the AI started to look stupid. Again, not really all that hard to handle. In fact, by simply doing what I suggested above (marking up the navmesh as being unusable), this becomes implied by her subsequent behavior of avoiding the stone. No animations, voice barks, etc. needed. She just doesn’t do the same thing twice.

The being stuck behind the gate thing is actually a separate problem entirely and I won’t bother to address the details here. Suffice to say, however, that it is partially similar in that it is based on the notion that NPCs rarely have a sense of “futility”.

Anyway, I just thought that this was worthy of note specifically because the solution is so easy to implement. It makes me wonder why major studios can advance so much in some aspects of their AI and yet have such glaring holes in other areas. I suppose that’s why we now have the AI Game Programmers Guild and the GDC AI Summit. We are trying to share enough information between us that we are lifting the floor of game AI as a whole.

Real-world Behavior/Bad Game AI: Doggie Pathfinding Fail!

Monday, November 21st, 2011

Yet another video example courtesy of our dogs (and my somewhat mischievous kids). Obviously Jake is having pathfinding issues despite knowing where he wants to go and seeing his way out. If this were in a game, it would go up on YouTube as an example of bad game AI. So why not put it up there anyway?


Fixing pathfinding a la Paul Tozour

Sunday, August 10th, 2008

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.

Damian Isla’s 2005 AIIDE Slides

Friday, July 4th, 2008

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.

Why always the shortest path?

Tuesday, May 27th, 2008

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?

Other coverage of GDC sessions

Friday, February 29th, 2008

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.

Autonomous Movement in a Hostile World

Thursday, November 15th, 2007

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.

Although it is 153 MB, make sure you download the video file that shows the agents in motion. Great stuff!

Add to Google Reader or Homepage

Latest blog posts:

IA News

IA on AI


Content ©2002-2010 by Intrinsic Algorithm L.L.C.