Hexagon board

Game Play & Game Design
#1

I’ve started planning out a hexagonal board/strategy game, and right now I’m working on the best way to lay out the board in memory.

My first impulse was to throw it in array and give each ‘half-step’ its own row (so one square down on the board would be two rows down in the array), but I’m not going to write code that wastes about half the memory it allocates with the empty cells this produces unless I have to.

My second thought was to force it to better fill the array by killing the white-space, however, this leads to problems distinguishing where to look for corners, which may possibly be solved by using mod 2 to figure out where the two side squares are.

Another possibility that I haven’t written out would be to just layout the ‘connections’ between pieces…

Anyways, since I have class in a bit, I thought I’d ask here. Has anyone done this, and if so, how did they do the board layout?

#2

I would do links. Each one has a pointer to N, NE, E, SE, S, SW, W, and NW. Then just store the “root” room (i.e. the center) and draw them out from there. You don’t want to have to use really kooky game logic to see if moves are legal and whatnot.

#3

I used a square grid of nodes (simple array). If you interconnect each node with it’s right, bottom and bottom-right neighbours - voila! A hexgrid! If you want to draw it on screen you’ll need to skew the rows…

#4

What you guys say makes sense. I think avoiding an array will also make certain part of the game (such as finding all the spaces in a straight line) much more intuitive.

Thanks ;D

#5

I have almost completely converted my games to a link based representation of the
board. There are numerous advantages - scanning in a particular direction or from
a particular center becomes a very natural process. Odd board geometry can also
be dealt with pretty naturally - for example, in my implementation of Fanorona,
the weak links are handled by simply removing the links, and in Tzaar, where the
center hex is not used, I simply remove it from the grid. Also, if properly parameterized,
switching a game from square to hex grid becomes simple. In my implementaion of
Volcano, normally played on a square grid, a version on a Hex grid is also available
which has almost no special cases to deal with the current board shape. You can
play these games at Boardspace.net

#6

So you guys mean…



public class Hex {
  private Hex north;
  private Hex northWest;
  private Hex west;

...

}
#7

Kinda… I used;


public class Node {
  // neighbour ordering: 0=E, 1=NE, 2=NW, 3=W, 4=SW, 5=SE
  private Node[] neighbours=new Node[6];
...
}

because the links need to be reciprocal for pathfinding.

#8

Yeah, but you definitely get the idea, I think. I’ve never done hex, but I’ve done N, E, S, W, up, down, and using links easily made the most sense.

#9

I’m now working on the AI for path finding, but I want to do the specifics on my own (so I’m not posting the code). All I want to say is that it makes use of the linked neighbors concept, and recursion is the best way to move through them.

So if there is the possibility of missing/occupied hexes and there is a set limit of moves, any1 have a good suggestion for finding the shortest path without mapping out all possible paths? I was thinking of finding a hex close to the midpoint mapping out an area around it that makes use of the moves available and then finding the path, but I’m not quite sure how I could do that and still ensure that, if a path exists with the given limit of moves, it will be found…

Ideas, examples, or even vague ramblings will all be appreciated :slight_smile:

EDIT: Nevermind, I figured it out, and I’m an idiot. I should have realized that as I got all the movable spaces, I could build paths (and only keep the shortest), because that’s essentially what its doing anyways.

#10

So here is your average 5x3 hexgrid


public int w = 5;
public int h = 3;
public Hex[] grid = new Hex[w*h];

Get the 2D coordinates of the cell at index N:


public void fillPositionOfIndex( int n, float[] result )
{
   int row = n / w;
   int col = n % w;
   result[0] = col;
   result[1] = row + ((col + row) % 2) * 0.5;
}

References to neighbours of cell N:


public static final int NORTH = 0;
public static final int NORTH_EAST = 1;
public static final int SOUTH_EAST = 2;
public static final int SOUTH = 2;
public static final int SOUTH_WEST = 3;
public static final int NORTH_WEST = 4;

public void fillNeighboursOfIndex(int n, Hex[] hexagon)
{
   hexagon[NORTH] = isValid(n-w) ? grid[n-w] : null;
   hexagon[SOUTH] = isValid(n+w) ? grid[n+w] : null;

   int x = ((n%w)%2)*w;
   int y = w-x;

   hexagon[NORTH_WEST] = isValid(n-x-1) ? grid[n-x-1] : null;
   hexagon[NORTH_EAST] = isValid(n-x+1) ? grid[n-x+1] : null;

   hexagon[SOUTH_WEST] = isValid(n+y-1) ? grid[n+y-1] : null;
   hexagon[SOUTH_EAST] = isValid(n+y+1) ? grid[n+y+1] : null;
}

private boolean isValid(int n)
{
   return n >= 0 && < w*h;
}

(Not tested, not even compiled!)

And the prize for least readable code goes toooo… :persecutioncomplex:

#11

A* ?

#12

If you establish the hex grid solely through linking from a central spot, can you still do pixel - hex coordinate conversion for mouse events and such? What about finding the viewable hexes for efficient drawing?

#13

For my purposes, keeping a master list of hexagons and iterating through them to find any ‘hits’ for the mouse event was perfectly acceptable, though that might be too slow in very large lists. Changing how that was stored (say a 2d array or what Riven posted rather than an ArrayList) could conceivably speed that up to O(1) (assuming theres a correlation between location and index) and allow for clipping unseen hexes for drawing, though populating the list would be more complicated. Basically you would be supporting both methods of map storage (b/c laying out the master list like this would support finding neighbors etc. from it) and using the links for faster interaction operations (like moving a piece) and the master list for global events (drawing, updating, and mouse events).

However, the whole reason I went with the links was to avoid populating that list (so that I could throw together arbitrary boards of various shapes and sizes by removing neighbors w/o worrying about null pieces).

If, as you said, you only stored the links, you could find mouse hits by recursively* stepping through the list from the center the same way you would ‘grow’ the array, but I feel that would end up having more overhead than even an ArrayList.

*A question occurred to me while working on this project and I never found the answer. Is it still recursion if you call the same Class.method() but using different objects, as in calling neighbor[i].grow(n-1) within Hex.grow(int n)?

#14

I’m planning on large (1000+) hex maps, so iterating through them is definitely not an option. Like you said, I’ll probably index the hexagons in an array so they map quickly to pixels, but then use the link mappings for movement. I was just wondering if there was a clever way of using the “link” method for all of my needs :slight_smile:

#15

Oh, here’s an idea that might make stepping through the links faster than iterating through a master list.

You start from the center and instead of spreading out in all directions you just step in the direction to get closer to the mouse event point (assuming you have the coordinates of the hexes). You’d have to be careful of cases where the mouse didn’t click anything (may or may not be possible in your game) and how you determined the next step direction (otherwise you might end up circling). Also, you would want to store the neighbors in a way that lets you know the direction the neighbors are in (as in an array with index correlating to specific directions, or whatever you could come up with).

That’s about the ‘cleverest’ thing I could think of, but I wouldn’t be surprised if someone came along and blew my mind out the back of my skull with awesomeness, lol.

#16

In my Hexodama (J4K) game, I used the skewed 2D array, really good to check for rows of objects.

See the attachment.