1
\$\begingroup\$

I have a grid of hexagonal tiles. Every other row is slightly offset for visual reasons. Imagine a player touches any tile - I need to compare the coordinate of that tile, with any tile they touch next so that I can ensure they're right next to each other.

enter image description here

If the grid had no offset, I could simply ensure we were within 1 x and 1 y coordinate, but that fails in certain scenarios here.

I can get extremely close - the following code works in all cases, but still allows coordinates 3,2 and 4,3 to count as neighbors, among others with a similar mathematical relationship.

int diffX = abs(newCoord.x - lastCoord.x);
int diffY = abs(newCoord.y - lastCoord.y);

// Never allow jumping rows
if( diffY > 1 || diffX > 1 ) return false;

// Allow same columns
if( diffX == 0 || diffY == 0 ) return true;

return false;

A friend had an idea about combining the coordinates into single numbers and ensuring the neighbor was within a certain amount, but that fails for several combinations as well.

\$\endgroup\$
2
\$\begingroup\$

If I understood you correctly, you only want to know whether two tiles, specified by their 2D offset coordinates, are adjacent or not.

For any question related to hexagon grids, I'd recommend to refer to the Hexagonal Grids page by Amit Patel. It contains the mathematical backgrounds as well as excellent animated interactive examples, and probably Everything You Always Wanted to Know About Hex grids (But Were Afraid to Ask)

Your grid type is called the "odd-row horizontal layout" there. Handling these grids properly is a bit tricky, because the relationship between a tile in an odd row and its neighbors, and the relationship between a tile in an even row and its neighbors are so different. So for nearly all computations, you have to take into account whether the tiles are located in odd or in even rows.

I had to solve a similar problem recently, namely computing the distance between two such tiles - but your case is just the special case of detecting whether they have a distance of 1. As recommended on the linked site, I solved this by converting the offset coordinates to cube coordinates, and using the cube coordinates to compute the distance. The final method is this:

int distance(int x0, int y0, int x1, int y1)
{
    int cx0 = x0 - (y0 - (y0&1)) / 2;
    int cz0 = y0;
    int cy0 = -cx0-cz0;
    int cx1 = x1 - (y1 - (y1&1)) / 2;
    int cz1 = y1;
    int cy1 = -cx1-cz1;
    int dx = abs(cx0 - cx1); 
    int dy = abs(cy0 - cy1); 
    int dz = abs(cz0 - cz1); 
    return max(dx, max(dy, dz));
}

which you could use to implement your adjacency check by just returning

return distance(newCoord.x, newCoord.y, lastCoord.x, lastCoord.y) == 1;

The different treatment of odd and even rows is "hidden" in the &1 that is done during the conversion: For odd values, this will be 1, and for even values, it will be 0.

Note that there may be a more efficient or elegant implementation for this special case, but when you want to do more with hex grids, such a distance function may come in handy as well.

\$\endgroup\$
  • \$\begingroup\$ Geez. Now I can't see a hex grid without seeing a bunch of cubes. Nice resource. \$\endgroup\$ – James Skemp Mar 1 '15 at 1:16
  • \$\begingroup\$ I've implemented this logic and so far, it seems to completely solve the problem. \$\endgroup\$ – BotskoNet Mar 1 '15 at 1:58
0
\$\begingroup\$

You'll probably want distance eventually, so I'd use Marco13's solution.

However if you only need adjacency, there's a simpler way. Because every other row is offset, the logic is going to be different for odd and even rows. Look around 2,3 (odd y) and you'll see the x==2 column bends to the right like ">". If you look at 2,2 (even y), the x==2 column bends to the left like "<". So we'll need the code to treat odd and even rows separately. The x logic isn't symmetric for positive and negative so I won't take the absolute value:

int dx = newCoord.x - lastCoord.x;
int distY = abs(newCoord.y - lastCoord.y);

if (lastCoord.x & 1) {
    // Odd rows
    return (0 <= dx && dx <= 1 && distY <= 1) || (dx == -1 && distY == 0);
} else {
    // Even rows
    return (-1 <= dx && dx <= 0 && distY <= 1) || (dx == 1 && distY == 0);
}

The logic of the code here treats the adjacent hexes as either "・>>" or "<<・" (there are two bent columns and one extra hex), and the "<" or ">" part is the first (....) condition and the "・" part is the second (...) condition. (I'm not sure this explanation helps)

\$\endgroup\$
  • \$\begingroup\$ In what regard is the "x logic not symmetric"? Shouldn't a check like if (dy==0) return (abs(dx)==1); already handle the x-case properly? (In fact, this is "implicitly" done in your code...). Nevertheless, I agree that, if only the adjacency check is needed, the conversion to cube coords could be omitted and the check could be simplified. \$\endgroup\$ – Marco13 Mar 1 '15 at 11:12
0
\$\begingroup\$

In my HexGridUtilities project (Open Source, MIT Licence) I found it both useful and performant to define the coordinates of a hex as a vector of four integers - the rectangular coordinates and the obtuse (120 degrees between basis vectors) coordinates. Although I initially used Lazy calculations, it turned out to be more performant to always track both.

The code to generate the adjacency list for a hex is the following extract from the library's HexCoords struct:

static readonly IntVector2D vectorN  = new IntVector2D( 0,-1);
static readonly IntVector2D vectorNE = new IntVector2D( 1, 0);
static readonly IntVector2D vectorSE = new IntVector2D( 1, 1);
static readonly IntVector2D vectorS  = new IntVector2D( 0, 1);
static readonly IntVector2D vectorSW = new IntVector2D(-1, 0);
static readonly IntVector2D vectorNW = new IntVector2D(-1,-1);
static readonly IntVector2D[] HexsideVectorsCanon = new IntVector2D[] {
  vectorN,  vectorNE, vectorSE, vectorS,  vectorSW, vectorNW
};

static readonly IntVector2D userEvenN  = new IntVector2D( 0,-1);
static readonly IntVector2D userEvenNE = new IntVector2D( 1, 0);
static readonly IntVector2D userEvenSE = new IntVector2D( 1, 1);
static readonly IntVector2D userEvenS  = new IntVector2D( 0, 1);
static readonly IntVector2D userEvenSW = new IntVector2D(-1,+1);
static readonly IntVector2D userEvenNW = new IntVector2D(-1, 0);
static readonly IList<IntVector2D> HexsideVectorsUserEven = new List<IntVector2D>() {
  userEvenN,  userEvenNE, userEvenSE, userEvenS,  userEvenSW, userEvenNW
}.AsReadOnly();

static readonly IntVector2D userOddN  = new IntVector2D( 0,-1);
static readonly IntVector2D userOddNE = new IntVector2D( 1,-1);
static readonly IntVector2D userOddSE = new IntVector2D( 1, 0);
static readonly IntVector2D userOddS  = new IntVector2D( 0, 1);
static readonly IntVector2D userOddSW = new IntVector2D(-1, 0);
static readonly IntVector2D userOddNW = new IntVector2D(-1,-1);
static readonly IList<IntVector2D> HexsideVectorsUserOdd = new List<IntVector2D>() {
  userOddN,  userOddNE, userOddSE, userOddS,  userOddSW, userOddNW
}.AsReadOnly();

static readonly IList<IList<IntVector2D>> HexsideVectorsUser = new List<IList<IntVector2D>>() {
  HexsideVectorsUserEven,HexsideVectorsUserOdd
}.AsReadOnly();
#endregion

/// <summary>Returns an <c>HexCoords</c> for the hex in direction <c>hexside</c> from this one.</summary>
public HexCoords GetNeighbour(Hexside hexside) {
  var i = User.X % 2;
  return new HexCoords(Canon + HexsideVectorsCanon  [(int)hexside]
                      ,User  + HexsideVectorsUser[i][(int)hexside] );
}

Similarly, taking advantage of the properties of the obtuse coordinate system, the range between two hexes is readily obtained with this method, allowing adjacency to be tested as the case when Range = 1:

/// <summary>Modified <i>Manhattan</i> distance of supplied coordinate from this one.</summary>
public int       Range(HexCoords coords) { 
  var deltaX = coords.Canon.X - Canon.X;
  var deltaY = coords.Canon.Y - Canon.Y;
  return ( Math.Abs(deltaX) + Math.Abs(deltaY) + Math.Abs(deltaX-deltaY) ) / 2;
}

Using an integer matrix implementation IntMatrix2D the conversion between the rectangular and obtuse coordinate systems is down thus:

static readonly IntMatrix2D MatrixUserToCanon = new IntMatrix2D(2, 1,  0,2,  0,0,  2);
static readonly IntMatrix2D MatrixCanonToUser = new IntMatrix2D(2,-1,  0,2,  0,1,  2);

/// <summary>Create a new instance located at the specified vector offset as interpreted in the Canon(ical) frame.</summary>
public static HexCoords NewCanonCoords (IntVector2D vector){ return new HexCoords(vector, vector * MatrixCanonToUser); }
/// <summary>Create a new instance located at the specified vector offset as interpreted in the Rectangular (User) frame.</summary>
public static HexCoords NewUserCoords  (IntVector2D vector){ return new HexCoords(vector * MatrixUserToCanon, vector); }

private HexCoords(IntVector2D canon, IntVector2D user) :this() {
  _canon = canon;
  _user  = user;
}

Note that the Norm of the conversion matrices is 2 rather than 1, allowing the arithmetic to be quite elegant:

/// <summary>(Contravariant) Vector transformation by a matrix.</summary>
/// <param name="v">IntVector2D to be transformed.</param>
/// <param name="m">IntMatrix2D to be applied.</param>
/// <returns>New IntVector2D resulting from application of vector <c>v</c> to matrix <c>m</c>.</returns>
public static IntVector2D operator * (IntVector2D v, IntMatrix2D m) {
  return new IntVector2D (
    v.X * m.M11 + v.Y * m.M21 + m.M31,   v.X * m.M12 + v.Y * m.M22 + m.M32,  v.W * m.M33
  ).Normalize();
}

/// <summary>Returns a new instance with coordinates normalized using integer arithmetic.</summary>
public IntVector2D Normalize() {
  switch (W) {
    case 0:   throw new InvalidOperationException("IntVector2D is uninitialized.");
    case 1:   return this;
    case 2:   return new IntVector2D(X >> 1, Y >> 1);
    case 4:   return new IntVector2D(X >> 2, Y >> 2);
    case 8:   return new IntVector2D(X >> 3, Y >> 3);

    default:  return new IntVector2D(Math.Sign(X)*Math.Sign(W)*Math.Abs(X)/Math.Abs(W),
                                     Math.Sign(Y)*Math.Sign(W)*Math.Abs(Y)/Math.Abs(W));
  }
}

Yes, all the above is C# code, but translating to Objective-C should not be an undue hardship. My orientation convention for hexes is the transpose of yours, but this is easily addressed either with a transpose matrix, or swapping North with East and West with South.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.