Comment by graue | Hacker News Reader

Comment by graue | Hacker News Reader

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

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.

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.

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

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

Reply on news.ycombinator.com