Generation of a hexagonal tessellation

• Download Hexagon.zip - 3.8 KB

Introduction

In this article I will design an algorithm to generate a hexagonal tessellation in a plane. After that, I will draw it using Unity3D

The Idea

The hexagons generation starts in a point which will be the centre. Then another loop of hexagon will surround the centre and this becomes the centre for a new loop of hexagons. The generation finishes when a given number of loops is reached.

In the following image, the original centre is coloured in red, the first loop in yellow and the second loop is green (and the centre for the second loop is formed by the red and yellow hexagons).

Inputs

Radius - The number of loops

Side - The length of the side of the hexagon.

Outputs

The algorithm can output the centre of every hexagon generated; however, in this implementation, we are going to use Unity3D to draw the hexagons.

The algorithm

The idea is to generate the centre for a new hexagon by looking at the last generated centre.

Let's start with a 2-dimensional euclidean space where we fix a point O to be the centre and the basis {(1,0), (0,1)} for our axes (a simple cartesian plane with orthogonal x and y axes). Note: we are going to use a 2-dimensional space for the algorithm, but we are going to generate the tessellation in a 3-dimensional space, therefore we need to take this into account during the implementation of the algorithm

We can start at point (0,0), which will be the centre of the first hexagon. Let's call S the side of the hexagon.

It is possible to generate all the centres for the hexagon in a "spiral" (see the image below: the darkest hexagon is the first, and the lightest is the last; in the middle, the shade of the hexagon represents the order of generation where darker means "generated before" and lighter means "generated after").

With this method of generation, to generate the point Pn it is enough to know the coordinates of the point Pn-1 and then do Pn =<sub> </sub>Pn-1 + (a,b) where (a,b) is a couple that can be easily found by remembering the properties of hexagons:

So, the possible couples (a,b) are:

• DR - (1.5, -sq3/2)
• DX - (0, -sq3)
• DL - (-1.5, -sq3/2)
• UL - (-1.5, sq3/2)
• UX - (0, sq3)
• UR - (1.5, sq3/2)

Where: sq3 = sqrt(3)  and U/D -> direction UP/DOWN and L/X/R -> direction LEFT/NONE/RIGHT

So, in order to generate the "hexagonal spiral" of centres from the centre (0, 0) we need to do the following actions.

nDR - nDX - nDL - nUL - nUX - UX - Exit? - nUR

where n is the current loop number and n<action> means "generate a hexagon in the current centre, add to the previous centre the couple corresponding to action multiplied by the length of the side of a hexagon, and repeat n times". Exit? means that if the number of So, to generate the first hexagon:

0DR - 0DX - 0DL - 0UL - 0UX - UX - Exit? - 0UR --> UX (generates a hexagon at (0, 0) and moves UP so that the next centre is (0, sq3 * s) where s is the length of the side of the hexagon).

The first loop of hexagons:

1DR - 1DX - 1DL - 1UL - 1UX - UX - Exit? - 1UR

which, starting from the previous centre (0, sq3 * s), generates 6+1 hexagons at

• (0, sq3 * s)
• (1.5*s, sq3*s/2)
• (1.5*s, -sq3*s/2)
• (0, -sq3*s)
• (-1.5*s,-sq3*s/2)
• (-1.5*s,sq3*s/2)
• (-1.5*s,3*sq3*s/2)

Leaving the centre at (0, 2*sq3*s)

The next image shows the first 19 centres generated by the algorithm

Unity implementation

The algorithm is really easy to implement in C#:

using UnityEngine;

public class GenerateHexFloor : MonoBehaviour {

    public GameObject Hexagon;
    public uint Radius;
    public float HexSideMultiplier = 1;

    private const float sq3 = 1.7320508075688772935274463415059F;

    // Use this for initialization
    void Start () {
        //Point of the next hexagon to be spawned
        Vector3 currentPoint = transform.position;

        if (Hexagon.transform.localScale.x != Hexagon.transform.localScale.z)
        {
            Debug.LogError("Hexagon has not uniform scale: cannot determine its side. Aborting");
            return;
        }

        //Spawn scheme: nDR, nDX, nDL, nUL, nUX, End??, UX, nUR
        Vector3[] mv = {
            new Vector3(1.5f,0, -sq3*0.5f),       //DR
            new Vector3(0,0, -sq3),               //DX
            new Vector3(-1.5f,0, -sq3*0.5f),      //DL
            new Vector3(-1.5f,0, sq3*0.5f),       //UL
            new Vector3(0,0, sq3),                //UX
            new Vector3(1.5f,0, sq3*0.5f)         //UR
        };

        int lmv = mv.Length;
        float HexSide = Hexagon.transform.localScale.x * HexSideMultiplier;

        for (int mult = 0; mult <= Radius; mult++)
        {
            int hn = 0;
            for (int j = 0; j < lmv; j++)
            {
                for (int i = 0; i < mult; i++, hn++)
                {
                    GameObject h = Instantiate(Hexagon, currentPoint, Hexagon.transform.rotation, transform);
                    h.name = string.Format("Hex Layer: {0}, n: {1}", mult, hn);
                    currentPoint += (mv[j] * HexSide);
                }
                if (j == 4)
                {
                    GameObject h = Instantiate(Hexagon, currentPoint, Hexagon.transform.rotation, transform);
                    h.name = string.Format("Hex Layer: {0}, n: {1}", mult, hn);
                    currentPoint += (mv[j] * HexSide);
                    hn++;
                    if (mult == Radius)
                        break;      //Finished
                }
            }
        }
    }

}

Comments

Having the idea ready, writing the code was very very easy. I would just like to comment some of the implementation choices I made.

First of all, for anybody that does not know how Unity 3D works, basically each public field of a class that inherits from MonoBehaviour can be set from the editor and used as an input field, so that each instance of the class can have its own parameters easily set from the editor. So I asked for the 3D model of a hexagon (you can find one attached to this article, modeled using Blender 3D), for the radius of the tessellation, and the field HexSideMultipler is for multiply the length of the side of the hexagon by a constant. I get the length of the side of the hexagon by looking at the scale of the model (that's why I ask the x and z scaling to be the same).

Then I start from the origin point of the gameObject I attach the script to: in Unity each class that inherits from MonoBehaviour can be attached to any GameObject. In this case, this GameObject is a simple point in the 3D space that provides x, y and z coordinates. So I build the hexagon tessellation starting from that point.

The rest of the code, provided the idea that I explained before is self-explanatory: I just generate each centre for the hexagons starting from the previous point (which I called currentPoint). I spawn each hexagon (using the Instantiate method) and then I calculate the next point.

Points of Interest

Although it might seems that this algorithm is not efficient because it contains three nested for loops, it is optimal because we do one iteration for each hexagon. The nested loops come from the fact that if the tessellation has radius R it does not mean that there are R total hexagons!

Gist

I previously published this code in a gist that is not explained as deep as it is here. If you want to visit the gist, here's the link: https://gist.github.com/LuxGiammi/8c1e17feecf7d3c33a1a493657a4d153