CodeProject: Hexagonal grid for games and other
projects
Author: Jeff Modzel
http://www.codeproject.com/KB/graphics/hexagonal_part1.aspx
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.
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?
Collapse
h = sin( 30°) * s
r = cos( 30°) *
s
b =
s + 2 * h
a
= 2
* r
<
/FONT
>
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.
Collapse
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.
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.
Collapse
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:
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.
Collapse
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.
Collapse
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.
Collapse
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.
Collapse
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;
} }
}
}
<
/FONT
>
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.
Collapse
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.