Hexagonal grid for games

Sample Image - app_screenshot.jpg

Introduction

The goal of my project is to create a modular, reusable hexagon based map that could be used in simple games and ALife applications. I wanted to leverage as much functionality as possible from .NET, which meant using GDI+ and Forms. Drawing shapes with GDI+ and capturing mouse events with Forms is fairly trivial, which would allow me to spend my programming time solving on more important issues (like hexagon geometry!). This is the first “version” of the hex map, and by no means complete.

Hexagon

Hexagon based games, whether traditional board games or computer-based, provide more strategic and tactical game-play when compared to simple square based games (like the Checkers game board). The hexagon has six sides, which allows movement in six directions, instead of four. The distance from the center of a hexagon to the center of each neighboring hexagon is equal, which eliminates the distortion of calculating diagonal distance in a traditional square based map. Hexagons are more pleasing to look at, which counts for something, right?

The core of my code is based on the geometry of the hexagon. When I use the word hexagon, I really mean regular hexagon, which is a six-sided polygon where all six sides have the same length. The beauty of the hexagon based map is that you really only need to know one thing: the length of a side of a hexagon. After that, you can calculate everything else you need to know.

hexagon geometry

If you know the length of side s, then you can calculate r and h. The values for a and b are pretty much irrelevant because you can calculate them from sr, and h, and you don’t really need a and b for any calculations anyway. So, how do you find r and h?

h = sin( 30°) * s
r = cos( 30°) * s
b = s + 2 * h
a = 2 * r

My namespace is Hexagonal

For lack of a better term, I called my namespace Hexagonal, and that’s where all my core classes live. The classMath has a bunch of static methods to handle geometric calculations. Some people may argue that these are trigonometric calculations, but for my purposes, trigonometry is a subset of geometry.

public static float CalculateH(float side)
{
    return ConvertToFloat(System.Math.Sin(DegreesToRadians(30)) * side);
}

public static float CalculateR(float side)
{
    return ConvertToFloat(System.Math.Cos(DegreesToRadians(30)) * side);
} 
public static double DegreesToRadians(double degrees)
{
    return degrees * System.Math.PI / 180;
}

The Sin and Cos methods in System.Math take arguments in radians, not degrees. So, we need a helper method to convert degrees to radians.

The Hex object represents a hexagon. When creating a Hex object, you need to know a few things – the length of a side, the x,y coordinates of the upper vertex, and the orientation of the hex. I introduced the concept of orientation so that hexes could be created with the flat side down or a pointy side down. The orientation will affect how the vertices are calculated.

Flat and Pointy Hexagons

The vertices are numbered somewhat arbitrarily on my part, but we need to refer to vertices in some manner. The important method in Hex is CalculateVertices(), which is private and called by the constructor. I also created an enumeration for hexagonal orientation.

public class Hex
{
    private System.Drawing.PointF[] points;
    private float side;
    private float h;
    private float r;
    private Hexagonal.HexOrientation orientation;
    private float x;
    private float y; 
    ...

    private void CalculateVertices()
    {
        h = Hexagonal.Math.CalculateH(side);
        r = Hexagonal.Math.CalculateR(side); 
        switch (orientation)
        {       
            case Hexagonal.HexOrientation.Flat:
                // x,y coordinates are top left point

                points = new System.Drawing.PointF[6];
                points[0] = new PointF(x, y);
                points[1] = new PointF(x + side, y);
                points[2] = new PointF(x + side + h, y + r);
                points[3] = new PointF(x + side, y + r + r);
                points[4] = new PointF(x, y + r + r);
                points[5] = new PointF(x - h, y + r );
                break;
            case Hexagonal.HexOrientation.Pointy:
                //x,y coordinates are top center point

                points = new System.Drawing.PointF[6];
                points[0] = new PointF(x, y);
                points[1] = new PointF(x + r, y + h);
                points[2] = new PointF(x + r, y + side + h);
                points[3] = new PointF(x, y + side + h + h);
                points[4] = new PointF(x - r, y + side + h);
                points[5] = new PointF(x - r, y + h);
                break;
            default:
                throw new Exception("No HexOrientation defined for Hex object.");
        }
    }
}

public enum HexOrientation
{
    Flat = 0,
    Pointy = 1,
}

The Hex class was designed to be simple. All it does is remember its position in two dimensional space. The Boardclass is a collection of Hex objects that represent a game board. For this first version, the only type of board that can be created is rectangular. Arranging hexagons in a rectangular shape can be done fairly simply using a two dimensional array. For example, a board with Flat orientation would map to a two dimensional array like this:

two dimensional hexagon array

The most important method in the Board class is Initialize(), which is private and called from the constructor. Initialize() creates a two dimensional array of Hex objects with all the calculations for the hex vertices.

public class Board
{
    private Hexagonal.Hex[,] hexes;
    private int width;
    private int height;
    private int xOffset;
    private int yOffset;
    private int side;
    private float pixelWidth;
    private float pixelHeight;
    private Hexagonal.HexOrientation orientation;

    ... 

    private void Initialize(int width, int height, int side, 
            Hexagonal.HexOrientation orientation, 
            int xOffset, int yOffset)
    {
        this.width = width;
        this.height = height;
        this.xOffset = xOffset;
        this.yOffset = yOffset;
        this.side = side;
        this.orientation = orientation;
        hexes = new Hex[height, width];
        //opposite of what we'd expect

        this.boardState = new BoardState(); 
        // short side
        float h = Hexagonal.Math.CalculateH(side);
        // long side 
        float r = Hexagonal.Math.CalculateR(side);

        //
        // Calculate pixel info..remove?
        // because of staggering, need to add an extra r/h

        float hexWidth = 0;
        float hexHeight = 0;
        switch (orientation)
        {
            case HexOrientation.Flat:
                hexWidth = side + h;
                hexHeight = r + r;
                this.pixelWidth = (width * hexWidth) + h;
                this.pixelHeight = (height * hexHeight) + r;
                break;
            case HexOrientation.Pointy:
                hexWidth = r + r;
                hexHeight = side + h;
                this.pixelWidth = (width * hexWidth) + r;
                this.pixelHeight = (height * hexHeight) + h;
                break;
                default:
                break;
        } 

        bool inTopRow = false;
        bool inBottomRow = false;
        bool inLeftColumn = false;
        bool inRightColumn = false;
        bool isTopLeft = false;
        bool isTopRight = false;
        bool isBotomLeft = false;
        bool isBottomRight = false; 

        // i = y coordinate (rows), j = x coordinate
        //      (columns) of the hex tiles 2D plane

        for (int i = 0; i < height; i++)
        {
            for (int j = 0; j < width; j++)
            {
                // Set position booleans

            #region Position Booleans
                if (i == 0)
                {
                    inTopRow = true;
                }
                else
                {
                    inTopRow = false;
                } 
                if (i == height - 1)
                {
                    inBottomRow = true;
                }
                else
                {
                    inBottomRow = false;
                } 
                if (j == 0)
                {
                    inLeftColumn = true;
                }
                else
                {
                    inLeftColumn = false;
                } 
                if (j == width - 1)
                {
                    inRightColumn = true;
                }
                else
                {
                    inRightColumn = false;
                } 
                if (inTopRow && inLeftColumn)
                {
                    isTopLeft = true;
                }
                else
                {
                    isTopLeft = false;
                } 
                    if (inTopRow && inRightColumn)
                {
                isTopRight = true;
                }
                else
                {
                    isTopRight = false;
                } 
                if (inBottomRow && inLeftColumn)
                {
                    isBotomLeft = true;
                }
                else
                {
                    isBotomLeft = false;
                } 
                if (inBottomRow && inRightColumn)
                {
                    isBottomRight = true;
                }
                else
                {
                    isBottomRight = false;
                }
                #endregion 

                //
                // Calculate Hex positions
                //

                if (isTopLeft)
                {
                    //First hex
                    switch (orientation)
                    { 
                        case HexOrientation.Flat:
                            hexes[0, 0] = new Hex(0 + h + xOffset, 
                                          0 + yOffset, side, orientation);
                            break;
                        case HexOrientation.Pointy:
                            hexes[0, 0] = new Hex(0 + r + xOffset, 
                                          0 + yOffset, side, orientation);
                            break;
                        default:
                            break;
                    }
                }
                else
                {
                    switch (orientation)
                    {
                        case HexOrientation.Flat:
                            if (inLeftColumn)
                            {
                                // Calculate from hex above
                                hexes[i, j] = new Hex(hexes[i - 1, j].
                                  Points[(int)Hexagonal.FlatVertice.BottomLeft], 
                                  side, orientation);
                            }
                            else
                            {
                                // Calculate from Hex to the left
                                // and need to stagger the columns
                                if (j % 2 == 0)
                                {
                                    // Calculate from Hex to left's
                                    // Upper Right Vertice plus h and R offset 
                                    float x = hexes[i, j - 1].Points[
                                      (int)Hexagonal.FlatVertice.UpperRight].X;
                                    float y = hexes[i, j - 1].Points[
                                      (int)Hexagonal.FlatVertice.UpperRight].Y;
                                    x += h;
                                    y -= r;
                                    hexes[i, j] = new Hex(x, y, side, orientation);
                                }
                                else
                                {
                                    // Calculate from Hex to left's Middle Right Vertice
                                    hexes[i, j] = new Hex(hexes[i, j - 1].Points[
                                      (int)Hexagonal.FlatVertice.MiddleRight], 
                                      side, orientation);
                                }
                            }
                               break;
                           case HexOrientation.Pointy:
                            if (inLeftColumn)
                            {
                                 // Calculate from hex above and need to stagger the rows

                                if (i % 2 == 0)
                                {
                                    hexes[i, j] = new Hex(hexes[i - 1, j].Points[
                                      (int)Hexagonal.PointyVertice.BottomLeft], 
                                      side, orientation);
                                }
                                else
                                {
                                    hexes[i, j] = new Hex(hexes[i - 1, j].Points[
                                      (int)Hexagonal.PointyVertice.BottomRight], 
                                      side, orientation);
                                }
                            }
                            else
                            {
                                // Calculate from Hex to the left
                                float x = hexes[i, j - 1].Points[
                                  (int)Hexagonal.PointyVertice.UpperRight].X;
                                float y = hexes[i, j - 1].Points[
                                  (int)Hexagonal.PointyVertice.UpperRight].Y;
                                x += r;
                                y -= h;
                                hexes[i, j] = new Hex(x, y, side, orientation); 
                            }
                            break;
                        default:
                            break;
                    }
                }
            }
        }
    }
} 

public enum FlatVertice
{
    UpperLeft = 0,
    UpperRight = 1,
    MiddleRight = 2,
    BottomRight = 3,
    BottomLeft = 4,
    MiddleLeft = 5,
}

public enum PointyVertice
{
    Top = 0,
    UpperRight = 1,
    BottomRight = 2,
    Bottom = 3,
    BottomLeft = 4,
    TopLeft = 5,
}

This method starts by creating a Hex at the array position 0,0. After a Hex object is created, every other Hex can be created because some vertex of a Hex is also the vertex of another Hex. So, you can loop through the two dimensional array from top to bottom, left to right, creating Hexes. The orientation will affect the calculations. I also created enumerations to give friendly names to the vertices. It’s important to note that we have a two dimensional array of Hex objects, and we’re also calculating x,y pixel coordinates for our hexes, so it’s easy to get confused when you see x,y or i,j, or 0,0.

The Hex and Board code above is not complete, you’ll have to download the source to view all of it. There’s just too much to show it all here. I’ve shown you the core methods that do the important work. The position booleans inBoard‘s Initialize() method are not strictly necessary, and not all of them are used, but I left them in for now.

public class GraphicsEngine
{
    private Hexagonal.Board board;
    private float boardPixelWidth;
    private float boardPixelHeight;
    private int boardXOffset;
    private int boardYOffset;
    ...

    public void Draw(Graphics graphics)
    { 

        int width =  Convert.ToInt32(System.Math.Ceiling(board.PixelWidth));
        int height = Convert.ToInt32(System.Math.Ceiling(board.PixelHeight));
        // seems to be needed to avoid bottom and right from being chopped off

        width += 1;
        height += 1; 

        //
        // Create drawing objects
        //

        Bitmap bitmap = new Bitmap(width, height);
        Graphics bitmapGraphics = Graphics.FromImage(bitmap);
        Pen p = new Pen(Color.Black);
        SolidBrush sb = new SolidBrush(Color.Black); 

        //
        // Draw Board background
        //

        sb = new SolidBrush(board.BoardState.BackgroundColor);
        bitmapGraphics.FillRectangle(sb, 0, 0, width, height); 

        //
        // Draw Hex Background 
        //

        for (int i = 0; i < board.Hexes.GetLength(0); i++)
        {
            for (int j = 0; j < board.Hexes.GetLength(1); j++)
            {
                bitmapGraphics.FillPolygon(new SolidBrush(board.Hexes[i,j].
                   HexState.BackgroundColor), board.Hexes[i, j].Points);
            }
        } 

        //
        // Draw Hex Grid
        //

        p.Color = board.BoardState.GridColor;
        p.Width = board.BoardState.GridPenWidth;
        for (int i = 0; i < board.Hexes.GetLength(0); i++)
        {
            for (int j = 0; j < board.Hexes.GetLength(1); j++)
            {
                bitmapGraphics.DrawPolygon(p, board.Hexes[i, j].Points);
            }
        } 

        //
        // Draw Active Hex, if present
        //

        if (board.BoardState.ActiveHex != null)
        {
            p.Color = board.BoardState.ActiveHexBorderColor;
            p.Width = board.BoardState.ActiveHexBorderWidth;
            bitmapGraphics.DrawPolygon(p, board.BoardState.ActiveHex.Points);
        } 

        //
        // Draw internal bitmap to screen
        //
        graphics.DrawImage(bitmap, new Point(this.boardXOffset, 
                                             this.boardYOffset));

        //
        // Release objects
        //
        bitmapGraphics.Dispose();
        bitmap.Dispose(); 
    }

The GraphicsEngine class takes a Board object and writes it to the screen using GDI+. I’m not going to take a lot of time to explain GDI+, but the Draw() method accepts a Graphics object which is derived from a calling form. Draw() then writes the Board and Hexes to a bitmap variable, and finally displays that bitmap to the screen. You’ll notice that there are the HexState and BoardState classes that are properties of the Hex and Boardclasses, respectively. The HexState and BoardState classes contain state type information about the Hex orBoard. In this case, the state information is color. These classes are not strictly necessary, but I wanted to keep theHex and Board classes as pure as possible, meaning that they only contain information about geometry and pixels. This way, the stateful information is separated, and can be developed independently.

Pulling it all together in a Form

To make this all work, you need to create a Form with a GraphicsEngine object and a Board object. Then, create a handler for the form’s Paint event.

private void Form_Paint(object sender, PaintEventArgs e)
{
    foreach (Control c in this.Controls)
    {
        c.Refresh();
    } 
    if (graphicsEngine != null)
    {
        graphicsEngine.Draw(e.Graphics);
    } 
    //Force the next Paint()

    this.Invalidate(); 
}

Another option is to override the form’s OnPaint method. I’ve seen this done both ways, but I’ve decided to leaveOnPaint alone. I’m not sure which is the best method, but they both work. Also, the form’s DoubleBufferedproperty needs to be set to true. This can be done in code or in the designer. Double buffering prevents flicker when you are painting to the screen (set it to false and see what happens).

To capture mouse clicks, create a handler for the form’s MouseClick or MouseDown event.

private void Form_MouseClick(object sender, MouseEventArgs e)
{
    if (board != null && graphicsEngine != null)
    {
        //
        // need to account for any offset
        //

        Point mouseClick = new Point(e.X - graphicsEngine.BoardXOffset, 
                                     e.Y - graphicsEngine.BoardYOffset); 
        Hex clickedHex = board.FindHexMouseClick(mouseClick); 
        if (clickedHex == null)
        {
            board.BoardState.ActiveHex = null;
        }
        else
        {
            board.BoardState.ActiveHex = clickedHex;
            if (e.Button == MouseButtons.Right)
            {
                clickedHex.HexState.BackgroundColor = Color.Blue;
            }
        }
    }
}

One of the things the GraphicsEngine can do is keep track of an x,y offset so that the Board object can be drawn anywhere on the form. If there is an offset, the mouse click needs to account for that offset and pass that new x,y value to the Board‘s FindHexMouseClick() method. The FindHexMouseClick() method is very important because it translates x,y pixel coordinates to Board/Hex coordinates. There are several ways to convert pixel to hex coordinates, Google “pixel to hexagon”. I found a really slick algorithm that will work for any polygon, not just hexagons. The algorithm takes a point and determines if it lies within a polygon by drawing lines through the edges of the polygon. A full description can be found here. My implementation lives in my Math class.

public static bool InsidePolygon(PointF[] polygon, int N, PointF p)
{
    int counter = 0;
    int i;
    double xinters;
    PointF p1,p2; 
    p1 = polygon[0];
    for (i=1;i<=N;i++) 
    {
        p2 = polygon[i % N];
        if (p.Y > System.Math.Min(p1.Y,p2.Y)) 
        {
            if (p.Y <= System.Math.Max(p1.Y,p2.Y)) 
            {
                if (p.X <= System.Math.Max(p1.X,p2.X)) 
                {
                    if (p1.Y != p2.Y) 
                    {
                        xinters = (p.Y-p1.Y)*(p2.X-p1.X)/(p2.Y-p1.Y)+p1.X;
                        if (p1.X == p2.X || p.X <= xinters)
                            counter++;
                    }
                }
            }
        } 
        p1 = p2;
    } 
    if (counter % 2 == 0)
        return false;
    else
        return true;
}

On the way of Hexagonal Coordinates

This page contains a message that Charles Fu posted to rec.games.programmer in 1994, plus a collection of messages that people emailed to me directly.

From: ccwf@plato.klab.caltech.edu (Charles Fu)
Newsgroups: rec.games.programmer
Subject: Re: Which point is in the hex?
Date: 4 Jun 1994 16:47:28 GMT

In article <2sinkh$kj@controversy.math.lsa.umich.edu>,
Zachary S. Delproposto <zsd@umich.edu> wrote:
>:Joseph Hlebasko (hlebasko@lilly.com) wrote:
>:     |2  \|  is x above or below the line? You can use Y=MX+B and search
>: this way (brute force)
>:     |____\     or if your hexes are small enough you can pre-calculate
>: the coords and store in
>:                a table and do a table search.

>This is a very good description, and is quite similar to what I did in
>a program I wrote.  However, the triangle part was easy -- I used
>the region functions in the Windows API (now under DOS, it's a bit
>more difficult!).

Am I the only one who has found all the solutions presented so far less than elegant? Maybe it’s just my mathematical background. Anyways, I presented my solution to this problem in this group, oh, almost a decade ago now. Since I didn’t save the article 🙂, I put pencil to paper and rederived the results. (Actually, this is slightly cleaner than my original solution: I’ve improved a little over the years.🙂 Basically, for hex grids I advocated using a symmetric system of three axes each 120 degrees apart (obviously, one is redundant). For example, have x increasing to the right, y increasing to the upper left, and z increasing to the lower left. Then, your hexes will have coordinates like this:

           ____
          /    \\
     ____/ 0 1-1\\____
         \      //    \
   -1 1 0 \____// 1 0-1\___
          /    \\      /
     ____/ 0 0 0\\____/ 2 -1 -1
         \      //    \
   -1 0 1 \____// 1-1 0\__
          /    \\      /
     ____/ 0-1 1\\____/
         \      //    \
          \____//      \

The formula for which hex a point belongs to is then

  ____   ____ _
  rint { rint(r) - [ 0.5 - max |rint(r )-r | ] sum rint(r ) }
			    i         i   i     i        i

where r is your ungridded position, rint is your rounding function of choise, and the top bar indicates a vector. The zig-zag is not directly relevant and is explained at the end of the article.

Of course, this is just a pretty formula and not an efficient implementation. An efficient implementation would go something like this:

  /* doubles x, y, and z hold the initial raw ungridded position */
  double rx, ry, rz;
  int ix, iy, iz, s;

  ix = rx = rint(x);
  iy = ry = rint(y);
  iz = rz = rint(z);
  s = ix + iy + iz;
  if(s) {
    double abs_dx = fabs(rx-x),
           abs_dy = fabs(ry-y), abs_dz = fabs(rz-z);

    if(abs_dx >= abs_dy && abs_dx >= abs_dz) ix -= s; /* abs_dx is max. */
    else if(abs_dy >= abs_dx && abs_dy >= abs_dz)
      iy -= s; /* abs_dy is max. *.
    else iz-=s;
  }

  /* ix, iy, iz now hold the coordinates of the hex. */

Obviously, further machine implementation optimizations can be made depending upon the speed with which doubles can be cast to ints, whether or not rint and fabs are inlined and implemented in hardware, whether or not your machine uses a IEEE floating point representation, pipelining issues, and so forth. The if-else if-else can also be improved.

Note that the algorithm is symmetric in x,y,z since the axes are symmetric. Also, x+y+z is always zero. These two facts make algorithms more intuitive and bugs much easier to spot. Similarity in instructions may also improve chances for compiler or hand optimization. If desired, z can be computed whenever needed to reduce the memory usage by a few measly bytes.

Of course, if you don’t use my coordinate system, you will need to convert in and out of it. This should be pretty simple. For example, if you use the popular system with x increasing by one every hex to the right and y increasing by one every hex up with y going 0.5,1.5,2.5,… on the odd columns, then your x is the same as my x and your y is just offset from mine by x/2 (and my z=-x-y as pointed out above).

**mathematical details below—not for the fain-hearted**

How was the above formula derived? The insight is that a uniform hex grid is the isometric projection of an infinite grid of unit cubes whose centers satisfy the equation x+y+z=0. Thus, hairy problems with hexes in 2-D become nicer problems with cubes in 3-D in very much the same way that using homogenous coordinates linearizes projective transformations.

(An isometric projection is an orthographic, i.e., non-perspective, projection onto the x+y+z=0 plane. It is one of the standard views used by draftsmen: the one with x, y, and z 120 degrees from each other, just like my axes.)

In this particular case, the problem of determining which hex contains a given point becomes the trivial problem of which cube contains a point. The rest of the code just transforms from the x+y+z=0 plane to the cube grid and vice versa. That’s it.

With the cube grid system, problems like counting the number of hexes between points also becomes trivial. The system also has interesting bizarre properties such as lines of constant x zigzagging to follow hex sides as shown in the diagram above. If you want a Euclidean metric, just stick with the rotated coordinate system and avoid the fancy projection except when discrete hexes are needed.

Final note: my advocacy of this approach got no support when I first posted it years ago. Perhaps it will stir more interest now. There does seem to be a gradual trend toward mathematical literacy amongst game designers and CG programmers. Perhaps there’s hope for me yet. 🙂

-ccwf

...  Anatomy is very poor...  See how that muscle connects?...  And
that perspective, _yeesh_!...  Do you know what a _vanishing point_
is?  And as for _faces_...
                     -Scott McCloud, _Understanding Comics_

Along the same lines, Bram de Greve writes:

From: Bram de Greve 
To: amitp@CS.Stanford.EDU
Subject: Distance in hexaconal grids with Isometric Cube Coordinates 
Date: Wed, 17 Nov 1999 20:50:44 +0100 (MET)

Hi,

I have here a very simple method to calculate the “walk-distance” between 2 hexagons with ISOMETRIC CUBE COORDINATES. I think that it might be worth to be published because it’s very simple and very handy, but isn’t mentioned at your pages yet. At least, I didn’t found it.

With “walk-distance” I mean how many hexagons do you have to walk over to reach another one.

Let us call the 2 hexagons H1 and H2 with the isometric cube coordinates (x1,y1,z1) and (x2,y2,z2).

Now the distance is given by:

   1/2 * [ Abs(x1-x2)+Abs(y1-y2)+Abs(z1-z2) ]

You see it is very simple.

And of course, if one should need the “light-distance” you may use pythagoras. With “light-distance” I mean the distance between the 2 centers of the hexagons, measured in 1 straight line. It’s given by

   [ (x1-x2)^2 + (y1-y1)^2 + (z1-z2)^2 ] ^ (1/2)

Regards,
Bram


Cris Fuhrman writes that the distance can alternatively be expressed as:

distance = max [ abs(x1-x2), abs(y1-y2), abs(z1-z2) ]

It appears that when x+y+z = 0, this approach is equivalent to the 1/2 of the sum approach, but I (Amit) was not sure how to prove it.


Ariel Birnbaum offers this:

From: Ariel Birnbaum
To: amitp@cs.stanford.edu
Subject: Hex Grid - missing proof
Date: Mon, 22 Jan 2007 13:24:54 +0200

Here’s a possible proof:

If x=x1-x2y=y1-y2z=z1-z2, then x+y+z=x1+y1+z1-(x2+y2-z2)=0.

Hence it suffices to show that:

 ( |x| + |y| + |z| ) / 2 = max { |x|, |y|, |z| }, for x+y+z=0.

Assume wlog that max { |x|, |y|, |z| } = |x|. Also wlog, assume x to be nonnegative. If x=0, the claim is trivial, so we assume x to be positive. If y is also positive, then z=-(x+y), and we see that |z|=|x|+|y| > |x| which contradicts the previous assumption. Hence y is nonpositive, similarly for z. We then have:

 |x|+|y|+|z| = x - y - z = x - (y+z) = x + x = 2x = 2|x|

which proves the claim. For the case where x is negative, we just negate the whole vector and proceed as above.


Matt Walker offers this:

To: amitp@cs.stanford.edu
From: Matt Walker <matt.r.walker@gmail.com>
Subject: Isometric cube coordinate distance proof
Date: Sun, 18 Feb 2007 09:21:54 -0600

I thought I’d lend a hand (I’m not claiming it’s elegant, but I do think it’s a proof):

x1 + y1 + z1 = 0
x2 + y2 + z2 = 0
x1 + y1 + z1 = x2 + y2 + z2

show:
1/2 (|x1 - x2| + |y1 - y2| + |z1 - z2|) = max(|x1 - x2|, |y1 - y2|, |z1 - z2|)

1/2 (|x1 - x2| + |y1 - y2| + |z1 - z2|)
= 1/2 (|y2 - y1 + z2 - z1| + |y1 - y2| + |z1 - z2|)
= 1/2 (|-(a + b)| + |a| + |b|)
= 1/2 (|a + b| + |a| + |b|)

case 1: sign(a) = sign(b)

= 1/2 (|a| + |b| + |a| + |b|)
= |a| + |b|
= max(|a| + |b|, |a|, |b|)
= max(|a + b|, |a|, |b|)
= max(|x1 - x2|, |y1 - y2|, |z1 - z2|)

case 2: sign(a) ~= sign(b), |a| > |b|

= 1/2 (||a| - |b|| + |a| + |b|)
= 1/2 (|a| - |b| + |a| + |b|)
= |a|
= max(|a| - |b|, |a|, |b|)
= max(||a| - |b||, |a|, |b|)
= max(|a + b|, |a|, |b|)
= max(|x1 - x2|, |y1 - y2|, |z1 - z2|)

case 3: symmetric for |b| > |a|

Hexagonal grid math

Uniform hexagonal grid is a recurring pattern in computer games and graphics applications.
There are few operations one might need to perform:

  • finding hexagon’s position by its index in the grid;
  • picking a hexagon by mouse;
  • finding neighbor cells;
  • finding hexagon’s corner coordinates etc.

While these things do not appear hard at all (something like primary school-level geometry/arithmetics), it’s not as straightforward as with a rectangular grid, however.

What have confused me, though, is that presented solution (and code) seemed to be more complex than one could expect:

  • hexagon positions are found iteratively, based on the previously computed positions;
  • a bunch of corner cases are treated in the process;
  • a whole lot of state is stored for each hexagon;
  • there is a separate codepath for the alternative hexagon orientation mode (aka “pointy” orientation), which interwines with the main one;
  • to pick a hexagon by mouse, the code iterates on the array of hexagons, and performs generic “point-in-polygon” test for each, using stored corners’ coordinates.