## Introduction

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.

**Calculating vertex coordinates**

A hexagon is consisted of six equilateral triangles (all angles , all sides equal). in fig. 2 is one of them. We can see that . We know that the angle between 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 , **P1** and **P2** . So we need to find the right **fA** and **fB** line equations depending and . We’ll use and to iterate through **fA** and **fB** respectively.

For **fB** the line equation will be given by . **S** divides **R** in equal parts, so the y for points **P0**, **P3**, **P4** and **P2** will be given by . Reflecting those points over x we get the points on negative y. Those values are our y-intersect for **fB** given .

To calculate the slope **m** we just need to do . So our **fB**, given is:

.

**fA** is parallel to x, having an equation .

We know that , x coordinate of **P1** is given by and that we can divide **R** in equal parts using **S** with . So our **fA** will be:

.

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

. Which gives us a point coordinates given .

Now we need a way to iterate through to get only the points we need.

We notice that each 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:

and .

For we’ll iterate through [-S, S], .

For each we need to find and so we can get the right to intersect with our . For **fA** where we can see that , but when then is increased by . We end up with:

.

.

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

**Constructing the triangles**

Iterating through and generating a vertex (x, y, z) for each 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 we can create the triangles 0-1-5, 1-2-6 and 2-3-7, combining 2 vertices from with a vertex from to the right. For we get 4-5-10, 5-6-11, 6-7-12 and 7-8-13 combining 2 vertices with a vertex from 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 on the left.

So, given a we can generate triangles to the left and to the right if is in (-S, S) . If , 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 at we can create triangles as follows:

Triangles right from this column:

,

and left:

.

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

## The code

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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; } |

Project Polis (Dev Journal #1): Generating the hexagon grid | Polis – Dev Blog

[…] constructing a tile using the triangular grid found in this post I wrote a long time ago, which allows us to specify the tile’s size and the number of […]