Click here to Skip to main content
65,938 articles
CodeProject is changing. Read more.
Articles
(untagged)

Hexagonal grid for games and other projects - Part 1

0.00/5 (No votes)
26 Jul 2006 1  
First version of a hexagonal grid for games or other apps.

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 s, r, 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 class Math 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 Board class 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 in Board'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 Board classes, respectively. The HexState and BoardState classes contain state type information about the Hex or Board. In this case, the state information is color. These classes are not strictly necessary, but I wanted to keep the Hex 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 leave OnPaint alone. I'm not sure which is the best method, but they both work. Also, the form's DoubleBuffered property 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;
}

Conclusion

Please download the source project since it was impossible to include every last line of code in this article. My source is a Visual Studio 2005 console project. The console project actually launches the form. I did this because you can make Console.WriteLine() calls from the form and send messages to the console, which is obviously helpful for debugging.

This is the first "version" of the Hexagonal namespace. I'd like to add more functionality as I have time. Some of the features I'd like to add are gradient backgrounds and images, scrollable boards, and boards of different shapes. Being able to serialize a Board object out to XML for storage would be nice as well. Comments and suggestions welcome.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here