Tagged: a-star Toggle Comment Threads | Keyboard Shortcuts

  • danielsaidi 10:22 pm on February 22, 2010 Permalink | Reply
    Tags: a-star, ai, , , random path, shortest path, ,   

    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.

     
    • brian 3:38 pm on February 23, 2010 Permalink | Reply

      as you said, brute force will work with a small board, but not one larger. this reminds me of problem 67 of projecteuler…

      http://projecteuler.net/index.php?section=problems&id=67

      (20 billion years!!)

      • danielsaidi 4:10 pm on February 23, 2010 Permalink | Reply

        Well…computers ARE getting faster, so maybe the 20 billion years can be reduced by half in a couple of years? 😉

        No, but you are absolutely correct. This algorithm will get the work done for my boards, but it can be optimized a LOT…much like the LOS/FOV problem I am working on right now. As the boards grow in size, better algorithms will be needed.

        Thanks for the link! Very interesting.

    • Jens 1:30 pm on March 12, 2010 Permalink | Reply

      Vilken jättepost, snyggt!

    • Flash Game License 11:20 am on December 27, 2011 Permalink | Reply

      This is a really useful explanation and a good practical example of such algorithm. Thanks!

    • Charles 3:28 am on April 17, 2012 Permalink | Reply

      Do you mind if I use your pathfinding and bitmap parsing code in a game I’m making? I’ll be sure to credit you.

  • danielsaidi 5:18 pm on February 21, 2010 Permalink | Reply
    Tags: a-star, , , ,   

    A board game with tiles in XNA 

    During my experimenting with the XNA framework, I am currently developing a board game where the game board is made up of a grid of square shaped tiles, over which player and monster pieces can move horizontally and vertically.

    Board movement example

    Game pieces can move horizontally and vertically

    So far, the board/tile model have presented these three main problem areas:

    • What is the best way to parse a bitmap into a game board, to make it easy to create dynamic mission maps?
    • Given a set of walkable and non-walkable tiles, how do I find the shortest path from tile A to tile B?
    • How can I determine if tile A is visible from tile B?

    I have successfully solved the first two problems, of which the first is presented in the next post.

     
  • danielsaidi 1:46 am on February 21, 2010 Permalink | Reply
    Tags: a-star, ,   

    A* algorithm implemented for XNA 

    I have implemented a dynamic A* algorithm, which will find the shortest way through a grid of tiles. If multiple possible paths exist, the algorithm will choose a random path, which adds to the random behavior of any computer character that is to be given an illusion of intelligence.

    I will publish the algorithm source code here as soon as I have rewritten it a bit. I will then begin working on an algorithm that will determine the line of sight from a tile in the grid…that is, which tiles can I see if I stand on a certain tile?

    If anyone have implemented such an algorithm, feel free to help me out.

     
  • danielsaidi 11:57 pm on February 16, 2010 Permalink | Reply
    Tags: a-star, pathfinding, ,   

    A* implementation for XNA 

    For a while now, I have played around with the XNA framework to get a grasp at how to develop games for the XBOX 360. It is great fun, but quite different from the development I usually do.

    I now have a working game stub with an object model that grows and grows and that feels really good. I can generate missions from an image/text file tuple, where the image describes the game board of the mission and the text file describes the mission, items on the board, goals etc.

    This setup makes it really easy to quickly develop a large amount of missions that can be divided into multiple campaigns. By making the base model solid, new missions will be content management than programming.

    When my game imports the various game board maps, it generates a grid of walkable and unwalkable tiles, of which the game board consists. The next step is now to be able to find the shortest way from one tile to another.

    I found this great tutorial and will use it to implement the A* algorithm, which hopefully will take care of this for me:

    http://dotnetperls.com/pathfinding

     
c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel