Progress Review Poster

Creating Meshes: Hexagonal Prisms

In a change of plan, rather than creating a plane in 2D, I have decided to work on creating 3D Meshes.

Unlike with the 2 meshes, I jumped straight in and created the hexagonal prism. I did this as the project will be using hex prisms rather than cubes, so I decided creating cubes would be a waste of time.

3D prism in Unity Scene Editor

The transition from 2D to 3D was relatively simple. To do this, what I did, was take the vertices of the original face, at +0.1 to the Y position. Then copied all the vertices but had the Y values as -0.1. The triangles for the bottom face, needed to be reversed as if the triangles were left the same, the bottom side of the mesh wouldn't be drawn. By reversing the triangles, the opposite side of the mesh was drawn.

Now that all the vertices are available, I was able to use these, to create the sides of the mesh.

-------------------------------------------------------------------------------------------------------------------------

The next step is to create a flat plane of these meshes.

However first I need to finish my poster that will be used for my Progress Review

Perlin Noise vs Simplex Noise

So, when I was doing my proposal for this project, I found out I should be using perlin noise to generate height maps so that my generated world will have height to it. But (there's always a but), upon further research I have happened upon the question, Perlin or Simplex. 

With the community debating over which one is more appropriate, It seems general consensus is that Simplex is the better algorithm, due to it having a lower computational complexity and requiring fewer multiplications. However the difference in the actual effect is marginal, and wouldn't affect the final product too much.

One major argument for using Perlin noise in the specific project, is that Unity has a built in Perlin noise function, so why over-complicate the project needlessly.

However, If I still have time at the end of the project, I may consider coming back to this point, and looking into implementing simplex noise

Creating Meshes: Hexagonal & Square

For me the logical starting point of the project was creating the meshes that would represent my voxels. So far I have only created 2D meshes, as a way to learn the mesh class in unity, because I thought it would be easier to start building 2D meshes rather than jumping in at the deep end and building 3D meshes from the get go. Rather than starting out with creating a shape such as a hexagon, I decided it would be easier to build a square and then translate the methods over to building a hexagon.

I have created lists for storing the Vertex, Triangle and UV data. I am using lists as they dynamically resize, and there for I can add many different vertices, triangles and uv coordinates.

The first step to building the mesh was to define the vertices. 

Values for building a Square

Values for building a Hexagon 

After defining the vertices, I needed to build the triangles using the vertices I've just created. For the square, I only need 2 triangles [0,1,3] and [1,2,3]. 

However building the hexagon, needed 4 triangles([1,5,0], [1,4,5],[1,2,4] and [2,3,4])

To work out how to build the meshes, I created some 'sketches' in order to know the vertices and triangles that I would need when coding.

Shows the vertices & triangles that I used to create the square mesh

The vertices & triangles I used to create the hexagon mesh

After building the triangles, I needed to set the UV Coordinates. UV Coords are a type of mapping that define the application of a 2D texture to a 3D object. This is done by giving each vertex a position on the texture, and that position corresponds to the colour on the texture that vertex should be.  

--------------------------------------------------------------------------------------------------------------------------

Here is the square shown in the Scene screen in Unity. You can see how the triangles have been drawn

Here is the Hexagon shown in the Scene screen in Unity. You can see how the triangles have been drawn

These are the what I have produced so far. Next step is to create a flat plane of these meshes and then building upon the meshes further and creating a cube, and then following on from that and building the hexagonal prism that will be the foundation of my project.

Proposal

Hexagonal Based Procedurally Generated Voxel Terrain

Overview

The idea of the project is to implement a voxel terrain that has been procedurally generated.  A voxel represents a value on a grid in three dimensional space and I will represent them in the world as hexagonal blocks. I will create small voxels so that when generated they will create a rounder more realistic version of a world.

The world I will generate will be limited to a set size that is defined at the start of the program. This size limit will be relatively large, but not full planet size. As a small game play feature I will implement removing and adding voxels to and from the terrain. I will create the world in a way so that there are no inaccessible areas to the world and cave systems.

Motivation / Rationale

My motivation for wanting to do this project is that Procedural Generation is a topic that I am very interested in and would like to further study and develop my knowledge on the subject.  My interest in the subject has been developed by interest in recent games that use procedural generation as a main feature.

The main games that are my inspiration for the project are 'Minecraft' and 'Ace of Spades'. Both games feature a 3D procedurally generated voxel terrain, but differ in that they use cubes to represent their voxels. However I feel both games feature a very jagged terrain, so my design of using a smaller voxel will give the look of a smoother terrain, whilst keeping the essence of the style.

Other games that I am interested in, but aren't directly related to the project include 'Terraria', 'Dwarf Fortress', 'Sir, You Are Being Hunted', 'Starbound' and 'No Mans Sky'. All of these games feature procedurally generated levels, but don't use the voxel style I am using. The procedural level generation used in these games is my main interest, as it allows the game to give the player a completely different experience on each play through, which I think is a really good concept in games that don't focus on a story, like my main influences.

Technical Overview

For this project I will implement algorithms to procedurally generate a voxel based terrain that have rules that will determine whether or not the terrain that has been generated is realistic. This will mean not having inaccessible areas of the world. To help create this I will use c# within unity 3d. By using unity 3d I will be able to use the mesh class unity have to create the polygons I will be using to represent the voxels.

I will use Perlin Noise to generate a height map that will allow me to give height to the world I am creating. This will also allow room for cave systems, and overhangs. For research into Perlin noise, I will use the book 'Texturing and Modeling: A Procedural Approach' (Ebert et al., 2002, p. 72). This book will be helpful to me for this project as it is co-written by Ken Perlin, the creator of Perlin Noise. I will also use the journal article 'Controlled Procedural Terrain Generation Using Software Agents' (Doran and Parberry, 2010). This will be useful research into terrain generation. Another journal article I will use is 'Efficient generation of simple polygons for characterizing the shape of a set of points in the plane' (Duckham et al., 2008). This article will be helpful to me for generating the polygons I will use to represent the voxels.  After getting a terrain created I will implement a feature that allows the user to remove voxels from the world, as well as placing a voxel in the world.

For the project I will use a Rapid Application Development method, this will allow me to develop a series of prototypes ranging through the different stages of the project. By using this method, I can split the project into smaller stages which makes the project more manageable. Due to the nature of this project, the ethical issues are minimal.  There are a few issues relating the use of unity as third party software. Because unity is available to use for free, this means that I will not be able to make a profit in excess of US$100,000 in the future. I will need to be careful with copyright as well if I decide to use free resources for texturing. 

Project Deliverables

For my project deliverables, I intend to create a fully working demo of an editable procedurally generated voxel terrain. This will be delivered as an executable file built via unity that has been created for windows. Along with the demo, I will include the unity project file that includes the source code I have written.

Project Plan

I plan to spend the first 5 weeks after submitting my proposal to research and develop solutions that will help me to implement my final solution. This period will include testing algorithms with code solutions so that I can be sure I'm heading in the correct direction. I will also use this time to focus on other modules so that I don't fall behind when the implementation phase of the project starts. The start of December through to mid-February will be the implementation phase. This time will be when I actually implement my solution. This will be the most intensive phase, so I will spend more time focused on the project. During the last few weeks of the module I will spend time testing and evaluating the final product. This will be done in an effort to find any bugs and fix them before the end of the module. As well as finding bugs, I will use this time to start writing my report so that I'm not left with having to write the report in the last 2 weeks.

Activity Title	Start Date	End Date	Notes
Proposal	29/09/2014	24/10/2014	Focusing on other modules, so that I don’t fall behind
Research & Design	24/10/2014	01/12/2014	·         Focusing on other modules, so that I don’t fall behind. ·         Creating Several Prototypes testing algorithms I will use in the final implementation
Implementation	01/12/2014	08/02/2015	This will be main focus
Testing & Evaluation	16/02/2015	27/02/2015	Start to focus on writing report
Report	02/03/2015	13/03/2015	Project Submitted 06/03/2015

References

Ebert, D., Musgrave, F. K., Peachey, D., Perlin, K., Worley, S.. (2002) Texturing and modeling: a procedural approach, 3^rd edn. Morgan Kaufmann.

Doran, J. & Parberry, I. (2010) "Controlled Procedural Terrain Generation Using Software Agents", IEEE Transactions on Computational Intelligence and AI in Games, vol. 1, no. 2, pp. 111-119.

Duckham, M., Kulik, L., Worboys, M. & Galton, A. (2008) "Efficient generation of simple polygons for characterizing the shape of a set of points in the plane", Pattern Recognition, vol. 41, no. 10, pp. 3224-3236.

Introduction to my FYP

Hello,

I'm Matthew, this is my blog for my Computing project of my final year of uni. For my project I plan to develop a 3D hexagonal based procedurally generated voxel terrain.

The inspiration behind this project was the fact procedual generation is a topic I am rather interested in, and would like to study further, as to develop my knowledge of the subject.

I have taken inspiration from games such as 'Minecraft' & 'Ace of Spades' due to the fact both games feature a 3D procedurally generated voxel terrain. As well as these 2 games, I have been inspired by the likes of 'Terraria', 'Dwarf Fortress', 'Sir, You Are Being Hunted', 'Starbound' & 'No Mans Sky'.

Over the course of the year I will detail the development process via this blog.