Sat 2009-08-15 ( pr )

Licenser and the folks of the Divided Space team want to use a hexagonal grid for their free massive multiplayer online role-play science-fiction fantasy browser game…thingy. Hex fields are so much cooler than squares or diamonds…remember Siedler 2? We want that. But it’s not easy…even the most basic thing, recognizing which hex field is currently under the cursor, proved to be hard to solve. So I worked hard to get it done, fast and reliable, because we can’t even begin to make an interface without such a function.

Licenser’s approach was absolutely funny, he actually checked the distance to the center coordinates of all hex fields to select the one nearest to the cursor – perfectly simple, but with quadratic complexity. Since the function has to be evaluated onmousemove, it needs to be FAST.

This is the function that I came up with, using school geometry knowledge and a great deal of trial-and-error:


PERFECT_HEXAGON = Math.sqrt(3) / 2;
row_height = HEXAGON_SIZE * Math.sqrt(3);
col_width = Math.round(row_height * PERFECT_HEXAGON);
w = Math.ceil(col_width * 2 / 3);
fac = (row_height / 2) / (col_width – w);

function getHexagonCoordinates(col, row) {
var hex_col = Math.floor(col / col_width); // column size factor
if (hex_col & 1) row -= Math.floor(row_height / 2); // odd row offset
var hex_row = Math.floor(row / row_height); // row size factor

// rectangle to hexagon magic var x = col % col_width; // x inside the rectangle, from left if (x < 0) x += col_width; var y = row % row_height; // y inside the rectangle, from top if (y < 0) y += row_height; if (x >= w) { x -= w; var yfac = y / fac; if (x > yfac) { hex_col += 1; if (hex_col & 1) hex_row -= 1; } yfac = (row_height – y) / fac; if (x >= yfac) { hex_col += 1; if ((hex_col & 1) == 0) hex_row += 1; } } return { col: hex_col, row: hex_row };


Don’t even ask me what fac and w stand for – it just works. Trust me. It’s a black box. I hate this code.

There’s an interactive demo, of course. I’m to lazy to include it in the post, so please visit this page:

Hex Grid with Cursor Recognition

Your page will be filled with a spacy hexagon grid; move the mouse over it or click to make the selection sticky (click again to make it follow the cursor again).

The nice thing is that it works. Coordinate conversion is now done in constant time, and fast. But the drawing of the hexagons still seems to be slow, about a few 100 per second; even the little pulsing effect (think lightness = sin(frameNumber)) I added starts the CPU fans. And I also found out that Firefox can’t use custom cursors on Mac OS X – darn!

Still, it shows that my drawing tools (DrawEngine, which takes care of drawing loops and FPS counting, and Shapes, a Canvas extension) work as a foundation for canvas engines; I am already using them for Chess and the Map Editor.

So, what next? I want to combine the new version with the old Hexagon Space Demo. It feels more and more like a real game interface to me :)

I have always dreamed of inventing and programming games. I really hope that we will be able to play with this game before this year is over.

Say something! / Sag was!

No markup, just plain monospace text. / Kein Markup, nur Normschrift-Klartext.