Hexagonal Grids (2013)

[amitp]

A surprise to see my page on HN! For those of you curious about the tech:

Diagrams are in SVG. Canvas would be faster but SVG is easier for me to work with, especially for attaching mouse events to each hexagon. It also automatically scales to high dpi displays. With SVG and HTML accessed the same way, I can use the same code for updating text/samples as I do for updating diagrams. This includes interpolating values as noted by anchpop.

I don't use a build step for the JS code. It's just <script> tags, like it's 1999! You can View Source and see them all. I realize it'd be better if I minified bundled etc. but I'm lazy and this was easier. The page is implemented differently from a "single page app". For that, you might want something like JSX so that you can stay on the JS side, and output HTML+CSS as needed. For this kind of page, I mostly write HTML+CSS, and I tap into JS when needed using Vue.js. For example, I want the text "w = 2 * size" to be next to the rest of the text for that paragraph, instead of in a separate JS file:

       <p>
          Next we want to put several hexagons together.
          In the {{layout}} orientation, a hexagon 
          has width
          <code v-if="layout === 'flat'">w = 2 * size</code>
          <code v-else="">w = sqrt(3) * size</code>
          …
        </p>

I do use a build step for the HTML+SVG. Although the page works without this step (see pre-index.html), the user experience is a little bit better if I generate it on the server. I use cheesy pre-rendering for this: "$(CHROME) --headless --disable-gpu --dump-dom". It means more bytes :( but having all the HTML/SVG load at once is better for linking to a section, hitting the back button, etc. You don't lose the scroll position. Bonus: the page loads if you have Javascript turned off!

The static SVG on the server doesn't include the interactive parts. I use InteractionObserver to replace the static diagram with an interactive one as soon as you scroll to that section of the page.

I said I don't have a JS build step, but that's not quite true. The core hexagon algorithms were originally implemented in Haxe, compiled to Javascript. At the time (2013), I was curious about Haxe as an alternative to Javascript. Because I was either bored or crazy or both, in 2015 I implemented a code generator that used Haxe macros to parse the algorithms in Haxe-ish syntax[1] and then generate C++, Javascript, Python, and other output. The Javascript output from that is what now powers the page. Well, it's even more convoluted than that. The Haxe code generates Typescript[2], which I turn into Javascript[3]. I don't know what I was thinking! Well, I do — I wanted my readers to be able to use my unit-tested hexagon algorithms even if they were using a different programming language.

I wrote [4] describing the process of making an interactive page like this with D3.js. Check out [5] for a collection of interactive explanations from other people.

It's unlikely that you will print the page, but if you do, it will show endnotes for all the links so that you can see the URLs.[6]

[1] https://www.redblobgames.com/grids/hexagons/codegen/Codegen.... [2] https://www.redblobgames.com/grids/hexagons/codegen/output/l... [3] https://www.redblobgames.com/grids/hexagons/codegen/output/l... [4] https://www.redblobgames.com/making-of/line-drawing/ [5] https://explorabl.es/ [6] https://simblob.blogspot.com/2018/12/printing-my-pages.html

[sharpercoder]

Your page is not only awesome in creating my Catan clone, but also very useful when communicating on it with others. You have set the gold standard or the defacto standard.

If you're interested in my implementation: https://github.com/generateui/jsettlers-web/blob/master/src/... https://github.com/generateui/jsettlers-web/blob/master/src/... https://github.com/generateui/jsettlers-web/blob/master/src/... https://github.com/generateui/jsettlers-web/blob/master/src/...

A hex has a coord. A coord has 6 nodes and 6 edges. An Edge can be created from 2 coords or 2 nodes. A node can be created from 3 edges or 3 coords. The implementation is immutable and memoized.

[maxnoe]

Hey,

I'm an astrophysicist in high energy gamma ray astronomy.

Or telescope sensors have hexagonal pixels.

You website is awesome and helped a lot writing the coordinate trafos and other stuff. We always recommended it to everyone involved.

One switch I always wished it had was to switch to a cartesian coordinate system where x points right, y points up and negative coordinates are allowed.

[timvdalen]

Thanks a lot for your website (an in particular this page and the hexagonal terrain generator page). I use it for small side projects quite often and I've actually re-implemented the terrain generator in C++ for a school project[1][2], with a 3D renderer for generated worlds[3].

[1]: https://github.com/H/2IV06-report [2]: https://github.com/Heightened/2IV06-map-generator [3]: https://github.com/Heightened/2IV06-map-viewer

[Longwelwind]

Your guide is the first thing I open in my browser every time I need to code an algorithm in a hexagonal space.

Thanks a lot for the amazing work!

[rishav_sharan]

Hey Amit

A big thanks for your site. As someone who fiddles around with small hobbyist game projects, your site is the defacto bible for me.

I was wondering if you plan on writing something on game AI. specially where the AI has infinite permutations of actions that they can take. How do these game AIs actually formulate a list of possible actions and how do they prioritise them?

[appleflaxen]

> . I use cheesy pre-rendering for this: "$(CHROME) --headless --disable-gpu --dump-dom". It means more bytes :( but having all the HTML/SVG load at once is better for linking to a section, hitting the back button, etc. You don't lose the scroll position.

this is an excellent tip! thanks for the awesome technique.

[ISV_Damocles]

Thank you so much for your wonderful documentation. The H3 team at Uber used it so much for so many things. :)

[invalidusernam3]

You have no idea how helpful this page has been for me in the development of my hex game. Chuck a donate link on there, I would love to buy you a few beers to say thank you

[johnmarinelli]

I used your site to implement A* as a learning exercise, and I learned a lot from it. Thanks!

[timvisee]

Have used the page maby times. It's brilliant, and perfectly explains. Thanks a lot!

[syspec]

Love all the content on your site, keep writing more new things please!

[phoe-krk]

It's not the first time it is here.

https://news.ycombinator.com/item?id=19188932

[prawn]

This is a regular and classic submission IMO. Pops up every few months on HN and is absolutely deserving! We used it as a resource in developing the iOS word game http://hexiledgame.com/

[amitp]

Thanks! Lots of changes since the last time it showed up (2017 I think): faster page load, less JS, better diagrams, more diagrams, better colors, axes legend, more polish, more interactive parts. I wrote about these http://simblob.blogspot.com/2018/04/april-updates-hex-grid-g... and http://simblob.blogspot.com/2018/04/april-updates-iteration....

[dang]

The big discussions are

2017: https://news.ycombinator.com/item?id=14627711

2015: https://news.ycombinator.com/item?id=8941588

2013: https://news.ycombinator.com/item?id=5809724

[krosaen]

Very cool!

If you like hexagons, and boy do I like hexagons, I recommend also checking out Uber’s Hexagonal Hierarchical Spatial Index

https://eng.uber.com/h3/

[mistrial9]

this uber-h3 has been public for a while, and it brings mixed reaction for me -- it seems like Uber wanted to 'invent' something really cool, as in, the showing off part is every bit as important, or more, than the tech. The reason to point that out is, spatial indexing is one of seriously studied topics in academic geometry. Yes, the classical papers can be a bit much, but there is a reason why they are so -- it really does benefit from that kind of attention.

If Uber needed a different kind of spatially indexed filter and search, then some system that is adaptive to data density would seem like the performant thing to build. Nested-hexagon space is certainly fun, but real car data is distributed in certain ways, that are not rectangle and also not hexagon.

[coreyp_1]

I use this site quite often as a resource that I point my students to when working on their end-of-semester (largely self-directed) coding project, which is often some sort of game.

It's very well done!

[crummy]

Not only is this very informative, but such a slick user experience too. Largely plain text with some simple diagrams, but click on things (e.g. "pointy" or "flat") and see not only the diagrams change but the code too!

[anchpop]

When switching between pointy and flat top, I see some values in the code interpolate. Some crazy attention to detail there. Reminds me of Tangle [1].

[1] http://worrydream.com/#!/Tangle

[aurelwu]

I used this page so much when creating my HexMap Library for Unity [1] (it's MIT Licensed so I hope its okay to advertise it here). Are there any other pages comparable to redblobgames which covers game related topics in such a engaging way?

He really inspired me to step up the effort spent in writing good documentation.

[1] https://aurelwu.github.io/

[amitp]

Thanks for your library! I've linked to it from my Hex code implementation guide.

For game related topics, I like http://gameprogrammingpatterns.com/ (book available for purchase, but also freely viewable on the web)

[unnouinceput]

As a DB mainly guy whom never did any hex maps of any kind, the double coordinates felt most natural to me. Was reading the other systems and kept wondering why one like that is not there until further reading. In my case I'd put them in a 4 column table and SQL the shit of everything in there. Would actually be very easy once you have experience with composite types from PostgreSQL, as an example.

[estomagordo]

I wish I knew this much about any subject at all.

[ajuc]

There's also square version of hexagonal map. It is made of squares, but every second row (or column) is moved by half a tile. Like bricks in a wall or tiles in pavement.

It doesn't look nearly so neat if the tile borders are visible, but when they aren't it doesn't make a difference as long as you draw tile backgrounds right. And it's easier to calculate on which tile you are, but it still keeps some of the benefits of hex grids.

One advantage of hexagonal grids for procedurally generated maps is that you only have 6 neighbors instead of 8 to consider when generating each new tile.

If you care about 1 bit of information from neighbors that's already 4 times less combinations to prepare. With more bits it's even bigger difference (but then manually drawing a tile background for each possible combination becomes too much work anyway).

[gliptic]

That's the first coordinate system described on the page, offset coordinates.

[ross-squires]

I have read this article sooooo many times. It's an awesome resource. Without it, Hex Kit (https://coneofnegativeenergy.com/hexkit/) would have never existed.

[Tade0]

This article made me realize that my NIH collision algorithm I implemented the other day[0] is a dead end.

I wanted to put obejcts into bins so that pairs which are unlikely to collide are not checked.

Square bins are nice, but an object can potentially be in four of them at a time.

Hexagonal bins on the other hand reduce that number to three - great, but assignment is not as obvious.

If you look at the hex pattern the centers form a skewed grid - an appropriate affine transform should deal with that.

Does it help? Kinda. Coordinates in "hex space" are weird and now I see why - I'm using the wrong coordinate system to begin with.

[0] Making a game after-hours - the real project here is escaping from the immensely pragmatic world of writing software for money.

[protomyth]

This is one of the great things about the internet. Not only is it an amazing article about hexagonal grids that you would never find in a magazine much less a book, but the references are equally amazing and exhaustive.

I do remember back in the late 70's and seeing D&D using hexagonal grids for outdoors, and the despair and pain of trying to find a damn pad of hexagonal paper (I think I had to mail order from The Armory or Chessex?!?). It was pretty funny that years later, one of the first PostScript programs I wrote generated hexagon sheets that could be printed on the college laser printers.

[zoba]

I used this guide to help me prototype this engine, which is a hexagonal tile map with the ability to scroll infinitely! (Though, the backend isn’t all there). You can click tiles the change colors and the color persists and has real-time updates between browsers.

https://territories-1d6eb.firebaseapp.com

[johnzim]

Hah! I literally JUST had to implement this last week. Wish I'd had this resource then!

[ttoinou]

Good for you, it's better to rediscover all the equations yourself :)

[Shinchy]

This is actually a really handy resource, I'm currently working on something with isometric hexagonal grids and it can get pretty complex at times.

[kostaw]

This is an extremely well-written and complete resource! Thank you!