Hex Math (for Hex Grid Games)
I few weeks ago I decided to write down a summary of the math necessary to do geometry on a hex grid.
If you want to have a look, it is here; I would appreciate any feedback (in particular whether the math is clear enough).
(This will only be helpful if you already know how vectors are used in normal 2D geometry; it does not introduce those concepts from scratch):
http://www.gamelogic.co.za/downloads/HexMath2.pdf
The rest of this post is to give you some idea of what is in it.
If you worked implemented your own hex algorithms before, you will know that if you choose the right coordinate system, the basics work out pretty much the same as for a square system: you can use vectors as offsets from one point to another; there is a distance formula for calculating how many hexes you have to cross to get from one hex to another; you can use simple transformations to do rotations and reflections.
I have made dozens of hex grid games, and have helped many people with their (often very unique) algorithms, and a few questions came up that was not answered by the (very little) information out there. Here are some of them to give you an idea.
A star has the equation min(max(x, y, z), max(-x, -y, -z)) <= r (r is the "radius" of the star, and z is an auxiliary coordinate we use throughout for -x-y)
Calculating hexagonal partitions.
How to calculate colorings such as these.
Representing a triangular grid using a hex grid allows you to work on a tri grid using all the same math. This is one use of the coloring shown above.
Representing a rhombille grid using a hex grid is the same trick.
How to iterate through the grid to preserve spatial coherence.
Using the traversal above with 1D correlated noise gives us a cheap way to implement generation algorithms that can produce images like this.
If you want to have a look, it is here; I would appreciate any feedback (in particular whether the math is clear enough).
(This will only be helpful if you already know how vectors are used in normal 2D geometry; it does not introduce those concepts from scratch):
http://www.gamelogic.co.za/downloads/HexMath2.pdf
The rest of this post is to give you some idea of what is in it.
If you worked implemented your own hex algorithms before, you will know that if you choose the right coordinate system, the basics work out pretty much the same as for a square system: you can use vectors as offsets from one point to another; there is a distance formula for calculating how many hexes you have to cross to get from one hex to another; you can use simple transformations to do rotations and reflections.
I have made dozens of hex grid games, and have helped many people with their (often very unique) algorithms, and a few questions came up that was not answered by the (very little) information out there. Here are some of them to give you an idea.
- Are there nice equations for common shapes? (Nice equations that can result in efficient implementations).
- The dot and perp dot products are used in square math to bypass trigonometry. One of the useful checks that use this is to determine whether a point lies in a half-plane or not, which is used to check whether a point belongs to a cone or polygon or not. So I wondered if there was a analogue for hex math; operations that can be performed on coordinates to avoid having to explicitly calculate the angle between vectors.
- We use quick calculations to construct quadtrees, or sample grids at lower resolutions (this is used to generate noise that can be used in procedural landscape generation, for example). How do we do these calculations on a hex grid?
- Is there a better way to work with triangular grids? (Vectors as displacements do not work directly on triangular grids).
- How do we transfer maze generation algorithms to hex grids? (Many of the square algorithms rely on the fact that we can easily represent edges - the walls - on a square grid.)
A star has the equation min(max(x, y, z), max(-x, -y, -z)) <= r (r is the "radius" of the star, and z is an auxiliary coordinate we use throughout for -x-y)
Calculating hexagonal partitions.
How to calculate colorings such as these.
Representing a triangular grid using a hex grid allows you to work on a tri grid using all the same math. This is one use of the coloring shown above.
Representing a rhombille grid using a hex grid is the same trick.
How to iterate through the grid to preserve spatial coherence.
Using the traversal above with 1D correlated noise gives us a cheap way to implement generation algorithms that can produce images like this.
star.png
1458 x 730 - 433K
partition_hex.png
1426 x 714 - 523K
trigrid.png
1466 x 734 - 506K
rhombgrid.png
1466 x 734 - 570K
gosper.png
1096 x 1096 - 210K
coloring3.png
744 x 744 - 105K
landscape1.png
1096 x 1096 - 390K
coloring4.png
744 x 744 - 107K
Comments
---
There is also a new image explaining how the hexagonal wrapping fits onto a torus.