Guide to hexagonal grids

From Red Blob Games's Blog

A few weeks before Game Developers Conference, I thought to myself, what article can I write that’ll just take 2 weeks? I decided hexagonal grids, as a subset of my bigger article on all grids, would be a reasonable choice. I already have all the material; I've collected it for nearly 20 years on my site.

I was wrong.

I was wrong about how long it would take. It took me roughly 8 weeks. I was also wrong that I already had all the material. The more I dug into hexagonal grid algorithms, the more cool patterns I found — things I hadn't seen elsewhere. And I wanted to not only write about them but implement them and create interactive diagrams. I printed out sheets of hex grid paper (from here), played with the algorithms, tested things out, and discovered new things. I implemented the data structures in Haxe and visualizations in d3.js.

And there are still so many things I wanted to do but didn’t!

For example, I wanted to generate code on the fly for each the grid types. I thought, if I represent the core algorithms in an abstract syntax tree format, I can compose parts together, write an expression optimizer, and generate new code. For example, the neighbor algorithm is written in hex cube coordinates. To use a different coordinate system, like odd-R offset, you’d use convert_cube_to_odd_r( neighbor( convert_odd_r_to_cube(hex) ) ). If you compose these functions, inline, and optimize, you could get a neighbor algorithm custom designed for the odd-R coordinate system. I could generate that, on the fly, in Javascript, and display it to you. I could then give you a menu asking you which of the 74 grid types you use, and then I could generate a hex algorithm library for you, based on your needs. And maybe even in the programming language of your choice.

Is that feasible? I think it is.

There are lots of other things that I would like to do but decided to cut. I would’ve liked to clean up the code to produce a reusable library for others to use. I’ve made a list on Trello with all of the things I could've done, but didn’t.

Instead of doing all those things, I decided it’s better to finish and publish (ship!) than to delay it to do the more ambitious things. I can leave them for version 2. It's like shipping a game. You have to cut things. It's better to ship something good enough than to never ship the perfect game.

Take a look at my new guide to hexagonal grids. Let me know what mistakes I made. Let me know what questions you have. Let me know what you’d like to see in a future version. Quick fixes I’ll make soon; bigger changes will wait for version 2. Thanks!

Labels: grids , hexagons , math