Feb 15, 2011

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, hovewer.

Having tried to consult with internets I've found a neat article on CodeProject, which was solving exactly the problems mentioned. It's considerably highy rated, which I guess means that this stuff is indeed in demand.

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.

Can we do any simpler?..

Hexagonal grid properties

Let's examine the geometric properties of a hexagon and define some constants:

We define the hexagon by its radius R, and find some other parameters based on it, such as W ("width"), S ("side") and H ("height").

Now, let's examine the hexagonal grid itself:

Finding hexagon position by its array index

From that picture one can figure out the formula for finding position of the top left corner of a hexagon cell by its array index (i, j):

Taking into account that for odd columns i%2 (remainder from division of i by 2) equals 1, and for even columns it equals 0, we can rewrite it:

Finding hexagon index by a point

Another operation is to find the hexagon array index from a point coordinates on the screen, which is used for mouse picking.

Let's start from the observation that hexagonal grid can be completely covered by the set of rectangular tiles (of width S and height H). They are drawn as green rectangles with purple triangular insets in the picture above. Each tile overlaps with three hexagons.

Finding which of those tiles our picking point gets into is not too hard:
Here (it, jt) are the column/row of the rectangular tile picked by the point. Those fancy brackets is a floor operation.

Coordinates of the point inside the tile are:
After we have all this, now we can find which one of the three possible hexagons corresponds to our point. For that we zoom into the rectangular cell's coordinate system and build a plot of the separating line (the fat red line in the picture). Its function is xt=R|0.5-yt/H|, and for all the points above the line (they fall into the green area) we have that xt>R|0.5-yt/H|.

For all the other points inside the rectangle, we have to pick either top or bottom hexagon to the left. This is decided based on value of yt.

Aditionally, we have to mind the odd/even rows indexing difference (as rows in the hexagon array go in zigzag pattern).

Putting it all together, the final array indices of the picked hexagon are:

The "pointy" grid orientation

So far we've been only considering the "flat" grid orientation (i.e. hexagons are "lying" on their sides).

What happens if we want to have the alternative orientation, when hexagons are oriented corners upwards, should we rewrite all the formulas?..

One simple observation about the "pointy" orientation is that one can get it by mirroring the "flat" one around the diagonal axis.

The direct consequence of this is that all the calculations for the "pointy" case can be performed by:
  • swapping the input coordinates (i.e. "mirror" them around the diagonal): x<->y or i<->j;
  • applying the formulas as described above;
  • swapping the output coordinates back ("unmirroring" them): i<->j, x<->y.
The operation is quite straightforward to do in code (as opposed to having a separate codepath for each case), I am leaving it as an exercise to the reader.

The code

Here's an example Java code, which has the formulas implemented:
package com.rush;

 * Uniform hexagonal grid cell's metrics utility class.
public class HexGridCell {
    private static final int[] NEIGHBORS_DI = { 0, 1, 1, 0, -1, -1 };
    private static final int[][] NEIGHBORS_DJ = { 
            { -1, -1, 0, 1, 0, -1 }, { -1, 0, 1, 1, 1, 0 } };

    private final int[] CORNERS_DX; // array of horizontal offsets of the cell's corners
    private final int[] CORNERS_DY; // array of vertical offsets of the cell's corners
    private final int SIDE;

    private int mX = 0; // cell's left coordinate
    private int mY = 0; // cell's top coordinate

    private int mI = 0; // cell's horizontal grid coordinate
    private int mJ = 0; // cell's vertical grid coordinate

     * Cell radius (distance from center to one of the corners)
    public final int RADIUS;
     * Cell height
    public final int HEIGHT;
     * Cell width
    public final int WIDTH;

    public static final int NUM_NEIGHBORS = 6;

     * @param radius Cell radius (distance from the center to one of the corners)
    public HexGridCell(int radius) {
        RADIUS = radius;
        WIDTH = radius * 2;
        HEIGHT = (int) (((float) radius) * Math.sqrt(3));
        SIDE = radius * 3 / 2;

        int cdx[] = { RADIUS / 2, SIDE, WIDTH, SIDE, RADIUS / 2, 0 };
        CORNERS_DX = cdx;
        int cdy[] = { 0, 0, HEIGHT / 2, HEIGHT, HEIGHT, HEIGHT / 2 };
        CORNERS_DY = cdy;

     * @return X coordinate of the cell's top left corner.
    public int getLeft() {
        return mX;

     * @return Y coordinate of the cell's top left corner.
    public int getTop() {
        return mY;

     * @return X coordinate of the cell's center
    public int getCenterX() {
        return mX + RADIUS;

     * @return Y coordinate of the cell's center
    public int getCenterY() {
        return mY + HEIGHT / 2;

     * @return Horizontal grid coordinate for the cell.
    public int getIndexI() {
        return mI;

     * @return Vertical grid coordinate for the cell.
    public int getIndexJ() {
        return mJ;

     * @return Horizontal grid coordinate for the given neighbor.
    public int getNeighborI(int neighborIdx) {
        return mI + NEIGHBORS_DI[neighborIdx];

     * @return Vertical grid coordinate for the given neighbor.
    public int getNeighborJ(int neighborIdx) {
        return mJ + NEIGHBORS_DJ[mI % 2][neighborIdx];

     * Computes X and Y coordinates for all of the cell's 6 corners, clockwise,
     * starting from the top left.
     * @param cornersX Array to fill in with X coordinates of the cell's corners
     * @param cornersX Array to fill in with Y coordinates of the cell's corners
    public void computeCorners(int[] cornersX, int[] cornersY) {
        for (int k = 0; k < NUM_NEIGHBORS; k++) {
            cornersX[k] = mX + CORNERS_DX[k];
            cornersY[k] = mY + CORNERS_DY[k];

     * Sets the cell's horizontal and vertical grid coordinates.
    public void setCellIndex(int i, int j) {
        mI = i;
        mJ = j;
        mX = i * SIDE;
        mY = HEIGHT * (2 * j + (i % 2)) / 2;
     * Sets the cell as corresponding to some point inside it (can be used for
     * e.g. mouse picking).
    public void setCellByPoint(int x, int y) {
        int ci = (int)Math.floor((float)x/(float)SIDE);
        int cx = x - SIDE*ci;

        int ty = y - (ci % 2) * HEIGHT / 2;
        int cj = (int)Math.floor((float)ty/(float)HEIGHT);
        int cy = ty - HEIGHT*cj;

        if (cx > Math.abs(RADIUS / 2 - RADIUS * cy / HEIGHT)) {
            setCellIndex(ci, cj);
        } else {
            setCellIndex(ci - 1, cj + (ci % 2) - ((cy < HEIGHT / 2) ? 1 : 0));

Testing the code

To test the code I've written a small Java applet.

It's a hexagonal version of the game called "Lights Out" (the idea of which I've borrowed from here).

One starts the game with all the "lights" on (all the hexagons are yellow), and the goal is to switch all of them off (so all the hexagons become gray).

Whenever user clicks on a hexagon, it toggles its light, together with all the neighbor hexagons.

package com.rush;

import java.applet.Applet;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;

import javax.swing.JFrame;
import javax.swing.JOptionPane;

 * Example applet which uses hexagonal grid. It's a hexagonal version of the
 * "lights out" puzzle game: http://en.wikipedia.org/wiki/Lights_Out_(game)
public class HexLightsOut extends Applet implements MouseListener {
    private static final long serialVersionUID = 1L;

    private static final int BOARD_WIDTH = 5;
    private static final int BOARD_HEIGHT = 4;

    private static final int L_ON = 1;
    private static final int L_OFF = 2;

    private static final int NUM_HEX_CORNERS = 6;
    private static final int CELL_RADIUS = 40;

    //  game board cells array
    private int[][] mCells = { {    0, L_ON, L_ON, L_ON,    0 }, 
                               { L_ON, L_ON, L_ON, L_ON, L_ON }, 
                               { L_ON, L_ON, L_ON, L_ON, L_ON },
                               {    0,    0, L_ON,    0,    0 } };

    private int[] mCornersX = new int[NUM_HEX_CORNERS];
    private int[] mCornersY = new int[NUM_HEX_CORNERS];

    private static HexGridCell mCellMetrics = new HexGridCell(CELL_RADIUS);

    public void init() {

    public void paint(Graphics g) {
        for (int j = 0; j < BOARD_HEIGHT; j++) {
            for (int i = 0; i < BOARD_WIDTH; i++) {
                mCellMetrics.setCellIndex(i, j);
                if (mCells[j][i] != 0) {
                    mCellMetrics.computeCorners(mCornersX, mCornersY);

                    g.setColor((mCells[j][i] == L_ON) ? Color.ORANGE : Color.GRAY);
                    g.fillPolygon(mCornersX, mCornersY, NUM_HEX_CORNERS);
                    g.drawPolygon(mCornersX, mCornersY, NUM_HEX_CORNERS);

    public void update(Graphics g) {

     * Returns true if the cell is inside the game board.
     * @param i cell's horizontal index
     * @param j cell's vertical index
    private boolean isInsideBoard(int i, int j) {
        return i >= 0 && i < BOARD_WIDTH && j >= 0 && j < BOARD_HEIGHT
                && mCells[j][i] != 0;

     * Toggles the cell's light ON<->OFF.
    private void toggleCell(int i, int j) {
        mCells[j][i] = (mCells[j][i] == L_ON) ? L_OFF : L_ON;

     * Returns true if all lights have been switched off.
    private boolean isWinCondition() {
        for (int j = 0; j < BOARD_HEIGHT; j++) {
            for (int i = 0; i < BOARD_WIDTH; i++) {
                if (mCells[j][i] == L_ON) {
                    return false;
        return true;

     * Resets the game to the initial position (all lights are on).
    private void resetGame() {
        for (int j = 0; j < BOARD_HEIGHT; j++) {
            for (int i = 0; i < BOARD_WIDTH; i++) {
                if (mCells[j][i] == L_OFF) {
                    mCells[j][i] = L_ON;

    public void mouseReleased(MouseEvent arg0) {
        mCellMetrics.setCellByPoint(arg0.getX(), arg0.getY());
        int clickI = mCellMetrics.getIndexI();
        int clickJ = mCellMetrics.getIndexJ();

        if (isInsideBoard(clickI, clickJ)) {
            // toggle the clicked cell together with the neighbors
            toggleCell(clickI, clickJ);
            for (int k = 0; k < 6; k++) {
                int nI = mCellMetrics.getNeighborI(k);
                int nJ = mCellMetrics.getNeighborJ(k);
                if (isInsideBoard(nI, nJ)) {
                    toggleCell(nI, nJ);

        if (isWinCondition()) {
            JOptionPane.showMessageDialog(new JFrame(), "Well done!");

    public void mouseClicked(MouseEvent arg0) {

    public void mouseEntered(MouseEvent arg0) {

    public void mouseExited(MouseEvent arg0) {

    public void mousePressed(MouseEvent arg0) {

The source is also available on github.

The applet in action can be seen here (all the usual java applet related disclaimers apply).

UPDATE: Ferris Thomas made an ActionScript 3 port of the code, kudos for that!

Additional thanks to Ruurd for spotting typos in the formulas.


BenBen said...

Saw this on Reddit, thanks for the explanation. You're right, it's simple in principle, but sometimes the details are easy to flub.

Unknown said...

I implemented a shift-right-first-row API in OpenSettlers (http://github.com/generateui/OpenSettlers). It does not use horrible arrays, but sane generic (lists).

I'd like to know if I can integrate your knowledge into the GPLv3 codebase.

Unknown said...

There are some notes on hexgrid math here

Artur Biesiadowski said...

I personally always found 3-component coordinate system for hexagonal grid most elegant. You can see some info at



Philihp Busby said...

I played around with hex grids in college. I found the 3-coordinate system to be helpful too, but realized that you can always derive the 3rd coordinate from the first two.

A plane is defined by two non-parallel lines. Essentially, a hex grid is no different from any plane, the two axes are at 60 degrees, rather than 90 (which is a "special" case where a lot of math becomes easier).

Ruslan Shestopalyuk said...


Sure, I'd be happy if you do!

Good luck with the project, it looks very interesting.

Ruslan Shestopalyuk said...


Thanks for the link, quite a nice gathering of knowledge there.

Ruslan Shestopalyuk said...


Thanks, I find the "hexagonal grid as an isometric projection of a cubic grid" approach to be really elegant (even though somewhat harder to wrap one's head around).

Reminds of the homogeneous coordinates idea... definitely is worth looking into.

Barry Kelly said...

Your DNS is misconfigured: http://www.dnsstuff.com/tools/traversal/?domain=blog.ruslans.com&type=A&token=11a0aba66da33b3d25d2b49601999019

OpenDNS is giving NXDOMAIN for blog.ruslans.com from several locations; you can check from http://www.opendns.com/support/cache/ .

I was only able to post this comment via a proxy.

Ruslan Shestopalyuk said...

Barry, that was indeed the case, name servers for ruslans.com were messed up.

Thanks for your help, really appreciate it.

Unknown said...

I personally found the weird coordinate system described here
to be useful when you are dealing with things like "what is the distance in hexes between hex A and hex B", and "given a line between hex A and hex B, what hexes does the line intersect."

Unknown said...
This comment has been removed by the author.
Unknown said...

Thank you for linking to my hexagonal LightsOut web page.

RMoelker said...

Great tutorial. Saved me a lot of headache!

Just some minor fault I found in your math variable names:

image: fromcell_1.png, should be "Yts = y - it%2 *H/2"
image: fromcell_3.png, should be "xt > R * abs(0.5 - yt / H)"

Ruslan Shestopalyuk said...


Thanks a bunch!
I've corrected the formulas.

alexander said...

great article.

the algorithm to find a hex from point seems to have problems with negative coords, but i can't figure out why.

any idea?

Ruslan Shestopalyuk said...

alexander, thanks for pointing that out!

A rather obvious problem lies in the sentence:

"Taking into account that for odd columns i%2 (remainder from division of i by 2) equals 1..."

...well, for negative i it does not equal 1, it equals -1 :)

It would be more correct to use |i%2| (abs) in this case.

I confess of having cut the corner and not paying much attention to the negative values in the first place.

But of course there is no reason for formulas not to be correct for negative values as well.

Thanks again.

Unknown said...

Thank you very much for your post. Your problem approach is so simple and so elegant, I was excited. Help me a lot.

Unknown said...

Begads there are some intelligent people out there in the interwebs.

Anonymous said...

How nice and informative post here. I will share this topic with my friends and i hope they will also like and share it more and more. Visit best-college-essay.com for best essays.

Unknown said...

Congratulations, Ruslan!
Your article was the clearest among my collection dealing with hexagonal grids.
Many thanks for it.
Ferenc Nagy franknagy.atw.hu

360DigiTMG said...

As always your articles do inspire me. Every single detail you have posted was great.
data scientist malaysia

360digiTMG Training said...

Very awesome!!! When I searched for this I found this website at the top of all blogs in search engines.

business analytics course

traininginstitute said...

I see some amazingly important and kept up to length of your strength searching for in your on the site
data scientist training in malaysia

training institute said...

I am impressed by the information that you have on this blog. It shows how well you understand this subject.
data science course

Service on Street said...

I’m very happy to uncover this page. I want to to thank you for ones time for this fantastic read!! I definitely enjoyed every part of it and i also have you bookmarked to check out new information in your site.
Best Refrigerator Repair Service in Hyderabad

traininginstitute said...

You completed certain reliable points there. I did a search on the subject and found nearly all persons will agree with your blog.
data science course in malaysia

data science said...

It is perfect chance to make a couple of game plans for the future and the opportunity has arrived to be sprightly. I've scrutinized this post and if I may I have the option to need to suggest you some interesting things or recommendations. Perhaps you could create next articles insinuating this article. I have to examine more things about it!

PMP Training in Malaysia said...

360DigiTMG, the top-rated organisation among the most prestigious industries around the world, is an educational destination for those looking to pursue their dreams around the globe. The company is changing careers of many people through constant improvement, 360DigiTMG provides an outstanding learning experience and distinguishes itself from the pack. 360DigiTMG is a prominent global presence by offering world-class training. Its main office is in India and subsidiaries across Malaysia, USA, East Asia, Australia, Uk, Netherlands, and the Middle East.