11

I have to implement the AI for Abalone game and I'm wondering what is the best way to represent the board logic using Java without wasting too much resources in all checks and updates routines involved.

Is better use various lists? A matrix of Cell objects? Any suggestion?

enter image description here

  • 1
    There is a great resource for hexagonal grids at redblobgames.com It has everything you need to know about hexagonal grids, their coordinate systems and how to do computations on them. – Roman Reiner Dec 28 '14 at 10:08
7

1) since the board has a fixed-size that you're just going to be feeding into an AI anyway, you could just represent it as a one-dimensional array with the right number of cells, where each cell represents a space on the board. Mapping that one-dimensional array to the screen for presentation might be a little weird, but it's a problem you only have to solve once.

The same would apply to validating moves; you could either create an adjacency matrix that tells which cells are adjacent to others, or come up with logic to determine adjacency. Either way, it would be a one-time cost.

2) Notice that every hex grid is also a two-axis grid, except that the axes are 60 or 120 degress from each other, instead of 90 degrees like grids where X and Y are perpendicular. (Old hex-tile boardgames used this trick to label the hexes 1, 2, 3 in one direction, and AA, BB, CC in the other, skewed, direction.)

I've looked at source code for computer implementations of board games that use (2), and they provided routines like "find a line between hexes" or "find the distance between hexes." That was a long time ago, so the details are lost to time, but I remember it wasn't too hard.

(It was more integer math rather than the Pythagorean stuff. ;))

  • 1
    For an AI for go make years ago, I had a 19x19 array of cells, and a 192x5 array of pointers to cells that the AI then used to figure out its move. – user40980 Jan 2 '15 at 0:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.