Updates from February, 2010 Toggle Comment Threads | Keyboard Shortcuts

  • danielsaidi 10:22 pm on February 22, 2010 Permalink | Reply
    Tags: , 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 10:08 pm on February 21, 2010 Permalink | Reply
    Tags: bitmap, , image, texture, ,   

    Generate a game board map from a bitmap in XNA 

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

    This entry will describe how a bitmap file can be used to quickly create a mission map, but first some relevant side information.

    Board movement

    In the game, players and monsters can move horizontally and vertically over the board:

    Board movement example

    Game pieces can move horizontally and vertically

    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
    • Tile B is occupied by another piece or furniture (another piece cannot stop at the same tile)
    • Tile B is occupied by a monster (players cannot pass through such a tile)

    Tile types

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

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

    When a tile is drawn later on, it can use any available texture, so the three tile types are more than sufficient.

    The None type is not really needed, since such a tile cannot entered. 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. There is an obvious conceptual difference between the two situations.

    Mission data

    In the game, players can chose to play one of a large set of missions. To make it easy to create a large number of missions, I have chosen to define them as such:

    • The mission board map is represented in a bitmap file
    • The mission data is specified in an XML file

    When a mission is loaded, the XML file is parsed into a mission object. The file points out the bitmap file, which is then parsed into a mission board map.

    The board map only specifies the board tiles and thus the look of the board, while the XML file specifies everything else, like the name of the mission, the mission targets, board items etc.

    The XML file content is the topic of a future post.

    Bitmap parsing overview

    Consider the following bitmap:

    An example of how a mission map (really small, though) can look.

    When the mission is initialized, it goes through the following steps:

    1. Parse the XML file (not covered in this post)
    2. Parse the bitmap into a mission board
    3. Initialize each tile using the corresponding color in the bitmap
    4. Divide the board tiles into rooms

    I have chosen to handle bitmap colors as such:

    • Black corresponds to the None tile type
    • The light grey at position (0,2) and (0,3) – #c3c3c3 – is specified in-code to be handled as a Nonwalkable tile
    • All other colors are regarded to be Walkable tiles

    The colors will later be used to determine which image that will be used for each tile:

    • Black tiles are not handled at all (they are None, remember?), thus they have no image
    • All other colors are converted into hex code (e.g. #ffffff instead of White) handled as such:
      • If one or several content textures have the hex code in their names (e.g. ffffff_1.png, ffffff_2.png etc.)  one is selected by random
      • If no corresponding image exists, the color is used to tint a random ffffff_x.png image

    Finally, when all tiles have been initialized with a type, an image and, perhaps, a tint, they are divided into rooms. Adjacent tiles that have the same color are considered to belong to the same room. When the board is then drawn, I make the game draw walls between all rooms.

    The process is really straightforward, as can be followed below. I have chosen not to include code for the Board and Tile classes that are mentioned below, since my classes are quite complex and I just want to describe the brief concept of how I parse the bitmap.

    Step 1: Initialize the mission board

    In my data model, the Board class has an Initialize function that takes an image as a parameter.

            public void Initialize(Texture2D image)
            {
                InitializeTiles(image);
                InitializeRooms();
            }
    

    As you can see, the function only consists of two sub-operations. First, all tiles are fully initialized, then the board is divided into rooms.

    Naturally, the bitmap has already been imported into the game content collection, which is why it is available here 🙂

    Step 2: Initialize each tile

    The InitializeTiles function really does nothing more than converting the texture into an array of colors, then applies each color the corresponding tile, as such:

            private void InitializeTiles(Texture2D image)
            {
                //Convert image to colors
                Color[] colors = new Color[image.Width * image.Height];
                image.GetData<Color>(colors);
    
                //Initialize the board tile matrix
                Tiles = new Tile[image.Width, image.Height];
    
                //Initialize each tile in the grid
                for (int y = 0; y < Tiles.GetLength(1); y++)
                    for (int x = 0; x < Tiles.GetLength(0); x++)
                        Tiles[x, y] = new Tile(colors[x + y * image.Width]);
            }
    

    In this example, I have reduced the numbers of parameters in the Tile constructor, to make the code easier to read.

    In my game, the Tile constructor uses the provided color to set the Image, Type and Tint of the tile. However, since this is really specific to my game, I have decided to leave the constructor code out of this post. Just drop a comment if you want to take a look at it.

    Step 3: Divide the board tiles into rooms

    Once the board has a grid of tiles, where each tile has a color, my game divides the tiles into rooms, using three functions.

    The parameterless InitializeRooms function makes sure that all tiles are handled, at least once:

            private void InitializeRooms()
            {
                for (int y = 0; y < Tiles.GetLength(1); y++)
                {
                    for (int x = 0; x < Tiles.GetLength(0); x++)
                    {
                        InitializeRooms(Tiles[x, y]);
                    }
                }
            }
    

    The InitializeRooms function that takes a tile as a parameter, makes sure that the tile fetches the room index from any already initialized adjacent tile that belongs to the same room (if any), sets a new room index if needed then finally spreads the room index to all non-initialized adjacent tiles that belong to the same room (once again…if any).

    For now, my function uses two sub-functions that cleans up the code a bit:

            private void InitializeRooms(Tile tile)
            {
                //Abort if no tile or if already checked
                if (tile == null || tile.RoomIndex.HasValue)
                    return;
    
                //Set negative room index if no tile or non walkable
                if (tile.TileType == TileType.None || tile.TileType == TileType.Unwalkable)
                    tile.RoomIndex = -1;
                
                //Fetch room number from similar siblings
                InitializeRooms_Fetch(tile, tile.TopSibling);
                InitializeRooms_Fetch(tile, tile.LeftSibling);
                InitializeRooms_Fetch(tile, tile.RightSibling);
                InitializeRooms_Fetch(tile, tile.BottomSibling);
    
                //Set room number if none has been set
                if (!tile.RoomIndex.HasValue)
                    tile.RoomIndex = roomIndex++;
    
                //Spread room number to similar siblings
                InitializeRooms_Spread(tile, tile.TopSibling);
                InitializeRooms_Spread(tile, tile.LeftSibling);
                InitializeRooms_Spread(tile, tile.RightSibling);
                InitializeRooms_Spread(tile, tile.BottomSibling);
            }
            private void InitializeRooms_Fetch(Tile tile, Tile sibling)
            {
                //Abort if either tile is null
                if (tile == null || sibling == null)
                    return;
    
                //Fetch index if the tiles have the same color
                if (sibling.RoomIndex.HasValue && tile.Color == sibling.Color)
                    tile.RoomIndex = sibling.RoomIndex;
            }
    
            private void InitializeRooms_Spread(Tile tile, Tile sibling)
            {
                //Abort if either tile is null
                if (tile == null || sibling == null)
                    return;
    
                //Spread by initializing the sibling
                if (tile.RoomIndex.HasValue && tile.Color == sibling.Color)
                    InitializeRooms(sibling);
            }
    

    Example

    The steps above are all you really need to parse a bitmap into an image.

    In the game that generated the final result below, I have 12 “ffffff” images and 4 “c3c3c3” images. I have no images for the red color and no images for the darker grey rooms, which is why they use the same images as is used in the hallway and apply a tint above them.

    In the image, I also display the room index. As you can see, all non and non-walkable tiles are given the room index -1, while all other tiles are divided into room 1-4.

    Mission map with a 6×6 grid of tiles with images, types and room indices

    If I want to create a totally different map for another mission, or simply edit the map above, this approach makes it reaaaaally easy to do so.

    I will return to the XML file in another blog post, as well as how to draw walls between the various rooms, how to use different colors/images for the same rooms etc. etc. etc. But all that will have to wait for another day 🙂

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

    • None
    • Nonwalkable
    • Walkable
     
  • danielsaidi 5:18 pm on February 21, 2010 Permalink | Reply
    Tags: , , , ,   

    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* 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: , 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

     
  • danielsaidi 4:05 pm on February 4, 2010 Permalink | Reply
    Tags: shared libraries   

    Using shared libraries in iOS 

    After a couple of evenings, my first (really simple) iPhone app is taking shape. However, since I have my heart in .NET development, it is painfully clear how Microsoft has spoiled us with fantastic Visual Studio features.

    Some things that are natural and so easy to accomplish in .NET does not come so natural with iOS. One example is to gather reusable functionality in shared libraries. With the iPhone, it is not as easy-going as when developing in .NET.

    I have found several blog entries that describe how to accomplish this. One good example is:

    http://www.clintharris.net/2009/iphone-app-shared-libraries/

    In time, this will hopefully be made a lot easier even for iOS.

     
  • danielsaidi 11:53 pm on February 1, 2010 Permalink | Reply
    Tags: nsuserdefaults, retrieve   

    Save data in iOS without using a database 

    I have now created my firs iOS app UI – a nice tab bar that toggles between four different views.

    I now want to store a string that I have entered in a text field, so that the application remembers it the next time I start the application. For this small piece of data, I do not want to go through the hassle of using a database.

    This great tutorial describes exactly how this is done:

    http://icodeblog.com/2008/10/03/iphone-programming-tutorial-savingretrieving-data-using-nsuserdefaults/

    NSUserDefaults is ideal for saving small amounts of data. Check it out.

     
  • danielsaidi 6:54 pm on February 1, 2010 Permalink | Reply
    Tags: , interface builder, striped background, view   

    Set striped background in iOS 3.1 

    I’ve finally begun looking into iOS development on my spare time. It’s good fun and I will write about my experiences here, as my work progresses.

    I first started to play around with this good tutorial. After completing it, I thought I’d just replace the plain white background with the striped background that is so common in iPhone apps.

    Beautiful, striped background

    Beautiful, striped background

    However, no matter where I looked in Interface Builder, I could not find a way to set this striped background. Sure, you could insert a table view, set its style to Grouped and let it fill the window…but I want the view itself to have the background.

    After searching around, I found that many developers set the striped background with either an image (which I will not cover since I do not want to use images when not absolutely necessary) or programatically.

    Option 1 – set the striped background programatically (“bad”)

    It is really simple to set the striped background programatically. Just do the following:

       //If you have a controller with the view, do this
       theController.view.backgroundColor = [UIColor groupTableViewBackgroundColor];
    
       //If you have the view directly, do this
       theView.backgroundColor = [UIColor groupTableViewBackgroundColor];
    

    However, is this as good as it gets? This way of setting the background means that the stripes will only show when you run the application and not if you open the view in Interface Builder…and that just don’t do it for me 🙂

    Thus, I mark this option as a “bad” way of setting the default background. Naturally, you may want to change the background programatically for various reasons, but maybe not the default background.

    Option 2 – set the striped background in the .xib file (“good”)

    Well, I did not find a way to set the striped background in Interface Builder (if you do know how, please leave a comment), but it is really easy to set it by modifying the .xib file in a text editor.

    To do so, just right click the .xib file you want to modify and select “Open As > Plain Text File”. Then, in the text editor, search for the following tag:

    
    

    For a plain, white view, the section should look something like this:

       
          1
          MC45ODQ3MTEyMDQ3IDAuOTg4NTMzNDAzNSAxAA
    

    Now, just add the following line as a sub tag to the object tag

       <string key="IBUIColorCocoaTouchKeyPath">groupTableViewBackgroundColor</string>

    so that the complete section looks something like this:

       
          1
          MC45ODQ3MTEyMDQ3IDAuOTg4NTMzNDAzNSAxAA
          groupTableViewBackgroundColor
    

    That’s it – if you open the view in Interface Builder, you will now have a beauuutiful striped background.

     
    • Badisi 4:08 pm on May 31, 2010 Permalink | Reply

      In Interface Builder :
      – Click on the background property of your view,
      – Click on the third tab of the colors window,
      – In the palette drop down list choose : iphone SDK,
      – And finally : groupTableViewBackgroundColor

      Hope it helps

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