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.