25 ms·
Everything you ever wanted to know about hexagonal grids
- nness 12y agoVery comprehensive. Enjoyed the interactive examples.
- jordigh 12y agoTangentially related, I have heard of modelling forest fires with cellular automata. http://en.wikipedia.org/wiki/Forest-fire_model http://en.wikipedia.org/wiki/Forest-fire_model The grid is usually rectangular, and I've always found this a bit odd: hexagons represent 2-d sphere packing, so they always seemed more natural to me. I once asked researchers in the field about this, around 2006, and they responded that rectangular grids serve just as well. I just found this paper from 2007 where apparently hexagonal grids fare better: http://www.sciencedirect.com/science/article/pii/S0307904X06000916 http://www.sciencedirect.com/science/article/pii/S0307904X06... This makes me wonder, for realistic models that are meant to model a notion of neighbour cells, why aren't we always using hexagonal grids in 2d or higher-dimensional analogues? With rectangular grids, you're always faced with the choice of defining whether touching on edges and corners count as neighbours or not, which seems like an unnatural choice. Why, then, does this not seem to matter in the end?
- JonRB 12y agoAs 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.
- rcfox 12y agoSquare 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.
- evanb 12y agoIf 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/ http://www.cs.cmu.edu/~caliente/ [1]: Lattice QCD codes use a (4D spacetime) rectangular lattice https://usqcd-software.github.io/ https://usqcd-software.github.io/ [2]: The BlueGene/Q, for example, is a 5-dimensional rectangular torus.
- wolfgke 12y agoAs 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.
- theoh 12y agoActually there is a simple 3D analog of the hexagonal grid, which occurs in crystal structures. Somewhat interestingly there are two variants, known in crystallography as Face-Centred Cubic and Hexagonal Close Packing. http://en.m.wikipedia.org/wiki/Close-packing_of_equal_spheres http://en.m.wikipedia.org/wiki/Close-packing_of_equal_sphere... In higher dimensions there are applications to broadband coding (you want the densest possible constellation). http://mathworld.wolfram.com/HyperspherePacking.html http://mathworld.wolfram.com/HyperspherePacking.html
- theoh 12y agoThough perhaps more relevant to FEM is the tetrahedral mesh...
- wolfgke 12y agoBoth types are important. The math is indeed more complicated for square meshes, but you can use the fact that the basis functions (is this the proper English translation of the German "Basisfunktionen"?) on square elements have more degrees of freedom to sometimes get better approximations. Disclosure: I heard some advanced lectures about FEM intended for students who intended to write a diploma thesis about this topic.
- VLM 12y agoI 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.
- tiler 12y agoJust 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.
- akanet 12y agoFascinating! One of Affirm's old job application puzzles was about a hexagonal grid. I did a write-up[1] of how I solved it, unaware that I was reinventing the wheel. The cube coordinates abstraction would have been killer for being able to explain things to myself. [1]: http://vincentwoo.com/2013/03/08/above-and-beyond-the-affirm-job-puzzle/ http://vincentwoo.com/2013/03/08/above-and-beyond-the-affirm...
- ims 12y agoThat's funny, I brought this exact puzzle up last time this link was posted. Twins! Nice solution. https://news.ycombinator.com/item?id=5809724 https://news.ycombinator.com/item?id=5809724
- antichaos 12y ago20 fun facts about hex grids: http://gamasutra.com/blogs/HermanTulleken/20140912/225495/20_Fun_Grid_Facts_Hex_Grids.php http://gamasutra.com/blogs/HermanTulleken/20140912/225495/20...
- jxf 12y agoThis was a fantastic article -- examples were concise and clear, and everything was well-written. Tangentially, I'd love to know the best way to create the visuals for this kind of content. I assume no one's writing all those SVGs by hand, right?
- amitp 12y agoThanks! (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 http://www.redblobgames.com/grids/hexagons/Grid.hx : hexagonalShape() [2] See http://www.redblobgames.com/grids/hexagons/ui.js http://www.redblobgames.com/grids/hexagons/ui.js : makeLineDrawer()
- MarkHarmon 12y agoThat is an amazing resource and I used it when developing my hex game library for PixiJS. https://github.com/mark-harmon/HexPixiJs https://github.com/mark-harmon/HexPixiJs
- dublinclontarf 12y agoI used it to to build the rule system for my game engine.
- prestonbriggs 12y agoI've explored similar questions using a grid of equilateral triangles. Obviously they are very close in spirit. I wonder though, if the triangles are somehow more basic.
- panic 12y agoThe 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.
- theoh 12y agoIt is maybe worth noting that triangles are 2D simplices, so for a non-flat mesh, triangles are a simpler solution. Hexagons won't always be flat. There's a literature of progressive mesh transmission that does fun things with mesh topology. Not sure if it's still a live topic but I remember a paper with nice illustrations from 2001: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.5034 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.5...
- gameshot911 12y agoWow. The interactive examples make for one of the most impressive tutorials I've ever come across. Great job, amitp!
- acidburnNSA 12y agoThat's neat. I spend my work days simulating advanced nuclear reactors that have hexagonal fuel assemblies. In my codes I've used a lot of this info. This is an excellent resource that I'll be referring people who come from the more traditional square lattice world.
- pocketstar 12y agofucking repost
- fit2rule 12y agoIf you want to get into grid programming, the MOAI framework has pretty good support, and the samples are pretty easy to grok: https://github.com/moai/moai-dev/blob/develop/samples/grid-hex/main.lua https://github.com/moai/moai-dev/blob/develop/samples/grid-h...
- novaleaf 12y agoI've never seen hex described this way, but here's how I envision simplifying their logic in games: a regular 2d array, but with every-other row logically offset by 50% of the cells width, thus you end up with: [ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ] super simple data structure (normal 2d array), and pathfinding isn't difficult (use hex algos). I wonder why nobody ever writes about this.... Edit: ahh, the article kind-of describes this in the "Offset coordinates" section, just no explicit mention of able to use an array for storage.
- baxter001 12y agoIsn't that precisely what the linked paged calls '"odd-r" horizontal layout' ?
- novaleaf 12y agoyeah it is (see my edit), but it may not be obvious to would-be implementers that their data structure could be modeled as an array.
- amitp 12y agoThe 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 http://www.redblobgames.com/grids/hexagons/#map-storage
- T-hawk 12y agoWhy are we storing in an array at all? Why keep that last vestige of rectangular representation? How about storing the map directly in cubic coordinates? The storage structure would be a dictionary with a three-value tuple as the key. Iterating along any of the three axes is perfectly simple, and all directions work the same way. Algorithms like A* work directly on a list of neighboring hexes with no coordinate conversion required. Serialization to a savegame format or network communication would look like JSON with key-value pairs of the 3-tuple (key) to the tile data (value). The advantage of the 2D array structure is only a bit of performance, that the coordinates of each tile are implicitly defined by the array indices. I'd venture to say that our modern languages and platforms don't need that optimization any more. We insert another layer of abstraction in decoupling the tile's coordinates away from its storage location in memory. Put another way, the only conversion occurring is between the 3-tuple key and the physical location in memory, and that's abstracted away from us in whatever mechanism (hashtable or whatever) that the dictionary uses internally. Everything at the application level works directly with cubic coordinates. By getting rid of the 2D array storage, we get rid of the last remnants of anything rectangularly-related, with never any need at all to convert to the rectangular vestiges of axial or offset coordinates.
- leni536 12y agoI would like to see a game on a Penrose tiling. Obviously you couldn't make it wrap though. http://en.wikipedia.org/wiki/Penrose_tiling http://en.wikipedia.org/wiki/Penrose_tiling
- scott_karana 12y agoThe lack of wrapping would be fine for something like Minecraft, where the world could be generated radially outwards from the starting point :)
- tericho 12y agoWow, I've been trying to make a Settlers of Catan game for fun and the thing I struggle most with is the board algorithms. This a fantastic resource to help with that, thanks.
- maccard 12y agoFor anyone who hasn't read it, (and is interested ofc.) this website has one of the best explanations of A* I've ever read. http://www.redblobgames.com/pathfinding/a-star/introduction.html http://www.redblobgames.com/pathfinding/a-star/introduction....
- ofcapl_ 12y agobrilliant article!
- lloeki 12y agoI wonder what a non-cubic polyhedron-based voxel system would look like, without going all the way to marching cubes/tetrahedrons (where the cubes/tetrahedrons are only part of the algorithm that helps in rendering basically arbitrary voxels). To wit: http://mathworld.wolfram.com/Space-FillingPolyhedron.html http://mathworld.wolfram.com/Space-FillingPolyhedron.html
- bhhaskin 12y agoThis is such a good resource!