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.
