Fast Path Finding (part I)

The other day in class I was telling my students that sometimes simple strategies simply do not cut it. As an easy-to-understand example, I discussed the behavior of baddies in video games. If your game asks for the baddies to chase the player, the first thing you might try is to move the baddies in the direction of the player, without any other sophistication.

monster-small

So the algorithm in this case is that you move the baddie closer to the player (or try to, as there might be obstacles), and this translates to something like two lines of code:

int dx=std::max(-1,std::min(1, player.x-monster.x));
int dy=std::max(-1,std::min(1, player.y-monster.y));

which assigns -1,0, or 1, to dx and dy; thus resulting the motion of exactly one tile closer to the player (and allowing diagonals).

These two lines of code are cute: minimalist, fail-safe, … and insufficient. If there’s an obstacle, we get something like:

simple-fail

where the baddy advances towards the player but is blocked by the obstacle. If the baddy has more than two non-dead neurons, it would quickly follow this path:

somewhat-better

And catch the player.

Accurate path finding (in this case, the shortest path to the player from any tile in the map) demands dynamic programming. Fast path finding demands good programming—we’ll come back on that part. Because of the structure of the graph—that is, the map—we can afford an interesting simplification of Dijkstra’s classic shortest paths algorithm, solving the problem in essentially linear time (in the number of tiles).

The algorithm goes as follows. We start where the player is (remember, the goal is to provide baddies with an optimal path to the player) and we set the value to zero. Everywhere else, the tiles’ value is \infty (some large numerical value, in practice, maybe std::numeric_limits<T>::max()). We scan the tiles immediately surrounding the one initialized to zero, and for each of these tiles, we look around for an already solved tile (one with non-\infty value), and pick the smallest one so far. We then set the tile values to the best tile value plus one (the path is now one longer) and the direction to this best tile. The tile now knows the length and direction of the shortest path to the player.

We repeat the scan around tiles already solved, and solve a few more tiles. We repeat until all (reachable) tiles are solved. The algorithm grows paths something like this:

(click to animate)

(click to animate)

When all tiles have been solved, we have a complete multi-path, avoiding obstacles, and the baddies can choose an optimal path to the player.

Of course, this has to be repeated every time the player moves; therefore we need a very fast implementation so that the computation of all path remains negligible in the whole game—especially important when we consider implementation on low compute power devices, say, and iPod or an Android phone.

The first implementation that comes to mind is to simply scan the whole map each time until all tiles are solved. To avoid weird artifacts, you need two arrays, one with all the values solved in the previous round, and one where you add the new values (or, if you’re more careful, a list where you keep where to put the new values). This is essentially an O(n^2) method. You scan each tile up to n times, resulting in n\times n operations. Let’s call this method naïve.

A C# implementation goes something like this (with preamble omitted):

  bool changed;
  Tuple<int,int> bestDirection=new Tuple<int,int>(0,0);
  do
   {
    changed=false;
    for (int h=0;h<height;h++)
     for (int w=0;w<width;w++)
      if (!obstacles[h,w]
          && (distances[h,w]==int.MaxValue))
       {
        int bestDistance=int.MaxValue;

        if (SolveAround(h,w,
                        ref bestDirection,
                        ref bestDistance))
         {
          newDistances[h,w]=bestDistance;
          directions[h,w]=bestDirection;
          changed=true;
         }
       }

    if (changed)
     // *much* faster than Array.Copy(...)
     for (int h=0;h<height;h++)
      for (int w=0;w<width;w++)
       distances[h,w]=newDistances[h,w];

   } while (changed);

(It’s C# because that’s what I teach in class.)

SolveAround is an helper function that looks at the 8 immediate neighbors of a tile and pick the best one (already solved) and returns best distance (length of path) and best direction.

*
* *

A better way would be to not copy the whole map, but to maintain the list of tiles we just solved. Then, you can find the tiles immediately neighboring the tiles we just solved and solve for them; and the newly solved tiles become the list of tiles just solved.

  do
   {
    currentList=nextList;
    nextList=new HashSet<Tuple<int,int>>();

    Tuple<int,int> bestDirection=new Tuple<int,int>(0,0);
    int bestDistance=0;

    foreach (var currentTile in currentList)
     {
      int h=currentTile.Item1;
      int w=currentTile.Item2;

      if (SolveAround(h,w,
                      ref bestDirection,
                      ref bestDistance))
       {
        distances[h,w]=bestDistance;
        directions[h,w]=bestDirection;
       }
     }

    foreach(var currentTile in currentList)
     AddUnsolvedNeighbors(currentTile.Item1,
                          currentTile.Item2,
                          nextList);

   } while (nextList.Count!=0);

Here, AddUnsolvedNeighbors scans the neighbors of a tile and add the unsolved ones to a list (nextList is in fact a HashSet, the closest thing to a bitmap C# has, as far as I know).

*
* *

Now let’s have a look at a complete (demo) application. The program reads a map, renders it in glorious utf-8 art, and lets you control a character with the arrow keys. The output looks like this:

carte-05

Where the left map shows the directions computed, the middle map shows distance in a kind-of-a-gray-level thing, and the right map shows the actual path length to reach the character. In the picture above, it’s somewhere in the room with nine pillars. The number at the upper left is the time in seconds taken to solve the map: 260µs—but that’s the C++ version.

But how fast is it in C#? Is it much slower than C++? What kind of optimization can we have to make it extremely fast? Let us have a look a performance of various implementations.

To be continued…

6 Responses to Fast Path Finding (part I)

  1. I’m not sure how much I’d invest in optimizing Dijkstra’s algorithm. It seems A* is likely to fare better, not to mention better possibilities (e.g., landmark algorithms).

  2. […] Last week we had a first look at a simple path finding algorithm with application to games. This week, let us have a look a the relative performance of the implementations considered: C# with a naïve implementation that scans the whole map multiple times; a C# implementation that uses lists to maintain and visit only the border of the solved region (affording massive speed-ups, one hopes); and C++ versions of these two variants, plus a C++ variant that uses set (as bitmaps) to maintain the border list. […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: