Hexagonal grids for games | Hacker News Reader

Hexagonal grids for games

redblobgames.com

709 pointsayx69 comments

This is an amazing resource. Bookmarked.

I recently implemented the board game Hex[1] using canvas. I didn't need most of this stuff... really only "neighbors", "hex to pixel" and "pixel to hex".

Hex uses a rhombus grid, a possibility surprisingly not mentioned in this article, which makes choosing a coordinate system easier. It's simply row and column, and finding a cell's neighbors is simple, if slightly counterintuitive. From my code:

    (let [possible-neighbors
            [[     col  (dec row)]   ; Upper left
             [(inc col) (dec row)]   ; Upper right
             [(dec col)      row ]   ; Left
             [(inc col)      row ]   ; Right
             [(dec col) (inc row)]   ; Lower left
             [     col  (inc row)]]] ; Lower right
      ...)

I found drawing the board unexpectedly tricky. In my first iteration I simply wrote a "draw hexagon" function that plugged in all the mathematical values, then called this function for each cell. The result looked terrible due to aliasing artifacts. Some lines were doubled and not all cells appeared the same size. In the end I precomputed integer values for the length of the vertical sides and the dy and dx for the diagonal sides, then used these integer values repeatedly to draw the board.

For converting pixel coordinates to hexes I used a different method[2]. If the pixel is inside the interior rectangle of a hex (the part of the hex with top and bottom removed), we know it's in that hex. Otherwise it's in the top or bottom of a hex, and I use the direct algebraic formula (y=mx+b style) for the hex tops' diagonal lines to find out if the point is above or below that line.

Maybe these approaches of mine would be helpful for someone whose needs are more basic, as they rely on less cleverness than the techniques in this article.

[1] http://toxicsli.me/hex/

[2] https://github.com/graue/cljs-hex/blob/master/src-cljs/locat...

I found drawing the board unexpectedly tricky.

Try again, but use an image for each hex rather than drawing its outline using lines. I'll wager you'll be pleased with the result.

As in a .png? Certainly simpler, but I wanted to be able to change the hex cells' radius with one line of code.

In fact, the way it is now, you can change one constant in the code to make the board size anything you like — 10×10, 13×13, 19×19, whatever, and it adjusts the hex cells' size to fit in the same page layout. This'll be exposed in the UI if I ever get back to the project.

Well, you'll want to think one level of abstraction higher than that. Imagine a camera. When you push a camera forward towards a wall, the wall stays the same size. It just fills more of your view.

You can code the equivalent of that pretty simply. So even if a png is 13x13, it might be drawn as 30x30 if the camera zooms in, or as 5x5 if the camera zooms out.

It's actually much simpler (and more visually consistent) to do it that way. It's probably more difficult to learn, but it's well worth the time spent learning it.

A 13×13 .png of line art stretched to 30×30 or 5×5 is gonna look pretty ugly[1]. Am I misinterpreting you?

[1] I tried it: http://toxicsli.me/file/hexes.png Leftmost is original, others resized.

Use vector image files

That just brings him back to the original problem though. His code was doing the equivalent of rendering a vector image of a hexagon already.

Well, two things to consider: (a) that particular example looks fine to me on a MacBook Pro in Chrome, and (b) you've discovered the motivation for mipmapping.

The Hex game is nice, but I don't see how the second player ever loses (swap rule).

Isn't this a solved game that, given optimal strategy, is either won or lost based on the where the first tile is placed?

No. Usually experienced players will begin in a cell like a2, b1 or b2, cells near to the top left corner — these are considered fairly neutral opening moves.

I wish I could link you to the Hex Wiki (hexwiki.org), where players much more advanced than I have written about Hex strategy. But it's been down with a message about database problems for months. Here's a link to their page on openings, via the Wayback Machine:

http://web.archive.org/web/20110806113426/http://www.hexwiki...

Edit: You may also wish to read https://en.wikipedia.org/wiki/Hex_%28board_game%29#Theory_an...

In theory, perfectly played Go is always won by either the first or second player, presumably depending on handicap. That doesn't stop Go from being interesting, because we're not even remotely close to knowing how to play it perfectly.

You need to add AI to your game.

Pull requests welcome!

I'm under the impression that making a non-sucky AI for nontrivial board sizes (say 10x10 and up) is an unsolved problem... much like no one had a Go AI that could beat even a skilled beginner until quite recently. And I couldn't find an example of any Hex-playing AI, even a crap one, that was open source.

I think it's okay if it's a poor AI, but it should be enough to play the game through. When you're sitting alone at your computer, there's nothing to do past the first move.

Got it. Yup, right now the site is only interesting if you have someone sitting next to you to share the computer with. The next step would be to add a server-side backend and allow playing online, if I end up revisiting this project.

FYI, if you and the other commenters just want to play Hex, there are existing sites you can play it on, like http://www.iggamecenter.com

I once programmed a pretty bad Othello/Reversi game for a friend of mine.

Given that it was my first AI the difficulty levels were called (in order of increasing difficulty): "Mr. Stupid" (chose random valid moves), and "Very Easy" (stupidly simplistic min-max algorithm over the next 2-3 possible moves).

You're right that the AI will be easy to beat, but it does at least give you something to do.

I imagine the basic chess algorithms adapt nicely for Hex. A min-max with alpha-beta prunning and, if needed, nega-scout. The trick is designing a good heuristic for game board state evaluation (non-final board states, of course). For Hex, this should be fairly trivial: How many pieces needed to win, how vulnerable am I to being blocked.

References:

http://en.wikipedia.org/wiki/Minimax

http://en.wikipedia.org/wiki/Alpha-beta_pruning

http://en.wikipedia.org/wiki/Negascout

If you ignore the fact that the vertical and horizontal aren't scaled the same (which can be part of the last step in the rendering code) then you can define a hexagon as six lines in [x y] space, as defined by their endpoints:

    [[0 0]  [0 2]]
    [[0 0]  [1 -1]]
    [[0 2]  [1 3]]
    [[1 -1] [2 0]]
    [[1 3]  [2 2]]
    [[2 0]  [2 2]]

These can be lexicographically ordered, meaning that if you construct a set of lines transformed by [(min p1 p2) (max p1 p2)] rather than a list of [p1 p2], you'll never have doubled lines -- the integer comparisons are exact, and each line has a canonical representation. Moving along the "horizontal" above is translation by [2 0] while moving along the diagonal is translation by [1 3], so it really is integers all the way through.

Since these translations [2 0] and [1 3] are the same distance in the real grid, our final scaling for the actual points is [x y] -> [x y/sqrt(3)]. As you note, rounding sqrt(3) inconsistently may create problems where not all hexes appear the same size, but we can fix that by using a rational approximation to 1/sqrt(3). Here are the first few best-rational-approximations to 1/sqrt(3) as determined by its continued fraction:

    0, 1, 1/2, 3/5, 4/7, 11/19, 15/26, 41/71, 56/97, 153/265, 209/362

So if you have hexes which must be around 50 px wide, we can arbitrarily choose 52 px and use the transform:

    [x y] -> [26*x, 15*y]

And then we get integer-pixel-perfection, by stating by fiat that our hexes are not perfect but just good enough. Since we chose a great approximation the error is actually only 0.74% so people presumably won't really notice.

When I drew a hex map in a vector fashion (many years ago) I used pointy-side-up hexes, and drew the horizontal zig-zag lines left-to-right across the screen, and then went back and filled in the vertical lines. This ensured I had consistent anti-alias effects on the diagonals, and wasn't overdrawing any lines. This meant I had to precompute the vertices, and order them by y-axis then x-axis before entering the drawing loops.

One use case for a hex grid is for a persistent MMO. Dividing the world up into a hex grid allows you to load-balance the world across different servers. This is more advantageous than a square grid because square grids share a corner with 3 other squares, whereas hex grids share only 2. That means it's less costly to hand off a player to different servers as they're running across the world.

Can you recommend any resources with more discussion about game server sharding? I worked at a defunct MMO game company and crossing shard tiles was an endless source of bugs for asset loading and server- side combat simulations.

Interesting, I have been thinking about that as well.

The idea of dividing the space in chunks is obvious but it works best if the players/units are spread uniformly across the map. Otherwise you'd want to perhaps do a K-means clustering and create clusters to handle at-most-N players/units, so for example if a busy section like the market has a density of 100/players per grid while a remote area only has 1/players per grid unit, you might assign a full server (dynamically, somehow to that one market are, while in a remote are the hundreds of grid units would be handled by a server).

I could be wrong, but the current gameplay of Planetside 2 suggests they are doing exactly that.

Your absolutly right, 5-6 months ago there an exploit involving the sunderer which crashed the hex it was in.

Observing from the outside the hex was very surreal, any entity that crossed the boundry simply stops dead. Not my video but shows what happens on the client when the handover of entity control fails! http://www.youtube.com/watch?v=bJGrFSQn3ZA

Oh my word. I'm going to be spending a good while disecting the construction of this page.

It's interactive and clear.

This is an informational web page. All craftsmenship is of the highest quality. It is adorned with illustrations of HTML Canvas masterfully made interactive by Amit Patel. There is an illustration of a hexagon and a developer with javascript. The developer is making a plaintive gesture. The javascript is laughing.

Strange moods are dangerous. I hope nobody's life was taken during the process...

I agree, really the first thing I noticed is how well the content was organized and presented.

Many times, the subject matter is interesting, but no attention is given to its presentation, making it hard to understand and read.

The article is math/code heavy, and still very readable and engaging.

Fantastic work.

Every illustration I looked at was SVG, not Canvas; even the interactive ones.

ahhh damn. Canvas worked so much better for that joke.

This stuff is pretty hard to get right when doing it all by heart. Last year I tried to make a multiplayer fighter on a hexagonal grid using websockets for a Ludum Dare, but I wasted the first day on making moving around on the hexagonal grid work, and the second on making the multiplayer code work, so at the end of the 48 hours the game was working technically, but I had no art whatsoever, and it wasn't fun at all :P

Ofcourse if I had taken the time to look for resources on building hexagonal game I would have found a lot of things like this article (though probably not as concisely summarised as in this one), but for some reason it didn't occur to me that it could actually be hard, since it seems like it's just some simple trigonometry.

Others said it was a fools errand to make a multiplayer game for a Ludum Dare (48 hour game compo), but actually if I hadn't been so stubborn with the hexagons I think I would have had enough time to build a pretty cool game.

There is a nice Haskell package called grid[1] that supports hexagonal grids, among other things. If you want to play around with some of these ideas, you might just have the perfect excuse to learn Haskell now!

More amusingly, the package also supports grids over things that aren't plains, so you can even have octoganal tiles![2] Also, perhaps counter to expectation (:(), it's well-documented, including an illustrated wiki[3].

[1]: http://hackage.haskell.org/package/grid

[2]: https://groups.google.com/forum/?fromgroups#!topic/haskell-c...

[3]: https://github.com/mhwombat/grid/wiki

This page brings back memories: Back in high school, I spent a few slow weeks in the back row of Physics class planning and working out some of the math behind a Military Madness/Nectaris clone for the TI-84+. I wasn't as clever as the people mentioned in the article, so I came up with a bog-standard "offset coordinates" system, with the flat-topped hexes and a rectangular map stolen from Military Madness.

Unfortunately, I never got around to programming it, because I realized early on that it would be really hard to fit a legible interface onto a 96x64 monochrome display. You either use small hexes with almost no room for actual graphics, or large hexes that fill up too much of the screen to give an effective view of the battlefield. Not to mention, lacking color or even shading would make it really hard to differentiate terrain, show which hex was selected, etc.

What I wasn't aware of at the time was that a lot of other strategy games from the 80s and early 90s (including the Game Boy port of Nectaris, which had to work around the limitations of a 160x144 4-shades-of-pea-soup greenscale display) used hex grids for gameplay, but displayed them as grids of staggered squares or tall rectangles. This made the graphics code (especially on tile based systems) much simpler, and gave artists a lot more room to fit legible graphics into, at a cost to the amount of hexes you could pack onto a screen. Examples:

http://youtu.be/iWra6nvKvok?t=1m13s

http://youtu.be/sTV06jd9j3A?t=7m21s

You could fit about 40 full 12x12 tiles onto the 83's display, and that just might be enough space for some primitive programmer art tanks and soldiers. Or, maybe plain ASCII would have been even more legible. The 83's built-in 6x8 font would have allowed me to fit about 120 full tiles on screen, more than enough to get a decent view of the battlefield. Damn, if had known about those games at the time, I might have actually stuck with the project... or at least, long enough to get stuck on figuring out how to implement a decent AI...

But enough of my rambling. This is an excellent resource, of the interesting and useful but very accessible kind the world needs more of desperately. It'd be interesting to read the author's thoughts on these "rectangular hex grid" systems; obviously, none of the internal data structures or algorithms change, but it does seem to be a bit simpler (under an offset coordinates system, at least) to convert between grid and pixel coordinates, to calculate how many tiles can be fit on screen, etc.

I made a hexagonal maze once: http://www.dllu.net/hexmaze/

Neat. I like how when you move the cursor over a cell, a path to that cell lights up.

It might be nice if there were a defined exit you could go to and win the maze.

I'm the author of Hexdefense (a tower defense game with a hex board), and I think this page would have saved me days. I'd love to see someone collect the logic and algorithms on this page into a portable library. Thanks for creating such a great resource!

+1 here! I started a canvas library[0][1] to draw hex grids and boxes, this would have been immensely useful! Maybe I can integrate it sometime in the future.

[0] example: http://hengles.net/piksel/ [1] https://github.com/rhengles/piksel/

Similarly, I reverse engineered a hex-tile Flash game to build my own Android client for it, and I had to learn so many things that he just presents here plain as day. The co-ordinate system alone took me a few hours to decipher.

The visualizations and explanations are fantastic. The mouseover highlighting of code as you mouse over the hexes in the 'Neighbors' section remind me of Bret Victor's work[1]

Also, I was amused to see that the author used a language called "Haxe"[2] which can generate (compiles into) javascript, flash, C++, java, C# etc. I guess it's good for making web games where you have a flash fallback (or vice versa)?

[1] http://worrydream.com/

[2] http://haxe.org/

Don't forget to trawl through the rest of Amit's stuff. His articles are responsible for who knows how many game developers learning interesting algorithms and howtos.

I remember reading an interesting article which said that hex-grids were overrated, since each hex was adjacent to only 6 spaces, whereas square-grids have 8 (including diagonals).

I just tried to dig up the article, but failed. It was a pdf, and it was his investigation into attempting to create the most balanced turn-based strategy game he could. I remember the first-player would move once, and then the second play twice to offset the first-play advantage. And the board wrapped around top-to-bottom and left-to-right. Shame I can't remember the name of it!

EDIT: Found it: http://www.symmetryperfect.com/shots/texts/descript.pdf

Sorry but this is pretty naive. The link you proposed is for a Chess variant. Now, in an abstract game like Chess, I may agree that using a square grid (and allowing diagonal moves) may be ok. In a wargame, though, or anything trying to "simulate" reality (e.g. a role playing game) using a square grid with diagonal moves will result in the "interesting" phenomena where moving your tank towards North-West would boost its speed by more than 40% (square root of 2=1.414...). And this would be even worse in case of favorable terrain like roads or plains. The reason why hexagons are favored is because they can perfectly cover a plane and at the same time you move a constant distance no matter which side you are exiting.

So you should at least qualify your "overrated" statement by saying "for abstract games where speed/range of units is not considered an important feature".

I didn't make the statement, the article did, and I wasn't quite sure of the details. I just thought it was interesting. You're right, of course re: moving distance on a square-grid.

Re-reading the article, I'm not sure why he was so concerned about finding tessellating shapes for the playing surface. Being an abstract game, and with the goal of exploring new gameplay concepts, surely he would consider using nodes and paths instead? That would be able to represent many more configurations.

Just in case someone is looking for a neat way to experiment with game Grids, the MOAI framework has some pretty good support for grids, in general, and works very well at giving you everything you need to set up a game and get a grid working, fairly smoothly:

http://getmoai.com/

(And, on a side-note, MOAI is going to get an HTML5 host pretty soon, meaning you can deploy to HTML5, iOS, Android, Linux, Windows, OSX .. Chrome NaCl .. and so on!)

Your page disables zooming on iPads (and other devices). Why? There is no good reason for doing that and it prevents some people from reading.

Great use of hexagonal gameplay ==> weewar.com

Being a lover of hex grids for strategy games and just about to set out to learn canvas along with Parenscript in order to create games, which will probably eventually have me rolling out my own naive implementation of half the world of game engines across genres, thanks for this, it has come at just the right time.

Awesome. My favorite video game of all time is Military Madness (Nectaris). The hex map was the best part. That and the music and level names.

I've implemented the FOV algorithm suggested on this article without ray casting in Javascript: https://s3.amazonaws.com/jbochi/layout.html

It was an experiment for a game that I was working on, but I never finished it: https://github.com/jbochi/duelo

Reminds me of hexagonal telescope mirror design. Check out TMT [1] and some images [2].

[1] http://www.tmt.org/sites/default/files/SPIE-Segmentation-Pap...

[2] http://lot.astro.utoronto.ca/design/tel.html

Articles like this remind me of what a small understanding I have of most everything.

Take the cube coordinates graphic, switch to hexagons, and you wind up with: Q*bert!

Interesting, was just thinking about this the other day when somebody linked to a coding challenge for Max Levchin's new company: https://affirm.com/jobs

This is a fantastic resource, a future side project I have been kicking around is for an online game that would use hex movement. This is a great place to start for laying out the logic, thanks for sharing!

We tackled a lot of these problems when building an app for Wrangler: http://appstore.com/wranglermileage

This might me my most favorite submission of all time so far.

Great article! Thanks for sharing!

Civilization 5 uses hexagons

Bookmarked, damn useful!

We tried to figure out how to cut a planet into hexes, turns out you can't (no surprise). Footballs use pentagons.

Well, I guess you can just make equal area square map and cut that. http://en.wikipedia.org/wiki/Gall%E2%80%93Peters_projection

Also, it's curious nobody mentioned Battle of Wesnoth. Battle of Wesnoth (together with Fantasy General and Battle Isle) is a shining example of hex-based strategic wargame.

Couldn't you map hexagons onto a Icosahedron, leaving some hexagons "flat" and some with a "rise" towards the top (by subdividing each triangle into one "centered" hexagon, and three triangles of one-third (well, one ninth, I guess) size, forming parts of other hexagons ?

           ,
          / \
         /___\
        /     \  the dots (.,') mark centers of "new"
       /   .   \  hexagons, each of the ,' would be
      /\       /\  "peaks", the one centered on "." would
     /__\_____/__\  be "flat".
    '             '

You'd probably need to subdivide the hexagons further, and decide what those "peaks" should "mean" -- or ignore them... Not sure if that would be easier than using pentagons, though...

Another way too look at it, is to say the hexes would be distorted wrt. area -- Not sure if that would matter though...

Replying to myself: all those sides would be of equal length, defying Eculid -- or rather I'm missing the fact that five triangles meet in the original icosahedron. So those "corners" would be pentagons, not hexagons.

Indeed that is one way to derive the same "football projection".

I can't say I understand what you mean, but hexagons should be more-or-less equal in size and possible for players to understand.

Yes, but as has been mentioned by others, that is impossible. So either one can use pentagons and hexagons (as I inadvertently did above ;-) or just pentagons.

My goal was trying to get a hex grid, with roughly "ignorable" distortion. I think the most straight forward way would be to use four "pseudo" (irregular) hexagons, and wrap them into a cube (ie: four "hexagons" made from a square and two triangles with 45 and 90 degree angels). You would then have a "round" map that could be subdivided. It would be far from perfect, but very straightforward -- and if mapped onto a planet "north-south" (aka pointy-side up) -- I think it would yield a similar distortion to what we are used to from various map projections:

        /\   /\   /\   /\  <- distorted sides
       /__\ /__\ /__\ /__\        ________       _______
      |  A |  B |  C |  D |      /       /\     |\  c  /|
      | __ | __ | __ | __ |     /   N   /bb\    |d \ /  |
       \  / \  / \  / \  /     /_______/bbbb\   |  /'\b |
        \/   \/   \/   \/      \aaaaaaa\bbbb/   |/__a__\|
                                \aaaaaaa\b /    top down view
                                 \_______\/    ("North pole")

When wrapped up into a cube, the south and north poles would lie at the intersection of the four hexagons. Unless I'm tricking myself, this has the interesting property that the distance from A to B and D is 1, while from A to C is 2 -- whichever way you "circumnavigate".

Being hexagons, they could be further subdivided into hexagons (as for most purposes this grid would be too coarse).

I'm not convinced it would be very useful as a "proper" map projection -- but might work for a game.

With triangles alone you could produce a Dymaxion map.

Yep, but not ones that would (directly) map "back" to hexagons.

One of the things that went through my mind as I read the article, was that triangles might make for useful maps as well.

For anyone wondering why you cannot tile a sphere with hexes: this is a matter of Euler characteristic.

Suppose that there is a tiling of sphere with N hexes. Each hex has 6 edges, but every edge is shared by two hexes, so there are 6N/2 = 3N edges. Similarly, there are 6N/3 = 2N vertices.Thus, the Euler characteristic would be 2N - 3N + N = 0. Now, the sphere has Euler characteristic 2, so we get a contradiction.

Incidentally, a torus has Euler characteristic 0, and indeed it turns out that you can tile torus with hexes.

Carbon nanotubes are mostly hexagons. They certainly could make toruses, if they wanted to.

There's no need to assume exactly 3 hexagons meet at each vertex: if you only assume at least 3 hexagons meet at each vertex, then 6N >=3V, and we get that the Euler characteristic is <=0, which is still a contradiction. Of course if you allow vertices with only two hexagons meeting at them you can make a sphere: for example, take two hexagons and glue them around the edges, then stuff the middle to get a hexagonal cushion.

Reply on news.ycombinator.com