Game Boards

From Gardenwiki

Jump to: navigation, search

Many games use some form of game board to represent their state. Board games, by their very definition, rely on some form of game board, as do most computer strategy games, and many puzzles.

Game boards can generally be represented as a set of connected tiles. Each tile represents a location on the game board which a game piece may occupy, which has certain properties, and which connects to some number of adjacent tiles. Game boards are most commonly represented as a two dimensional array of tiles but any number of alternate configurations are possible.

In considering the data representation of a game board for use in a Game Gardens game it only necessary to consider the logical layout of the board, rather than its graphical appearance. Therefore this article will discuss game boards based on their logical properties alone. Once a data representation for the game board has been established then any number of graphical displays could be designed to allow a player to interact with it.

In all cases a game board should provide several pieces of information;

  1. A means of finding a path between two nodes.
  2. The distance between two nodes (usually equivalent to the length of the path between them).
  3. The set of tiles adjacent to a given tile (allowing movement).

Contents

Distributed Game Boards

Games on Game Gardens use the Presents architecture to synchronize the game state between clients and the server. A game using a game board should take this into account. The game board itself usually does not need to be a distributed object. Most games are only concerned with the dimensions of the game board and the location of pieces on the board. Board dimensions can be set by the game host in the lobby and automatically shared with the clients so the only distributed objects needed are the game pieces.

If a game board includes dynamic terrain it becomes necessary to share this information between clients. Again consider how much information needs to be sent to each client. While it is certainly possible to create a distributed object for each tile on a game board it is more likely that objects will only be needed for locations which contain terrain other than some default type. By limiting the number of distributed object used the game can avoid excess network traffic, server load, and client events resulting in improved performance.

One Dimensional Game Boards

Classic table top board games such as Snakes and Ladders, Monopoly, or Sorry! can be represented as a one dimensional array or linked list of tiles. In general each player is given some number of pieces and moves them around the board as a result of a die roll.

The game may support conditional tiles which allow branches in the player's path or events which "jump" the player to a new location of the board. However because all tiles can always be considered "in front of" or "behind" a given piece neither of these events requires the addition of another dimension to the board's tiles.

In the case of Snakes and Ladders the board may be considered a simple array. Pieces incrementally forward and occasionally jump forward("climbing a ladder") or backward("sliding down a snake/chute") some number of spaces. The first piece to reach the last index of the array is declared the winner.

In the case of Monopoly the board forms a circular array. Players advance along the board and return to the beginning tile when the reach the end tile("passing go") until a winner is declared. There are also cases where a player may jump to certain locations but these do not depend on their initial position on the board.

In Sorry! the game board again forms a circular array with the exception that pieces leave the main board upon reaching a certain position, although they may return to the main board by moving backwards later.

Distances between tiles on such boards can be calculated directly, although games with branching paths may have multiple valid distances.

Two Dimensional Game Boards

Battleship, Chess, Clue, Go, Reversi, Risk, and others all require a two dimensional representation of the board. Tiles can no longer be sorted into those "in front of" and "behind" a given position and movement rules are increasingly complex.

The game boards used by these games can be roughly sorted into two categories; those which are based on a coordinate system using some form of regular tiles and those which are not. Only three polygons; triangles, squares, and hexagons can form regular tilings and of those triangles are not generally well suited for use as game maps.

Abstract Tiles

Games such as Risk use a board constructed of abstract regions which do not naturally lend themselves to a coordinate based index. The nodes on such a map are best defined as a graph where path finding techniques can be used to determine the distance between them.

Square Tiles

Square tiles arranged on a Cartesian coordinate system appear in a great number of games. Movement across such a board can be computed directly.

If diagonal movement is not allowed then each tile has only 4 adjacent neighbors {above, below, to the left, and to the right}. Distance between any two nodes can be calculated as the Manhattan distance:

   Distance = Math.abs(start.x-destination.x) + Math.abs(start.y-destination.y));

If diagonal movement is allowed then each tile has 8 adjacent neighbors. The diagonal distance can be calculated as:

   Distance = Math.max(Math.abs(start.x-destination.x), Math.abs(start.y-destination.y));

This assumes that the costs for cardinal and ordinal moves are equal, if this is not the case then see Amit's A* Heuristics Page for a more detailed discussion.

Hexagonal Tiles

Hexagonal tiles allow for smoother movement across a game map by reducing diagonal movement between nodes. The distance between the center of a tile on a square map and the center of its 8 neighbors is not constant whereas the distance between the center of a hexagon and its 6 neighbors is. The additional faces of a hexagon also allow sprites to rotate more freely while still remaining aligned to a valid direction of movement on the board.

Hex Grid Alignment

A hex grid with vertical alignment and even offset.

Unfortunately hexagonal boards introduce some additional complexity. Most notably the orientation and alignment of the hexagonal tiles may vary.

Hexagons may be aligned with faces parallel to either the vertical or horizontal axis. Aligning the hexagons to "point up and down" with faces parallel to the vertical axis allows a greater number of tiles to fit in each row and therefore a larger number of total tiles to appear on a computer screen.

If the hexagonal tiles are arranged to form a rectangular grid then either the odd or even rows may be offset to the right of the left most point on the grid. (If the grid is aligned horizontally then the columns will be offset.)

Hex Grid Coordinates

A hex grid using Cartesian coordinates.

A hex grid, as shown above, can be be represented and indexed as a two dimensional array. Each row and column is given a unique x and y coordinate. In the orientation shown the rows would be arranged nicely while the values in the same column would be slightly staggered. The index of a particular hex tile is therefore equivalent to the index of the corresponding array location however the adjacency rules expected from a Cartesian coordinate space do not apply.

Hex Grid Distances

The number of hexes which must be traversed to travel between two given hexes can be determined using the following algorithm.

          dx = destination.x - start.x;
          dy = destination.y - start.y;
          if ((dx >= 0 && dy >= 0) || (dx < 0 && dy < 0)) { // sign(dx) == sign(dy)
              dist = Math.max(Math.abs(dx),Math.abs(dy));
          } else {
              dist = Math.abs(dx) + Math.abs(dy);
          }

Note that this assumes a hex based coordinate system matching the one shown above. Alternate coordinate systems will require a difference distance calculation.

Example Hex Grid Implementation

An example of a hex grid as used in the Blockade Runner game.

   public class HexMap {
   
       enum HexMapOffset {
           LEFT {
                   Point hexToRect (Point hexLocation) {
                       return new Point((int)Math.floor((hexLocation.x+hexLocation.y)/2.0), hexLocation.y-hexLocation.x);
                   }
                   Point rectToHex (Point rectLocation) {
                       return new Point((int)(rectLocation.x - Math.floor(rectLocation.y/2.0)), (int)(rectLocation.x+Math.ceil(rectLocation.y/2.0)));
                   }
               },
           RIGHT{
                   Point hexToRect (Point hexLocation) {
                       return new Point((int)Math.ceil((hexLocation.x+hexLocation.y)/2.0), hexLocation.y-hexLocation.x);
                   }
                   Point rectToHex (Point rectLocation) {
                       return new Point((int)(rectLocation.x - Math.ceil(rectLocation.y/2.0)), (int)(rectLocation.x+Math.floor(rectLocation.y/2.0)));
                   }
           };
   
           /**
           * Converts a hex-based location to its equivalent coordinate in a rectangular grid.
           * 
           * @param hexLocation
           * @return
           */
           abstract Point hexToRect (Point hexLocation);
           /**
           * Converts a rect-based location to its equivalent coordinate in a hex-based grid.
           * 
           * @param rectLocation
           * @return
           */
           abstract Point rectToHex (Point rectLocation);
       }
   
       public HexMap(int x, int y) {
           this(new Dimension(x, y));
       }
   
       public HexMap(Dimension mapSize) {
           this(mapSize, HexMapOffset.LEFT);
       }
   
       public HexMap(Dimension mapSize, HexMapOffset mapRowOffset) {
           super();
           this.mapSize = mapSize;
           this.mapRowOffset = mapRowOffset;
       }
   
       public Dimension getSize() {
           return mapSize;
       }
   
       public HexMapOffset getOffset() {
           return mapRowOffset;
       }
   
       /**
       * Computes a distance between two tiles on a hexagonal map.
       * See http://www-cs-students.stanford.edu/~amitp/Articles/HexLOS.html for a more 
       * complete discussion of hex maps and the derivations of the algorithms used here.
       * 
       * @param start          the initial location, given in rect-based coordinates
       * @param destination    the final location, given in rect-based coordinates
       * @return               the number of tiles which must be crossed to reach the 
       *                           destination from the starting tile
       */
       public int hexDistance ( Point start, Point destination ) {
           //convert rect-based coordinates to hex based coordinates
           start = mapRowOffset.rectToHex(start);
           destination = mapRowOffset.rectToHex(destination);
           int dx, dy, dist;
           dx = destination.x - start.x;
           dy = destination.y - start.y;
           if (dx >= 0 && dy >= 0 || dx < 0 && dy < 0) { // sign(dx) == sign(dy)
               dist = Math.max(Math.abs(dx),Math.abs(dy));
           } else {
               dist = Math.abs(dx) + Math.abs(dy);
           }
           return dist;
       }	
   
       /**
       * Returns a collection of the rectangular coordinates of the hex tiles adjacent to 
       * a given rect-based location. Only tiles which fit within the bounds defined by this
       * map's size will be included in the result.
       * 
       * @param rectLocation
       * @return
       */
       public ArrayList<Point> getNeighbors (Point rectLocation) {
           ArrayList<Point> neighbors = new ArrayList<Point>();
           Point currentTile;
           /* The coordinates of the neighboring tiles are dependent on the parity of
           * rectLocation and the map's offset direction. Rather than account for all
           * of the possible combinations here we search the 8 possible rectangular
           * neighbors of a given coordinate and use the hexDistance function to test for
           * adjacency.*/
           for (int xIndex = rectLocation.x -1; xIndex <= rectLocation.x +1; xIndex++) {
               for (int yIndex = rectLocation.y -1; yIndex <= rectLocation.y +1; yIndex++) {
                   //check to make sure currentTile is within the map bounds
                   if (xIndex >= 0 && xIndex < mapSize.width && yIndex >= 0 && yIndex < mapSize.height) {
                       currentTile = new Point(xIndex, yIndex);
                       //if adjacent then add to the neighbors collection
                       if (hexDistance(currentTile, rectLocation) == 1) {
                           neighbors.add(currentTile);
                       }
                   }
               }
           }
           return neighbors;
       }
   
       /* The rectangular dimensions of the hex map*/
       protected Dimension mapSize;
       
       /* Determines the offset of the tile at (0,0) relative to the tile at (1,0) */
       /* A LEFT offset produces the following pattern
       *  / \ / \
       * |   |   |
       *  \ / \ / \
       *   |   |   |
       *  / \ / \ /
       *  
       * A RIGHT offset produces the following pattern
       *    / \ / \
       *   |   |   |
       *  / \ / \ /
       * |   |   |
       *  \ / \ / \
       */
       //TODO: Add support for UP/DOWN offsets to allow rotations of the hex tiles, and rename the enum because UP/DOWN are not intuitive
       protected HexMapOffset mapRowOffset;
   }
   

Multi-dimensional Game Boards

2.5D game boards

A two dimensional game board is often used in games which allow game pieces to move at various "heights." Game pieces can be set to a "jumping" or "flying" state while remaining in the same tile allowing then to pass over other game pieces or obey different movement rules without the developer needing to add a true third dimension to the game board. Similarly a two dimensional board does not need to be projected on to a flat surface. Each board tile can be at a different elevation allowing the game to include hills or other terrain. The difference in elevation between tiles is also commonly used as a factor when determining the cost of moving between them.

2.5D games can generally reuse the logic given for 2D boards when calculating distances although there may be special cases depending on the game's rules for moving in the extra half dimension.

3D game boards

Tile based game boards can be extended to include three, or even more, dimensions for more complex gameplay. If the game board is to be continuous then tiles should be selected which can form a three dimensional tessellation, with cubes likely being the simplest to implement.

Irregular game boards

If the tiles of a game board are not required to form a continuous space then it may be desirable to store the board as a graph. Each game tile can be stored as a node with available connections to other tiles stored as edges. While using a graph allows an arbitrary number of connections between nodes it may also prevent the use of a coordinate system for locating tiles or a simple function for determining the distance between tiles.

External Links

http://en.wikipedia.org/wiki/Square_grid

http://en.wikipedia.org/wiki/Hex_grid

http://www-cs-students.stanford.edu/~amitp/game-programming/grids/

http://www-cs-students.stanford.edu/~amitp/Articles/HexLOS.html

Personal tools