# Storing a hex grid

I've been creating a small hex grid framework for Unity3D and have come to the following dilemma. This is my coordinate system (taken from here):

It all works pretty nicely except for the fact I have no idea how to store it. I originally intended to store this in a 2D array and use images to generate my maps.

One problem was that it had negative values (this was easily fixed by offsetting the coordinates a bit).

However, due to this coordinate system, such an image or bitmap would have to be diamond shaped - and since these structures are square shaped, this would cause a lot of headaches even if I hack something together. Is there anything I'm missing that could fix this? I recall seeing a forum post regarding this in the unity forums but I can no longer find the link.

Is writing a set of coordinate translators the best solution here?

If you guys think it would be helpful, I can post code and images of my problem.

• Can't you just save PNG images that are transparent around hexagons? – Markus von Broady Oct 21 '12 at 12:00
• My main problem with saving to pngs and arrays is the amount of "whitespace" they would have to contain in order to keep this coordinate system intact. – Pedro Caetano Oct 21 '12 at 12:09
• If "whitespace" means transparent pixels, then why is amount of it a problem? – Markus von Broady Oct 21 '12 at 12:44
• That's a very good point. Most image formats don't waste that much memory storing repeated patterns. But still, it slightly annoys me that to store this map I'm using this much memory (grey pixels are empty space, other colours are valid hex coordinates). – Pedro Caetano Oct 21 '12 at 12:55
• Oh, you're storing the grid data, not tile images! Why won't you just save your data structures (grid) to a binary file, or encode it using e.g. JSON and save to a text file? I don't know capabilities of Unity, though. Also, you might want to confirm this, but I believe an area of same color is optimized (loosely compressed) in PNG format. – Markus von Broady Oct 21 '12 at 13:18

The parallelogram coordinates you're using are easier to work with, but they do have the drawback of being weird for rectangular maps. One approach is to store it with the offset coordinates but actually use parallelogram coordinates in your game logic.

Observation: in each row of the map, the grid data is contiguous. All the wasted space is on the left and right.

Solution: within that row, store data starting at the leftmost column instead of the column marked 0. Calculate the first column of the rectangular map in your coordinate system, then subtract that from the column coordinate to determine where in the array it goes. This works for negative column coordinates too.

Perform the conversion in the getter and setter for the map, with something like this:

inline function get(q, r) {
first_column_in_this_row = -floor(q/2);
return array[r][q - first_column_in_this_row];
}


You'll have to modify this to work with your choice of coordinates and map (pay attention to off by one differences). In some layouts you'll want to offset the columns by the row instead of vice versa.

You can use the same trick to make maps of other shapes; it's not limited to rectangles.

If you're using C or C++ you can use pointer arithmetic to make this faster. Instead of storing an array of pointers to arrays, store an array of pointers that have been adjusted by first_column_in_row. (This may not be portable)

• This works as far as I can tell, however the math was really strange. After trying out several equations that made sense in my head, I settled on yIndex = y-((x%2==0)?(x/2-x):(-x/2)-1) after some trial and error. No idea how it works tough. – Pedro Caetano Oct 24 '12 at 13:19
• Make that yIndex = y-((x%2==0)?(-x/2):(-x/2)-1). x/2 is all integer-based btw so no need to floor. – Pedro Caetano Oct 24 '12 at 17:47

Personally, I would prefer simplicity over saving memory. Don't optimize until needed!

If you're still bent on saving a few bytes, here's how you can do it:

1. Slice the parallelogram in half to form two right triangles
2. Rearrange the two triangles to form a rectangle.
3. (Note I added the green buffer strip so the math works out nicely.)

Python code to map rectangle coordinates to parallelogram coordinates and back:

# Height of rectangle
H = 15

def r2p(x, y):
"rectangle to parallelogram"
if y < -x/2 + H:
y = y + H
return (x - 1, y)

def p2r(x,y):
"parallelogram to rectangle"
if y >= H:
y = y - H
return (x + 1, y)

• you could also just move the pixels vertically down - on the image that would be offsetY = Math.floor ( (x+1)/2 ) – Markus von Broady Oct 21 '12 at 20:22

It's not necessary to distort your map, as conversion between rectangular and "canonical" coordinates is quick and easy. Here is a link to an intro on how to do it:

Converting between Rectangular and Canonical hex coordinates

This technique combines lazy evalutation with caching of calculated conversions.