709 points by ayx on June 2, 2013 | hide | past | favorite | 69 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.
 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.
 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.
 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.
 upwardbound on June 2, 2013 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.
 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.
 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...
 mikeash on June 3, 2013 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.
 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 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/Minimaxhttp://en.wikipedia.org/wiki/Alpha-beta_pruninghttp://en.wikipedia.org/wiki/Negascout
 mpyne on June 3, 2013 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.
 mynameishere on June 3, 2013 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
 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).
 hobs on June 3, 2013 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.
 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.
 Strange moods are dangerous. I hope nobody's life was taken during the process...
 ygra on June 3, 2013 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 :POfcourse 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].
 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.
 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)?
 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.htmlIt 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].
 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!
 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_projectionAlso, 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.
 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.
 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.
 marshray on June 4, 2013 Carbon nanotubes are mostly hexagons. They certainly could make toruses, if they wanted to.
 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...
 e12e on June 3, 2013 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.
 lmm on June 3, 2013 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.

Search: