Best data structure to represent a game board

Question

I'm trying to bring a board game to the computer world, and the board consists of 16 spaces, 6 for each side and 4 in the middle. The board is diamond-shaped and two ends represent both team bases. In the game, peices only move foward towards the enemy"s base (with special abilities of course). So here is my question: what do you think is the best data structure to represent the game board? The first thing that came to my mind was a tree, but I really don't like the idea because there would be two "roots". Any suggestions?

The board looks like this:

    &
   & &
 &  &  &
*  *  *  *
 $  $  $
  $  $
    $

so the & team can only move towards the $ team and vice-versa, * being neutral territory

Answer 1

Is it essentially a square? The diamond shape just a matter of interpretation? Like so ..

M A A A
B M A A
B B M A
B B B M

if so, maybe just use a 2D array, and use your display system to 'turn it' into a diamond.

edit

I think you can map you move set to the array - If your '$' pieces only move up-and-left or up-and-right, that is akin to my 'B' pieces moving only 'up' or 'right'. Similary, if the '&' pieces only move down-and-left or down-and-right, that's like the 'A' pieces only moving down or left.

The idea is that, internal to the program, think of your data 'up and down', but when you present your game state to your user, just draw it in the diamond configuration.

Answer 2

Your concern is not just how to represent the board but also how to represent the pieces because the board and the pieces need to communicate their mutual presence and effects.

Therefore, how you represent your board will be determined by how you represent your pieces and the rules of the game constraining the board and the pieces.

Your first concern is how to represent the pieces.

A game piece or a game automaton is a perfect model for object oriented programming.

Let me illustrate by dispensing away with the declarations such as public, static, etc.

abstract class BasicUnit
{
 // determine constraints of movement here.
 // update position and return new position
 abstract Position move(Direction d);

 abstract Position getPosition();
 Arsenal arsenal;
}

class Worker
extends BasicUnit
{
 Position move(Direct d)
 {
  //whateveer, etc
 }
}

class farmer
extends Worker
{
 Position move(Direct d)
 {
  //whateveer, etc
 }
}

class Warrior
extends BasicUnit
{
 Position move(Direct d)
 {
  //whateveer, etc
 }
}

class Sniper
extends Warrior
{
 Position move(Direct d)
 {
  //whateveer, etc
 }
}

Now you have to decide if the positions of pieces on the board is

• board centric: positions of pieces are registered on the board only
• piece centric: positions are registered on pieces only
• redundant: you have to redundantly update both piece and board when a piece is moved.

For most board games, piece-centric would not be a good idea because, you would have to search every piece to determine if a position is occupied.

If board-centric, you would need to search every position of the board to find the position of a piece.

For redundant, you have to ensure that positions registered by both board and pieces are not misaligned. If you plan to allow your game to be played over the internet, where sessions can be paused and hibernated - you might face challenges in synchronising.

So, the answer to your question is - a hashed vector to represent the board.

A hashed vector is a collection with two access doors - one accessed by position, second accessed by key. Your hashed vector would allow you to access

• the board by position to find out what unit is on a position
• the id of the piece to find out where on the board it is.

You cannot represent the board as a tree unless yours is a multidimensional board game. A tree is needed when you have a tree, a ladder, or a castle that sits on a board position, so that when a unit reaches that horizontal position of a board, it would need to advance to the vertical position of the ladder or castle. And in the castle the unit needs to be diverted to numerous rooms. Or on the tree is a witch capable of capturing the unit into a bottle with a confusing escape path. Therefore, using a tree structure to represent your board would present needless complication to programming your game.

It does not matter whether it is square of diamond or circle, etc. You just need to enumerate the position of the board. The method of enumeration must be convenient for your rules to capture.

That means, you should not enumerate one piece as (1,3) and then enumerate its neighbouring piece as (2,7) - it's just common sense. Because the neighbours of (1,3) are (0,2), (1,2), (2,2), (0,3), (2,3), (0,4), (1,4) and (2,4) but not (2,7).

Therefore you need a 2-dimensional hashed vector.

To cater to your need of finding out what unit is on the x,y position of your board:

BasicUnit getPosition(x,y)

As well as, finding out the (x,y) position of a unit.

Position getUnit(BasicUnit unit)

Then you might plan your game to be expandable so that a player on achieving victory could go on to play the next level which has a different board shape. Your 2-D hashed vector would still be used because you separate presentation layer of your software from its data structure.

You merely insert more positions into your vector.

You can view my Java implementation of a 1-D hashed vector at http://code.google.com/p/synthfuljava/wiki/HashVector

translate it to your choice of programming language and add one more vector dimension to it.

Answer 3

What about two trees with the middle four fields being the same? (I mean referencing the same objects)