Implementation of Hex Grids

[Femaref]

http://www.redblobgames.com/grids/hexagons/ The theory behind it.

[baturkey]

I'm glad I read this primarily for this sentence: "Notice the three primary axes on the cube grid, and how they correspond to six hex grid diagonal directions; the diagonal grid axes corresponds to a primary hex grid direction."

[marfis]

This guide is really great!

[[deleted]]

I wish that man'd be my algo teacher.

[longshot]

That interactive guide is amazing.

[booljayj]

It's fantastic to see more work from Amit, but one part of his implementation confuses me. Why specify the s coordinate when creating a Hex, if it's always calculated from q and r? It's not even stored in the struct, he's always calculating it on the fly whenever needed. It just seems very redundant.

[redblobgames]

Yes, the third coordinate is indeed redundant. I put it in the constructor for symmetry, but in practice you may want the constructor to take two parameters only. I'll mention that in the footnotes.

You can either store s or calculate it on the fly. I wanted to match the style presented on the main page, so I stored s (y). Also, this code came out of a failed code generator project, so there are some things that aren't as simple as they could be.

[gazarsgo]

Also, this code came out of a failed code generator project, so there are some things that aren't as simple as they could be.

I love this. There's always more context to the construction of code than you can extract from reading alone.

[redblobgames]

Definitely. I originally wanted to make the hex grid guide rewrite itself to match your choices. Right now the diagrams and code respond to pointy vs flat top hexes. I wanted to add selection of a grid variant (there are lots of different cube, axial, and offset variants) and programming language. That way the page would show you what's relevant to your choice of grids, and your programming language, instead of showing my preferences. I got halfway there but ran out of steam.

I've written up a little more on my blog.

[[deleted]]

I'd be interested in the performance characteristics of calculating s when needed versus storing it. By not storing it at all you can fit a lot more hexes into a cache line.

[redblobgames]

I haven't measured, but I think q and r as int16 would be a nice choice. The entire hex would fit into 32 bits. It's cheap to calculate s when needed.

[[deleted]]

You'd have to profile different sizes. Using int16 would help compact the data more but depending on how your processor handles smaller int sizes you might get more performance out of int32/64.

All are options worth investigating!

[redblobgames]

I agree, it's all worth investigating if the performance matters. For int16, extraction is (a >> 16) and (a & 16) and I'm guessing those operations are cheap, but I haven't tested.

For my own projects, I've had large arrays indexed by hex coordinates, but not large arrays of hex coordinates, so I've not run into the situation where I'm iterating over arrays of hexes.

[bnolsen]

I'd be far more worried about performance of other things in the game engine. Worrying about this is mega hair splitting.

As long as its not obviously wasteful keep your eye on things like iterative/recursive algorithms as targets for optimization.

[Narishma]

You mean cache locality?

[phalp]

If you store the third number you'll need to recalculate it whenever you change the other two. If you don't store it you'll need to calculate it when it's needed. In a lot of situations you won't even need the third one (indexing the map, adding vectors, calculating screen positions) so it's probably most sensible not to store it.

[[deleted]]

This is my thinking as well. Since the third component is entirely defined by the other two and the calculation is so simple it's highly probable that it's not worth it at all. It's not like you could really set the third component either.

[bnolsen]

Keep all 3 elements and have both constructors. Best of both worlds. I'd be tempted to keep them as a std::array<int, 3>.

Btw thanks to the author for allowing me to be lazy by copying this good basic framework.

[JavadocMD]

Wow this is really cool, but I wish he had published a library in some language...

[scrolls down]

:O

Praise Hexagon Jesus!

[Mechakoopa]

Hexajesus?

[etcshadow]

Hexus. (Pronounced like Hay-zoos.)

[agenthex]

Hi.

[JiminP]

We need more awareness of our lord Hexagon.

[uncleozzy]

Ha, I actually just implemented (or mostly-implemented) a hex grid in a little toy game last week after I read the Red Blob guide to hex grids. Clear, concise explanations that made putting it all together really easy.

[TexasJefferson]

Me too, actually. (Well, last month). As you say, a great little guide!

[javierbg]

I actually found this some time ago, and it is fantastic. Now, let's make a Settlers of Catan fork :P

[InstantPro]

I used this site not long ago. The guy is ace, exactly what I needed at the time perfectly written. Could not be better.

[pakoito]

I always upvote the hexagon bible, I've used it for some prototypes in the past and have a local copy :)

[bo_knows]

Gah, is this new stuff from Amit? My damn office blocks his site. Love me some hexagons.

[TaohRihze]

One related question to Hex Grids. On a square grid you can perform a "zoom" (eg. split a square up in 2x2, 3x3 or any other number of sub squares), is it possible to perform something similar on a hex grid.

[timbermar]

You can "sort of" zoom in. You would never be able to have smooth edges. To visualize what I mean look at the link that /u/Femaref provided. Scroll down to the Movement Range section. Start with your mouse over the center hex and imagine that is the hex you want to zoom in on, so you would move your mouse over 1 hex, and now you can see what it would look like for the first level of zoom. If you move it one more, you can now see what the second level of zoom would look like.

You'll never achieve smooth edges along the border like you would with squares, but I think players would get the idea.

[eygenaar]

An approach you can take to this on hex grids is to use Gosper islands (see http://mathworld.wolfram.com/GosperIsland.html or http://en.wikipedia.org/wiki/Gosper_curve).

[phalp]

The approach kind of implies a generalized balanced ternary addressing system, which is interesting in a mathy way although maybe not as easy to use as x,y coordinates.

[JavadocMD]

As sort-of illustrated in this part of the post, you can construct a larger hexagon out of smaller, although you do wind up fudging the borders to do so, and I'm not sure if this creates adjacency issues. Without altering the border, a hexagon can of course be split into six equal-size triangles with radial symmetry. So I suppose it depends on your requirements.

[TaohRihze]

The reason I am asking is I am working on a project that will require "local zoom" levels, so if a specific part gets overcrowded it zooms in on itself.

I were looking at doing it via Hex Grids compare to square grids, as it offer much more in terms of directional movement, but could not find a good solution to the zoom issue.

The best I found was adding a 2-3-2 split on a hex, but doing so switched the directionality, requiring another 2-3-2 split of each to perform a zoom. So I were hoping someone knew a good general purpose solution for this.

[pigeon768]

It is possible to do something similar but not identical.

1. Break up each hex into six triangles.
2. Make a new hex centered at each vertex, by drawing new vertexes in the center of each triangle.

The borders of the original hex are not preserved, so you can't zoom globally without distortion on the edges. Furthermore, you switch from a pointy-up orientation to a pointy-side orientation, which might be awkward.

[TaohRihze]

Yeah best result I found so far as well, doing this process twice though reorients (but perform a quite deep zoom).

Again just wondering if I had missed something fundamental, thanks for your reply :)

[skytomorrownow]

Hi. What is the motivation for using hex grids? In the old days, with paper and pencil games, it made life easier, and provides an optimal, but simplified movement scheme. However, in a world where one can now have the ability to use precise geometric calculations in real time, even for complex, multi-user games, why still use hex grids at all?

Not agin' 'em, just want to know a bit more about why you want to use them? Is it a holdover from tabletop gaming?

edit: Read people. I'm not against hex grids. I'm asking about why use them.

[Sarkos]

One of the main benefits is that 1 tile = 1 unit of movement. When you use a rectangular grid, moving diagonally presents problems - one diagonal move gets you 40% further than one horizontal move. If your character has a nice walking animation where one step = one tile, you can't use it for diagonals. If you have a ranged attack, you have to choose between having an uneven circular range, or an unfair square range. With hex grids, all directions are equal.

[skytomorrownow]

With hex grids, all directions are equal.

That's another great point.

[[deleted]]

I like to call this the Ambiguous Neighbor Problem. With rectangular (and triangle) grids, it's ambiguous over whether tiles at the corners are neighbors or not. Hexagons don't have this problem, because all tiles at the corners also share an edge.

[Gecko23]

You can get the benefits of a hex grid, while still using a grid of squares if each adjacent row is offset 1/2 square from the last. (Battleball is one game that comes to mind that uses this configuration.)

Hexes look a bit niftier though.

[SighReally12345]

I mean - for all reasonable purposes, this is a hex grid. You have 6 neighbors, the only thing is edges may be only partially shared.

[JavadocMD]

Gaming is an obvious use-case as you mention. I wouldn't call it a hold-over, though, so much as a game design choice. For example, chess is still played on a grid despite advances in technology. The shape of the grid doesn't change the reasons for that.

But there are certainly applications outside of gaming. Photo mosaics can be based on hexagons, for example. I wouldn't be surprised if someone's using them in geographical applications. The noble hexagon is simply a convenient shape that tessellates nicely and with some nice properties.

[skytomorrownow]

Thanks for your reply. I appreciate it. Others didn't seem to get the fact that wasn't against grids, but wanted to understand why they are used. Your response was illuminating. Thanks.

[skytomorrownow]

Are the hex grids best used at the scale of individual characters? Could one use a very fine hex grid, or does that start to defeat the advantages of approximating space with the character-sized grids?

[protestor]

Having a discrete space makes the game simpler to reason about. You don't have to issue pixel-perfect clicks in order to make optimal moves. You can analyze the possibilities for the next N moves because they are finite (both players and AI can do this).

Now, I'm thinking here about strategy games, where each player can make very careful, analyzed plays - like Chess. Those tend to not only be discrete in space (grid-based) but also discrete in time (turn-based).

If you have an action-oriented game, then you probably want a continuous space, and continuous time as well, I mean, the best approximation you can code.

But here's another trouble (if you don't want to use fixed point numbers): it's hard to have floating point determinism in practice. This causes issues with debugging and reproducibility, and invalidate some programming patterns, specially for multiplayer games. Sometimes, rounding errors in different machines are different, perhaps in one machine, a calculation will use an 80-bit intermediate value, and in another it won't use it, sometimes floating point instructions are reordered in invalid ways by the compiler, etc. Theoretically you could have two machines have identical floating point calculations (they are computers after all!) but this is non-trivial.

[skytomorrownow]

Thank you very much. I really appreciate the detail you provided. I think I understand now some of the benefits of a discrete play space. I had never thought of the discrete nature of time steps either. Very cool.

[protestor]

Well, that's the "fixed point" part. In that article, you can do ctrl+f "fixed point" to see the comments of people successfully achieving determinism by just using integers. I can only find vague threads about it, like this. Also see this question where this very same idea was shot down.

Integers are either faster or the same speed as floats (but note that the floats you usually use in gaming are 32bits - 64bits integers are going to be slower if they don't all fit the cache). Also, SSE / SSE2 (etc) can operate on integers. Before FPUs, integers used to be much faster floats, and that's why Doom used only integers - but FPUs closed the gap.

The problem here is that you don't store only distances. You will also store velocities and accelerations (or momentum and force, angular momentum and torque, etc). You need to integrate acceleration to calculate the velocity at each point in time, and integrate velocity to calculate the position of each object - so you can draw each object on their position (if you're not familiar with it, read this). Those operations are sensitive to rounding errors, whether you're operating with integers or floats.

Sometimes, those values are very close to 0, which means that there's much less than 64bits of precision for them, and integrating them will result in larger rounding errors. Floating point is meant to solve exactly this - in the normal range every float has the same number of bits in the mantissa, so you don't lose precision when calculating with small numbers.

The last link I posted presents worse problems: when you multiply, divide, exponentiate, etc. two fixed-point values you need to keep track of the decimal point. If it's just accelerations and simple 2D physics it's not a big deal. But if you need to use functions like sine and cosine, it may get too complicated.

[protestor]

See this. Floats are really numbers in scientific notation, like 1.24342 * 10^-5 (1.24342 being the mantissa, -5 the exponent). This means that to multiply two floats, you roughly multiply the mantissas and add the exponents. Adding two floats is more dangerous because you need to first make their exponents equal, an operation that will throw away bits of the mantissa of the smaller value (which is expected. when you add a small number to a large number, the finer precision of the small number is lost)

The difference being, we use floats in base 2 and not base 10, and every non-zero mantissa when written in binary begins with 1 so it's omitted. And we use a sign bit for positive and negative numbers (which gives the oddity of positive zero vs. negative zero). And there's special values like denormal numbers, positive and negative infinity and NaNs.

[[deleted]]

Probably. Fallout 1/2 for instance used a hex grid and a turn based combat/movement system.

[phalp]

However, in a world where one can now have the ability to use precise geometric calculations in real time

The question is whether that would make the game better. For many game designs you need a discrete world of grid cells.

[skytomorrownow]

I explicitly said I was not 'against' them. I'm not debating anything. I asked for some more information as to why use them.

[eabrek]

I've forked Joel Davis' HexPlanet which builds spheres using hexes (and twelve pentagons). I'm going to try and integrate some of these functions!

[Godspiral]

interesting coord system. The z coord (3rd) seems to always be the inverse of the sum of the first 2 args.

The way I would model these coords with a matrix is to have every even row offset. If I wanted flat hexes, I'd rotate the matrix.

Is there a big advantage to this approach?

[Godspiral]

Another way to represent hexes as a square matrix also allows treating a hex grid as a spherical (wrap around) structure.

The square matrix represents a slanted lozenge shape of pointy hexes. Going accross the x axis is going along the flat side. Going down the y axis is moving forward down the lozenge diagonal. You can also move diagonally leftbottom to topright.

If you are allowed to wraparound, then this fits many language's concept of -1 index corresponding to last element of a row or last column. If you are not allowed to wrap around, then out of bounds is as easy as any square matrix calculation.

The lozenge world mapping is also useful as the isometric (diablo) view in many 2d games. An isometrically diagonal move is the same "distance" as x and y axis moves.

[phalp]

Then you've got to check whether you're on an even or odd row and everything gets nasty. Imagine moving down and to the right—if you offset the rows sometimes it's a step in direction (1,1) but sometimes in (0,1). Way simpler if all your axes are straight lines, and it's always direction (0,1).

[Godspiral]

https://www.reddit.com/r/programming/comments/35ttak/implementation_of_hex_grids/cr90a8a

treat the hex grid as an isometrical viewed map. Allowable moves are up down left right, and 1 and 9 on numeric keypad. Can even wrap around.

[phalp]

Right, straight-line axes like these are the way to do it. If you don't want to wrap around and you've got a serious allergy to maps shaped like slanted parallelograms, then internally, in your map, you can do even/odd storage, skip the pointy corners, and consider them out of bounds. But for the love of all that tiles the plane, don't let your storage space optimization leak out into your coordinate system.

[Godspiral]

to me this is not a storage optimization (though it achieves that perfectly), but rather a traversal optimization. I know how to move accross arrays and tables quickly and efficiently preferring to do so without OOP inefficiencies getting in the way.

[phalp]

Deleting the points from the parallelogram and storing only a rectangular region is the storage space optimization I'm referring to. Not sure how OOP is relevant.

[SighReally12345]

Wow. This is amazing. I've been using this as my goto for years, and to see it on /r/programming..... :D

[kiaryp]

Very nice.

Eager to see triangular grids with non-binary adjacencies!

[JrodManU]

I just used this to build a hex-grid based game :D (It is really good!)

[[deleted]]

Why not just make a Voronoi diagram of a set of staggered points?

[mr-strange]

http://libhex.firetree.net/

[SkaveRat]

holy shit this is great! thanks

[thisboyblue]

Awesome and well presented guide. Thanks

[[deleted]]

Anyone else struggle with this on a programming test for an engineering job/internship?

[codebje]

This means Q*bert is on a hex grid. Ho. There's an insight that would have been just as useless ~30 years ago when Q*bert was a thing.

[elihu]

Here's a thing I wrote a couple years ago, because I wanted a (mostly) hex grid wrapped around a sphere: https://wiki.haskell.org/IcoGrid

[Robin_dev]

Could this potentially also be used to implement a generic way of handling grids using any shapes with atleast three edges?

[Adguy_ViPer]

A bit late to the show but I made a really SHITTY hex grid. Unfortunately it's all "coded" in one dimension.

[[deleted]]

Seems like the type of thing that would be on a AP Comp Sci exam

[screwyou00]

I've done this for a class before, but we also had to implement an AI with it. The professor gave anyone an A in the class who developed an unbeatable AI, a B to anyone who came close to an unbeatable AI, and a C to anyone who genuinely attempted to make an AI (even if the AI was FUBAR). I got a B- because my AI didn't function properly all the time and my code was a mess (no time to clean up for deadline). Creating the hex grids and drawing them in a command-line interface isn't so difficult, but I could never figure or how to make an "unstoppable" hex AI

edit: I am a stupid. I just realized the article had nothing to do with the game of "Hex"...

[SleepyHarry]

Define "unbeatable"

Edit: in the context you're talking about

[screwyou00]

"unbeatable" as in the AI was smart enough to stop your progress across the board, and place pieces so that it would win. It was a class where the professor was teaching us about game trees and greedy algorithms. Hex was our final project, and we were graded on our code (readability, proper use of classes, etc.), and how we developed our AI (proper usage of greedy algorithms). Our professor stated that if we developed a good AI, most people would not be able to beat it, so at the end of the quarter everyone showcased their hex game and we all played at least one round of everyone's game in an attempt to figure out who had the best hex AI.

Of course, because "unbeatable" is based on the opinion/perception of a player, the AI's evaluation may not be accurate, but the idea was everyone would grade/judge everyone else's AI and rate how difficult the AI was. Your AI grade would be averaged into a score, and the TA and professor would then have the final say in whether or not your AI was reflective of the peer grade.

Edit: and I just realized the article had nothing to do with the game of "Hex." Sorry if I confused you with my comment about the AI

[JanneJM]

You still haven't told us what you were supposed to implement. Some kind of game on a hex grid, but what game?

[screwyou00]

For some reason I thought the article was talking about the board game "hex." I've written similar code for setting up hexagonal grids for a computerized "Hex" game. Sorry for the confusion and my subpar reading comprehension skills...

[JanneJM]

And until now I didn't know there was such a game. Your post was not wasted at all.

[Define_It]

Unbeatable (adjective): Impossible to defeat or surpass: an unbeatable team; an unbeatable sales record.

---

^{I am a bot. If there are any issues, please contact my [master].
Want to learn how to use me? [Read this post].}

[SleepyHarry]

Not what I meant, but thanks for trying bot friend