## Saturday, March 31, 2012

### A programming question relating to board games

Specifically hexagonal games. I'm trying to write out concise descriptions (almost pseudocode) of some games played on hexagonally tiled board. Something like this checkers variant:

If these were rectangular tiles, the coordinates would be obvious, but with hexagons, I'm not sure which way to go.

Any suggestions?

1. I think "column-# from bottom of black" would make the most sense. For column, I would use 0 or C for the center, then L1 for the first column to the left of center, L6 for the far left column, R6 for the far right, and so on. The bottom hex is C-0, the top is C-11, top left is L6-6, and so on.

This has the advantage of being fairly easy to recognize adjacent hexes -- S(X)-(Y), for S = L or R and X between 2 and 5 is next to S(X+1)-(Y), S(X+1)-(Y-1), S(X-1)-(Y), and S(X-1)-(Y+1).

2. I think that what representation is best depends on the sort of computations/operations which need to be made on it.

The system I have seen most commonly used is a 2d coordinate system where one dimension (rows in your example) has the property that any column only has even numbered rows or odd numbered rows, because of the offset of the hexes. So, Nick's C-0 = (0,1),C-1 = (0,3), C-11 = (0,21), L1-1 = (-1,2), L1-2 = (-1,4) and L6-6 = (-6,16). Unlike Nick's system, this allows for easier comparison of distant objects. For example, Is L6-5 higher or lower than C-9? becomes Is (-6, 14) higher or lower than (0,17)? This also retains similar properties for identifying neighboring cells with only minor modification. You can also use halves instead of even and odd - this is slightly harder to do in your head but can make the distance metric more intuitive. On the other hand, compared to Nick's system, identification of boundary hexes is more difficult (in some cases - his has the same problem along the top edge).

When I was in cognitive psych grad school, I did some research on spatial representation in which I used hexagonal, cubic and square grids. The task involved mentally tracking a pretend object which made a series of 1 space movements in directions presented one at a time. A strategy I found worked well for me then was to think of it as a 3 dimensional coordinate system with a many to 1 mapping between triplets and hexes. For example, if (0,0,0) is the center, with first axis extends positive towards 10:00 and negative towards 4:00, second axis is positive towards 12:00 and negative towards 6:00, third axis is positive towards 2:00 and negative towards 8:00, then (1,-1,0) is the same as (0,0,-1). But this meant that retaining and updating a net movement vector was very easy, and calculating the location given a triplet was easy. However, it would not work well to track 2 objects and monitor whether they collide, because determining whether two triplets represent the same cell is non-trivial (though not computationally demanding by machine standards). Incidentally, the use of hex grids was inspired by their use in board games.

Whew. It's hard to talk about something this spatial without diagrams. Hope this makes sense.

3. I wanted to share this with someone who could help me understand if it's a bad idea or a good idea.

I'm trying to work on a hexagon based tablegame, my problem came in many different flavours, understanding a good way to save the information in the device, so I went with what I understand best, arrays.

Using an array 11x11 I went with this kind of positioning inside my code (small sample):

- O O O -
O I I O -
O I I I O
O I I O -
- O O O -

- = null tile
O = outer game tile
I = inner game tile

With bigger games more null tiles, but it enables the developer to create not fixed games with different escenarios (or so I think, I'm still developing it myself).

You think is a bad idea?

And for the movement, I create a fixed table for movement depending if its a offset line or not so you can travel through the table with not so much difficulty. Is there a better way?

1. http://www.codeproject.com/KB/graphics/hexagonal_part1/hex_array.jpg

this is more or less the image sample for the definition of an hexagon in an array.