View source for Game Design Ideas Articles Hexagonal Grid for games

Game Design Articles to ADD to wiki as reference, expanding ideas and forming a Game Build Plan.

<span style="color:#e76700">'''A'''</span>
<span style="color:#900">'''A'''</span>


==[[Game_Design_Ideas_Articles_Hexagonal_Grid_for_games | Hexagonal grid for games and other projects - Part 1]]==
Jeff Modzel, 26 Jul 2006

First version of a hexagonal grid for games or other apps.

[http://www.codeproject.com/KB/graphics/hexagonal_part1/HexagonalTest.zip Download demo project - 26.7 KB]

[[File:app_screenshot.jpg|center|link= ]]


===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.

[[File:hex_single.png|center|link= ]]


===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.

[[File:hex_geometry.jpg|center|link= ]]

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'''?

'''CODE'''

h = sin( 30°) * s

r = cos( 30°) * s

b = s + 2 * h

a = 2 * r

'''/CODE'''


===My namespace is Hexagonal===
<span style="color:#900">CODE</span>

For lack of a better term, I called my namespace <span style="color:#900">Hexagonal</span>, and that's where all my core classes live. The class <span style="color:#900">Math</span> 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.

'''CODE'''
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;
}
'''/CODE'''

The <span style="color:#900">Sin</span> and <span style="color:#900">Cos</span> methods in <span style="color:#900">System.Math</span> take arguments in radians, not degrees. So, we need a helper method to convert degrees to radians.

The <span style="color:#900">Hex</span> object represents a hexagon. When creating a <span style="color:#900">Hex</span> 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.

[[File:flat_pointy.jpg|center|link= ]]

The vertices are numbered somewhat arbitrarily on my part, but we need to refer to vertices in some manner. The important method in <span style="color:#900">Hex</span> is <span style="color:#900">CalculateVertices()</span>, which is <span style="color:#900">private</span> and called by the constructor. I also created an enumeration for hexagonal orientation.

'''CODE'''

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,
}

'''/CODE'''

The <span style="color:#900">Hex</span> class was designed to be simple. All it does is remember its position in two dimensional space. The <span style="color:#900">Board</span> class is a collection of <span style="color:#900">Hex</span> 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 <span style="color:#900">Flat</span> orientation would map to a two dimensional array like this:


[[File:hex_array.jpg|center|link= ]]


The most important method in the <span style="color:#900">Board</span> class is <span style="color:#900">Initialize()</span>, which is <span style="color:#900">private</span> and called from the constructor. <span style="color:#900">Initialize()</span> creates a two dimensional array of <span style="color:#900">Hex</span> objects with all the calculations for the hex vertices.

'''CODE'''

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,
}

'''/CODE'''

This method starts by creating a <span style="color:#900">Hex</span> at the array position 0,0. After a <span style="color:#900">Hex</span> object is created, every other <span style="color:#900">Hex</span> can be created because some vertex of a <span style="color:#900">Hex</span> is also the vertex of another <span style="color:#900">Hex</span>. So, you can loop through the two dimensional array from top to bottom, left to right, creating <span style="color:#900">Hex</span>es. 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 <span style="color:#900">Hex</span> 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 <span style="color:#900">Hex</span> and <span style="color:#900">Board</span> 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 <span style="color:#900">Board</span>'s <span style="color:#900">Initialize()</span> method are not strictly necessary, and not all of them are used, but I left them in for now.


'''CODE'''

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(); 
    }

'''/CODE'''

The <span style="color:#900">GraphicsEngine</span> class takes a <span style="color:#900">Board</span> object and writes it to the screen using GDI+. I'm not going to take a lot of time to explain GDI+, but the <span style="color:#900">Draw()</span> method accepts a <span style="color:#900">Graphics</span> object which is derived from a calling form. <span style="color:#900">Draw()</span> then writes the <span style="color:#900">Board</span> and <span style="color:#900">Hex</span>es to a bitmap variable, and finally displays that bitmap to the screen. You'll notice that there are the <span style="color:#900">HexState</span> and <span style="color:#900">BoardState</span> classes that are properties of the <span style="color:#900">Hex</span> and <span style="color:#900">Board</span> classes, respectively. The <span style="color:#900">HexState</span> and <span style="color:#900">BoardState</span> classes contain state type information about the <span style="color:#900">Hex</span> or <span style="color:#900">Board</span>. In this case, the state information is color. These classes are not strictly necessary, but I wanted to keep the <span style="color:#900">Hex</span> and <span style="color:#900">Board</span> 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 <span style="color:#900">Form</span> with a <span style="color:#900">GraphicsEngine</span> object and a <span style="color:#900">Board</span> object. Then, create a handler for the form's <span style="color:#900">Paint</span> event.

'''CODE'''

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(); 
}

'''/CODE'''

Another option is to override the form's <span style="color:#900">OnPaint</span> method. I've seen this done both ways, but I've decided to leave <span style="color:#900">OnPaint</span> alone. I'm not sure which is the best method, but they both work. Also, the form's <span style="color:#900">DoubleBuffered</span> property needs to be set to <span style="color:#900">true</span>. This can be done in code or in the designer. Double buffering prevents flicker when you are painting to the screen (set it to <span style="color:#900">false</span> and see what happens).

To capture mouse clicks, create a handler for the form's <span style="color:#900">MouseClick</span> or <span style="color:#900">MouseDown</span> event.

'''CODE'''

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;
            }
        }
    }
}

'''/CODE'''

One of the things the <span style="color:#900">GraphicsEngine</span> can do is keep track of an x,y offset so that the <span style="color:#900">Board</span> 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 <span style="color:#900">Board</span>'s <span style="color:#900">FindHexMouseClick()</span> method. The <span style="color:#900">FindHexMouseClick()</span> method is very important because it translates x,y pixel coordinates to <span style="color:#900">Board/Hex</span> 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 [http://astronomy.swin.edu.au/~pbourke/geometry/insidepoly/ here]. My implementation lives in my <span style="color:#900">Math</span> class.

'''CODE'''

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;
}

'''/CODE'''


===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 <span style="color:#900">Console.WriteLine()</span> calls from the form and send messages to the console, which is obviously helpful for debugging.

This is the first "version" of the <span style="color:#900">Hexagonal</span> 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 <span style="color:#900">Board</span> object out to XML for storage would be nice as well. Comments and suggestions welcome.


===License===
This article, along with any associated source code and files, is licensed under [http://www.codeproject.com/info/cpol10.aspx The Code Project Open License (CPOL)]


===About the Author===
Jeff Modzel

Web Developer

United States United States

Technical Architect

Sungard HE


=Notes=
* [http://www.codeproject.com/KB/graphics/hexagonal_part1.aspx Hexagonal grid for games and other projects - Part 1]
* [http://paulbourke.net/geometry/ Geometry, Surfaces, Curves, Polyhedra] ~ [http://scholar.google.com.au/citations?user=BM_z6YwAAAAJ&hl=en Paul Bourke]
** [http://www.eecs.umich.edu/courses/eecs380/HANDOUTS/PROJ2/InsidePoly.html Determining if a point lies on the interior of a polygon]

[[Category:Research]] [[Category:Game Design]] [[Category:Articles]] [[Category:Programming]] [[Category:Hexes]] [[Category:Hex Grids]] [[Category:Math]]