ID:122097   Dec 21 2011, 12:23 am (Edited on Apr 2 2016, 11:28 pm) The title rolls right off the tongue, wouldn't you say? Lately I've been working on a non-BYOND project. One of the many I'll probably never finish. This particular one is the reason I started Orrery, the HTML5-based game engine I'm working on. In particular, part of the project is going to involve translating positions on a hex grid to positions on a Cartesian grid, which is the sort of grid that you normally see on stuff like graph paper, and is one of the most common coordinate systems. Before we start off, I need to describe how my particular hex grid system is built. Starting some research on this topic, I used this site to begin. Basically, I begin with a simple Cartesian grid, as shown below. The website I used suggested building a hex grid out of a rectangular grid. This is basically the same as a Cartesian grid, except the grid is stretched along the x-axis. My particular transformation basically multiplied the width by two, so I have (x', y') → (2x, y). This generates the grid shown below (overlaid on top of the Cartesian grid). The red is the rectangular grid. The blue is the underlying Cartesian grid, which has been stretched. Now, over-top of this I draw the hex grid, with a particular tiling relative to the rectangular grid, which I'll describe next. Now, in order to do all this, I have to make a choice about what coordinates on the rectangular grid the hex coordinates will map to. I have chosen the coordinate of the first full rectangular block on the bottom-left of the hexagon, and colored these blocks gray so they stand out. In addition to this, I've chosen a particular tiling for the hex grid to simplify our mathematics. From this point on, I'll use the notation R(x,y) to indicate a particular rectangular coordinate, C(x,y) to indicate a particular Cartesian coordinate, and H(x,y) to indicate a particular hex coordinate. There is a highlighted rectangular block at the coordinate R(0,0). This is no accident. I have chosen this particular location so we can have the mapping H(0,0) → R(0,0). This means we won't have to translate the result of our transformation from the hex grid to the rectangular grid. Now that we have that out of the way, we have to define our coordinate system for the hex grid. Often, when people attempt this, they try and emulate the Cartesian coordinate system. Basically, assume our drawing is on a piece of paper. The common method is define the x-axis and y-axis emulating, exactly, the underlying Cartesian system. The problem with this is that it results in alternating rows of hexagons having different x values, because in a hex grid you can't move straight 'up' into another hexagon; you have to move two rows to do this. As it turns out, this particular pattern is not very optimal. For one, it's just plain wonky. Two, it doesn't allow for nice translations to a Cartesian grid. The basic idea isn't flawed, though. Once again, with our paper example, there's no real problem with having an x-axis that increases from left-to-right as you move along the bottom of the paper, and there's no problem in having a y-axis that increases as you move bottom-to-top along the side of the paper. What you can do to rectify this, though, is have the x-axis move diagonally, through the hexagons. This results in the coordinate system below. The orange lines are the x-coordinates. The green lines are the y-coordinates. The thick lines indicate x-coordinates and y-coordinates of 0. The origin is where these intersect Using this particular orientation, we now see that, indeed, H(0,0) → R(0,0). Now, we need to define our linear transformation that converts our hex coordinates into rectangular coordinates. The concept is much, much more nuanced than this, but basically our particular linear transformation boils down to this. There exist constants a,b,c,d such that R(x', y') → H(ax + by, cx + dy). To do this, we need to find a few sample points on our grid to test. Really, we only need two, though it helps to not choose the sample points H(0,0) → R(0,0). I'm going to choose the sample points H(0,1) → R(1,3) and H(-1,-1) → R(-3,-3). You can verify these yourself. Now, our linear transformation is as follows: x' → ax + by y' → cx + dy We have two sets of sample data that for each of these. We know x, x', y, and y', so we plug these in. For H(0,1) → R(1,3) we get 1 → 0a + 1b 3 → 0c + 1d and for H(-1,-1) → R(-3,-3) we get -3 → -1a + -1b -3 → -1c + -1d This allows us to create two systems of equations: 1 = 0a + 1b -3 = -1a + -1b 3 = 0c + 1d -3 = -1c + -1d Solving this system of equations gets us the following constants: a = 2 b = 1 c = 0 d = 3 Thus, we get the transformation R(x', y') = H(2x + y, 3y). If we plug in our sample points, we see that we get what we should. H(0,1) → R(1,3), H(-1,-1) → R(-3,-3), H(0,0) → R(0,0). The thing is, we would like the Cartesian coordinates, not the rectangular coordinates. We're working on a Cartesian grid, after all. This happens to be very simple. Above I noted (using slightly-different notation), C(x',y') → R(2x, y). Because we Know R(x',y') → H(2x + y, 3y), we can just plug in the Rectangle-to-Cartesian transformation into the Hex-to-Rectangle transformation: C(x',y') → H(2(2x + y), 2(3y)) = H(4x + 2y, 6y). Thus, to transform between hex coordinates and Cartesian coordinates, we have C(x',y') → H(4x + 2y, 6y). Simple enough. Lastly, we will likely want to convert from Cartesian coordinates to Hex coordinates. This could be complicated depending on the transformation. Luckily for us, it's simple. We can use the transformation we already have. Basically, we have the following equations above (after swapping the variables around): x = 4x' + 2y' y = 6y' And now we solve for, in the first equation, x', and in the second equation y'. For the second equation, this is simple: y' = y/6 The second equation gives us x' = (x - 2y')/4 = (x - 2y/6)/4) = x/4 - y/12 Thus, our transformation is H(x',y') → C(x/4 - y/12, y/6). This transformation will, though, will generate non-integer values, which are not actually meaningful for our hexadecimal coordinate system. Thus, we simply need to floor the resultant values: C( floor(x/4 - y/12), floor(y/6) ). This gives our transformation. Once again, you can test with a few sample points, like those above, to verify this is true. Now, because BYOND uses a positive Cartesian grid (meaning that BYOND only uses the first quadrant of a Cartesian grid), this isn't necessarily the best layout to use. In fact, it may be better to shift the hex grid up by one, so that the very hexagon at H(0,0) is completely on the map. This means that when we convert from Hex coordinates to Cartesian coordinates, we need to subtract one from the transformation, and add one when we convert from Cartesian coordinates to Hex coordinates. These leaves our transformations as follows: C(x',y') → H(4x + 2y - 1, 3y) H(x',y') → C(x',y') → ( floor(x/4 - y/12 + 1), floor(y/6) ) As it happens, this means our translation is no longer a linear transformation (in fact, it becomes an affine transformation), but this doesn't matter for most applications, and it greatly simplifies things. And thus, we have the mathematics of one potential regular hexagon grid and coordinate system in BYOND. This isn't necessarily the best for every game. For example, someone may want to have the flat portion of the hexagons be at the bottom, rather than the sides, which requires different mathematics. Or they may want differently-sized hexagons. Still, using this you should be able to get a start on what the mathematics of the transformations for your system need to be!
 <-> Dec 21 2011, 1:48 am Another wonderfully interesting article from Fizzy. I wish you wrote in your blog more often, honestly. P.S> When did spam bots hit BYOND?
 <-> Dec 21 2011, 7:50 am What happened with that online game dev company that was interested in you?
 <-> Dec 21 2011, 9:23 am Airjoe wrote: What happened with that online game dev company that was interested in you? They sent me an email. I sent an email back. Then nothing. I get the feeling they were never terribly interested in anything, so I just quit caring about it.
 <-> Dec 21 2011, 2:05 pm This was an interesting post. I feel like you had a mathematical error in there, though. Good job!