Error in Finding Nearest Hexagonal Tile

Question

Using Openfl for a game using hexagonal tiles

Working out the problem of walkability in a game, and I've run into an issue with my Hexagonal tiles. I think it is an odd rounding error of sorts. When heading down on the left side of tile, for a moment the nearest returns the coordinates of the tile on the right side. So the coordinates I get from the bellow nearest causes the "no walk" area for each unwalkable (water in this case) tile to be the area in red on this image.

public function nearest(pos:Point):Point
{
  var real_x:Float = pos.x + character.xOffset;
  var real_y:Float = pos.y + character.yOffset;
  var pos_y:Float = ((real_y + yOffset) / tileHeight)+1;
  var pos_x:Float = ((real_x  + xOffset - ( pos_y%2 * tileWidth/2) ) / tileWidth);
  return new Point(Math.round(pos_x),Std.int(pos_y));
}

For reference, this is how my map is laid out, later the map data will be read in from a file and not hard coded into the application.

public function createMap()
{
  map.push([0,0,0,0,0,0,0,3,0,0]);
  map.push([ 0,0,0,0,0,0,3,0,0,0]);
  map.push([0,0,0,0,0,0,3,0,0,0]);
  map.push([ 0,0,0,0,0,3,0,0,0,0]);
  map.push([0,0,0,0,0,3,0,0,0,0]);
  map.push([ 0,0,0,0,3,0,1,1,0,0]);
  map.push([0,0,0,0,3,0,1,2,1,0]);
  map.push([ 0,0,0,3,0,0,1,1,0,0]);
  map.push([0,0,0,3,0,0,0,0,0,0]);
  map.push([ 0,0,3,0,0,0,0,0,0,0]);

  walkMap.push([true,true,true,true,true,true,true,false,true,true]);
  walkMap.push([true,true,true,true,true,true,false,true,true,true]);
  walkMap.push([true,true,true,true,true,true,false,true,true,true]);
  walkMap.push([true,true,true,true,true,false,true,true,true,true]);
  walkMap.push([true,true,true,true,true,false,true,true,true,true]);
  walkMap.push([true,true,true,true,false,true,true,true,true,true]);
  walkMap.push([true,true,true,true,false,true,true,true,true,true]);
  walkMap.push([true,true,true,false,true,true,true,true,true,true]);
  walkMap.push([true,true,true,false,true,true,true,true,true,true]);
  walkMap.push([true,true,false,true,true,true,true,true,true,true]);

  tileData = [];
  for (row in 0...map.length) 
  {
    for (cell in 0...map[row].length) 
    {
      tileData = tileData.concat(
        [
          (tileWidth * cell + ((row%2) * (tileWidth/2))) - xOffset,
          (tileHeight * row) - yOffset,
          map[row][cell]
        ]
      );
    }
  }
}

What is causing the issue, where is my math off that I'm getting this odd effect?

Update:

The tile mapping from the above code should look like (realizing that I haven't taken the corners into account yet):

But instead look like:

They are not diagonal at all (like DMGregory suggests in his answer), the the top of them where the corners live is shifted by 1/2 a tile width, and I don't see why.

I could force the the tops to the right half a tile after (and that might be what I end up doing), but the code above should work, and I don't see where it is off by half a tile.

The bit DMGregory is doing at the bottom of his answer is what I was starting to work on to try and solve the corner problem (except the corners are at the top, not the bottom), when I realized what the shifting bug that's really going on really is.

Answer 1

Here are the areas your nearest function associates with each tile:

(assuming float % int is performed as a floating point modulo in your environment. If not, you can get broken/offset tiles instead, as visualized in the third image above)

As a unit travels down and to the left, they briefly touch the stretched/offset corner of the tile below and to the right, causing the issue that you describe.

If you floor the value of pos_y used in calculating pos_x (adjusting offsets as needed) you'll get something like this instead:

var pos_x:Float = ((real_x  + xOffset - (Std.int(pos_y)%2 * tileWidth/2) ) / tileWidth);

This is closer to correct (the tile adjacencies are right, although top & bottom borders are the wrong shapes), and may be close enough for your needs.

If you need to be more accurate yet, take a look at the two white lines in the image above. Every point in the red rectangle above those two lines is correctly-categorized - it's only the two triangles at the bottom that are mismatched. (I deliberately shifted the tiles vertically to line them up this way)

So we can apply a minor correction to these points:

(Here, I'm assuming tileX & tileY are the outputs of your old nearest function, ie. integer tile row & column indices, so a tile's right neighbour is at tileX+1. pos_x & pos_y are the values before they've been rounded/floored)

// Get the fractional offset of the point from the bottom center of the tile:
fracX = pos_x - tileX;  // Range -0.5...0.5
fracY = pos_y - tileY;  // Range 0...1

// Identify points inside the miscategorized triangles
if(abs(fracX) * 2 > fracY * 3)
{
   // Because of offset coordinates, 
   // which side needs its x corrected depends on whether we're in an even or odd row:
   if(fracX > 0) // Bottom-right corner
   {
      tileX += tileY % 2 - 1;
   }
   else  // Bottom-left corner
   {
      tileX += tileY % 2;
   }

   // Assign row to the one below
   tileY -= 1;
}

(I'm making some assumptions about which way your axes point & your data is laid out, so you may need to make minor tweaks)

Getting something that looks like this:

You can see the area in those two bottom triangles still gets caught by the rectangle for the tile above, but this correction ensures they get assigned to the right tile (here visualized with colour)

This is a little bit hacky for my taste, but it's probably the smallest change that will correct your nearest() function.

If you're up for more refactoring, I think the strategies described at the link provided by @madneon in the comments above will give you a more elegant and robust solution. This will require working in axial rather than offset coordinates as you are now, but this makes a lot of the tile math more consistent, with fewer special cases.

Answer 2

I'm not totally sure I understand your question. You are having trouble converting a position into a hexagon coordinate? If so I did some research on turning a vector position into a hexagon coordinate that might help you out.

But first of all I highly recommend this website for general hexagon coordinate information:

http://www.redblobgames.com/grids/hexagons/

and this is the website I used to do the coordinate conversation calculations.

http://playtechs.blogspot.co.uk/2007/04/hex-grids.html

The coordinate systems we use are different but you should be able to quickly modify it to suit your needs. I simply made a struct Hex that uses a coordinate system described in the redblobgames link and then used the second link with my coordinate system to design my Nearest function. You can follow along with my math and the second link to easily create yours.

System : (R : rows, Q: columns)

   +R
  /HH\+Q
-Q\HH/
   -R

Some calculations I made using that blog post an example:

R Matrix Solutions :

[edge/2, radius]  = [1, 0]

[-edge, 0] = [0, 1]

A = 0,    B = 1/radius,    C = -1/edge,    D = 1/diameter

Q Matrix Solutions :

[edge/2, -radius] = [1, 0]

[edge/2, radius] = [0, 1]

 A = 1/edge,    B = -1/diameter,    C = 1/edge,    D = 1/diameter

Formulae

l = Floor(z / radius);
m = Floor(z / diameter - x / edge);
R = Floor((l + m + 2) / 3);

n = Floor(x / edge - z / diameter);
o = Floor(x / edge + z / diameter);
Q = Floor((n + o + 2) / 3);

C# Code

/// <summary> Return the Hex whose center is closest to the Vector3 position </summary>
public static Hex NearestHex(Vector3 pos) {
    double t1 = pos.x / edge;
    double t2 = pos.z / diameter;

    double r = Math.Floor( (Math.Floor(pos.z / radius) + Math.Floor(t2 - t1) + 2 ) / 3);
    double q = Math.Floor( (Math.Floor(t1 - t2) + Math.Floor(t1 + t2) + 2 ) / 3); 

    return new Hex((int)q, (int)r, (int)(pos.y / height)); 
}

Answer 3

If I understand your question correctly, you are trying to find the center of the hex cell to which an arbitrary point belongs. Your question made me think of Voronoi diagrams... I have a gut feeling that they might be relevant here, though other solutions might have a better performance. (This solution might be wrong too, but I feel like it could be relevant.)

Voronoi Diagrams

A Voronoi diagram is a pattern of cells, with each cell containing one predefined point. Each cell holds all positions ("pixels" if you will) for which the cell's point is the nearest neighbour. In other words, a all positions get assigned to the nearest predefined point. In even other words, the borders of the cells represent positions that are equidistant to at least two points. The image below is an example of an arbitrary Voronoi diagram (taken from http://wikid.eu/):

Depending on how your points are positioned, you'll end up with a different Voronoi diagram. If you align your points as "horizontal lines, with all odd lines being offset by 50% of the horizontal distance between points" you'll end up with a hex pattern as in your example. You can adjust the vertical spacing between lines of points to "flatten" your hexes as in your post. The image below shows the layout of the points visually (image edited from http://www.designcoding.net/):

---

Solution 1: Closest Hex Center by Comparing Center Points

The clue of this, is that your hex grid is a Voronoi pattern. This means: to figure out which hex (Voronoi cell) a point belongs to, you only need to consider the distance of the point to the hex center (Voronoi cell center). A brute force solution would be to iterate through all your hex-centers (ie. horizontal lines of points, with odd rows shifted by 50% of the tile width) and just find the one with the closest distance to your point.

---

Solution 2: Closest Hex Center by Comparing Four Points

To speed up this brute force solution, you could note that there is no need to check all hex centers. Instead, you only need to check four:

1. From the row of points above, take the closest point that is smaller or equal in x-coordinate
2. From the row of points above, take the closest point that is strictly larger in x-coordinate
3. From the row of points below, take the closest point that is smaller or equal in x-coordinate
4. From the row of points below, take the closest point that is strictly larger in x-coordinate

These points are shown in the image below:

Now, as in solution 1, just calculate the distances to all these hex center points. The closest point indicates the center of the nearest hex cell.

---

Solution 3: Closest Hex Center by Comparing Two Points

To save a minuscule amount of processing time, you could note that only two points need to be checked. Instead of taking two points of the row above, and two points of the row below, only take one point of each row. Choose the point that is closest in x-coordinate. After all, when calculating the distance to these points, only their x-distance is different (dist = sqrt(pow(x_dist,2) + pow(y_dist,2)); ). Note that this trick doesn't work to compare points of different rows, as their x-coordinates are not aligned (due to the shift of odd rows).

The image below illustrates this. You'd do roughly the following steps:

1. Find the two nearest points in the row above (steps 1 and 2 in solution 2)
2. Discard the one with the largest x-distance to your point (brown lines in the image)
3. Find the two nearest points in the row below (steps 3 and 4 in solution 2)
4. Discard the one with the largest x-distance to your point (brown lines in the image)
5. Calculate the distance to these two points, and use the one that is closest (as in solution 1)

Basically, what is happening is that your check the "vertical boundaries" of your hex cells in steps 1 through 4. In step 5, you check one "diagonal boundary" to figure out what cell the points belongs to.

---

In short, you can find the cell to which a point belongs by calculating the distance to the center of all hex cells (as your hex pattern is similar to a Voronoi diagram). You can further optimize this by noting that you don't need to compare to all hex centers. In fact, you only need to compare to two.

Note: I did not check this solution myself, I'm just writing this based on some quick Google searching and gut feeling. Specifically, it is possible that you won't be able to make the Voronoi hex pattern match your hex pattern exactly (especially the slope of the diagonal borders). It could be a good approximation though.