Hexagonal Grids (2013) | Hacker News Reader

Hexagonal Grids (2013)

redblobgames.com

250 pointsnovaRom56 comments

I smile a little bit every time someone links to Red Blob. This is just a wonderful, fascinating resource, the kind of thing the Internet was supposed to be for.

I also love that this isn't just theory; there's an entire implementation guide[1] to all of the concepts discussed here.

[1] https://www.redblobgames.com/grids/hexagons/implementation.h...

Tech note (or horror story): the implementation guide's code at the bottom, which is also the code used to implement the diagrams on the the main page, is generated.

I start with hex algorithms written in Haxe. I use Haxe's macro system to turn this into an abstract syntax tree. I then use Haxe's ADT + pattern matching to transform this into a different syntax tree. And then I again use Haxe's ADT + pattern matching to transform this into Python, C++, JavaScript, C#, TypeScript, Lua, Java, and Haxe code. (I also have partial support for Rust and Lisp)

Unlike most "transpilers" I'm trying to generate code that looks reasonably idiomatic for the target language. I transform names and structure (e.g. `hex_add()` for a C global function but `Hex.add()` for a Java class method) and also transform for dynamic types (e.g. Point(x,y) can have numbers in JavaScript but I need a separate Point and FloatPoint for int/float in C++). This means I need to sometimes annotate the original Haxe-syntax code with hints about how it should translate into each language. For example, 1/2 produces a different value in Python (0.5) than in C (0), so I need to add hints to tell the transform code which one I mean.

I also translate the unit tests in this way, and run them as part of the output code.

It's been a fun project but it's grown out of hand. The past week I've been pondering refactoring parts of it.

The reason for all this complexity is that my original goal was to add a language drop-down on the implementation guide page. Then you could read the implementation guide in your choice of language, your choice of grid, your choice of indentation, etc. That was an overly ambitious project :-)

Thanks a lot for your work :)) It was very helpful when I tried to implement a simple version of Settlers of Catan.

But more importantly, reading/interacting with your work is fun! It enthused me to tinker with the concepts and even to try and go beyond the explained theory and think of other ways to tile, encode maps, represent coordinates, etc.

I could get enthusiastic about almost any subject if it's presented this well.

Thanks!

For more pages like this, look at https://explorabl.es/ — it's a collection of visual/interactive explanations of various topics

That’s very, very ambitious. I think, in the help systems I’ve seen with multiple languages, each language example is written by hand.

I personally have some related ideas for a personal project but haven’t gotten anything done on it.

I also took a crack at implementing this in python: https://pastebin.com/tfFXZj89

totally agree! another blog that is equally great is https://ciechanow.ski/

Also take a look at https://explorabl.es/

Red Blob helped me a lot when I was in high school and college.

This is great, and there are a lot of past discussions about it (and other articles on the site): https://hn.algolia.com/?q=redblobgames

709 points | 10 years ago | 69 comments https://news.ycombinator.com/item?id=5809724

462 points | 9 years ago | 39 comments https://news.ycombinator.com/item?id=8941588

368 points | 3 years ago | 74 comments https://news.ycombinator.com/item?id=25340425

337 points | 5 years ago | 46 comments https://news.ycombinator.com/item?id=19184412

174 points | 6 years ago | 18 comments https://news.ycombinator.com/item?id=14627711

174 points | 8 years ago | 15 comments https://news.ycombinator.com/item?id=9537009

Somewhat related, excellent youtube video: Hexagon is the Bestagon [1]

[1] https://www.youtube.com/watch?v=thOifuHs6eY

FWIW, I am a square-grid fanatic for tabletop games. Manmade structures just don't fit on a hex grid and 1.5 is a "close enough" approximation to sqrt(2) that you have 8 degrees of freedom instead of a mere 6.

You can briefly see the red blob logo at 7m 37s into the video. :-)

> "I've been collecting hex grid resources for over 25 years."

Weird hobby, but hey, who am I to judge? Thanks for the ultimate resource, I genuinely enjoyed following and interacting with it.

Thanks! I celebrate weird hobby web sites. Here are some of my favorites:

* 59828 different definitions of "triangle center" https://faculty.evansville.edu/ck6/encyclopedia/ETC.html

* Amazing reference on bezier curves https://pomax.github.io/bezierinfo/

* Sunbeam radiant toaster http://automaticbeyondbelief.org/

* How to pack geometric shapes inside other shapes https://erich-friedman.github.io/packing/

* Pictures of library cards https://librarycards.tripod.com/id1.html

* All about pc fans https://nick-black.com/dankwiki/index.php?title=PC_Fans

* Cross sections of candy bars https://scandybars.tumblr.com/

* All kinds of info about bicycles https://www.sheldonbrown.com/

* Every type of plastic used by lego https://bricknerd.com/home/every-type-of-plastic-used-by-leg...

* Ian's Shoelace Site https://www.fieggen.com/shoelace/

Another one of my favorites has disappeared recently :-(

"the sierpinski triangle page to end most sierpinski triangle pages ™" — but it's still on wayback machine https://web.archive.org/web/20190322201106/https://www.often...

> How to pack geometric shapes inside other shapes https://erich-friedman.github.io/packing/

Packing / bin-packing is very serious stuff: savings made there directly translate to less waste / reduced costs (for example when cutting shapes into sheets of metal in big factories).

> * Amazing reference on bezier curves https://pomax.github.io/bezierinfo/

And some beautiful graphs in there, notably those under section 26 "Curvature of a curve". Screenshot'ed for my own collection of good looking stuff!

I spent some good quality time in this document.

Pure joy to interact and learn from resources such as these. Amit Patel - thank you if you ever read this!

Thank you!

While looking at hexagonal grids, check out the news about the aperiodic monotile: https://mathworld.wolfram.com/AperiodicMonotile.html

That's awesome, here is original paper: https://arxiv.org/abs/2303.10798

This is greatly improved. It’s a beautiful, functional page.

Back when I was playing with hex grids, the orientation he was using (pointy top) wasn’t what I wanted to use, so I really wasn’t able to apply any of it to my work.

So I ended up doing it much on my own. I did scavenge Google for a “distance” formula and that took a couple of goes.

I’ll have to read it in more detail to see whether it’s worthwhile to adopt this vs just sticking with what I have.

Two ways of thinking about pointy vs flat top:

1. Pointy and flat are 60° rotations away from each other. This is what I use for animations. But it's not as useful for the math.

2. Pointy and flat are the same with x/y flipped. This is much more useful for coding.

Should be (2021) based on most recent update.

It has improved significantly, at least in presentation, over time. Suspect the content has, too, but I have a less-clear recollection to assess the differences in content than I do for presentation from the last time I visited probably 3-5 years ago.

I treat it as a "living document" and update it over time, especially to update links. The last few updates:

* 2023-02: used the mouse event techniques I described here: https://news.ycombinator.com/item?id=37703291

* 2023-02: added an interactive calculation of the number of hexagons in a spiral

* 2022-12: rewrote the introductory diagrams after trying out many alternative designs; wrote about it https://simblob.blogspot.com/2022/11/introduction-to-hexagon...

* 2022-10: removed server-side rendering, as it was complicating the build process, and it wasn't a clear win (page loaded slower)

* 2022-07: fixed some embarassing typos in the sample code (ugh)

* 2021-11: updated sample code to be easier to read and not use python-specific constructs; updated naming to be more clear about which code works on cube coordinates vs axial coordinates; filled in missing helper functions that I thought would be obvious but I should've included all along

* 2021-10: unified the hex implementation guide, which used q/r/s coordinate names for cube-hexagon and q/r for axial-hexagon and x/y for cartesian, with the hex theory page, which used x/z/y for cube-hexagons and q/r for axial-hexagons and x/y for cartesian. This was the last major update, as it involved updating all the text, diagrams, and sample code. The unification is something I had been wanting to do for several years but I knew it would take a while and it would also break "backwards compatibility" with everyone who had read the x/z/y version. It was especially tricky because x/z/y not x/y/z corresponded to q/r/s, and that's what led to the embarassing typos in code I had to fix later. And the change in order also changed which direction the rotation algorithm worked.

* 2021-01: updated the size & spacing diagram to visually show the relationships between the different measurements

* 2021-01: changed the hex and axis labels to try to make them correspond because it's a bit confusing; see https://simblob.blogspot.com/2021/01/hex-diagram-labels.html

* 2020-12: added a section about reflections https://www.redblobgames.com/grids/hexagons/#reflection

* 2020-04: improved the labels on the cube/hex diagram to try to improve the correspondence between the diagram and text https://www.redblobgames.com/grids/hexagons/#coordinates-cub...

* 2019-04: rewrote the map storage section because I wasn't at all happy with how it was written before; I wrote up the change https://simblob.blogspot.com/2019/03/improving-hexagon-map-s...

* 2019-02: used IntersectionObserver to delay the diagram rendering until you reach that section of the page; this improves page load times

* 2018-05: added the "doubled" coordinate system. It's a pretty nice system, and I didn't know about it when I first wrote the page. I learned about it from rot.js.

I had lots more changes in 2018. I had just reimplemented the entire page (https://simblob.blogspot.com/2018/04/april-updates-hex-grid-...) and that gave me lots of ideas of things to improve. I first rewrote it without changing the diagrams, but then went back and made lots of diagram and text changes.

This is critically missing spiral hex coordinates which require only a single coordinate, not two.

I think the original idea is from Paul Bourke. He calls it a Spiral Honeycomb Mosaic (SHM).

See his "Tiling on The Plane" page [1]. Scroll down to the section titled "Hexagonal Lattice" (contains links to source code with coordinate conversions).

Here is a Rust implementation of a different variant of the same idea [2].

[1] http://paulbourke.net/geometry/tilingplane/

[2] https://crates.io/crates/hex-spiral

Spiral and other coordinate systems are on my list of things to add to the page. In addition to the Paul Bourke page, I have these bookmarked:

- https://gamedev.stackexchange.com/questions/71785/converting...

- https://tex.stackexchange.com/questions/275490/is-there-an-e...

- https://github.com/cooscoos/spiral_cube

- https://web.archive.org/web/20160309172431/http://www.pyxisi...

- https://www.sciencedirect.com/science/article/pii/0166218X92...

- https://thoughtstreams.io/jtauber/hex-map-addressing/

- http://tzaphiriron.sidemoon.net/static/hex/hex.html

- https://tilde.zone/@misterdave/109736460410840020

There's so much more to add to the page, and I keep adding over time. Thanks for the link to the hex-spiral crate; I'll add it to my bookmarks.

That's pretty sweet. I tried to work something like that out on my own while I was using this resource to do some spiral iteration on a Tonnetz[1] I was making in SwiftUI. (Janky screenshot[2]) I ended up retreating from that approach — but now I might give it another go. Thanks for the links!

[1] https://en.wikipedia.org/wiki/Tonnetz

[2] https://hachyderm.io/@pohl/110918457500286347

There is a note on another page about it:

https://www.redblobgames.com/grids/parts/#more

> Spiral Honeycomb Mosaic [0] (search the page for "Spiral Honeycomb Mosaic") is an interesting way to assign numbers to hexagons in a hexagonal grid. It results in bizarre properties.

[0] http://paulbourke.net/geometry/tilingplane/

I used that page so much when I was implementing my hexagonal grid AI game for a workshop at work.[1] It was such an amazing resource for the grid coordinate systems and distance algorithms. It also showed how to map between grid and regular Cartesian coordinates.

[1] https://github.com/go-fjords/astroficial-intelligence

> The cube coordinates are a reasonable choice for a hex grid coordinate system. The constraint is that q + r + s = 0 so the algorithms must preserve that. The constraint also ensures that there's a canonical coordinate for each hex.

If the dimensions aren't independent and/or orthogonal, can this even be called a coordinate system? For example, you can have (1, 4, -5) but you can't have (1, 4, -4).

I don't think coordinate systems are required to be independent or orthogonal.

https://en.wikipedia.org/wiki/Coordinate_system

https://en.wikipedia.org/wiki/Curvilinear_coordinates

https://en.wikipedia.org/wiki/Skew_coordinates

https://en.wikipedia.org/wiki/Generalized_coordinates

Actually, I think all the examples you provided were independent dimensions. I'll concede orthogonality.

More specifically: can you think of coordinate systems with explicit binary or ternary constraints on the parameters in the coordinates? I can't immediately think of any.

Holonomic constraints etc. are constraints on the validity of regions of the space, not constraints on the ability of coordinates to exist.

Good point! Hmm...

If I understand correctly, homogeneous coordinates have additional independent dimensions, but are many-to-one instead of constraining their parameters. Maybe normalized homogeneous coordinates? That's not a particularly interesting system.

I'm now second guessing my definition of coordinate system...

Would points in a simplex qualify as a coordinate system? Their dimensions would have to sum to 1. That is, so-called "normalized" barycentric coordinates maybe, as opposed to standard barycentric coordinates?

https://en.wikipedia.org/wiki/Simplex

https://en.wikipedia.org/wiki/Barycentric_coordinate_system

Note that any combination of two of the three "dimensions" does constitute an independent system. That is, given that q + r + s = 0, then q + r = -s, so you could use only (q, r) as your coordinates (and indeed that's likely how you'd canonically refer to them)

The "third coordinate" is only for convenience when working with the three main axes of an hexagonal grid. Without it, the three directions of your grid are {+q, +r, -q-r}, which introduces an ugly asymmetry for one of the three axes.

I've looked at a number of implementations of the board game Hive, which uses a technically unbounded hexagonal layout. Most of them have read your article and really like the 3-axis cube system, usually with hash table representation. As the core of a minimax engine, this is very inefficient, so my engine uses a [wrapping 16x16 rhombus](https://github.com/edre/nokamute/blob/master/src/hex_grid.rs) in a packed 256-entry array. The adjacency operations are very fast, but I have yet to come up with a way to efficiently compute distance...

I, also, referred to this developing a hexagonal grid application. <3

Wow. I clicked on this link thinking "what more can you say about hex grids that we don't already know?" But the author(s) of this guide proved me wrong. While hex grids are fairly straight-forward, I greatly appreciate the effort taken in this deep dive.

And check out the other posts on this site. Good stuff.

This is one the most amazing articles on the internet! I find I become more interested in how it’s put together than the actual content, even though the article is the content. It blows my mind and should set a standard for how technical concepts should be delivered.

Hex grids fascinated me as a kid. I used to do all my dungeons on grid paper and figured out independently some of the stuff in this article which I was probably a bit too proud of my (not so great) mathematical ability to do so.

Does anyone know of a game (board or otherwise) that uses non-regular hexagons? It seems like it could be a sort of neat way to represent bottlenecks, for example in a strategic game. (You could of course make the hexes smaller and represent a bottleneck by making some of them impassable… but then things might get more tactical I guess).

Check out Star Fleet Battles.

https://en.m.wikipedia.org/wiki/Star_Fleet_Battles

I played this for days at a time as a kid. Literally.

Because hexagons don't neatly stack the way that squares do, using different sizes (an irregular grid of regular hexagons) doesn't work as neatly as it can with squares. If you are using actual irregular polygons, I don't think there is much value to using any particular number of sides, you might as well just use a map with arbitrarily-drawn divisions.

has anyone used this information to make something with hex grids?

I first saw this page years ago, when considering a hex grid-based game design, and, despite the page's excellent information, my takeaway was: eh, too complicated, not worth it.

I wrote my heatmaps & isochrone polygons based on this page 4 years ago, with Python & GeoPandas.[1] It was rather easy, and didn't damage performance.

But looking back, it wasn't worth the hassle. Because what's the advantage of hex, apart from looking unusual? If you have, let's say, a road on a map, and some heatmap should highlight it, then cells of rectangular heatmap are going to be like low-res pixel art -- only in 2 directions it coincides with cells and looks nice.

Well, with hex grid you have +50% of such directions. Uber's H3 advocates insist there's also exactly the same distance between cells centroids. Well, that's all advantages.

Anti-bonus of hexgrid: you can't aggregate it. Hexagons don't sum up into bigger hexagons.

[1] https://github.com/culebron/erde/blob/master/erde/op/isochro...

Its a good question but I suspect the answer depends on your context.

I have seen hex grids used a lot in approximating geographic contours. Its possible that for a given number of cells they do better approximations than a regular, but one would need to check this mathematically

one interesting use of hex grids I came across is Sunset Overdrive's implementation of a streaming open-world system: https://www.gdcvault.com/play/1022268/Streaming-in-Sunset-Ov... hexagons are closer to circles than squares are, so they define chunks of the world as circles (positional coordinates for stuff in the chunk are offset from the center of the circle), packed in a hex grid. they explain the rationale more in the video, but if I remember correctly it just kinda makes a lot of sense given that a.) Sunset City's layout isn't very square-grid-based, and b.) it reduces the number of chunks per concentric "LOD layer" surrounding the chunk the player presently occupies (6 instead of 8 for the first layer, etc.)

> Anti-bonus of hexgrid: you can't aggregate it. Hexagons don't sum up into bigger hexagons.

They don't nest perfectly the way squares do, but if you rotate at alternate levels they have a decent approximate 7-in-1 nesting that H3 leverages.

Which makes no sense if you work with aggregated data, because your summed aggregations start to deviate from direct ones. You have to basically aggregate the entire dataset of millions of rows again and again for each level, instead of just doing a group-by at lowest level once, and then grouping the groups (which are just thousands).

If you have H3 and several million records, every aggregation takes noteable amount of time.

It also means that you must keep those indice for each record for each level. Because the parent function gives wrong cell for points on the fringe.

> Which makes no sense if you work with aggregated data, because your summed aggregations start to deviate from direct ones.

It depends on the purpose of the aggregation; if you are aggregating based on logical containment and using a consistent grid level for deciding the canonical location, this isn't an issue; if you are doing "aggregation" by doing strict geographical lookup for each datapoint at the grid level of the "aggregate", then it is an issue, but that is not actually an aggregation, that's a separate basic bucketing at each resolution level (though it may be the sensible way to handle data for a particular application.)

In essence, you can use an H3 index at one level as a reference to particular polygon or an a reference to the aggregate of polygons on specified level which are logically contained within it, and which makes sense depends on the application.

It is a true, and a disadvantage for some uses, that these are necessarily different interpretations, and you have to choose and apply one, whereas with lat/long or S2, geographical and logical containment are identical.

The purpose of aggregation is quite simple -- it has to show which area has which amount of some objects/properties. And it must be mathematically consistent.

If a cell is said to be a sum of 7 underlying cells, then their sum of objects must equal to this cell's sum of objects, which is not the case in H3.

You can just hope that the diff of these values is within acceptable limits, and that company management never tries to drill down into your data, and does not put all the blame for some incorrectness on you.

So, even though H3 cells kinda add-up, they actually don't, and you have to either just plainly hope, or take care of data, as I decided to do.

You'd never had this dilemma, nor need to cure the data, with a rectangular grid in either UTM projection, or Google pseudo-Mecrator, both of which preserve horizontal/vertical aspects and are perfect for such aggregative cell grids.

> If a cell is said to be a sum of 7 underlying cells, then their sum of objects must equal to this cell's sum of objects, which is not the case in H3.

If you are using an H3 index as an index to the aggregate of the logically-contained cells at some specified level, it absolutely is true (in this case, the exact geographic border is the border of the set of contained cells ay thr specified level, not the border of the higher-level cell specified by the index.)

But yes, "depending on the purpose" -- probably, to show something to layman users, like external partners, who'd unlikely drill down into particular numbers, and would be excited to see something techy-fancy-looking, it's ok to show a heatmap based on H3.

Red Blob is the man.

very cool. thanks so much for sharing...

Reply on news.ycombinator.com