Hexagonal Grids (2013) | Hacker News Reader

Hexagonal Grids (2013)

redblobgames.com

337 pointsskilled46 comments

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

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.

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.

Cool! Glad the page helped! On the implementation page the code supports both y-up and y-down, as well as negative coordinates. One of these days I should update the diagrams on the main page to support this too.

What drove the decision to go with hexagonal pixels? Sounds pretty crazy and cool.

Historically, the "pixels" are mostly round photomultiplier tubes. So the natural way to place those is a hexagonal grid.

     o o
    o o o
     o o

The pixels are very sensitive, we can register single photons with a time resolution of half a nano second.

Quite recently, some telescopes started using silicon photo multipliers, which are mostly square by design.

But: The first telescope to use those also used light concentrators to increase the detector area and these have hexagonal entrance windows, so we also have hexagonal pixels.

Physicists like symmetries, and light concentrators are more effective when round than square, hexagonal is a good middle ground.

Thanks for explaining! Makes sense.

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

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!

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?

Thanks! I've found that my best pages are topics from real projects I've worked on, and I haven't worked on many game AI systems. I might have pointers to papers or web sites for you; feel free to email me at redblobgames@gmail.com

> . 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.

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

Wow, awesome to hear it!

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

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

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

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

Thanks! I'm keeping a list of ideas here: https://trello.com/b/mjOSMtsi/2019 but I'm not working on much at the moment. I needed a break after mapgen4 (2017-2018).

It's not the first time it is here.

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

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/

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....

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

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/

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.

I don't understand.

The events are associated with coordinates and then binned into their containing hexagon at a given resolution.

So if 10 people request a ride in the same hexagon in a given time frame it weights that hexagon according to surge pricing rules.

I just want to make it clear that there's a real reason behind H3, not just "invent something really cool." I don't work at Uber, anymore, but I did work on the team that originated H3 and worked on H3.

To condense it down to a few bullet points, we realized:

1. We needed to move from geofences to a grid for both data science reasons and scaling reasons to perform realtime aggregated and anonymized activity analysis for things like surge pricing.

2. With a grid along with quantized time ranges (eg 10 seconds or 1 minute intervals) we can reduce data collection to distributed increments across a small cluster of machines with O(1) compute time rather than a more complicated R-Tree (O(log(n)) + Point-in-Poly (O(m)) system for geofences (that also can't backfill prior results when new geofences are added)

3. With a grid, data science can be assured of approximately equal area and time across these space-time buckets so normalizing the data for analysis between them is not necessary, regardless of where on the planet it came from (cross-city analysis and forecasting). With a hexagon grid, data science can also be assured that all neighboring cells are the same distance from each other and that all neighboring cells share a measurable edge rather than an infinitesimal point (like squares) so flow analysis between the cells is similarly simplified and needs no normalizing.

4. With a hierarchical hexagon grid we can quantize the data at the finest granularity (which is higher resolution than commercial GPS, about the size of a coffee table in diameter) and it can be rapidly reaggregated upwards to other resolutions (with some small error introduced since hexagons do not properly tessellate) for data science to determine what the "right" resolution is for the analysis at hand, then the realtime aggregating system can be updated to index at that resolution natively, as well, to improve bucketing accuracy (H3 resolution 9 was one such blessed coarser resolution).

When we determined exactly what we needed, we didn't invent it to feel like we did something really cool, we reached out to Dr. Kevin Sahr in academia to help us make it, who used part of his DGGRID code to do so[1], and then spent nearly 2 years to make sure everything was legal for open sourcing.

What we did at Uber was focus on getting his core more easily consumable: Request that the core does not allocate memory on its own, but is passed in memory (so integration with memory-managed languages would be much simpler), implement many of the algorithms described by Red Blob Games to make manipulation of the data in the grid system more amenable, update the build and test system to a more modern standard (CMake, code coverage, and unit tests), and write C bindings in various languages.

[1](https://uber.github.io/h3/#/documentation/overview/use-cases) (references the paper that covers the work he did)

excellent -- reading carefully; this one is fun .. https://github.com/uber/h3-py/blob/master/docs/UnifiedDataLa...

Using H3 to analyze data originally indexed in different formats is definitely cool, but you can totally do that with S2 as well.

I personally feel the unidirectional edges[1] are a real differentiator. If you have these space-time buckets and compare counts between two points in time, you can see the change in density, but you don't know how active it is. Tracking transitions between hexagons in an anonymous, aggregated fashion lets you see if the "stagnant" areas of your map are stagnant because the actors actually aren't moving, or if there's a large "mixing" of the actors but you've reached a quasi-static-equilibrium in the system.

It also lets you see which regions are more connected to each other if, for instance, hexagon A always flows back and forth with hexagon B which also flows back and forth with hexagon C bordering both but no such flow between C and A, so from data you can spot potential rivers, deduce roadblocks/accidents, that certain businesses must be closed, etc.

[1](https://uber.github.io/h3/#/documentation/api-reference/unid...)

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!

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!

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

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/

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)

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.

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

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).

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

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.

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.

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.

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

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

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

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.

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

Reply on news.ycombinator.com