I’m making a game with a hex based grid. These are my notes on my implementation (so, far). This is dry and without much explanation, but if you want to do the same, maybe this will help you.
Moving between tiles
Now, a hex grid is a 2D so one might think that 2D coordinates would work best. It is my opinion they don’t. You don’t have the same X-Y movement in a Cartesian environment. It’s actually more like three directions of movement: up-down, NW-SE, and SW-NE. So, how about 3D coordinates?
It may seem a bit odd, but trust me, it’s really nice. This system has some handy properties:
- The sum of coordinates
(a,b,c) will always equal zero. Handy for validation.
- Distance from origin is
max(abs(a), abs(b), abs(c)). I think that might be cheaper computationally than Cartesian distance mostly because I don’t have that square root.
- Distance from p1 and p2 is
max(abs(a2-a1), abs(b2-b1), abs(c2-c1)).
(a',b',c') = a+Δa, b+Δb, c+Δc(x', y') = x+Δa, y-floor(x/2)+Δb+floor((x+Δa)/2)
Line 5 is the sort of reason why the 3D coords work so much better. That math is just ugly. My first implementation had something much like that and it just causes so many bugs and brain twisters figuring things out.
Storing the tiles in memory
While this system is nice, it fails memory storage. It still has to be shoved in an array. Thankfully, translating from hex coords (a,b,c) to 2D coords (x,y) is straight forward. First, some basic principles.
(x, y)
= (a, b+floor(a/2))
= (a, b + a >> 1)
(a,b,c)
= (x, y-floor(x/2), -(a+b))
= (x, y - x >> 1, -(a+b))
= (x, y - x >> 1, (x>>1)-x-y)
Pretty simple code that can be optimized; just adds, subtractions, and bit shifts. But still more work needs to be done to get it into an array. First, let’s define some spaces:
Any tile could be considered a playable space in the game, but for Joyride, I was thinking having the colored tiles be the actual play space and the clear tiles would just be unused space. I like it because we have a hexagon made from hexagons! The pictures also indicate how a even-radius hex space and an odd-radius hex space would fit into the space. With this, I can translate into an array.
w = h = HexSpaceRadius * 2 + 1
(xMax, yMax) = (w-1, h-1)
Array length = w * h
Array index
= (x * h) + y
= (a * h) + b+ (a>>1)
(x,y) = floor(i/h), i%h
That will get me a hex grid with the following coordinates:
The “origin” in my hex space isn’t the same as my array, but here is the translation:
2D origin
= (x0, y0)
= (floor(xMax/2), floor(xMax/2))
= (xMax>>1, xMax>>1)
3D origin
= (a0, b0, c0)
= (x0, y0 - x0>>1, (x0>>1)-x0-y0)
To demonstrate through example, here is the stuff we would pre-compute for the 2-radius hex space above:
w = h = 2*2+1 = 5
xMax, yMax = 4, 4
Array length = 25
2D Origin = (2,2)
3D Origin = (2, 2 - 2 >> 1, 2>>1 - 2 - 2) = (2, 1, -3)
There’s is a lot of conversion to and from the different coordinate systems. I’m planning hide most of it away though convenience functions, type converters, and caching. I haven’t give that much thought yet. I can also figure out my wasted space (those clear tiles). The number of tiles use for my Hex Space is calculated as thus:
totalTiles = 1
for ( i=1; i<=r; i++)
totalTiles += i*6
waste = Array length - totalTiles
Just to put some real numbers on it, for a 3-Radius Hex Space and a 20-Radius Hex Space:
- 3-Radius
- Array Length = 7*7 = 49 tiles
- Total Tiles = 37 tiles
- Waste = 12 tiles (24.49%)
- 20-Radius
- Array Length = 41*41 = 1,681 tiles
- Total Tiles = 1,261 tiles
- Waste = 420 tiles (24.99%)
Interesting that the waste is always about 25%, but not too surprising. That’s quite a bit of memory that could end up being wasted and that might be something I’ll need to be wary of going forward.
Converting Screen Space to Hex Space
I have implemented this, but I haven’t done a write up on it yet. When I get back around to doing this again, I will fill this out. This is one of the things that’s pretty easy to find in a google search. It was one of the first topics I found when researching this. But, if for some reason you need this before I get to it, leave a comment and I will write it out.
