Everything you ever wanted to know about hexagonal grids

As a part of my university coursework I modeled forest fires with a grid but mine had varying densities of forests and each tree affected an area around it, not just adjacent cells. It's a really interesting thing to try and model if you get a chance, because tiny adjustments can make a world of difference.

Square grids are more intuitive: they map to our standard cardinal and ordinal directions. As long as you treat the ordinal neighbours (the corners) as being sqrt(2) away from the center (as oppposed to 1 away from the center like the cardinal neighbours, or all of the hexagonal neighbours) then you don't get spatial distortions.

If rotational symmetry is important to the dynamics, you're likely to do much better on coarse grids with a hex layout, because it has a finer rotational symmetry.

Of course, with a small-enough grid rotational symmetry should be restored (or you've chosen a poor discretization!). One might rephrase your statement as: the lattice artifacts / discretization errors vanish faster on a hex grid. Could be.

When I worked on fire-spreading models [0] the grids we used were square. I would wager that this is because it makes thinking significantly easier. In my current field[1], square lattices are chosen because of the underlying supercomputing architecture. The communication mesh in tera- and petascale computers tend to be rectangular [2]. At these scales, having a nice rectangular layout of the local subvolumes simplifies communication algorithms and can provide a dramatic speedup---in this case having fewer neighbors is better.

[0]: In high school I implemented the fact that fires burn faster uphill while working for David Keyes on http://www.cs.cmu.edu/~caliente/

[1]: Lattice QCD codes use a (4D spacetime) rectangular lattice https://usqcd-software.github.io/

[2]: The BlueGene/Q, for example, is a 5-dimensional rectangular torus.

As far as I know the reason why square lattices are preferred over hex lattices is that they can easily generalized to 3D, ... . If you invest lots of time thinking about good, say, FEM or Finite Volume algorithms, you want to have results that can easily generalized afterwards.

I can provide an intuitive thought picture answer, that if you're doing something that boils down to numerical integration under a curve, a pile of hexagons or other polygons will win over a simple raster array of square pixels at a similar quantity of polygons, but when implemented, if its computationally cheaper to run the rectangular raster array at 10, 100, maybe 1000 times the resolution of the hexagon implementation, then the raster will always win at the overall systemic level at the numerical integration game. Not implying forest fires are simple numerical integration games, but they are similar-ish in trying to discrete-ize a non-discrete analog problem.

If you were talking about EE DSP stuff, you'd call it quantization noise. Theoretically a floating point A/D converter would be nice / interesting if such a thing existed, but in practice you minimizing that noise source by using more fixed bits per sample.

Just a conjecture, but, it may not always be possible/straightforward to map a set of CA rules meant for a rectangular grid to a hex grid.

That's funny, I brought this exact puzzle up last time this link was posted. Twins! Nice solution.

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

Thanks! (I'm actually in the middle of a major update to the page — I hope to have it published in a few weeks)

I used d3.js for this page (and most of the pages on my site).

For a given shape of map (rectangular, triangular, hexagonal, parallelogram, etc.) I generate a set of cube hex coordinates. I then use d3 to instantiate an SVG shape for each coordinate. D3 will maintain the mapping from the cube coordinate to the SVG shape, so I can set element classes on mouse events, and then I style those with CSS.

For example, in the line drawing example, I have a generic function that creates a hexagonal shaped grid (of hexagons)[1]. On mouseover, I figure out which hex it is, then run the line drawing algorithm to create a set of coordinates from the start point to the hex you're pointing to. I then tell d3 to iterate over all the SVG dom nodes and set the "selected" class if it's in the set returned by the line drawing routine[2]. The color changes with the CSS rule #diagram-line .selected polygon {fill: hsl(200, 50%, 80%); }

I've used canvas for some of the pages but I find svg much easier to work with. I can attach mouse events to the elements, and I can set properties (such as color) easily without redrawing everything. D3 is great for maintaining a mapping from data (such as a set of hex coordinates) to dom nodes (such as a set of svg <polygon>s). D3 also has transitions, but I think most of my needs could be handled with CSS transitions instead of D3's JS transitions.

[1] See http://www.redblobgames.com/grids/hexagons/Grid.hx : hexagonalShape() [2] See http://www.redblobgames.com/grids/hexagons/ui.js : makeLineDrawer()

Isn't that precisely what the linked paged calls '"odd-r" horizontal layout' ?

The offset approach is what most people do. I've used it too. It makes the storage simpler for rectangle shaped maps but the algorithms more complicated (and slower). I wrote this page to present the alternative coordinate systems. The symmetry of the cube system greatly simplifies many of the algorithms, so it's often easier to convert offset or axial to cube, run the algorithm, and then convert the answer back to offset or axial. The main downside of axial is that map storage in an array is a little more complicated; http://www.redblobgames.com/grids/hexagons/#map-storage

The lack of wrapping would be fine for something like Minecraft, where the world could be generated radially outwards from the starting point :)

I used it to to build the rule system for my game engine.

The triangular grid is dual to the hexagonal grid -- if you take a hexagonal grid, put a vertex in the center of each hexagonal tile, then form tile edges by connecting each vertex to its six neighboring vertices, you get a triangular grid. Doing the same operation to the triangular grid gives you the hex-grid back again.