Wednesday, May 08, 2013

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: , ,

2 comments:

Pieter Geerkens wrote at May 09, 2013 5:27 PM

Amit: I believe you missed a 4th strategy for storage of rectangular maps: Store using rectangular coordinates, but make conversion to and from canonical coordinates painless. Check out the class HexCoords and the interfcacaes ICoordsCanon and ICoordsUser in my utility library

Amit wrote at May 09, 2013 5:40 PM

Hi Peter, yes, I did miss that. I believe it ends up being the same as the sliding approach (where the offsets are computed via formula instead of stored explicitly) but I haven't worked through it. Thanks!