Game Construction: Terraria and 2D Level Generation

Hello Reader!

Before we start I’d like to go on a bit of a tangent here about the concept and idea of a console developed by Valve.  This has been popularized as the ‘Steam Box‘.  What does this mean for future games and the future of the industry? Also these are the rumoured specs: Core i7 CPU, 8GB of RAM, and an NVIDIA GPU.

Rumoured Steambox

Valve is the world leader in PC/Mac video game online distribution. There are other services like this, EA has Origin but their customer service is a nightmare.  Steam on the other hand is loved by its community and is truly a great service.  With Sony, Nintendo and Microsoft (Big Three) pushing the market toward the consoles, Steam is keeping PC gaming alive.  Onlive tried releasing a cloud gaming console, however it is not doing so well.

This Steambox or ‘GabeCube’ would help drive PC game development and change the future of how we play video games.  Valve would offer better licensing fees to compete with the Big Three.  The most important element of the Steambox would be the sudden move to digital distribution.  The Steambox would help solve many issues that people have with consoles right now.  First of would be the limited technical specifications, overpriced games and the online gaming fees.

Here is a patent for a controller design that Valve applied for back in 2009/10.

Getting back on track with the main topic I wanted to cover today:

Overview

My post last week on Minecraft’s level generation was fairly abstract since I don’t have much knowledge of 3D noise generation and the use of voxels. This week I will try to conceptualize how the 2D level generation in Terraria works.

Goal

The technique that I have seen for 2D level generation works well when working with underground items like rocks, dirt and ore.  However things like grass, snowflakes and other biological entities are generated using a different method that is much more complex and harder to conceptualize.

Breakdown

Functions

We know we are dealing with just dirt and rocks that are below ground.  Lets get biblical and start dividing up the heavens from the earth.  The first step, similar to Minecraft is to take a function that can divide up our world and tell us what is solid and what is air.  This part is fairly easy because we all know a great function for diving things up into two parts linearly.

GRADIENT!  Given two points a gradient creates a line using parameters like: P1=(x1,y1,z1,w1,u1,v1) to P2=(x2,y2,z2,w2,u2,v2).  Here we have our points and our texture coordinates. But all we need is to set up a simple gradient from -1 to 1 and align it with the Y-axis.  Then we get something like this:

Simple Gradient

Using this as a starting point we can move onto our next part.  Similar to toon/cel shading we need a step function.  There are too many levels here to work with and we only need 2, solid or air.

After using the step function

Now this is much better.  We can clearly see what is air and what is ground.  Unfortunately this is boring.  We need to remove that horizontal divide in the middle because straight lines and linearity in games a boring.  The great thing is that we have another function that can help us with this.  However this is more of a technique then a function.

TURBULENCE! All this function does is translate points or translate the input coordinates of a function.  What we want to do is scatter that centre area given a range and offset of random numbers.  Now imagine the top part of our ‘level’ as y=1 and the bottom part is y=-1 leaving the centre to be y=0.  Given a range from y=0.25 and y=-0.25 we want to create come turbulence.  This would be the result of turbulence:

After Applying Turbulence

Better then having the flat line, however if a world had random blocks floating in the air we would have a serious problem.  This will not be our finished product, but it gives us something to work with.  Right now we have a messy chaotic pattern and we want a nice smooth terrain shape.  This is where it get complicated, we begin to use fractals.

The fractals I am talking about is a combiner of noise sources using different fractal methods.  First we have the basic noise groups like:

Value Noise – Generated by assigning a random value in the range (-1,1) at every lattice point in the image then using interpolation to generate corner values for each cell
Gradient Noise – This is Perlin’s original noise function using a similar method to Value noise. However it uses a wave-like pattern for generating the lattice points for a smoother output
Gradval Noise – This is a hybrid between Value and Gradient noise mainly created to hide artefacts that occur in the interpolation process in the Gradient Noise
Simplex Noise – Improved version of Perlin Noise using a ‘simplex’ instead of a hypercube. In 2D space a simplex is a equilateral triangle and in 3D it is a tetrahedron.
White Noise
White Noise – This is a more chaotic and random noise seen on many old TV’s. It generates a chaotic random signal with no pattern.

Just so we can get a better understanding of how noise is generated let us go through a few step-by-step examples:

All this image is, is Value noise without interpolating the values. You can easily see how each grid element has a value
Now if we add linear interpolation to the lattice coordinates we get something like this

You can experiment by using cubic and quintic interpolation to get varying results, but that is the process in a nutshell.

Getting back on track on how to implement fractals in our level design.  What we want to do is take our level begin distorting it so that each point gets randomly offset by a value determined by the fractal.

Fractal generated by a function

Here is an example of a fractal in the scope of our level. So how is this useful to us? Lets say the black areas represent -0.25 and white represents 0.25.  So anywhere where the fractal is at its darkest black we move the point -0.25 downward and upward if it is white.  Values in the middle will have interpolated values.  Why is this good? This will give us smooth hils because of the gradient of the fractal and we can get floating islands and overhangs with this.

Fractal Distortion Applied

There is a lot more we can do still to this image, its just a matter of adding more filters and functions to tweak in how you want.  We can take a horizontal gradient and create a heightmap if you want to get rid of the floating islands and want different types of terrain.

Horizontal Gradient

Taking this gradient we can apply a similar offset technique to move our terrain up or down as needed.

After Heightmap Adjustment

Closing Remarks

This process is very similar to the idea of shaders. Each point is just data and we can manipulate it as we want.  If we want to add caves we can create a fractal like:

Cave Shape

And using a step function and offset we can apply this to our level and get:

Smooth Cave System

Now if you want to make that cave system smoother, just add another fractal to perturb each area a bit.

Final Cave Shape

 

Source – [http://accidentalnoise.sourceforge.net/minecraftworlds.html]

Thank you for reading
– Moose