Project Hex: Part 2

 By Shamus Oct 20, 2010 92 comments

Maybe the name of the project has given this away, but this game is going to be played on a hex grid. Hex grids are elegant, beautiful, and better-looking than standard square grids. The only downside to using a hex based gameboard is that the computer and I are both rubbish at thinking in hexes.

See, computer memory is really just a long list of addresses. You can think of it like a long street with houses in a row. At the start is house #1, and they go one after another all the way down to house #2,147,483,648 at the far end of the street. This is the structure of the world you work in. You can organize that information (conceptually, in your head) however you like. To can imagine them as a table of values by (say) treating it like a new row every 25 addresses. If you need a grid of data that’s (say) 25×25, then the item in row 2, column 2 is at position #27. Some simple math will let you treat that infinite line of addresses like a grid of points, but in the end your program is still dealing with a long, long list.

If I have a grid of 8×8 points, I can use them to make a 7×7 grid of squares. If that sounds confusing, (and I don’t blame you) then please enjoy the following visual aid, which was crafted by a small team of professional artists over the course of nine days, working in a variety of mediums, from calligraphy pens to watercolor:

hex_squares.jpg

Yes, prints are available.

This is really easy. (Making a grid, not the artwork.) It’s how my terrain project made a grid with millions of squares:

terrain2.jpg

But how do you form this…

hex_grid1.jpg

…?

Uh. Hm.

This is a really important step. I’m trying to figure out how to organize a hex grid in computer memory. The entire game will be constructed atop this grid, so if I do a lousy job it will make things harder for me later. If I decide to change it later, it will be like changing the foundation of your house after the thing has been built and you’ve moved in.

I finally decide to take a regular grid and play connect-the-dots with it like this:

hex_grid2.jpg

I need to squash the grid vertically, making rows 33% shorter than they are wide. Then I make individual hexes 5 points tall, 3 points wide. This leaves a few unwanted points floating in the middle of the hex, which will go unused.

Actually, quite a few points will go unused. Over half. The upshot of this would be that I would waste a lot of memory storing data for points that I’m never going to use. It’s also going to be a bit strange making things move around a game board like this. I’ll have to work out a system for skipping points. This will also make it a bit odd to fill in the grid with data. If I load in some terrain I’ll have to map the grid positions into… uh…

No. No no no no. This is all wrong. This system could work, but it’s stupid and ungainly and there’s no reason to try and build a game on top of this mess. I need to think on this a bit more. And by “think” I mean “go play Civilization V”.

At some point in the game I start seeing the in-game hex grid differently.

hex_civ.jpg

Rather than all that nasty business with skipping points and squashing the grid, what if I just started with a normal, straight grid? And then shifted every other column of points downward by a half-unit? I just take this:

hex_grid3.jpg

And render it like this:

hex_grid4.jpg

As far as the computer is concerned, it’s a standard grid. But visually it’s… well, it’s a mangled grid. But if we connect the points right:

hex_grid5.jpg

Note that while this looks like a hex grid, it’s actually not shaped like one internally. I’m rendering every other column of points as if they were a half grid space down. If I draw the grid without doing that shifting:

hex_grid6.jpg

You see the world is really made of interlocking “house” shapes. This is what the game world looks like under the hood. When you move around the world, you’ll be moving around on this pattern of houses.

I realize that both of these techniques seem like oddly complex hacks. Maybe it’s not even clear why the second method is so much better than the first. I realize that any system to create a hex grid from a square grid of data is going to be a tricky one, but this second idea feels cleaner. Okay, the house thing is odd, but it feels like less of a hack than the first. Once I get the system in place, I’ll hopefully be able to ignore it. The point-skipping idea was the kind of thing that would come back to bite me again and again as the project wore on.

Well, we came all this way. Let’s feed the grid some elevation data and see how it looks:

hex_grid7.jpg

Pretty crappy!

Okay, the “elevation data” was just a couple of overlapping sine waves, but I like how this works so far.

2020202012There are now 92 comments. Almost a hundred!


  1. Scott says:

    I think it looks pretty good. I mean, it’s just elevation.

    EDIT: Also — about the empty points — isn’t it a good idea to have a point in the middle of each hex? I’m not a programmer, so I don’t really know what I’m talking about, but I would think it would be good to have a center point as a reference; if you were assigning some kind of value to the hex as a whole, you could use that point. (?)

    • Aldowyn says:

      Both methods have points in the middle of the hex, I’m pretty sure.

      • Geoff says:

        If you look at the “houses” picture, they all have one point contained inside the perimeter lines. When that column is shifted half a unit down (or the points on either side of it are) then that point will end up being in the middle of the hex.

        • kmc says:

          I kind of think that’s what he was saying–Shamus was saying that extra points are bad, and from a non-programming point-of-view, Scott was saying that it seemed like a good thing, which Shamus didn’t address.

          • Jabor says:

            Having one point in the middle of the hex is awesome, yes. But if you look at the squashed-rectangles picture, as well as the centrepoint, you’ve got a couple of extraneous interior points that wouldn’t be used for anything.

            • Viktor says:

              New thought(non-programmer, so this may be stupid), but why go with a point for each vertex at all? Locate each hex based on the midpoint, and only turn it into an actual hex grid in the graphics portion of the process.

  2. Mark says:

    I’m surprised you didn’t just go with triangles. It’s basically the same as your offset grid with each quad bisected along the shorter axis. The graphics pipeline is going to do that anyway, and it would give you a more consistent terrain shape.

    It still works in terms of rows and columns, too. Each even row has triangles pointing “south,” and each odd row has triangles pointing “north.”

    • Daemian lucifer says:

      Same here.Triangles are easy to group into hexes later,plus are much better to use when orientation comes into play.

    • wtrmute says:

      The point is connectivity. The hexagon is the largest regular polygon that can tile the plane on its own; however many sides the tiles have, the more directions you can move with constant distance between adjacent tiles.

      Allow me to explain: With a square grid, you can move to four adjacent tiles, North, South, East and West. If you want to move in a diagonal — say, Northeast — you need to move twice: once North, and once East. However, you’re not two units away from your starting point, but only 1.4142… units distant. This is why, for example, in D&D, diagonal movement costs 1.5 movement points: it’s a way to reduce the disparity between “movement expended” and “distance covered”.

      In the case of a hex grid, there are six directions one can move in with maximal efficiency: east, west, and 30° off the vertical. If you want to move on the vertical, you have to zigzag, which wastes a bit of movement, though not nearly as much as moving diagonally in a square grid: you spend two movement points and end up 1.73205… units distant.

      For a triangular grid, moving from a triangle to one which only touches vertices requires *three* moves to cover two units of distance, and only three directions where you can get full movement efficiency. That is the reason why wargamers (and, recently, Sid Meyer) seems to like hexes so much.

      • Will says:

        Hexes are also pretty.

      • Blanko2 says:

        i wouldnt be just using triangles, at least what i understood was that you would use the triangles to make a hexagon, rather than using squares.

        • Daemian lucifer says:

          Exactly.If you group 3 triangles,you get a hex.Plus,if you use facing,its much easier to have the hexes already torn apart.And you wont have those middle points of hexes empty.

          • wtrmute says:

            I myself need at least four triangles to make a hexagon. With three I can make, at best, a pentagon. Can you teach me how to split the hexagon into three triangles?

            • krellen says:

              A perfect hexagon, which is required to make a true Hex map, uses 6 triangles (equilateral, all with a vertex on a central point.)

              • wtrmute says:

                If the triangles are required to be equilateral, then yes. If not, an hexagon ABCDEF can be constructed from four triangles ABC, ACD, ADE, AEF (for example). In this case, ABC and AEF are isosceles and ACD and ADE are scalene (although right triangles). If there is a way to do it with three, like Daemian claimed, I sure would like to know, although I suspect he has simply misreported the number of triangles necessary.

            • Daemian lucifer says:

              My mistake.I meant to write 6 but something went twang in my brain at the moment of writing.And of course I was thinking of equilateral triangles,not any triangles and hexagons.

  3. Rob Conley says:

    The shift by half is known as the poor man’s hex grid in RPGs and gaming. GDW’ Atlas of the Imperium for the Traveller RPG used it. You can see the style here. http://www.travellermap.com/?x=-99.37&y=73&scale=32&options=2935

    Curious how come you just didn’t use the equivalent of number hex grid? A numbered hexgrid works like a rectangular hex grid all you have to remember is every other row (or column depending on orientation) is shift down by half. Or are you trying to go for a one to one between the hex and the pixels on the screen?

    The only gotcha is that you need make your rectangles the right proportion in order to keep the spacing across your hex columns (or row if oriented like your post)

    • Rilias says:

      Another upshot about the numbered hexgrid thing is that your AI will probably have to think about the world in this way anyways. So building the world the way you will later use it in seems like the intuitive way to do it.
      But you get a sloped shape by superimposing your hex-data on a matrix so you will probably lose some memory when your world is supposed to be a rectangle or Hex which is basicly the two forms you might want.

      • John Lopez says:

        I’m going to third this: the shift by half method is the way I have always represented in memory hex data. The disadvantage is that adjacency rules are different on even and odd rows, but once that is coded you can trace paths using A* just as easily as on a grid.

        (00)(01)(02)(03)
        –(10)(11)(12)(13)
        (20)(21)(22)(23)
        –(30)(31)(32)(33)

        Note that 11 (row, col) is adjacent to 01, 02, 10, 12, 22 and 22 or (-1,0)(-1,+1) (0,-1)(0,+1) (+1,0)(+1,+1). For 21 however we have (-1,-1)(-1,0) (0,-1)(0,+1) (+1,-1)(+1,0). The key difference is the offset for adjacent rows is either the 0,+1 or -1,0 depending on if you are looking at even or odd rows.

        Once you formalize that into an adjacency function you can flood fill and create search paths without thinking about it.

  4. Aldowyn says:

    I think I’m going to really enjoy this insight into the development process.. I kind of understand why the second way is better.. but not really.

    Really looking forward to seeing what you’re doing with this, Shamus!

  5. matt says:

    Shamus, I’m so happy to see these type of projects come back. They were always my favorite part of this blog. :)

    • larryboy114 says:

      Hear, Hear!

      Pixel City is what took me from occasionally checking this site to setting up an RSS that destroyed all of my productivity! Also, the procedural content discussions, like Fuel, are intriguing as well (can’t wait for that part of this project to come up)

    • RPharazon says:

      I freaking love these projects since they give me faith in the human race.

      I am an amateur programmer, mostly just to solve my own problems, make basic, but powerful, worksheet programs, render a few charts, and crunch large iterative processes. I once messed around with Project Euler with a few friends. I hit a wall after about 30 questions, and I did it using brute force methods, a powerful computer, and Python’s fun and useful large number capability.
      All my friends did it in C++. Since they had to work around a bunch of things, like C++’s digit limit, and they mostly used weak school 2004 computers, they had to be efficient.
      My solutions got the job done, but not elegantly or quickly. Their solutions got the job done in milliseconds.

      In Shamus, I see the same thing that my friends did. About 80% of Shamus’ solutions and work-arounds are so simple, elegant, and efficient, that I would never have thought of them. I like the big, complex things. Simplicity is not a thing I do easily. I lack the creative spark, basically. To see it in other people, in programmers and in people who work with modern technology especially, brings joy to my heart.

      I’ll stick to flying and throwing a plane around in the air. I can be confident about the future of technology if it is in the hands of programmers like Shamus.

      • froogger says:

        Hugs for that – I feel exactly the same way.

        Best thing about engineering in the digital realm is the lack of friction. Yes, it doesn’t feel like that when you’re wrestling a problem, but there are so many issues you don’t have to deal with.

        What you get is a short distance from idea to conception and I love it. Too bad I suck at it, but I still admire and respect those who work this.

        Thanks for sharing, keep us posted!

    • James says:

      Me too. My programming mana is mostly tied up with work, but it’s really nice to read these kind of blog posts and fantasize about finishing up some of my own pet projects.

  6. Henebry says:

    It looks to me like your terrain project works from a triangular grid. That’s what the picture looks like, anyway.

    And that made me think, why bother with a hex grid if you can easily construct a grid of triangles?

    Alternatively, I’m betting it’s easier to construct a hex grid out of a triangle grid than it is to make one out of a grid of squares.

    Edit: I guess Mark said this already, and said it better!

  7. Steev says:

    While the offset-square works nicely, you’ve already got the triangles. Why not just use them? Looking at the TerrainProject shot you’ve got there, you can definitely see some hexes formed out of the triangles; I can’t quite make out if they can tesselate properly though.

    EDIT: Beaten twice. Guess that’s what happens when I try to double check that it would work.

  8. omicron says:

    I messed with something like this at one point in the past, and did about the same thing you did.

    If you’re taking this a long ways, you should also consider pathfinding (a* on a hex grid is really no different from a* on a square grid; it’s just structured differently) and AIs (distance detection is one of the trickier aspects of hex-grids, as you can’t just use the pythagorean theorem with x- and y- differences and expect to get accurate results)

  9. krellen says:

    If it’s any consolation, the second method is actually a truer “hex grid” than the first, because those diagonals you had weren’t actually equal to the straight rows, so your hexes weren’t equilateral.

  10. Sydney says:

    Maybe this is because I’m a non-programmer, but the shift-every-other-line-sideways thing was my gut reaction when you said “But how do you form this…?”

    I’m not sure what that says about me.

    • Abnaxis says:

      I did the same thing, but I just blamed it on my old Material Science classes. The difference between a cubic and a hexagonal crystal lattice is a similar sort of half-shift like he’s doing here.

  11. anaphysik says:

    Yeah, this actually looks just fine.
    I think I would’ve personally found it easier to deal with a grid of rhombi than houses, but I’m a materials scientist (so I’d make something out of the hexagonal lattice’s unit cell), not a programmer, so maybe the second is better.

    • Felblood says:

      So, you would draw a line down the center of each house, connecting the peak to the point where the base of the house meets the peak of the house below? If you’re going to go that fat, why not divide each rhombus into three triangle, as was suggested above?

      I don’t know what a unit cell is, but it sounds like something it would be good to understand before working in a particular coordinate system. Is there some hidden benefit to that first halving that will simplify the work we have to later?

      • anaphysik says:

        [Basic materials lesson: a crystal is described by two parts, its lattice (a repeated arrangement of points), and a basis (what goes on those points). The unit cell that I mentioned is the basic portion of a crystal that can be repeated to create the entire crystal - it's what represents the symmetry and composition of a crystal (kind of like how an atom represents an element).]

        The houses seem bass-ackwards to me (so does Shamus’s ‘mangled’ grid). I would’ve started with a 2-d lattice by inputting the distances and angles that define that lattice.
        There are 5 ways to do this, by tesselating squares, rectangles, parallelograms, rhombuses, and “hexagonal” rhombuses. A pattern of lattice points represented by rhombuses can also be represented by rectangles with an extra lattice point in the center, and the ‘hexagonal’ rhombuses (120 degrees for the larger angle) form the same pattern as tessalated hexagons do (with an extra point in the center).
        The reason for using rhombuses rather than hexagons is simple: you can repeat along 2 axes and get the same overall pattern, rather than needing to introduce offsets and all that yadda-yadda.

        So, I would say: axis 1 repeat length is a, axis 2 repeat length is also a, angle between axes is pi/3. Then I would have some loops extend that pattern to whatever size I need, and voila I’ve got all my points. The base lattice looks like someone took a square lattice and stretched it along the diagonal, such that the squares became these ‘hexagonal’ rhombuses (note that this has the same points as Shamus’s rhombus pattern (assuming he got it from half-shifting an actually square pattern, which his first pattern bizarrely appears not to be), but I got it in a very different fashion). From there, the “hexagon with an extra point in the center” pattern fits right onto the base lattice.

        One benefit of this construction is that it’s extremely easy to make it bigger or smaller, or change shape – just extend the pattern more or less along one or both axes.

        Now, I’m no programmer (though it’s worth pointing out that this lattice creation is a super-simple procedural method), so this method might not be as good for making a hex grid for a game. My guess is that the difficulty comes in overlaying a hexagonal pattern on a lattice of rhombal points, and in not assigning connectors between the ‘center’ points and the non-center points (which look indistinguishable – after all, that’s the point of a lattice). I’m sure Shamus could explain better, since he actually knows programming pitfalls. (I’ll give this a bit more thought. There might be a way of exploiting lattice symmetry to make this easy, but I don’t think so.)

        • anaphysik says:

          Alright, here’s an idea: why do we even need the hexagonal segments to have lattice points at their ends? Shamus, got a reason?

          Because, if we don’t, then we simply make a lattice of points defined by the ‘hexagonal’ rhombus pattern, as I described above, and then as we define the basis (what we’ll draw) as a regular hexagon with its center on the lattice point.
          If the hexagon is the right size (center to the edge is half the distance between points), then all the hexagons touch, forming a what looks like a perfectly tessellated pattern. Under the hood, it’s just a bunch of points that data can be attached to, and the hexagon attached to each point is a visual representation of the point.

          Shamus, check this out!

          • Kacky Snorgle says:

            This. I’m sitting here trying to work out how the shifting-the-odd-columns-by-half system would operate, and I can sort of see it, but it isn’t pretty what with the need to treat the odd and even columns differently.

            In contrast, what you’re describing would effectively shift *every* column by half a unit more than the previous column was shifted. That gives us exactly the same collection of grid points, but now they’re indexed differently–the amount of shift is a simple multiple of the column number, and the math works out more elegantly.

            (In the notation of Ingvar’s post further down the page, the neighbors of [i,j] are just the standard four [i+1,j], [i-1,j], [i,j+1], and [i,j-1], plus also [i+1,j-1] and [i-1,j+1]. And that’s true no matter the parity of i and j. And I *think* this makes distance calculations easier too, since you only need to ask whether or not delta_i and delta_j have the same sign…but don’t quote me on that since I’m trying to do this all in my head….)

    • Abnaxis says:

      Heh, I just type a material science post above, and lo and behold, the next comment…

      Materials engineers for the win :p

  12. jack V says:

    I’m curious how this turns out. At one point I started writing a game on a hex grid, but didn’t go very far. I think I just gave them coordinates as:

    row 0: 0 1 2 3 4 5
    row 1:  0 1 2 3 4
    row 2: 0 1 2 3 4 5
    row 3:  0 1 2 3 4
    
    or
    
    row 0: 0 1 2 3 4 5
    row 1:  0 1 2 3 4
    row 2:   0 1 2 3 4
    row 3:    0 1 2 3

    (Where the numbers represent the coordinates used to store values in an array, and the layout represents the hexes (not to scale))

    And then worked out a reasonable shortest-path algorithm, which was fun to muse about but probably over-engineered :)

  13. wtrmute says:

    I see; you’re starting with the mapping from logical points on your grid to the points in OpenGL space. I think that can only end in tears, really.

    Start by generating the grid (thinking about rows as half-unit-translated is cool) and write six operators (E, NE, NW, W, SW, SE) which return the adjacent cell in that direction. Then generate your height field and paint the hexagons as a triangle fan with the cell’s height in the middle and the average of the three cells that meet in that vertex. Done.

    • LintMan says:

      I was going to say the same thing about starting from the game grid, rather than from the graphic space.

      You should be able to set up a mapping function from the game grid coords to the graphic coords, and once you have that, the two are independent of each other. As long as you can figure out a mapping function, you can draw the image however you want. And more importantly, you can make your game logic think and move purely in terms of the high level grid.

  14. Athan says:

    I assume the point of Shamus thinking in this way is so that the code can easily do “from this hex move X hexes in *that* direction”, combined with the same data being used for rendering.

    If you squint enough at what he has you’ll see that to move left or right you go two units along the ‘horizontal’ (jagged due to the shift) lines. If you want to move any of the other 4 possible directions it’s 1 left/right and 1 up/down. This is all moving between points that represent the middle of a hex.

    This does look to lend itself to that stated aim.

    • Athan says:

      Oh yes. To start with I was wondering if there was some easy way to do this with a pure hex grid, but treating it as a 3-dimensional space.

      I don’t think there is, but I’m no mathematician.

      If you start from the 0,0,0 hex and move one right to what we’ll call 1,0,0 or one left to -1,0,0, all is OK. But no move to the hex that’s in the 60degree direction, we’ll call that 0,1,0, and the one in the 240 degree direction is 0,-1,0. Then complete the definiton with one in the 300 degree direction being 0,0,1 and 120 degree direction being 0,0,-1.

      Now if we’ve moved to 1,0,0 and want to get “one in 300deg direction” we’ll end up at 0,1,0, so that was “x =- 1, y =+1, z = z”. Go the other way and this is reversed. Now from 0,1,0 move along the 60deg direction, we’ll end up at 0,2,0 so the rule here is “x = x, y += 1, z = z”, and its converse.

      Actually I think this could work. And in fact it’s looking a lot like what Shamus has anyway, isn’t it ?

      • Jabor says:

        The problem with this is that there’s no easy way to tell relative positions. A rectangular coordinate system would have you thinking that (100, 0, 0) is a long way away from (0, 100, -99), when on a hex grid with this mapping, they’re right next to each other.

        • Kacky Snorgle says:

          Or to restate the problem, the axes aren’t independent, so each point has lots of sets of coordinates: (100, 0, 0) is identical to (0, 100, -100).

          Fortunately, this problem is easy to solve by simply fixing z=0 and working with only the other two coordinates. Doing so produces the system that Anaphysik described a few posts up the page.

  15. SolkaTruesilver says:

    I am still hoping to be able to participate in this project, Shamus. *sigh*, if you could receive my emails.

  16. Narida says:

    Thinking about this, I think there are actually two problems. The first is: How do you have the Hex data in memory.
    The second is: How do you render a hexagonal grid.

    It seems you’ve kind of mixed those two problems which doesn’t really make it clearer…

    The answer to the first problem would be to use a 2d array and to render it, just figure out where the vertices have to go from your hex data and have an algorithm join the dots.

    Then again, you know what you’re trying to achieve better than I do, so it may be that I’m missing the point…

  17. Vegedus says:

    Uh, does this have anything to do with arrays? In my inexperienced programmer mind, it does, because, well, every time I’ve need a grid of squares I’ve used arrays, and I can see the difficulty of making hexes with them.

    • Ingvar M says:

      Sort of. You can (essentially) treat a NxM hex grid as an NxM array, only with a bit “funny” connectivity.

      If you’re at [i,j], your neighbours are [i-1,j] and [i+1,j] and either [i-1,j+-1] and [i,j+-1] or [i,j+.1] and [i+1,j+-1], depending on if j is odd or even. But that’s “only” helpful for keeping track of things internally and not necessarily helpful for the rendering.

      Um, looking at that, I don’t know if it makes any sense outside of my head.

      • Narida says:

        Hmm, yes it does. Now what was Shamus trying to do? Render it or keep track of it internally?

      • Shamus says:

        This is exactly the approach I’m using.

        • Zak McKracken says:

          So I was thinking … my intuitive approach would have been to use a numbered hex grid (just one node to store for each hex, which represents the center, hexes are in lines already).
          How do both approaches, the skewed quads and the numbered hex behave if you get some “noise” in the elevation data? The hexes can’t stay planar in either case, but what’s it gonna look like? And have you got an easy way of fixing which diagonal is going to be used for the two remaining quads in each hex? As I understand it, you can only render triangles in the end.

          So, the way I’d have done it would be one array as described above, so I only actually store data for the hex centers. The corners of the hexes would then be centers of triangles between three hex midpoints, and with those you can make each hex into six triangles. At the moment, though, I’m lacking the imagination to find out whether a noisy surface (or cliffs, ridges and such) would look good that way. Also, it might take longer to compute all those hex corners. Or not, couldn’t say.

          • Ingvar M says:

            Me, I’d probably calculate an artithmetic mean of the corner elevation, use that as “the hex’s elevation” and base movement costs and the like on it. Keep it nicely stepped and discrete in the “under the hood” representation, but still have it somewhat nicely drawable on the front end. But, then, I am very much more an “engine man” than a “render man” (e.g., my current hobby coding is implementing OSPF and BGP, because that’s kinda cool to play with; only down-side is that I also need to write virtual routers for it to run on).

      • Vegedus says:

        It makes sense to me. I think I’ll hit this thread up if I ever need to make a hex grid :D

  18. chabuhi says:

    Shamus – maybe you’ve come across this already, but if not you might find it useful as you progress.

    http://www.gamedev.net/reference/articles/article1800.asp

  19. Johan says:

    I never really cared for hexes since… I guess I just don’t like them. But it’s interesting to see how they can be made “under the hood”

  20. Jarenth says:

    I find this whole post a bit odd because when I look at your ‘Terrain Project’ picture, apparently made up of squares, all I see are triangles and (by extension) hexes.

    So not only is this an interesting look into your work process, but I’m learning new things as well. I think. So keep ‘em coming.

    • Sumanai says:

      I learned that it took Shamus to play Civ5 to come up with something that occurred to me almost ten years ago while playing Age of Wonders or HoMM3. I mean I was in my teens for crying out loud!

      Shamus, I’m very disappointed in you and your life decisions. >:(

      Though seriously, I’m surprised you never ran into Popcap games’ Bookworm.

  21. bit says:

    I’m not a programmer (well, aside from some perl and very basic visual C) but, can somebody explain why you’d need to make the hexes, well, polygons? In my mind, it seems like it would be simpler to go with the first method, and instead of assigning each hex as a space with values, you simply assign values to the central point, with the hexes being just a visual/game mechanic thing.

    • wtrmute says:

      Yes, several of us are mentioning this. Shamus has two problems conflated, but since he’s a graphics guy it makes sense that he’d think of the graphical construction of the grid as a first problem… Hopefully he’ll understand what we’re talking about — it’s been mentioned in the blog before how technical geeks usually have communication problems…

  22. Slothful says:

    Oh god this is terrifying.

    Hexagons are a terrible abomination I tell you, an abomination!

  23. vukodlak says:

    Hey cool, Belgrade has a marine coastline. Or a marine hex. :)

  24. Deoxy says:

    Shamus, I REALLY think you are either thinking too hard about this, or you are trying to solve more problems at once than just “how to store it in memory”.

    If all you are worried about is how to store it in memory, simply store it as a regular square grid. The only thing that changes that makes it a “hex” grid, in terms of storage in memory, is how to calculate “adjacent” cells. Really, that’s all. (Well, ok, that change does cause a cascading change to a few other things, like distance and pathfinding algorithms…)

  25. Ateius says:

    This is fascinating – including the conversation that follows each post. Thank you for sharing this process, Shamus.

  26. Duffy says:

    As a non-graphics programmer my logical approach would be to create a data structure that holds some hex’s ID, and the ‘adjacent’ hexes’ IDs, plus any terrain info or unit on hex info. (This should make AI pathfinding directly tied to the game logic the same thing) That in turn would be held in a two dimensional array which should mimic the rough graphical layout. The graphics layer would simply draw on ‘top’ of this setup, more or less “cheating” by just being a graphics overlay as opposed to the actual game logic. All data calculations or changes would be done on the array and just be reflected by the graphics engine.

    Not entirely sure, but I think others have been hinting at the same idea.

  27. Steve C says:

    My first thought to represent a hex grid was to google “open source hex grid”. Not to use the code but to see the “gotcha’s” coming down the pipe 200 hours into the project. That returned a lot of useful pages.

  28. Allen says:

    Just in case someone hasn’t mentioned it yet..

    Check out Star Fleet Battle’s hex maps – they use a coordinate system that’s pretty much your “shift the odd ones down” plan. (At least, my old map is numbered that way.)

  29. John says:

    Hi,

    I don’t have your experience. What I would have done is just made a grid of all the centre points of the hexes since that is all your game logic would probably care about (moving, collision detection etc). Then I would do the rest with graphics. ie overlay a hex grid. As long as it matches up with the grid no-one will know. Your units will move from centre point to centre point and it will look like they are moving from hex to hex.

    John.

  30. Bryan says:

    Ah, I see your house numbers are only 32 bits wide. Bit of a tragedy, that.

    (They’re also off by one, but I blame that on the human tendency to start counting at one. You use fewer bits if you start counting at zero, but silly humans don’t tend to think that way…)

    :-P

  31. Thom says:

    I’m not a programmer, but I do remember you telling something about stuff in computers being made out of triangles a while ago… And there’s your example, the blue TerrainProject screenshot. Haven’t you noticed that if you put 6 triangles together, you have one hexagon? And if you make clusters of 6, you can fill the entire map with hexes seamlessly?
    Maybe it’s just useless what I’m saying, but hey… even people that don’t know anything may have bright ideas ;)

  32. Wouter Lievens says:

    Just use a normal X-Y grid internally and use a different “neighbour” function. I’ve solved it that way in the past and it works fine.

  33. Random says:

    Somewhere on my pc, is an old c# project called… “HexEngine”, wich was supposed to eveolve in a tactical rpg on an hexagonal map.
    Anyway, if you don’t know it already (and for the benefit of other who might be interested), here are some good references for this kind of stuff: http://www-cs-students.stanford.edu/~amitp/gameprog.html#hex
    It’s quite helpful regarding how to use hexagonal grids, and adapt square-grid stuff to work with hex (e.g. A*)

  34. mark says:

    Shamus: Out of curiosity, As a pen and paper RPGer, do you prefer hex or square grids in your games?

    I’ve never tried a hex grid, and this project has gotten me curious now.

  35. Hey Shamus, the only sensible solution is what “bit” said in his comment post further above.

    Simply use single points, so that you get co-ords 0,0 and 0,1 and so on.
    For co-ords that start with 1,0 and 3,0 and so on they are actually offset by 0.5.
    This is easy to do as you can automate this easily by just checking if the x is a odd number.

    Movement from a square is simply left,right or diagonally (instead of up and down). so the same as a hex grid in that regard.

    Visually the squares actually “overlap”, imagine if the squares have their corners lobbed off visually. Hmm, looks just like hexes don’t they?
    And additionally make sure that player pieces that are moved, do not move all the way to the edge of the “squares”.
    Instead allow the pieces to move “freely” within a circle in the square,
    this will visually make it seem like they move “within” the hex (this could be traveling direction based, or simply random after each move),
    this also makes it easier visually if more than one piece is at the same co-ordinates.

    This the way I’d implement it, and if Civ5 isn’t doing it this way too then whomever did that part of the coding did a stupid thing. (no offense to whomever on the Civ5 team did that, but I’m assuming it’s done like how I describe here *laughs*)

  36. If I was making Civ5 though, I wouldn’t use a square or hex grid at all visually.

    In fact I’d simply use co-ords. (with sub-coords within regions)
    This way the “grid” or square or hex simply becomes a “action radius”,
    this means each unit would have a sensor range and a visual range and a action range (aka action radius), oh and I almost forgot travel range as well, all those are usually different values.

    The actual movement would be “free”. (not really, it’s still restricted to co-ords and whatever resolution the sub-coords may be.
    Although if using two 64bit floating point values you could represent a full planet “grid” easily (in a game at least), then again, depending on the game and the size of the “world” 32bit floating point may just be enough.

    So unit A moves to 6097.4581,6097.9581
    then unit B moves to 6097.1581,6097.3581
    Now if unit B’s distance is 1.0 or less (diameter or radius calculation perhaps, although subtracting x and y could also be used)
    and if it is then we’ll have a nice fight, if not wait another turn.
    This would even allow features like some units having longer attack range (which makes sense with infantry vs artillery)

    Another benefit is that a “grid” is not really needed at all any longer, thus no need for arrays or weird calculations etc.
    It does mean however that each unit will need two 32bit or two 64bit floating point variables to store their coords though.

    Maybe Civ6 will be similar to that?

    • Jarenth says:

      Actually, a lot of Turn-Based Strategy games made by Nippon Ichi Software (Phantom Brave and Makai Kingdom, for instance) use a similar distance-radius movement system. So it’s already out there.

  37. Hmmm… first attempt failed? good thing I ctrl+inserted:
    Okay, I figured out a simple way to do this ages ago. It struck me as so simple, I thought that surely someone else had figured it out already, but apparently not as I do not see it referenced in any of the articles other shave linked to. So here, published for the very first time, is the Mad Tinkerer’s Square To Hex Stupidly Simple Conversion System:

    You start with the “poor man’s hex grid”, but this is just for display purposes. Underneath is a plain old square grid, no fudging necessary. Each coordinate on the square grid matches perfectly with the hex grid, and then you simply need to tell the squares that two of their corners do not exist. Basically, you fool the squares into thinking they’re hexagons. That’s all there is to it.

    Example: Assuming you’re using a horizontally staggered vertical grid, each square tile then has the following exits:

    XX, +Y, XX
    -X, T, +X
    -X-Y, -Y, +X-Y

    XX= a direction to disallow or simply not use.
    T = the tile
    X,Y = 2 dimensions of the array

    Now on the hex map that actually translates to:

    +Y = North
    -X = Northwest
    +X = Northeast
    -X-Y = southwest
    +X-Y = southeast
    -Y = south

    +Y
    |
    -X, | +X
    \T/
    /|\
    -X-Y, | +X-Y
    |
    -Y

    I have tested this and it works. It seems weird at first to have three possible directions de-incrementing Y and only one direction incrementing Y, but it works. I really am surprised no one else thought of this yet, though it did take me a while to figure it out myself.

    The best part is that you can convert pretty much any regular grid-based pathfinding algorithm to this, as long as you make sure to tell the algorithm that it can’t move -X+Y or +X+Y.

    I should probably write this up as a proper article with better visual illustrations.

    • Kian says:

      I don’t know how thoroughly you tested this solution, but it strikes me as having a problem with adjacency. Say I start in one hex. I then move +x-y. To undo that movement and return to the original hex I started from, I would have to move -x+y. But in your implementation, that movement is illegal, whereas in a hex grid you should be able to go back and forth on any border.

  38. [...] Recently Shamus Young posted about a problem he had on his weblog: He wanted to make a game which used a hexagonal grid, but he didn’t know an elegant way to represent it in computer memory. [...]

  39. Rich says:

    Forgive this, but it seems that “mapping data into a hegaonal grid” is not what ur trying to do. it doesnt matter how u sort out the data. The placement of that data’s representation can be arrived at algebraically allowing the computer to work out the equation based onn the shape of the finished grid, having those representations in data files already telling the computer, based on the rules of the game what the desired output should be on the screen and having the computer calculate the precise position of where to place the appropriate representation automaticaaly. this means ur able to fucus more on the creative aspects of the game and less on data management.

    Good Luck!

  40. Anachronist says:

    I know I’m posting this a couple years after the fact, but I just came across it.

    I wanted to mention that one can map a square grid directly to a hex grid without using multiple squares or splitting them. Just think about the topology. Imagine each row of squares shifted 1/2 square, like a row of bricks on a wall. Now count the number of edge intersections around any particular square. Six!! Each square is actually a six-sided polygon where two pairs of sides happen to be in a line.

    Shifting things back to a non-offset square grid, movement between each hex-square is easy. You simply have the four usual directions, plus directions along one diagonal only, to reach the squares touching either corner.

  41. [...] order to implement a hexagon grid I went with the idea explained here. It shifts down odd rows of a normal grid to allow relatively easy rendering of hexagons without [...]

  42. [...] order to implement a hexagon grid I went with the idea explained here. It shifts down odd rows of a normal grid to allow relatively easy rendering of hexagons without [...]

3 Trackbacks

  1. [...] Recently Shamus Young posted about a problem he had on his weblog: He wanted to make a game which used a hexagonal grid, but he didn’t know an elegant way to represent it in computer memory. [...]

  2. [...] order to implement a hexagon grid I went with the idea explained here. It shifts down odd rows of a normal grid to allow relatively easy rendering of hexagons without [...]

  3. [...] order to implement a hexagon grid I went with the idea explained here. It shifts down odd rows of a normal grid to allow relatively easy rendering of hexagons without [...]

Leave a Reply

Comments are moderated and may not be posted immediately. Required fields are marked *

*
*

Thanks for joining the discussion. Be nice, don't post angry, and enjoy yourself. This is supposed to be fun.

You can enclose spoilers in <strike> tags like so:
<strike>Darth Vader is Luke's father!</strike>

You can make things italics like this:
Can you imagine having Darth Vader as your <i>father</i>?

You can make things bold like this:
I'm <b>very</b> glad Darth Vader isn't my father.

You can make links like this:
I'm reading about <a href="http://en.wikipedia.org/wiki/Darth_Vader">Darth Vader</a> on Wikipedia!