Blender Spheres

Island Invasion Tech III – Procedural Map Generation

One of the key features of Island Invasion is its procedural level generation. In non-tech speak, this means that each level is created by the game, rather than hand-designed, making each map different.

What is low-poly?

The term low-poly typically refers to a 3D model with a low polygon count. You may choose to create a low-poly model for a few reasons:

  • Models need to have a low polygon count for hardware purposes. You may have lots of the same model, or are targetting mobile, which has lower GPU bandwidth.
  • You don’t have the time/ skill to create higher polygon models. There’s no shame in this; like myself, you may specialise in something else, like programming.
  • The style is appealing. Games like Kingdoms and Castles looks beautiful using a low-poly style.

Low-poly can also refer to the “flat-shaded” style. This requires a more detailed and technical explanation. 3D models are made up of hundreds or likely thousands of polygons (in Unity, they’re broken down into triangles, as a triangle is always flat on one plane). When lighting is calculated, the direction of the lighting sources and the direction (normal) of each plane is used to work out its colour. So why can a low-poly sphere look smooth all over? Interpolation. The GPU works out a normal for each pixel on the screen (this is the fragment shader part, though shaders is another topic altogether). Remember the normal is a vector perpendicular to the “pixel”. It does this because you will not provide many vertices to the GPU, to save on memory. To better demonstrate, here is a render of two spheres in Blender:

Blender Spheres

A flat-shader sphere on the left, and a smooth shaded-sphere on the right.

Both spheres contain the same number of vertices, meaning they take up the same amount of space on disk and in GPU memory. However, the one on the right looks more like a sphere, because each pixel is using an interpolation of normals between vertices.

I’m aware reading back that a lot of this is using assumed knowledge about rendering, 3D math, and shaders. If you want to implement a low-poly style in your own game, I highly recommend learning more about these subjects. I’ll leave some links in the “Further Reading” at the bottom.

How do you do low-poly in Unity?

It depends on the type of mesh you’re using, though both share a common technique behind the scenes.

The key is to give the shader faces that do not share vertices. This way, it won’t interpolate all pixels sharing that vertex. This does result in a much higher mesh size, because we’re essentially going to duplicate each vertex for every face it is part of. In Unity at least, this is the only reliable way of creating a low-poly look.

If you’re importing a mesh from say a .obj file, you’ll want to use the Unity Editor to make it low-poly. When highlighting the imported model in its folder, observe the “Normals and Tangents” section in the Inspector:

Model inspector

Observing the “Copter” model in the Unity inspector.

This is the Copter model from Island Invasion. You can see that I’ve set the Normals to “Calculate”, and the Smoothing Angle to be zero. This has Unity recalculate the normals per-vertex, which will split the models faces up based on the smoothing angle. Imagine the smoothing angle as the angle between two faces at an edge. If the smoothing angle is smaller than the angle between the normals of two joined faces, they will be broken up into separate faces, not sharing vertices. When passed to the shader, these two faces will be shaded flat.

So for imported models, it’s actually really simple. Beware that the model size, and thus the number of vertices the GPU has to process, will be increased by this technique.

Smoothing comparison in Unity

Notice the difference is the number of vertices on screen – left, flat-shaded, right, smooth

The other way of creating meshes is procedurally – using code.

Procedural mesh generation in Unity

This is a topic fairly well covered elsewhere, but I’ll go over the basics. It’s worth noting that this does not cover the entity component system, though it’s likely the basic concepts are the same.

Unity uses two components to show a 3D mesh on screen: a MeshFilter and a MeshRenderer. The MeshFilter component contains the mesh data via its mesh property, including vertices, normals, and UVs (for textures). The MeshRenderer contains the data required to render the mesh out, which includes a MeshFilter component at least, but also a material, which determines how it looks on screen (colours, textures, shader, and so on).

For this, I’ll do everything in pseudocode, for simplicity. If you wanted to, you could create a prefab with these components attached, but in my opinion this is less verbose.

To start, we’ll do the following to set things up:

GameObject entity = new GameObject("Land", typeof(MeshFilter), typeof(MeshRenderer), typeof(MeshCollider));

The mesh is our target, as we want to create vertices to represent the mesh. For Island Invasion, this is how the maps are randomly generated, but you could use it for other things too, like clouds. Island Invasions maps are 96×96 “tiles” in size. A tile is a square on the map. We will need a way of generating a height at each vertex of the map; this is where a noise function comes in. A noise function creates pseudo-random noise, based on a function. Perhaps the most famous example is Perlin noise, which you will see a lot in things like Blender and Unity. Visualised as a “heightmap”, it looks a little like this:

Perlin noise visualisation

Perlin noise visualised (Wikipedia)

We can sample this noise at each point in “space”, by providing a 2D coordinate. This will be our X and Z position, which we will represent in code like this:

for (int x = 0; x < 96; x++)
{
    for (int z = 0; z < 96; z++)
    {
        float height = GetNoise(x, z);
        Vector3 position = new Vector3(x, height, z);
    }
}

We now have a position in space. To get this into the mesh, we will need to maintain an array of vertex data to assign to it at the end. We don’t do this every iteration of the loop as that would be extremely slow. The Mesh component also requires a triangles array. This is an array of indices into the vertex array, which make up a list of triangles to display on screen. Each three indices (e.g. 0, 1, and 2) make up a triangle, so we can fill this as we iterate.

We also want to make quads (squares), not triangles, as we’re making a grid to build on. Therefore we need to know four vertices, making up the four corners of the quad. We can still represent the quad using triangles – it will be split down the middle diagonally, which looks like this:

Quad

A quad, split diagonally into two triangles.

Put together, the code to populate the vertex and triangle arrays looks a little like this:

int triangleIndex = 0;

for (int x = 0; x < 96; x++)
{
    for (int z = 0; z < 96; z++)
    {
        Vector3 bl = new Vector3(x, GetNoise(x, z), z);
        Vector3 tl = new Vector3(x, GetNoise(x, z + 1), z + 1);
        Vector3 br = new Vector3(x, GetNoise(x + 1, z), z);
        Vector3 tr = new Vector3(x, GetNoise(x + 1, z + 1), z + 1);

        int arrayOffset = triangleIndex * 3;

        // four quad vertices
        vectors[arrayOffset] = bl;
        vectors[arrayOffset + 1] = tl;
        vectors[arrayOffset + 2] = br;
        vectors[arrayOffset + 3] = br;
        vectors[arrayOffset + 4] = tl;
        vectors[arrayOffset + 5] = tr;

        // bottom left triangle
        triangles[arrayOffset] = arrayOffset;
        triangles[arrayOffset + 1] = arrayOffset + 1;
        triangles[arrayOffset + 2] = arrayOffset + 2;

        // top right triangle
        triangles[arrayOffset + 3] = arrayOffset + 3;
        triangles[arrayOffset + 4] = arrayOffset + 4;
        triangles[arrayOffset + 5] = arrayOffset + 5;

        triangleIndex += 2;
    }
}

Note that we have to create 6 vertices, where the quad really only needs 4. This is the important step in making it look low-poly, or flat-shaded. The two other things to note are the index variables. Because we are creating quads with two triangles, we maintain a triangle index, which increases by 2 each iteration. The second index variable is the arrayOffset, which is an offset into the vertex and triangle arrays were are creating. This is used to work out the actual offset into the vertex and triangle arrays. Hopefully reading through it makes sense!

It’s worth mentioning that these arrays have a precalculated size, though you could just as easily use a generic List to add dynamically. This will be slower though as memory will need to be allocated whenever the size of the list change, and usually a native array will be quicker than a list when you know the indices. In our case, we need 6 vertices per quad, and are creating a 96×96 grid. So we need 96x96x6 array indices, which is 55,296. Seems like a lot, but for a decent PC this isn’t too hot to handle. We need the same number of triangle indices too, one per vertex, so that array would also be 55,296 in size.

The last thing to do is assign it to the Mesh, then the Mesh to the MeshRenderer:

mesh.SetVertices(vertices);
mesh.SetTriangles(triangles, 0);

mesh.RecalculateNormals();
mesh.RecalculateBounds();
mesh.RecalculateTangents();

meshFilter.mesh = mapMesh;

This finished things up! You may want to apply a material to the finished grid too, which you can do by assigning to MeshRenderer.material. Recalculating the normals, bounds, and tangents are all necessary to get the mesh showing properly on screen. For Island Invasion, it’s also a necessity in creating the MeshCollider, which is used for pathfinding. The result looks a bit like this:

Island Invasion map generation

The final map, admittedly with all the nice extras you get in Island Invasion!

Optimization
  • Chunking – rather than creating one large 96×96 size object, you can break it down into “chunks”. Meshes with too many vertices will not be rendered by Unity, so it is important to cut them down. As importantly, breaking the world into chunks allows you to cull (not render) bits of the map that aren’t on screen. This saves the GPU rendering unseen parts of the map offscreen, increasing performance.
  • Collapsing planes – it’s likely there are large, flat areas of the map. Because all normals are pointing the same direction anyway, you could “collapse” these faces, removing the unnecessary vertices between the corners of the plane. This is better explained with an image from Blender:
    Quad compare

    Both of these planes will look the same when rendered, but the one on the right has significantly fewer vertices.

    Given the variation in height in Island Invasion, this wasn’t worth the compromised in code complexity, as you no longer have 6 vertices per grid square. But if your game is pushing millions of vertices to the GPU, or is for mobile, you might want to consider collapsing flat planes.

  • Re-using arrays – this is an easy one: don’t re-create your data structures every time you create a new map! The size of the array will always be the same, so you can just re-use the array next time. The downside of this is that you have an array in memory you’re rarely using. For a simple vertex with just 3 coordinates (x, y, z), this would be at least 12 bytes per vertex (assuming each coordinate is represented by a 4-byte floating point number). For a 1024×1024 grid, using low-poly, that’s 72 (1024 x 1024 x 12 x 6, divided by 1024^2 for byte to megabyte conversion) megabytes of data doing nothing – on mobile, a crime!
Further Reading
Island Invasion sounds like an amazing game, where can I play it?

I’m glad you asked.

Check out Island Invasion’s page on this website, or if you’re super-keen, there’s a link to Steam below.