At Gamelogic we are obsessed with grids. We make tools for grids and write about grids, but our obsession goes way beyond this (we even have "Grid shirt Fridays").
We thought it might be a good idea to share some of the interesting (and obscure) facts we have uncovered in our quest to know everything we can about grids and their use in games. We have been sharing a short fact each day over Twitter; here we expand on those facts and add a few more. These are all about hexagonal grids, one of our favorite types of grids.
Edit: This is a sample of some of the fun facts of hex grids. For a more serious and in-depth mathematical look at hex grids, I wrote a PDF document that covers many aspects you won't see anywhere else, with specific emphasis on the things that arise in game developemnt: defining shapes with simple equations on a hex grid (a triangle has max(x, y, z) < r), dot and croiss products for cheap trigonometry, tranformations matrices, the hex equivalnt of quadtrees, procedural generation (with perlin-like noise), and repsentation of triangular, rhombille and floret pentagonal grids.
You can doanload it here: http://www.gamelogic.co.za/downloads/HexMath2.pdf
The images below is from this file.
The use of hexagons in games seems to be a recent practice. As far as we can tell, Agon, also known as Queen's Guard, was the first one. It first appeared in the¬†18th century, in France, and became popular because of its simple rules and complex strategy:¬†Each player has one¬†queen¬†and six¬†guards. Players decide who moves first, then alternate turns. On each turn, a player moves one of their pieces. The aim of the game is to be first to reach the central hex (the¬†throne at the center of the board) with one's queen and surround her with all six of her guards.
Hex¬†is a stratgey board game¬†played on a¬†hexagonal grid of any size and several possible shapes. It was invented the first time by Danish mathematician Piet Hein around 1942.
The goal of the game is to form a connected path with one‚Äôs pieces from one side of the board (marked by the players colors) to the opposite side before one‚Äôs opponent does the same. The first player to complete his or her connection wins.¬†
Hex can't end in a draw;¬†one player always wins. The only way a player can prevent an opponent from forming a connected path is to form one of their own.
John Nash re-invented the game independently in 1947. He showed that the first player can force a win by using the "strategy-stealing" principle:¬† An extra move for either player in any position can only improve that player's position. So if the second player has a winning strategy, the first player could "steal" it. The player could do this by playing an irrelevant move, and then follow the second player's strategy. If the strategy ever required moving on the square already chosen, the first player can just make another arbitrary move. This ensures that the first players wins. ¬†
It's useful to draw when working on game algorithms or mechanics, but drawing hexagons on paper is a nuisance. Of course, you can print out some hex-graph paper, but when an idea strikes you in the middle of nowhere (or if you draw as much as I do), then you need to be able to make hex grids quickly on paper. One way to do this is to use a brick grid, as the one shown below. It is much easier to draw quickly, and it still captures all the topological information of a hex grid ‚Äď each brick has six neighbors, and the same rules of connection apply.
Recall that the area of a parallelogram in normal Euclidean vector space with two sides given by two vectors (x1, y1) and (x2, y2) is given by |x1y2 - x2y1|.¬†
So if all the components are integers, so is the area. But if we shear the points parallel to the x axes, the area of parallelograms stay the same, so if we shear a rectangular lattice to a hex lattice, all the parallelograms have the same areas as if they were on the rect lattice, and so they must be integer values too.
From this fact, it follows that any triangle with vertices on a hex grid has an area that is half an integer (since the area of a triangle is half that of a parallelogram). Therefore, any polygon with vertices on the grid has an area that is half an integer.
Because video screens are rectangular, the idea of rectangular wrapping is quite natural ‚Äď what goes out at the one end comes in at the other end. It's not immediately obvious how to wrap hex grids in an analogous way. In fact, there is more than one way to do it, and it depends on the shape of the hex grid.
A hex grid in a parallelogram can be wrapped very similar to the rectangular wrapping. This is straightforward, and it should be easy to see how this corresponds to a torus topologically. A more exciting scheme can be used on a hex grid that is in a hexagon shape. In this case, if you go out of one edge, you come out of the opposite edge. But unlike the parallelogram case, here you travel across the hex twice before you end up where you started. It's not so easy to see it, but this too corresponds topologically to a torus. The following figure shows how this works:
There are magic squares possible for any order, where all the numbers run from one to however many cells there are. But, except for the single cell, there is only one such magic hexagon possible (ignoring reflections and rotations).
Magic shapes that have all the integers in sequence starting from 1 are called normal. Abnormal magic shapes have numbers in sequence that start at a different integer. If we allow abnormal magic hexagons, then there are more possibilities.
Exactly 6 circles of the same radius as a given circle will fit around it snuggly. You would think that the same will happen with spheres ‚Äď a certain number will fit snuggly around a center one. However, this is not the case. We can fit 12, but there is a bit more space left, and it seems impossible to fit another one. (This is called the Kissing number problem.)¬†
The rhombic dodecahedral honeycomb is a tessellation of 3D space. It is the Voronoi diagram of the¬†face-centered cubic¬†sphere-packing, which is believed to be the densest possible packing of equal spheres in ordinary space. A face-centered sphere packing is how a bunch of balls (such as canon balls) will stack when you pack them. There is a question on this on gamedev.stackexchange.
For this reason hex-tetris does not work so well ‚Äď you cannot have a bar shape piece slide into a bar-shaped opening the way you can in square Tetris.
You can get around this problem by making the tiles a bit smaller than they need to be. Another solution is to use circles for the cells instead of hexes. Circles will touch, but still slide as is necessary in tile sliding games.
A hex grid and triangular grid are related as shown in the image below. The trick is to use a uniform coloring with 3 colors. One color corresponds to up-triangles, one color to down-triangles, and one color to vertices.
If you have not worked with triangular grids before, you may not immediately realise how this makes the math easier. Triangular grids are often coordinated in a clumsy way, so that it is not possible to perform vector calculations to answer simple geometric questions the way it is for hex grids and rectangular grids. For example, using the scheme where triangular grids are coordinated as shown below, it is not possible to have an "offset" vector for movement calculations. However, with the scheme of using a hex grid underneath, you can use the same elegant vector math for offsets, shape inequalities (such as explained here), and you can perform rotations and reflections using matrix multiplication. ¬†
Hex-shaped building blocks offer some interesting design possibilities. The two types of blocks are shown below.
With clever placement of the pins and sockets, it is possible to build blocks either "in phase" as is done with normal Lego blocks, or "out of phase".
The edges can be left open, so that pins can also be put into "half sockets".
It's also possible to make connector blocks so that square and hex blocks can be used together.
Yes, hex grids are not just for bees.
The house shown above is called the Queen B, and has been designed to protect humans against the weather and radiation of Mars. Here is a feature list of the building from the web site:
¬†The last point is particular relevant to games: hex buildings makes for easy promotion :-)¬†
This is sometimes inconvenient for two-player games.
It can however be done with any number of higher colors. The 3-color pattern is used in hex chess (http://en.wikipedia.org/wiki/Hexagonal_chess).¬† Bishop moves are designed so that they always stay on the same color in this pattern as they do in normal chess.
The closest you can come is by using 12 pentagons too. Semi-regular spheres like this are based on the icosahedron (the regular polyhedron with 20 triangles), see this video (via¬†@hamishtodd1):¬†
There are many different ways to build spheres from hexagons and pentagons, and chemist‚Äôs study them together with other fullerenes¬† (molecules of carbon in the shape of spheres, tubes, and so on).¬†
Cylinders, toruses and even Mobius strips can be composed from hexagons.
While you cannot build a sphere with only hexes, you can cheat it by making a torus or cylinder look like a sphere. One scheme is used by the game Antipod. You can read about how that works on their site.
Another scheme uses a wrapped hexagon (thus, a torus) morphed into hemispherical shape as we have done here.
The tiles in Tetris are called tetrominoes (four edge-to-edge squares per tile), and are a subset of polyominoes (any number of edge-to-edge squares per tile). The hex equivalent of a polyomino is called a polyhex.
There are many puzzles that use polyhexes. The most common type asks the player to build a given shape with a set of polyhexes. There is no known¬†formula for the number of polyhexes of a given order.
We harvested this question on gamedev.stackexchange for some of the pro's and cons:
Other (not necessarily regular) hexagons can also tile the plane. For convex hexagons, there are only three cases, given by the following conditions:
You can play with these tilings in this app (via¬†@mike_geogebra): http://www.geogebratube.org/student/m155779.
(For pentagons, no one knows all the pentagons that tile the plane! We know there are at least 14 types, but there may be more.)
These integers share many properties with real integers. For example, you have concepts of dividing evenly or with a remainder, and so you can define prime numbers, and hence build a complete number theory.
These integers can also be used in the implementation of certain algorithms, such as the colorings that form the building blocks of many other algorithms. See also:¬†http://math.stackexchange.com/questions/851136/are-there-2d-analogues-for-integer-division-and-modular-arithmetic
What this means is that any game played on the vertices of a triangular grid, instead of the faces, is really a game played on the faces of a hexagonal grid. This fact is useful for both game design and algorithm design. (If you implement Chinese checkers, you should use a hex grid, not a triangular grid for the logic!)
Many tile games are designed so that tiles match at edges so that larger shapes can be built. The number of tiles in such sets can be quite high. One way to solve this problem is to divide hexagons into triangles. This can drastically reduce the number of tiles needed. It's especially useful for computer games, where the triangles can be made totally invisible to the player.
The isometric projection of a cube is a hexagon. By dividing each cell into three quads, and using appropriate shading, the grid looks just like a stack of cubes. (If you consider each quad a cell, then the grid is a rhombille grid. Rhombille grids are also implemented using hex grids as a base.)¬†¬†
This fact has been exploited in many games. Q*bert is the first video game to do this, and was praised for its use of 3D at the time (1982).¬†
If you let hexagons overlap, you can create more interesting 3D effects. This has been exploited in card games like the ones shown below.