Project TWA – Part 1: Generating a hexagonal tile and it’s triangular grid

Introduction

Fig. 1: Single map cell triangular grid

This is an idea I’ve been working on in my mind for quite some time now and finally decided to start working on it; I want an exploration kinda game, taking place on a hexagonal grid, where the world gets procedurally generated as you explore it.

In general lines it should work like this: Each time you step on a tile the system should check if it was generated before (player already explored it) generating it’s mesh based on some values. If the tile has not been explored yet, we get to generate it procedurally. I really love procedurally generated stuff and I want to be able to do the tile’s elevation, vegetation, rock formations resources, etc, procedurally. But we still got a long way for that. The idea is though to generate those values (the tile’s properties) once and use them to generate the cell geometry when needed. Same values should result in the exact same cell every time.

So let’s start with the basics: To be able to do all that fancy stuff we need to create a tile (a hexagon) and to be able to play around with the elevation of that tile we’ll need to split its mesh into triangles. To create a tile and it’s grid we want to be able to specify how big it should be (let’s call this input Radius) and how many triangles its grid should have. For the latter we’ll use Subdivisions, which basically specifies how many times we should split our tile’s grid. This should be more than enough to generate our tile and it’s grid.

Initially I looked around the web to find something that would do what I wanted (as I’m a lazy bastard) but I couldn’t find anything so I decided to do it myself and it actually was a lot easier than I expected…

The mathematics behind it

Our tile is a hexagon and it’s grid is consisted of triangles. To be able to construct a grid we need two things: vertex coordinates (x, y) for our vertex buffer and triangle indices for our index buffer. The vertex coordinates specify where a point is in XYZ space and the indices specify the points that generate a triangle. Take a look at Fig.2, we’ve got the vertices 0 (0, 0), 1 (0.866, 0.5) and 2 (0, 1) and from those points we can create the triangle 0-1-2.

So we need a way to calculate the point coordinates depending on the values or R and S. Fortunately hexagons have some interesting properties [1] making this fairly simple. Let’ take a look at the figure below.

Fig. 2: Hexagon triangular grid geometry

Calculating vertex coordinates

A hexagon is consisted of six equilateral triangles (all angles $60^0$ , all sides equal). $P_0P_1P_2$ in fig. 2 is one of them. We can see that $\|P_0P_1\| = \|P_1P_2\| = \|P_0P_2\| = R$ . We know that the angle between $P_0P_1, P_0P_2$ is 60 degrees. Knowing that calculating P1 coordinates is easy using basic trigonometric functions.

We can notice that the points of the grid are the result of line intersections. For example P0 is the result of $fB_0 \perp fA_0$ , P1 $fB_0 \perp fA_3$ and P2 $fB_3 \perp fA_0$ . So we need to find the right fA and fB line equations depending $Col_i$ and $Row_i$ . We’ll use $Col_id$ and $Row_id$ to iterate through fA and fB respectively.

For fB the line equation will be given by $y=m \times x + b, where\ m=\Delta y / \Delta x \ and\ b: y-intercept$ . S divides R in equal parts, so the y for points P0, P3, P4 and P2 will be given by $y=\frac{R}{S} \times Row_i$ . Reflecting those points over x we get the points on negative y. Those values are our y-intersect for fB given $Row_i$ .

To calculate the slope m we just need to do $m = \frac{\Delta y}{\Delta x} = \frac{cos(\frac{\pi}{3})}{sin(\frac{\pi}{3})} = \frac{1}{tan(\frac{\pi}{3})}$ . So our fB, given $Row_i$ is:

$fB_{Row_i}\ y = \frac{1}{tan(\frac{\pi}{3})} \times x + \frac{R}{S} \times Row_i \ (1)$ .

fA is parallel to x, having an equation $x=A, where\ A:\ a\ constant\ value$ .

We know that $\|P_0P_1\| = \|P_0P_2\| = R$ , x coordinate of P1 is given by $x = \sin({\pi}{3}) \times R$ and that we can divide R in equal parts using S with $y=\frac{R}{S} \times Col_i$ . So our fA will be:

$fA_{Col_i}\ x= \sin(\frac{\pi}{3}) \times \frac{R}{S} \times Col_i \ (2)$ .

Intersecting (1) and (2) we end up with:

$P_{[Col_i, Row_i]} = (\sin(\frac{\pi}{3}) \times \frac{R}{S} \times Col_i, \frac{1}{tan(\frac{\pi}{3})} \times x_{Col_i, Row_i} + \frac{R}{S} \times Row_i) (3)$ . Which gives us a point coordinates given $Col_i, Row_i$ .

Now we need a way to iterate through $Col_i, Row_i$ to get only the points we need.

We notice that each $fA_{Col_i}$ produces a different amount of points. So, fA(-3) and fA(3) will generate 4 points, fA(-2), fA(2) 5 points, fA(-1), fA(1) 6 points and fA(0) 7 points. As we move away from fA(0) the number of points is reduced by one. Thus:

$NP_{Col_i} = NP_{Col_0} - \lvert Col_i \lvert \ (4)$ and $NP_{Col_o} = 2 \times S + 1 \ (5)$ .

For $Col_i$ we’ll iterate through [-S, S], $Min_{Col_i}=-S\ (6_a), Max_{Col_i}=S\ (6_b)$ .

For each $Col_i$ we need to find $Min_{Row_i}$ and $Max_{Row_i}$ so we can get the right $fB_{Row_i}$ to intersect with our $fA_{Col_i}$ . For fA where $Col_i = [0, S]$ we can see that $Min_{Row_i} = -S$ , but when $Col_i < 0$ then $Min_{Row_i}$ is increased by $\lvert Col_i \lvert$ . We end up with:

$Min_{Row_i}=\begin{cases} -S+\lvert Col_i \lvert, \text{if } Col_i<0 \\ -S, \text{if } Col_i \geq 0 \end{cases} \ (7_a)$ .

$Max_{Row_i} = Min_{Row_i} + NP_{Col_i} - 1 \ (7_b)$ .

Knowing all that, iterating through rows and columns and calculating the coordinates given $Col_i, Row_i$ should be fairly simple.

Constructing the triangles

Fig.3: Triangle grid construction using vertex indices.

Iterating through $Col_i$ and $Row_i$ generating a vertex (x, y, z) for each $(Col_i, Row_w)$ results in the grid shown in fig.3. To create a mesh out of these points, we need to combine them into triangles. We observe that we can construct a triangle combining 2 points on a column and a point from a column left or right. So for $Col_{-3}$ we can create the triangles 0-1-5, 1-2-6 and 2-3-7, combining 2 vertices from $Col_{-3}$ with a vertex from $Col_{-2}$ to the right. For $Col_{-2}$ we get 4-5-10, 5-6-11, 6-7-12 and 7-8-13 combining 2 vertices with a vertex from $Col_{-1}$ on the right while 4-5-0, 5-6-1, 6-7-2 and 7-8-3 combining the same vertices with a vertex from $Col_{-3}$ on the left.

So, given a $Col_i$ we can generate $NP_{Col_i} - 1$ triangles to the left and to the right if $Col_i$ is in (-S, S) . If $Col_i = -S \ or\ S$ , meaning that it’s a point on an edge, then we can only create that many triangles to left or to the right. Therefore given a vertex index $V_{index}$ at $(Col_i, Row_i)$ we can create triangles as follows:

Triangles right from this column:

$(V_{index}, V_{index} + 1, V_{index} + NP_{Col_i} + P), P=1\ if\ Col_i<0, otherwise\ P=0$ ,

and left:

$(V_{index} + 1, V_{index}, V_{index} - NP_{Col_i-1} + P), P=1\ if\ Col_i>0, otherwise\ P=0$ .

Finally we’ll need to calculate the number of vertices and indices so we can allocate our buffers.

$N_{Vertices}=1 + \sum \limits_{i=1}^S (6\times i)$

$N_{Indices}=\sum \limits_{i=1}^S (36\times i-18)$

The code

Here’s the C# code I use in Unity to generate the cell in Fig. 1.

void generateGrid(ref Mesh rMesh)
{
	// We'll need those later to generate our x, z coordinates
	float sin60     = Mathf.Sin(Mathf.PI / 3);
	//float tan60     = ;
	float inv_tan60 = 1/ Mathf.Tan(Mathf.PI / 3);
	float RdS       = mRadius / mSubdivisions;              // R / S


	// Calculate number of vertices we need to generate
	// num_vertices = 1 + Σ {S, i=1} (i*6)
	int num_vertices = 1;
	for (int i = 1; i <= mSubdivisions; i++)
		num_vertices += i * 6;

	// Allocate our vertex buffer
	int vertices_index = 0;
	Vector3[] vertices = new Vector3[num_vertices];

	// Calculate number of indices we need to generate
	// num_indices = Σ {S, i=1} (36*i - 18)
	int num_indices = 0;
	for (int i = 1; i <= mSubdivisions; i++)
		num_indices += 36 * i - 18;

	// Allocate our index buffer
	int indices_index   = 0;
	int[] indices       = new int[num_indices];

	// We'll need those to calculate our indices
	int current_num_points  = 0;
	int prev_row_num_points = 0;

	// [col_min, col_max]
	int np_col_0	= 2 * mSubdivisions + 1;
	int col_min		= -mSubdivisions;
	int col_max		= mSubdivisions;

	//
	// Now let's generate the grid
	// First we'll iterate through the Columns, starting from the bottom (fA)
	for (int itC = col_min; itC <= col_max; itC++)
	{
		// Calculate z for this row
		// That's the same for each point in this column
		float x = sin60 * RdS * itC;

		// Calculate how many points (z values) we need to generate on for this column
		int np_col_i = np_col_0 - Mathf.Abs(itC);

		// [row_min, row_max]
		int row_min = -mSubdivisions;
		if(itC < 0)
			row_min += Mathf.Abs(itC);
			
		int row_max = row_min + np_col_i - 1;

		// We need this for the indices
		current_num_points += np_col_i;

		// Iterate through the Rows (fB)
		for (int itR = row_min; itR <= row_max; itR++)
		{
			// Calculate z
			float z = inv_tan60 * x + RdS * itR;

			vertices[vertices_index] = new Vector3(x, 0, z);

			// Debug
			//Debug.Log("[" + itC + ", " + itR + "] " + vertices[vertices_index]);

			//
			// Indices
			// From each point we'll try to create triangles left and right
			if (vertices_index < (current_num_points - 1))
			{
				// Triangles left from this column
				if (itC >= col_min && itC < col_max)
				{
					// To get the point above
					int pad_left = 0;
					if (itC < 0)
						pad_left = 1;

					//string dbg = "(";
					//dbg += vertices_index;	// Debug
					indices[indices_index] = vertices_index;
					indices_index++;

					//dbg += vertices_index + 1;	// Debug
					indices[indices_index] = vertices_index + 1;
					indices_index++;

					//dbg += vertices_index + np_col_i + pad_left;	// Debug
					indices[indices_index] = vertices_index + np_col_i + pad_left;
					indices_index++;

					//Debug.Log(dbg + ")");
				}

				// Triangles right from this column
				if (itC > col_min && itC <= col_max)
				{
					// To get point bellow
					int pad_right = 0;
					if (itC > 0)
						pad_right = 1;

					//string dbg = "(";
					//dbg += vertices_index;	// Debug
					indices[indices_index] = vertices_index + 1;
					indices_index++;

					//dbg += vertices_index;	// Debug
					indices[indices_index] = vertices_index;
					indices_index++;

					//dbg += vertices_index;	// Debug
					indices[indices_index] = vertices_index - prev_row_num_points + pad_right;
					indices_index++;
					//Debug.Log(dbg + ")");
				}
			}

			// Next vertex...
			vertices_index++;
		}

		// Store the previous row number of points, used to calculate the index buffer
		prev_row_num_points = np_col_i;
	}

	// Store to mesh
	rMesh.vertices  = vertices;
	rMesh.triangles = indices;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

void generateGrid(ref Mesh rMesh)

{

// We'll need those later to generate our x, z coordinates

float sin60 = Mathf.Sin(Mathf.PI / 3);

//float tan60 = ;

float inv_tan60 = 1/ Mathf.Tan(Mathf.PI / 3);

float RdS = mRadius / mSubdivisions; // R / S

// Calculate number of vertices we need to generate

// num_vertices = 1 + Σ {S, i=1} (i*6)

int num_vertices = 1;

for (int i = 1; i <= mSubdivisions; i++)

num_vertices += i * 6;

// Allocate our vertex buffer

int vertices_index = 0;

Vector3[] vertices = new Vector3[num_vertices];

// Calculate number of indices we need to generate

// num_indices = Σ {S, i=1} (36*i - 18)

int num_indices = 0;

for (int i = 1; i <= mSubdivisions; i++)

num_indices += 36 * i - 18;

// Allocate our index buffer

int indices_index = 0;

int[] indices = new int[num_indices];

// We'll need those to calculate our indices

int current_num_points = 0;

int prev_row_num_points = 0;

// [col_min, col_max]

int np_col_0 = 2 * mSubdivisions + 1;

int col_min = -mSubdivisions;

int col_max = mSubdivisions;

// Now let's generate the grid

// First we'll iterate through the Columns, starting from the bottom (fA)

for (int itC = col_min; itC <= col_max; itC++)

{

// Calculate z for this row

// That's the same for each point in this column

float x = sin60 * RdS * itC;

// Calculate how many points (z values) we need to generate on for this column

int np_col_i = np_col_0 - Mathf.Abs(itC);

// [row_min, row_max]

int row_min = -mSubdivisions;

if(itC < 0)

row_min += Mathf.Abs(itC);

int row_max = row_min + np_col_i - 1;

// We need this for the indices

current_num_points += np_col_i;

// Iterate through the Rows (fB)

for (int itR = row_min; itR <= row_max; itR++)

{

// Calculate z

float z = inv_tan60 * x + RdS * itR;

vertices[vertices_index] = new Vector3(x, 0, z);

// Debug

//Debug.Log("[" + itC + ", " + itR + "] " + vertices[vertices_index]);

// Indices

// From each point we'll try to create triangles left and right

if (vertices_index < (current_num_points - 1))

{

// Triangles left from this column

if (itC >= col_min && itC < col_max)

{

// To get the point above

int pad_left = 0;

if (itC < 0)

pad_left = 1;

//string dbg = "(";

//dbg += vertices_index; // Debug

indices[indices_index] = vertices_index;

indices_index++;

//dbg += vertices_index + 1; // Debug

indices[indices_index] = vertices_index + 1;

indices_index++;

//dbg += vertices_index + np_col_i + pad_left; // Debug

indices[indices_index] = vertices_index + np_col_i + pad_left;

indices_index++;

//Debug.Log(dbg + ")");

}

// Triangles right from this column

if (itC > col_min && itC <= col_max)

{

// To get point bellow

int pad_right = 0;

if (itC > 0)

pad_right = 1;

//string dbg = "(";

//dbg += vertices_index; // Debug

indices[indices_index] = vertices_index + 1;

indices_index++;

//dbg += vertices_index; // Debug

indices[indices_index] = vertices_index;

indices_index++;

//dbg += vertices_index; // Debug

indices[indices_index] = vertices_index - prev_row_num_points + pad_right;

indices_index++;

//Debug.Log(dbg + ")");

}

// Next vertex...

vertices_index++;

}

// Store the previous row number of points, used to calculate the index buffer

prev_row_num_points = np_col_i;

}

// Store to mesh

rMesh.vertices = vertices;

rMesh.triangles = indices;

}

References

1. An Introduction to Hexagonal Geometry – hexnet.org

Be Sociable, Share!

VoidInSpace

I make games. Video games.

Generating a hexagonal tile and its triangular grid

Introduction

The mathematics behind it

The code

References

One Comment

Leave a Reply Cancel reply