Article: Hexagonal Coordinates

by Blecki

This article describes how to use hexagonal coordinates and is provided with a sample project.

Hexagon Dimensions

DimensionsDiagram

First, we will calculate the dimensions of various parts of a hexagon. To calculate the width and halfWidth, we use the pythagorean theroem.

    class Hex
    {
        private float radius;
        private float width;
        private float halfWidth;
        private float height;
        private float rowHeight;

        public Hex(float radius)
        {
            this.radius = radius;
            this.height = 2 * radius;
            this.rowHeight = 1.5f * radius;
            this.halfWidth = (float)Math.Sqrt((radius * radius) - ((radius / 2) * (radius / 2)));
            this.width = 2 * this.halfWidth;
        }

CoordinatesDiagram

Coordinate System

Origin and Center

We will use Vector2s as our hex tile map coordinates. Tile map coordinates increase to the right and up.

We will need to turn tile map coordinates into world coordinates. There are two points that make logical tile origins. There is the center of the tile, and there is the point outside the hex, as in the diagram.

Whichever you use, the value is the same. All you're changing is which of these you position at 0,0. Be consistent in your drawing code, and these two values will be the same. This does make a different later, in the conversion from world coordinates back to tile coordinates. The origin point is the easier to work with there, so that's what we'll use here.

OriginCenterDiagram

We must account for every other row being offset half a hex width.

Notice that we use the rowHeight value, not the height value. This accounts for the way Hexagons interlock.

    public Vector2 TileOrigin(Vector2 tileCoordinate)
    {
        return new Vector2(
                (tileCoordinate.X * width) + ((tileCoordinate.Y % 2 == 1) ? halfWidth : 0),
                tileCoordinate.Y * rowHeight);
    }

We'll go ahead and calculate the center based on the origin.

    public Vector2 TileCenter(Vector2 tileCoordinate)
    {
        return TileOrigin(tileCoordinate) + new Vector2(halfWidth, height/2);
    }

Directions

DirectionsDiagram

The chief advantage of a hex map over a square map is that there are six neighbors all the same distance away, rather than only four. We will first create an enumeration to represent our six directions, then we will define some functions for manipulating them.

    public enum Direction
    {
        NorthEast,
        East,
        SouthEast,
        SouthWest,
        West,
        NorthWest,
        NumberOfDirections,
    }

Now we will add a few functions to manipulate directions.

    public static Direction RotateDirection(Direction direction, int amount)
    {

        //Let's make sure our directions stay within the enumerated values.
        if (direction < Direction.NorthEast ||
            direction > Direction.NorthWest ||
            Math.Abs(amount) > (int)Direction.NorthWest)
        {
            throw new InvalidOperationException("Directions out of range.");
        }
       direction += amount;
       //Now we need to make sure direction stays within the proper range.
       //C# does not allow modulus operations on enums, so we have to convert to and from int.

       int n_dir = (int)direction % (int)Direction.NumberOfDirections;

       if (n_dir < 0) n_dir = (int)Direction.NumberOfDirections + n_dir;
           direction = (Direction)n_dir;

       return direction;
    }

Finding the opposite is probably the simplest.

public static Direction Opposite(Direction direction)
{
	return RotateDirection(direction, 3);
}

Now that we have directions, we can figure out who our neighbors are. We must again account for odd numbered rows being different. The algorithm is pretty simple. We must simply apply a different set of offsets per direction depending on whether this is an odd or even row.


public static Vector2 Neighbor(Vector2 tile, Direction direction)
{
if (tile.Y % 2 == 0) //Is this row even?
{

Even Neighbors

    switch(direction)
    {
        case Direction.NorthEast : tile.Y += 1; break;
        case Direction.East : tile.X += 1; break;
        case Direction.SouthEast: tile.Y -= 1; break;
        case Direction.SouthWest: tile.Y -= 1; tile.X -= 1; break;
        case Direction.West: tile.X -= 1; break;
        case Direction.NorthWest: tile.X -= 1; tile.Y += 1; break;
        default: throw new InvalidOperationException("Invalid direction");
    }
}
else //This is an odd row.
{

Odd Neighbors

    switch (direction)
    {
        case Direction.NorthEast: tile.X += 1;  tile.Y += 1; break;
        case Direction.East: tile.X += 1; break;
        case Direction.SouthEast: tile.X += 1; tile.Y -= 1; break;
        case Direction.SouthWest: tile.Y -= 1;; break;
        case Direction.West: tile.X -= 1; break;
        case Direction.NorthWest: tile.Y += 1; break;
        default: throw new InvalidOperationException("Invalid direction");
    }
}

return tile;
}

Unfortunately, as you can see, iterating over tiles in a specific direction is not as simple as incrementing values in the tile coordinate. To iterate in a specific direction, use a loop such as

for (Vector2 coordinate = new Vector(0,0); /*end condition*/;
    coordinate = Hex.Neighbor(coordinate, Hex.Direction.NorthEast))

CoordinatesDiagram

There's not much left. All we need to do now is get a tile coordinate back from a world coordinate. This requires a little bit of linear algebra, and once again we are complicated by odd rows.

public Vector2 TileAt(Vector2 worldCoordinate)
{

First we will calculate a few constants to make the rest of code simpler.

float rise = height - rowHeight;
float slope = rise / halfWidth;

World to Tile

The first step is to find our position in a square grid. This grid allows us to divide the hex map into two types of tiles.

int X = (int)Math.Floor(worldCoordinate.X / width);
int Y = (int)Math.Floor(worldCoordinate.Y / rowHeight);

Now we find the offset of the real point from the corner of this square grid section.

Vector2 offset = new Vector2(worldCoordinate.X - X * width, worldCoordinate.Y - Y * rowHeight);

if (Y % 2 == 0) //Is this an even row?
{
//Section type A

Looking at the diagram for section A, we can see that two hexagons poke into the bottom of the square. We plug the offset's X value into the equation for the line of the top of those hexes at the bottom. If you've taken algebra, you know that the equation of a line like this is Y=MX+B. That's why we calculated the rise and slope earlier. The line on the left of section A has a negative slope, and a Y intercept of rise. The other has a positive slope, and a Y intercept of negative rise. We adjust the X,Y tile coordinates if we discover that the point is below one of these lines. This is the same adjustment used for finding neighbors.

    //Point is below left line; inside SouthWest neighbor
    if (offset.Y < (-slope * offset.X + rise))
    {
        X -= 1;
        Y -= 1;
    }
    //Point is below right line; inside SouthEast neighbor
    else if (offset.Y < (slope * offset.X - rise))
    {
        Y -= 1;
    }
    else
    {
        //Section type B

Section B is slightly more complex. First we determine if the point is in the right or left section. Since odd rows are offset by halfWidth, the large section on the right has the same coordinates as the square grid.

        if (offset.X >= halfWidth) //Is the point on the right side?
        {
            if (offset.Y < (-slope * offset.X + rise * 2.0f))
					//Point is below bottom line; inside SouthWest neighbor.
                Y -= 1;
        }
        else //Point is on the left side
        {
            if (offset.Y < (slope * offset.X))
					//Point is below the bottom line; inside SouthWest neighbor.
                Y -= 1;
            else //Point is above the bottom line; inside West neighbor.
                X -= 1;
        }
    }

    return new Vector2(X, Y);
}

Here's a complete class, ready to handle Hex coordinate systems.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;

namespace HexDemo
{
    class Hex
    {
        private float radius;
        private float width;
        private float halfWidth;
        private float height;
        private float rowHeight;

        public Hex(float radius)
        {
            this.radius = radius;
            this.height = 2 * radius;
            this.rowHeight = 1.5f * radius;
            this.halfWidth = (float)Math.Sqrt((radius * radius) - ((radius / 2) * (radius / 2)));
            this.width = 2 * this.halfWidth;
        }

        public Vector2 TileOrigin(Vector2 tileCoordinate)
        {
            return new Vector2(
                (tileCoordinate.X * width) + ((tileCoordinate.Y % 2 == 1) ? halfWidth : 0), //Y % 2 == 1 is asking 'Is Y odd?'
                tileCoordinate.Y * rowHeight);
        }

        public Vector2 TileCenter(Vector2 tileCoordinate)
        {
            return TileOrigin(tileCoordinate) + new Vector2(halfWidth, halfWidth);
        }

        public enum Direction
        {
            NorthEast,
            East,
            SouthEast,
            SouthWest,
            West,
            NorthWest,
            NumberOfDirections,
        }

        public static Direction RotateDirection(Direction direction, int amount)
        {
            //Let's make sure our directions stay within the enumerated values.
            if (direction < Direction.NorthEast || direction > Direction.NorthWest || Math.Abs(amount) > (int)Direction.NorthWest)
                throw new InvalidOperationException("Directions out of range.");

            direction += amount;

            //Now we need to make sure direction stays within the proper range.
            //C# does not allow modulus operations on enums, so we have to convert to and from int.

            int n_dir = (int)direction % (int)Direction.NumberOfDirections;
            if (n_dir < 0) n_dir = (int)Direction.NumberOfDirections + n_dir;
            direction = (Direction)n_dir;

            return direction;
        }

        public static Direction Opposite(Direction direction) { return RotateDirection(direction, 3); }

        public static Vector2 Neighbor(Vector2 tile, Direction direction)
        {
            if (tile.Y % 2 == 0) //Is this row even?
            {
                switch (direction)
                {
                    case Direction.NorthEast: tile.Y += 1; break;
                    case Direction.East: tile.X += 1; break;
                    case Direction.SouthEast: tile.Y -= 1; break;
                    case Direction.SouthWest: tile.Y -= 1; tile.X -= 1; break;
                    case Direction.West: tile.X -= 1; break;
                    case Direction.NorthWest: tile.X -= 1; tile.Y += 1; break;
                    default: throw new InvalidOperationException("Invalid direction");
                }
            }
            else //This is an odd row.
            {
                switch (direction)
                {
                    case Direction.NorthEast: tile.X += 1; tile.Y += 1; break;
                    case Direction.East: tile.X += 1; break;
                    case Direction.SouthEast: tile.X += 1; tile.Y -= 1; break;
                    case Direction.SouthWest: tile.Y -= 1; ; break;
                    case Direction.West: tile.X -= 1; break;
                    case Direction.NorthWest: tile.Y += 1; break;
                    default: throw new InvalidOperationException("Invalid direction");
                }
            }

            return tile;
        }

        public Vector2 TileAt(Vector2 worldCoordinate)
        {
            float rise = height - rowHeight;
            float slope = rise / halfWidth;
            int X = (int)Math.Floor(worldCoordinate.X / width);
            int Y = (int)Math.Floor(worldCoordinate.Y / rowHeight);
            Vector2 offset = new Vector2(worldCoordinate.X - X * width, worldCoordinate.Y - Y * rowHeight);

            if (Y % 2 == 0) //Is this an even row?
            {
                //Section type A
                if (offset.Y < (-slope * offset.X + rise)) //Point is below left line; inside SouthWest neighbor.
                {
                    X -= 1;
                    Y -= 1;
                }
                else if (offset.Y < (slope * offset.X - rise)) //Point is below right line; inside SouthEast neighbor.
                    Y -= 1;
            }
            else
            {
                //Section type B
                if (offset.X >= halfWidth) //Is the point on the right side?
                {
                    if (offset.Y < (-slope * offset.X + rise * 2.0f)) //Point is below bottom line; inside SouthWest neighbor.
                        Y -= 1;
                }
                else //Point is on the left side
                {
                    if (offset.Y < (slope * offset.X)) //Point is below the bottom line; inside SouthWest neighbor.
                        Y -= 1;
                    else //Point is above the bottom line; inside West neighbor.
                        X -= 1;
                }
            }

            return new Vector2(X, Y);
        }

    }
}

Download the sample code here :- Link

Back from holidays. News Recap

Hi all!

I'm back from my holidays, so here's a list of news from the XNA world that stacked up, and you might have missed:

Nuclex welcomes us to the first part of his XNA Game Archtiecture Series, where he talks about his proposed development tree and third party libraries.

The series of Free Game Assets continues with a new free pack of Planet Sprites and Textures.

Innovative Game's "Game Engine Tutorial" continues with a new part about the Content Manager.

Shawn Hargreaves has two very enlightening posts the you should definitely read. This first is "Bug or Feature" talking about a bug in Extreme G that was seen as a feature by reviewers. The second one talks about AI Coordinate Systems, as used in Moto GP.

Finally, Nick Gravelyn posted some tweaks to his Interpolators.

Ratings And Pillory

SCENE X

A well known gamedev site.

Enter Richard “I'm the highest-rated user on this site” Fine.

Richard. One of the questions from a previous entry was what's happening to user ratings in V5. I don't have funky screenshots to show you this time, but I'll talk about what the plan is.

Lays out the plan.

Richard. The new system doesn't quite solve the problems that the original rating system set out to solve. Instead, it focuses on the deeper problems of how to get the best content into your hands as quickly as possible and how to describe users; they're harder problems, naturally, but I think more worthwhile.

INTERLUDE

The official XNA GS/FX site.

Enter the IDN Team.

IDN Team. Our MVP’s are an important part of the work done on XNA Creators Club Online, and are an extension of our team. Therefore we’ve listed each of our MVP’s and their bios on our new Meet the Team page, in order for you to get to know them better.

Observe: lacks contact information and photos.

Free UI sprites

Looks like I was wrong last time, when I assumed something 4D would be next in the series of Free Game Assets :(

But even if it's not 4D, what we get this time is still cool: some sprites to use for User Interfaces.

Game Architecture Series

Markus Ewalds of Nuclex promises a series of articles about designing a game and it's architecture. I'm curious to see what he has in store for us, and hope the series will be an interesting one. Read the announcement on his site.

Merry Christmas, Thank You and Sgt. Conker wants to do more

As the festive season is now in full flow we would just like to say to those who celebrate it.

HAVE A VERY MERRY CHRISTMAS FROM ALL AT SGT. CONKER!

Here at Sgt. Conker we are all very impressed with the response our website has so far received.

So we would firstly like to say a big THANK YOU to everyone who visits our site and spreads the word.

We want to continue to get more visitors and to help the community as much as we can and need your help.

What else can Sgt. Conker do for you?

We know we need more articles, so please speak to us about any ideas for new articles and if you are an article author yourself, we are very happy to host great content on your behalf.

If there is something you think is missing or anything else you think we can do to help the community further, please comment on this post.

Sgt. Conker also takes feedback seriously, so please comment on anything you like or dislike about our existing or future content.

New And Bold

SCENE VII

A well known gamedev site.

Enter Richard “Superpig al rescate” Fine.

Richard. The navbar is really going to be your primary means for getting around the site, so it's important that we get it right. There's a lot of functionality packed in there! I'm not going to show you everything today, but we'll cover enough to be worth talking about.

Explains the navigation bar in detail.

Richard. The biggest risk that Search Don't Sort poses is to people who aren't really looking for anything; 'browsers,' in the purest sense. It's very important to make sure that users who don't have any particular information need in mind, still have the means to just float through the content at random. As you'll see in future posts, though, I think we've got this fairly well covered.

SCENE VIII

Twitter.

Enter Nick “We are running out of descriptions” Gravelyn.

Nick. EasyStorage 1.5 with localization support and some changes to the API is checked in.

Points to the source code on CodePlex.

Nick. If you speak Spanish, French, German, or Japanese, consider helping translate some strings for EasyStorage.

SCENE IX

A rural location Down Under. A campfire.

Enter Glenn “Not a Crocodile Dundee” Wilson.

Glenn. night all See you at #ozgamecamp in the morning.

Presents 5 sessions in 3 days.

Glenn. Been a good couple of days here at #ozgamecamp, on the final stretch.

Prophecy And Disaster

SCENE V

An innocent interview with Derek Yu and the public demise of a XBLIGer.

Enter George W. “Not the Bush” Clingerman and Jim “Not the Moustache” Perry to rescue the reputation of the community.

George. I also would like to point out that not all XBLIG devs have this same chip on the shoulder that Adam has.

Derek Yu is so dreamy!!!! :)

Jim. Part of the problem is that many developers are looking at XBLIG wrong. […] If you're going to treat it like a business in that you want sites to review your game, you as a developer need to step up and be professional and do some PR. You have a ton of codes that you can hand out so use them.

Silence.

SCENE VI

A vent space on the interwebs.

Enter Promit “I am Slim” Roy.

Promit. So, how is Windows API Code Pack 1.0?

Tumbleweed crosses the stage.

About That Publicity Thingy Dingy

They say “Any publicity is good publicity” and P.T. Barnum is quoted to have said “I don't care what they say about me as long as they spell my name right.”

With this introduction I present you the comments thread on Pondering Indie Spirit: Derek Yu Speaks (the interview itself is worth reading). In the words of Michael Rose: “This thread went from irritating to epic in a matter of hours, and two things are definitely clear: (1) Spelunky is awesome and (2) Adam Coate should have his own chat show, as watching train-wrecks is fun”

“Flytrap” (no link yet as it is behind closed bars and there’s no webpage, video or anything else to link to…) is back in peer review now.

And to have a clearly positive take away in this post and the let’s-call-it-reputation-building of a XNA GS fellow: The Idiot's Guide to Marketing Your Indie Game by Michael Rose.

(Hat tip to Ben Baird)

Edit: how could I forget about Xbox Indies?

More Free stuff

Remember that day when we linked to some free music for indie games? If you do, REJOICE! There's two more packs of free stuff coming from the same guys at Iron Star Media. First, some sprites for particle effects, followed by low poly sports models.

Following a linear progression, the next pack should contain something that's 4D! Can't wait to see what it is...

Month List

Page List