Voxel Engine Part3 – Culling, HUD and the source

So we now have a randomly-generated world filled with cube. Cool! I’m pretty happy of the outcome. However, there are way too many gameobject being drawn and the FPS drop quite low easily. We now need to do some culling to only draw what is in front of us.

Unity already does a bit of culling for us, it doesn’t draw object that are not in your sight of view! However, we need to determine ourselves what we want to be drawn on the camera view. In the code we have so far, we draw all of the cube. An easy way to remove a lot of cube is to avoid drawing cube that are enclosed by 6 cubes around it. There is no way such a cube will ever be seen by the user. This isn’t really hard to do, before drawing a cube, you look around it in the blocksArray. If all cube around it are solid, don’t draw it. In my code, I decided to not create the object at all. This will easier to process for now.

I also added a small GUI to the project. When you press F1, you can see some information about the cube being created and the cube being occluded. This allow to see the number of cube being removed. Here are the hotkey :

F1 – See information on cubes

Q – Generate and draw the cubes

R – Remove all the cubes

Z – Turn Culling ON/OFF, can be interesting to test.

I added the Voxel Engine on GitHub. It contains the whole Unity Project. You can find the project as it is at the end of this part here. The master branch will hold the up-to-date version of the project.

If you just want the code-source without the rest of the Unity’s Project, here it is! However, you will need to create the Unity project yourself. Just put PlayerHUD and CubeGeneration.cs on the __GameMaster GameObject and it will work fine. You can change the size of the area created in Chunk.cs  Have Fun!

Voxel Engine Part2 – Height map and Perlin Noise

So let’s look at the GamePlan from Part 1 :

  1. Setup a basic environment
  2. Create and texture a cube
  3. Display a bunch of cube
  4. Create a 3D array containing the information of all cube
  5. Fill the 3D array and display it
  6. Use a Perlin Noise algorithm to generate a coherent random world

We’ve got a couple of things done, but we still have a lot to do!! We finished Part 1 with a prism of cube displayed on the screen. However, we don’t know which cube is where and how to interact with them, they are just being displayed on the screen. To achieve this, we’ll make a 3D array that contain the blocktype of each cube, and we will draw them.

4.Create a 3D array containing the information of all cube

For this, I decided to create a new Class called Chunk. A chunk in minecraft, the most popular Voxel Engine, is a block of 16x64x16 cubes. When you move in the game, you keep loading/saving chunks and exchange them between your hard disk and your RAM. Right now, we will only work with 1 chunk and it will hold the information of it’s size itself, something that might eventually changes. Create a new C# script, call it Chunk.cs and add the following code to it :

using UnityEngine;
using System.Collections;
using System.Collections.Generic; // For List class;

public class Chunk
{

  // Size of the Chunk
  public int sizeX = 25;
  public int sizeY = 15;
  public int sizeZ = 25;

  // Declare the 3D block Array
  public int[,,] blocksArray;

  // Initialize the block array
  public void Initialize()
  {
    blocksArray = new int[sizeX, sizeY, sizeZ];
  }
}

I know I could use List to have resizable array. However, the size won’t change after the chunk is created and List seems to bring a small overhead that I’d like to avoid since we’ll work with lots of cube.

5.Fill the 3D array and display it

In CubeGeneration.cs, let’s initialize a Chunk, fill it with random cubes and display it. I got rid of the CreatePrism function because we won’t need it anymore. Here is the up-to-date version of cubeGeneration.cs :


using UnityEngine;
using System.Collections;

public class CubeGeneration : MonoBehaviour {

public GameObject CubeGrass;
public GameObject CubeRock;
public GameObject CubeSand;

private Chunk _CurChunk;

// Use this for initialization
 void Start ()
 {
// Create a Chunk
_CurChunk = new Chunk(); // Instantiate a new Chunk
_CurChunk.Initialize(); // Initialize its blockArray
   FillChunk(); // Fill the _CurChunk with blocktype
   AddChunk(); // Add all the cube to the current scene
 }

// Randomly fill the chunk
 void FillChunk()
 {
  int maxHeight = _CurChunk.sizeY;

  int _curHeight;

  for(int i = 0; i < _CurChunk.sizeX; i++)
  {
    for(int k = 0; k < _CurChunk.sizeZ; k++)
    {
      _curHeight = Random.Range (0,_CurChunk.sizeY+1); // I use _CurChunk.sizeY + 1 since it is exclusive

      // Fill blocksArray with different value according to the height of the block
      for(int j = 0; j < _curHeight; j++)
      {
        if(j == _curHeight - 1)
          _CurChunk.blocksArray[i,j,k] = 1; // Grass
        else if(j == _curHeight - 2)
          _CurChunk.blocksArray[i,j,k] = 3; // Sand
        else
          _CurChunk.blocksArray[i,j,k] = 2; // Rock
      }
    }
  }
}

// Create a cube of the right type for each entry of the blocksArray
 void AddChunk()
 {
   for(int i = 0; i < _CurChunk.sizeX; i++)
   {
     for(int j = 0; j < _CurChunk.sizeY; j++)
     {
       for(int k = 0; k < _CurChunk.sizeZ; k++)
       {
         if(_CurChunk.blocksArray[i,j,k] != 0)
         {
           CreateCube(i,j,k, _CurChunk.blocksArray[i,j,k]);
         }
       }
     }
   }
 }

// Create a Cube at the inputted position with a texture matching the blockType
 void CreateCube(int _posX, int _posY, int _posZ, int _blockType)
 {
   GameObject _CurCube = CubeRock; //Local variable that only remember the good prefab to be displayed

   // _blockType is inputted as an integer. 1 = Grass, 2 = Rock, 3 = Sand
   if(_blockType == 1)
     _CurCube = CubeGrass;
   else if(_blockType == 2)
     _CurCube = CubeRock;
   else if(_blockType == 3)
     _CurCube = CubeSand;

  // Instantiate a new cube at the inputted position, facing identity
   GameObject.Instantiate(_CurCube, new Vector3(_posX, _posY, _posZ), Quaternion.identity);
   }
 }

If you hit play, you should get something like this : 6 - RandomChunk

Fig1 – Displayed cube from a randomly generated Heightmap

6.Use a Perlin Noise algorithm generate a coherent random world

Having all those cube randomly generated is pretty cool, but it won’t make for a nice level. This is where Perlin noise come to the rescue! Perlin noise give you a random coherent array. To make a short story, perlin noise stack different noise together. The low frequency noise will give mountain and valleys  and the high frequency noise will give it some kind of roughness to the terrain. Look at this link for a technical definition.[Edit: As pointed by Carlos in the comments, this link is for Value Noise but give a good idea of perlin noise] If you’re interested in going deeper with Perlin noise, look at Simplex noise which is an updated version of Perlin noise.

I thought about implementing it myself at first. However,  a quick google search gave me a nice and ready C# implementation so I’d figure it’d be quicker to use it. Here is a link to the the page explaining the implementation. Here is another link that helped while debugging it. I cleaned the code a bit and implemented it in a C# script called PerlinNoise.cs. 

using System;
using System.Collections.Generic;
using System.Text;

public class PerlinNoise
  {
  static Random random = new Random();

  // Tools
  public static T[][] GetEmptyArray(int width, int height)
  {
    T[][] image = new T[width][];

    for (int i = 0; i < width; i++)
    {
      image[i] = new T[height];
    }
    return image;
 }

 public static float Interpolate(float x0, float x1, float alpha)
   {
     return x0 * (1 - alpha) + alpha * x1;
   }

// Perlin Noise Generation
 public static float[][] GenerateWhiteNoise(int width, int height)
 {
   float[][] noise = GetEmptyArray(width, height);

    for (int i = 0; i < width; i++)
    {
      for (int j = 0; j < height; j++)
      {
        noise[i][j] = (float)random.NextDouble() % 1;
      }
    }
 return noise;
 }

public static float[][] GenerateSmoothNoise(float[][] baseNoise, int octave)
 {
   int width = baseNoise.Length;
   int height = baseNoise[0].Length;

   float[][] smoothNoise = GetEmptyArray(width, height);
   int samplePeriod = 1 << octave; // calculates 2 ^ k
   float sampleFrequency = 1.0f / samplePeriod;

for (int i = 0; i < width; i++)
  {
  //calculate the horizontal sampling indices
  int sample_i0 = (i / samplePeriod) * samplePeriod;
  int sample_i1 = (sample_i0 + samplePeriod) % width; //wrap around
  float horizontal_blend = (i - sample_i0) * sampleFrequency;

  for (int j = 0; j < height; j++)
  {
    //calculate the vertical sampling indices
    int sample_j0 = (j / samplePeriod) * samplePeriod;
    int sample_j1 = (sample_j0 + samplePeriod) % height; //wrap around
    float vertical_blend = (j - sample_j0) * sampleFrequency;

    //blend the top two corners
    float top = Interpolate(baseNoise[sample_i0][sample_j0],
    baseNoise[sample_i1][sample_j0], horizontal_blend);

    //blend the bottom two corners
    float bottom = Interpolate(baseNoise[sample_i0][sample_j1],
    baseNoise[sample_i1][sample_j1], horizontal_blend);

    //final blend
    smoothNoise[i][j] = Interpolate(top, bottom, vertical_blend);
  }
 }

return smoothNoise;
}

public static float[][] GeneratePerlinNoise(float[][] baseNoise, int octaveCount)
 {
   int width = baseNoise.Length;
   int height = baseNoise[0].Length;

   float[][][] smoothNoise = new float[octaveCount][][]; //an array of 2D arrays containing

   float persistance = 0.45f;

   //generate smooth noise
   for (int i = 0; i < octaveCount; i++)    {      smoothNoise[i] = GenerateSmoothNoise(baseNoise, i);    }  float[][] perlinNoise = GetEmptyArray(width, height); //an array of floats initialised to 0  float amplitude = 1.00f;  float totalAmplitude = 0.0f;  //blend noise together  for (int octave = octaveCount - 1; octave >= 0; octave--)
 {
   amplitude *= persistance;
   totalAmplitude += amplitude;

   for (int i = 0; i < width; i++)
   {
     for (int j = 0; j < height; j++)
     {
       perlinNoise[i][j] += smoothNoise[octave][i][j] * amplitude;;
     }
   }
 }

 return perlinNoise;
}

public static float[][] GeneratePerlinNoise(int width, int height, int octaveCount)
  {
  float[][] baseNoise = GenerateWhiteNoise(width, height);

  return GeneratePerlinNoise(baseNoise, octaveCount);
  }
}

Now that the perlinNoise is implemented, all we need to do is change how the chunk is filled in CubeGeneration.cs. Update the FillChunk() function with this :

void FillChunk()
  {
  int maxHeight = _CurChunk.sizeY;
  int octaveCount = 5;
  int _curHeight;

  float[][] perlinNoiseArray = new float[_CurChunk.sizeX][];

  // Calculate the perlinNoiseArray
  perlinNoiseArray = PerlinNoise.GeneratePerlinNoise(_CurChunk.sizeX,_CurChunk.sizeZ,octaveCount);

  for(int i = 0; i < _CurChunk.sizeX; i++)
  {
    for(int k = 0; k < _CurChunk.sizeZ; k++)
    {
      _curHeight = (int)(maxHeight*Mathf.Clamp01(perlinNoiseArray[i][k]));

     // Specify the type of block according to its height
     for(int j = 0; j < _curHeight; j++)      {        if(j == _curHeight - 1)          _CurChunk.blocksArray[i,j,k] = 1; // Grass        else if(j == _curHeight - 2)          _CurChunk.blocksArray[i,j,k] = 3; // Sand        else          _CurChunk.blocksArray[i,j,k] = 2; // Rock        if(j > 8)
         _CurChunk.blocksArray[i,j,k] = 2; // Rock
      }
    }
  }
}

You can see that _curHeight is now calculated the perlinFunction. Mathf.Clamp01 make sure that it is between 0 and 1. It is then multiplied by the maxHeight to fill the chunk accordingly! I also added rock to cube above level 8 to give a bit of life.

As it is right now, the PerlinNoise is hard to customize. You need to go in the PerlinNoise.cs file to change amplitude and persistance. I will change it later or implement my own version of perlin noise. However, I can say that I get the best result with 5-7 octave, an amplitude of 1.0f and a persistance of 0.5f. Anyway, try it yourself. 7 - PerlinNoiseChunk

Fig2 – Displayed cube from a Perlin Noise generated Heightmap

Yeah! It works! Well, I hope it does if you try it at home!!. You can draw something like 75x15x75 and it should 3-20sec depending of your hardware. However, you’ll quickly notice that the performance drop quickly. There is too much cube being drawn on the screen. We will need to do some Culling. Unity Pro has an Occlusion Culling feature. However, I don’t have Unity Pro and I’m interested in learning it myself.

In Part 3, we will add a small culling feature that will save a lot of draw, because we currently are drawing everything even if it’s hidden. We will also add a small GUI to see the result of the culling. I will give the full code-source. Stay tuned!

Voxel Engine Part1 – Let’s display some cubes!

Hey, First Post! Yesterday I decided to start a new project with Unity3D Free. Why Unity3D ? Because it’s easy to work with and I like C#.  It also deals with a lot of things that aren’t really nice to do on your own.

I’ve been thinking for a while about implementing some Procedural Generation algorithms. The algorithm used in this video, Marching Cube, is something I would eventually like to try. However, I figured I’d try with something simpler to get my head around the concepts. Since I’ve been playing Minecraft a lot recently, I figured that making a Voxel Engine would be an interesting project that would allow me to learn a lot.

This 3 part tutorial will explain the path I took to achieve the result shown in this picture :

Result of the Minecraft-Clone prototype

Fig1 – Example of the procedurally generated cube world

The example above is a 125x125x15 chunk.It contains a total of 91803 cubes, if we count the occluded ones. So how did I get there ? Let’s start from the basics!

First of all, here are some links :

Up-To-Date WebPlayer (Small world for quick calculation, 25x12x25)

Up-To-Date Unity Project on GitHub (Will be updated as the project goes on)

Part3 Unity Project on GitHub (Will stay as the project end at Part3.)

Game Plan

So, without any experience on the topic, what would be the path to have a bunch of nicely organized cube displayed on the screen ? Here is the path I took :

  1. Setup a basic environment
  2. Create and texture a cube
  3. Display a bunch of cube
  4. Create a 3D array containing the information of all cube
  5. Fill the 3D array and display it
  6. Use a Perlin Noise algorithm generate a coherent random world

In this post, I will assume that the user know its way around unity. I’ll try to explain as much as possible so beginner can follow but I won’t explain how Unity works, that’ll be for another post!

Also, I’m not claiming in anyway that it is the good way to do it. I’ll go as far as saying that it is probably not the best way to do it. This is a naive implementation that will definitely end up using too many GameObject. However, this will be a nice and easy way to tackle the problem. We will look afterward on ways to improve the engine.

The objective here is to learn. I really like to try things myself and look after how it has been done by others. This way, I understand much more the design decisions and the code I’m looking at.

1.Setup a basic environment

I didn’t want to spend too much time on this part so I kept it simple.

I started by creating a new scene and by loading the First Person Controller provided by unity. It isn’t perfect, but it will do for a quick prototype. I changed the Extra Height parameter in the Character Motor script/Jumping to 50. This allow for an easier navigation in the height of the world. I’ll remake the Character Controller in a later post.

It’s position is 0x2x-10 to be able to see created cube. (Assets -> Import Package -> Character Controller).

Then, I created a simple 1000x1x1000 cube to make the ground at position 0 x 0 x-1. (GameObject -> Create Other -> Cube)

Then I added a Directional Light to light the see a bit! (GameObject -> Create Other -> Directional Light)

I finally created an empty GameObject called __GameMaster to handle everything related to cube generation. I always put “__” in front of GameObjects that are only script handler and not part of the actual scene. (GameObject -> Create Empty)

2.Display 1 cube

Now that the basic scene is there, we can try to display our first cube. First thing to do is to create a script responsible for the generation of cube. Mine is called CubeGeneration. Original, I know.

(In the Project window, Right-Click -> Create -> C# Script)

Now attach this new script to the “__GameMaster” GameObject.

(edit : Sorry for bad code formatting, I’ll figure a way to keep code formatting when posting it)

In CubeGeneration.cs, Add the following code :


using UnityEngine;
 using System.Collections;

public class CubeGeneration : MonoBehaviour {
public GameObject Cube;

// Use this for initialization
void Start ()
{
CreateCube(0,0,0);
}

void CreateCube(int _posX, int _posY, int _posZ)
{
GameObject.Instantiate(Cube, new Vector3(_posX, _posY, _posZ), Quaternion.identity);
}

Now all we need is to create a Cube and save it as a prefab so it can easily be instantiated. This line :


public GameObject Cube;

means that the script inspector will need to be given a prefab so the script know which prefab to instantiate. So let’s create a prefab and add a material to it!

To do this, Create a Cube, drag it from the Hierarchy window to the Project window. The cube is now a prefab that you can copy over and over. Now we need to add texture to it. I took my textures from the Standard Terrain Assets :

(Assets -> Import Package -> Terrain Assets).

To apply the texture to the cube, you need to create a material first.

(Project Window Right-Click -> Create -> Material)

Now drag and drop the texture from Terrain Assets onto the Material texture slot. I created 3 different Material for 3 different block :

  • Grass
  • Rock
  • Sand

I then copied the cube Prefab twice to have 3 different Prefab. I applied the material to the 3 cube prefab to have 3 different blocks :

  • CubeGrass
  • CubeRock
  • CubeSand

Finally, I drag and drop one of the prefab onto the __GameMaster’s CubeGeneration Script Inspector. Your Unity UI should look like this :

2 - Cube UI

Fig2 – Unity’s UI after cube texturing

When you hit Play, you should get a nice textured cube in front of you!

4 - 1CubeResult

Fig3 – Unity Scene with script running.

If you don’t get the cube, you probably forgot to attach the CubeGeneration.cs to the __GameMaster or you forgot to add the cube’s prefab to the CubeGeneration.cs script.

3.Display a bunch of cube

We now have a cube on screen, yea! Next step would be to draw a bunch of cube on screen. For test purpose, let’s make a prism of sizeX x sizeY x sizeZ and fill it with random blocktype. Here is the updated CubeGeneration.cs script :


using UnityEngine;
using System.Collections;

public class CubeGeneration : MonoBehaviour {

public GameObject CubeGrass;
public GameObject CubeRock;
public GameObject CubeSand;
// Use this for initialization
void Start ()
{
    CreatePrism(10,7,3);
}

// Create a sizeX by sizeY by sizeZ prism with random cube in it
  void CreatePrism(int sizeX, int sizeY, int sizeZ)
  {
    int _curType; // The blocktype of the next created cube

    for(int i = 0; i < sizeX; i++)
    {
      for(int j = 0; j < sizeY; j++)
      {
        for(int k = 0; k < sizeZ; k++)
        {
          _curType = Random.Range (1,4); // The last number is excluded, this will return a random number between 1,2 and 3
          CreateCube (i,j,k, _curType); // Call the CreateCube function to instantiate a cube
        }
      }
    }
  }

  // Create a Cube at the inputted position with a texture matching the blockType
  void CreateCube(int _posX, int _posY, int _posZ, int _blockType)
  {
    GameObject _CurCube = CubeRock; //Local variable that only remember the good prefab to be displayed

    // _blockType is inputted as an integer. 1 = Grass, 2 = Rock, 3 = Sand
    if(_blockType == 1)
      _CurCube = CubeGrass;
    else if(_blockType == 2)
      _CurCube = CubeRock;
    else if(_blockType == 3)
      _CurCube = CubeSand;

    // Instantiate a new cube at the inputted position, facing identity
    GameObject.Instantiate(_CurCube, new Vector3(_posX, _posY, _posZ), Quaternion.identity);
   }
 }

Don’t forget to drag and drop the 3 cube prefab to the CubeGeneration Inspector or you will have problems. You should get something similar to this :

5 - PrismResult

Pretty cool! We now have a bunch of cube on the screen!  It’s now time to keep track of which cube is where and have a better data structure. This is exactly what Part 2 will do with the implementation of a Perlin Noise algorithm!

Feel free to ask question in the comment section if you run into trouble trying to implement this. I’m also interested in getting feedback on the structures of the tutorials and on what you would like me to try to implement in later posts!

See you in Part2!