Recently Shamus Young posted about a problem he had on his weblog: He wanted to make a game which used a hexagonal grid, but he didn’t know an elegant way to represent it in computer memory.
If you’ve never done any game programming before, regular square grids are easy to represent via a two dimensional array. 2D arrays are also used to determine where things are on your computer screen. You start off at coordinates 0,0 (or wherever) and you increase X to go right, decrease X to go left, increase Y to go down, and decrease Y to go up. (This is contrary to your high school math textbook because screen coordinates start in the upper left hand corner instead of lower left hand because of the way the screen is displayed.) So if an image starts at 60, 100 on the screen and you want to go 20 pixels right and 30 down, you move the image to 80, 130.
I recommend you read this article before going further. It explains things pretty well.
Back already? Okay, the problem of finding an elegant way of representing hexagonal grids has led to many, many, other articles and it seems there’s no particular consensus on how best to do it. But I figured out a really easy way to do it a few years ago:
1) Use a regular 2D array.
2) Pretend it’s staggered to represent the hex grid (you did read the above articles, right?).
3) Block off two of the eight directions based on how you staggered the array.
4) Block off the opposite two directions for odd/even rows/columns.
That’s it. No half-coordinates or messing about with triangles. You still have to tell the computer that odd/even rows/columns of the array line up with the odd/even rows/columns of the hex grid, but that’s the easy part.
Let’s say you have a hex grid that’s a vertically staggered vertical grid, similar to this, (which is actually a horizontally staggered vertical grid but bear with me (image stolen from here)):
Okay, so let’s say you start off in the very middle dark blue hex. -Y would be up one, and +Y would be down one. +X would be right one (into the dark blue hex to the right) and -X would be left one (into the dark blue hex on the left). Moving diagonally -X-Y or +X-Y would put you two hexes away, so we simply disallow that behind the scenes. Moving diagonally -X+Y puts you in the lower left (light blue) hex and +X +Y puts you in the lower right (light blue) hex.
THEN (and this is the slightly more complicated part), you disallow -X+Y and +X+Y for odd columns, and allow -X-Y and +X-Y.
Now having three directions that increment Y, and only one direction that de-increments Y, and vice-versa in adjacent columns, may seem counter-intuitive but it works. It simply works. Once you move to another hex, the directions line up just fine with that hex. This is partly because moving +X and -X on even columns actually moves slightly -Y diagonally on the hex grid (but you don’t tell your array that; you just let the hex grid display it offset) and slightly +Y diagonally on odd columns.
I don’t know for sure if this is a proper mathamological discoveramy, which would allow me to name it after myself and force mathematicians to use it henceforth forever after, but if it is, I proclaim this Mather’s Simple Square To Hex Conversion Method.