Find the shortest path between two tiles in a grid in XNA

I am currently developing an adventure board game in XNA, in which the players can play various missions that take place on dynamic boards that are made up of tiles.

In the game, players should be able to select to which tile they want to move their game piece. The game should then suggest the shortest possible path to reach that tile.

The path finding algorithm will also be used by the game to move the various enemies that are to be controlled by the computer, thus providing a primitive form of AI.

To improve the AI illusion a bit, the algorithm should also be able to select a random path if multiple options exist, which will give the enemies a random, unpredictable (well, sort of) behavior.

Before I describe the method, let’s just recap a bit.

Board movement

In the game, players and computer controlled enemies can move horizontally and vertically over the board.

Board movement example

Factors that limit whether or not a game piece can move from one tile to another (tile A to tile B) are (so far):

  • Tile B simply does not exist (the piece would move outside of the board boundaries)
  • Tile B is marked as a None or a Nonwalkable tile (see below)
  • Tile B belongs to another room and is separated from tile A by a wall (covered in the previous post)
  • Tile B is occupied by another piece or furniture (another piece cannot stop at the same tile)
  • Tile B is occupied by a player or enemy (players and enemies cannot walk past eachother)

All these rules are (in my game) handled by a single Tile class function – x.CanMoveTo(Tile y). This function is not presented here, since it is very specific to my game.

Tile types

I have chosen to limit myself to three different tile types:

  • None (tile has no properties and is ignored)
  • Nonwalkable
  • Walkable

The None type is not really needed, but I have kept it to separate tiles that are not to be considered as part of the game board from tiles that just cannot be entered.

Path finding overview

Consider the following map, where a player stands on the green tile and wants to move to the red tile:

A player on the green tile wants to move to the red tile

In the example above, multiple “shortest paths” exist. As we will see later, the method presented below will find a random path each time it is executed.

The method presented below has the following main steps:

  1. Beginning at the start tile, set its “path length” to zero.
  2. Recursively handle each sibling, according to the following:
    • If the sibling has not been handled yet, set its path length
    • If the sibling has already been handled, do it again if the new path length is shorter
  3. When no tile can be improved, start at the end tile and find the shortest path to the start tile

I call the two main procedures spreading (a tile spreads its path length to its siblings) and tracing (trace the shortest path that has been found during the spreading operation).

Step 1: Spreading

In my game, the path finding operation is started with the following Board class function :

   //Placeholder for the calculated path (not thread safe :)
   int[,] pathLengths;

   public List<Tile> FindPath(Tile startTile, Tile endTile)
   {
      //Abort if start or end tile is null
      if (startTile == null || endTile == null)
         return new List<Tile>();

      //Abort if the end tile is non-stoppable
      if (!endTile.IsStoppable)
         return new List<Tile>();

      //Initialize the path length array
      pathLengths = new int[Tiles.GetLength(0), Tiles.GetLength(1)];
      for (int y = 0; y < pathLengths.GetLength(1); y++)
         for (int x = 0; x < pathLengths.GetLength(0); x++)
            pathLengths[x, y] = int.MaxValue;
 
      //Begin at the start tile
      pathLengths[startTile.BoardPosition.X, startTile.BoardPosition.Y] = 0;
      FindPath_Spread(startTile);

      //Once done, backtrack from the end tile
      List<Tile> result = FindPath_Trace(endTile);

      //Only return the path if it contains the start tile
      if (result.Contains(startTile))
         return result;
      return new List<Tile>();
   }

This function corresponds to the first part of the numbered list above. We do not proceed if any tile is null or if the end tile cannot be stopped at. We then initialize the placeholder array with max values, then begin our spread operation at the start tile.

Once the spread operation is done, we trace the path, but let’s return to that part later.

As you can see, the function only returns a path if it contains the start tile. If the trace operation cannot reach the start point, we cannot reach the end point from the start point, and thus no path should be returned.

The spread operation is a recursive one that eventually will handle each tile at least once. It consists of two functions:

   private void FindPath_Spread(Tile tile)
   {
      FindPath_Spread(tile, tile.TopSibling);
      FindPath_Spread(tile, tile.LeftSibling);
      FindPath_Spread(tile, tile.RightSibling);
      FindPath_Spread(tile, tile.BottomSibling);
   }

   private void FindPath_Spread(Tile tile, Tile target)
   {
      //Abort if any tile is null
      if (tile == null || target == null)
         return;

      //Abort if no movement is allowed
      if (!tile.CanMoveTo(target))
         return;

      //Get current path lengths
      int tileLength = FindPath_GetPathLength(tile);
      int targetLength = FindPath_GetPathLength(target);

      //Use length if it improves target
      if (tileLength + 1 < targetLength)
      {
         pathLengths[target.BoardPosition.X, target.BoardPosition.Y] = tileLength + 1;
         FindPath_Spread(target);
      }
   }

Beginning at the start tile (which has a path length of zero), the path info is spread out to the tile siblings, but is only regarded if the sibling’s path length would be improved. Thus, the recursive operation will stop once all tiles are “as good as they can be”. When this happens, the spread operation will automatically stop.

Step 2: Tracing

Once the spread operation is done, the recursive trace operation will be started, which we could see in the FindPath function above.

The trace operation will start at the end tile and follow the shortest way back in an attempt to reach the start tile. If the start tile cannot be reached, no path exists between the two tiles. The operation will then return an empty list.

The trace operation consists of a single function:

   private List<Tile> FindPath_Trace(Tile tile)
   {
      //Find the sibling paths
      int tileLength = FindPath_GetPathLength(tile);
      int topLength = FindPath_GetPathLength(tile.TopSibling);
      int leftLength = FindPath_GetPathLength(tile.LeftSibling);
      int rightLength = FindPath_GetPathLength(tile.RightSibling);
      int bottomLength = FindPath_GetPathLength(tile.BottomSibling);

      //Calculate the lowest path length
      int lowestLength =
         Math.Min(tileLength,
         Math.Min(topLength,
         Math.Min(leftLength,
         Math.Min(rightLength, bottomLength))));

      //Add each possible path
      List<Tile> possiblePaths = new List<Tile>();
      if (topLength == lowestLength)
         possiblePaths.Add(tile.TopSibling);
      if (leftLength == lowestLength)
         possiblePaths.Add(tile.LeftSibling);
      if (rightLength == lowestLength)
         possiblePaths.Add(tile.RightSibling);
      if (bottomLength == lowestLength)
         possiblePaths.Add(tile.BottomSibling);

      //Continue through a random possible path
      List<Tile> result = new List<Tile>();
      if (possiblePaths.Count() > 0)
         result = FindPath_Trace(possiblePaths[RandomHelper.GetInt32(0, possiblePaths.Count())]);
 
      //Add the tile itself, then return
      result.Add(tile);
      return result;
   }

The FindPath_GetPathLength function is only a small function that I added in order to avoid duplicate code:

   private int FindPath_GetPathLength(Tile tile)
   {
      if (tile == null)
         return int.MaxValue;
      return pathLengths[tile.BoardPosition.X, tile.BoardPosition.Y];
   }

Example

If you consider the map that I presented at the beginning of this blog post, my game will parse it into a game board as is described in the previous blog post.

This is how my game (for now) displays the tiles (walls are missing)

In the image above, all tiles are walkable, to increase the number of “shortest” paths. However, it is not possible to walk to a dark tile from a light one, which means that the path must be concentrated to light grey tiles only. Note that the green and red tile are just highlighted display the start and end tile – in fact, they are also light grey!

When I run my game (well, game-to-be) and press the A button, I generate a path between the green and red tiles. Below are displayed three example of resulting path suggestions:

Three paths returned by the function

The path finding operation is fast and can handle large board games. However, I doubt that it would be suitable for more complex games, where the “world” is not made up of square tiles of equal size.

Advertisements