Representing the board in a boardgame

Question

I'm trying to write a nice representation of a boardgame's board and the movement of players around it. The board is a grid of tiles, players can move up, down, left or right. Several sets of contiguous tiles are grouped together into named regions. There are walls which block movement between some tiles.

That's basically it. I think I know where to start if all the players were human controlled, but I'm struggling with what happens with a computer controlled player. I want the player to be able to say to itself: "I'm on square x, I want to go to region R a lot, and I want to go to region S a little. I have 6 moves available, therefore I should do..."

I'm at a loss where to begin. Any ideas? This would be in a modern OO language.

EDIT: I'm not concerned (yet) with the graphical representation of the board, it's more about the route-finding part.

Answer 1

If you are looking for in-memory representation of the games (and it's state), a matrix is the simplest. However, depending on the complexity of the board, the strategy, you may have to maintain a list of states.

If you mean on-screen representation, you'd need some graphics library to begin with.

Answer 2

Have a Player class, which has Map field associating Squares to probability of moving there, that is, Map<Square, Double> if you'll represent them as a 0..1 double.

Have a Board class encapsulating a series of Squares. Each Square will have four booleans or similar to mark where it has a wall, its coordinates, and which Player, if any, is on it.

Answer 3

I'd say use a tree structure representing each possible move. You can use a Minimax-type algorithm to figure out what move the computer should take.

Answer 4

If the problem is with pathfinding, there are quite a few pathfinding algorithms out there.

The Wikipedia article on Pathfinding has a list of pathfinding algorithms. One of the common ones used in games is the A* search algorithm, which can do a good job. A* can account for costs of passing over different types of areas (such as impenetrable walls, tiles which take longer to travel on, etc.)

In many cases, a board can be represented by a 2-dimensional array, where each element represents a type of tile. However, the requirement for regions may make it a little more interesting to try to solve.

Answer 5

I can tell you what worked for me on a commercial board game style product.

Break your representation of the board and core game logic into it's own module, with well defined interfaces to the rest of the game. We had functions like bool IsValidMove(origin, dest), and bool PerformMove(origin, dest), along with interfaces back to the GUI such as AnimateMove(gamePieceID, origin, dest, animInfo).

The board and rules only knew the state of the board, and what was valid to do. It didn't know anything about rendering, AI, animations, sound, input, or anything else. Each frame, we would handle input from the user at the GUI level, send commands to the board/game state code, and then be done. The game state code would get commands, resolve if they were valid or not, update the game state and board, then send messages back to the GUI to visually represent the new state of teh board. These updates were queued by the visual representation system, so we could batch a bunch of animations to happen in sequence.

The good thing about this is that the board doesn't know or care about human vs. AI players. Your AI can be a separate submodule that acts on it's turn. It can send the same commands as the human player, and the game logic and visual results will be the same. You'll need to either have a local per-AI bit of info about the game board state, or expose some BoardSnapshot() functionality from the game logic that lets the AI "see" the board, but that's it. Alternately, you could register each AI as an Observer Pattern on the game state, so they get notified when the board updates as well, in case they need to do any complex realtime planning.

Keeping each section of your game separate and isolated will help with unit testing, and provide a more robust system. Well defined interfaces are your friend.