Pathfinding Part 1
The fundamental goal of a game AI system is to make the non player characters appear smart. Well, that may be over reaching a touch; making the non player characters appear not stupid is a high enough bar for my AI ambitions on this project. The problem is that it is very difficult to make an AI that can compete in a wide array of situations with even the most developmentally handicapped elementary school student.
There are a few impressive applications of AI concepts that have been developed but they all apply only to a very specific, or a set of very specific situations, and usually they have a lot of help. By a lot of help, I mean, autonomous vehicle systems that work splendidly as long as they are given gps waypoints every couple meters or warehouse management robots that read barcodes off the floor to determine where they are and are fed the locations of every other robot in the warehouse so they don’t collide. I certainly don’t mean to demean either of the two systems that I mention, but to my childhood-sci-fi idea of artificial intelligence, they seem like cheating. They would also fail to follow instructions that our hypothetical kindergartener could perform with ease, such as: “walk to school,” or “find all the red things in the warehouse.”
Well, if those seem like cheating, game AI will seem like reading the answer out of the back of the book. Or, in the case of my Pathfinding AI system, precalculating every answer, then just looking up the one that we need this time.
The Problem
Characters in a game need to move from one point to another. In fact, this needs to happen quite a bit. In many cases the motion of one or more characters is what drives the game.
Unless you’ve had some exposure to this problem before, it probably doesn’t sound like much of a problem. Just tell the character to move from point A to point B right? The shortest distance between two points is a line. But, what if there is a mountain in the middle of that line, or if point A is in the middle of the street and point B is at the top of a sky scraper? The problem is (unfortunately) much more complex.
A Solution
For any pathfinding solution you need a method to determine if a given move is legal. This can be broken down into a simpler form by creating a way to determine if a given “step” is legal. By step, I mean a very small move from one point to a very nearby point. Once we have that, we can determine the legality of any move, since any longer move can be made up of a series of small steps in various directions. I use my engine’s physics system as the basis for the “is this step legal” test. Although the test can be as simple as a collision test, a lot of extra work is required to allow walking up hills or stairs and making sure we don’t walk off a cliff. PhysX has some nice tools to make writing those extra checks easier.
A graph walk between the two circled points.
To simplify the problem a bit, lets say that our character can only walk in four directions in increments of some small length (the same small length that we called a “step” in the previous paragraph). This may sound like an over-simplification but it isn’t far off from my first implementation (I allowed diagonal steps, for a total of 8 possible moves from each point).
Now we have set up the problem in a way that we can apply a terribly useful algorithm from graph theory called A* (pronounced “A star”). In plain english it amounts to at each point choosing the move that brings us closest to our destination while adding the least distance to how far we have to travel to get there. In the illustration to the left we want to get from one red circle to the other. The black lines represent legal moves. One could trace a large number of possible paths between the red circles, some longer than others (a path that went in circles could be infinitely long). One could also find several shortest paths, such as the two paths highlighted in green. A* finds a shortest path between the start and the end, which shortest path we end up with depends on the intricacies of the particular implementation (which I won’t discuss because it’s dull and not terribly important).
This solution works, but it is also slow because we run our physics check four times for each step along a path. Another reason it is so slow is that our step length needs to be short enough to find it’s way through doors and narrow passages. If the diagonal of the grid formed by the step length is bigger than a doorway, it may never find it’s way through a door that is positioned at a 45 degree angle to the grid. Essentially, this means we need to be checking a LOT of steps, which means running our physics test a lot. When I had one character pathfinding using this implementation I was spending 1/20th of every second on pathfinding. Even though I could have done a lot to optimise the implementation for speed, this was orders of magnitude off the time I have to spend on pathfinding. If I had just 20 characters pathfinding, the performance of the game would be seriously affected. I needed a drastically different approach.
To be continued in Pathfinding Part 2 or A Millisecond Saved is a Millisecond Earned.
Tags: A*, Artificial Intelligence, Game AI, Pathfinding
