Random Generation

Tyler Dahl - CPE 471 - Winter 2016 - Zoe Wood

Project Description

For my final project in CPE 471, I created randomly generated trees, terrain, and clouds.

When starting this project, I was inspired by games such as No Man's Sky and Minecraft, where entire worlds are procedurally generated to contain realistic landscapes and beautiful scenery. I knew I wouldn't have the time or knowledge to achieve anything near what these two games have accomplished, but I was extremely interested in learning how they go about generating their nearly-infinite worlds.

My original goals for this project were:

  • Randomly generate trees
  • Randomly generate terrain
  • Randomly generate clouds

trees, terrain, and clouds

What is Random Generation?

Well, when I say "randomly" generate, I actually mean "pseudo-randomly" generate. I want a function that will give me the same output every time I provide it with the same input, but for the outputs to look like random values (i.e. small changes in input will result in large changes in output). This way, I can provide my world with a "seed" value, and it will always generate the same world for the same seed (just like Minecraft!). Whereas, if I were to use completely random values, then I would get different outputs every time I provided the function with the same input, and my world would never look the same no matter what seed it was given. Well, good news is that computers are pseudo-random by nature! Thus, most random functions will give pseudo-random values that satisfy the above requirements.

To go about actually generating something using pseudo-random values (like terrain for instance), I need to create a function that will give me a single value for each 2D coordinate that I provide it. I will call this function "noise", because that is essentially what it is doing. If you were to display a 2D grid of these values, it would just look like a noisy image. The goal is to smooth these values so that the transitions between values aren't so harsh. If you imaging the value from the noise method as being the height for a single vertex of terrain, you can imagine the jagged slopes that would occur. Smoothing the noise makes the transitions less harsh, thus creating a smoother transition between points on the terrain. This is good because real terrain isn't spiky; it has smooth transitions between high and low points.

To make this "smooth" noise, I am going to use something called Perlin noise. I don't want to go into the details of how Perlin noise works, but if you are interested, there are a couple links at the bottom of this page I found helpful when learning about it. In short summary, Perlin noise was developed by Ken Perlin in 1983 to do … Since its inception, Perlin noise has been used to create terrain, clouds, fire, smoke, water ripples, wood textures, lava textures, and a plethora of other things. It is also often used in the entertainment industry to add noise to the edges of meshes to make them appear more realistic.

Randomly Generating Trees

The first thing I worked on for this project was the trees. I wanted to specify the number of times that the tree branched out at each level of its creation, and I wanted to specify the number of levels the tree would have. So, if I specified a level 3, branch 2 tree, then the tree would have a single trunk, would then split into two branches, and then each of those branches would split into two more branches, with each successive level of splitting making the branches smaller in size.

I began by looking into L-Systems, which are basically coded strings that specify how to build a particular object. These L-Systems are very simple to create since they follow a set of production rules that you specify. At each generation, it runs the production rules on the string, and after the specified number of generations, it returns the resulting string (I recommend taking a look at the Wikipedia article on L-Systems, as it is very informative). The hard part is actually rendering the tree after creating this L-System. I created my own L-System for generating trees that specified when to branch left, when to branch right, when to create a trunk, and when to create a leaf. Creating the L-System was simple, but when trying to render my tree, I had many difficulties with resizing the tree after branching left or right.

Long story short, I ended up ditching L-Systems altogether and used a recursive function instead. This was much easier for me to visualize what was going on, and it was much quicker for me to get it working properly. My trees branch out in the x and z directions by random amounts (within a constrained range), and they choose a random number of branches to create at each split (2-4).

Randomly Generating Terrain

To generate terrain, I used a 2D slice of Perlin noise to create a height map, which I then used as the y component of each vertex of the terrain. I created a 50x50 grid of vertices for each "chunk" of terrain. I then colored each fragment based upon its height in order to simulate water, sand, grass, and snow at varying heights. I also created a 2D array of chunks which would keep track of the chunks local to your position in the world. As you move toward the edge of the terrain, new chunks will be generated in that direction, and the 2D array of chunks will be shifted accordingly.

terrain terrain sky view

Randomly Generating Clouds

To generate the clouds, I again used a 2D slice of Perlin noise, but this time I let the y value given to the noise function vary with time as opposed to keeping it at a constant amount like I did for the terrain. I then mapped this 2D slice of noise onto the skybox (I'll talk about implementing the skybox later) and varied the color of each pixel linearly from blue to white. To make it look even more like clouds, I modified the noise generation to use a steep polynomial curve when interpolating between points so that the smooth noise would rapidly change from high to low frequencies rather than slowly. The results speak for themselves.

animating 2D clouds (refresh if gif isn't animating)

Skybox

I also implemented a skybox so that I could map textures onto the boundaries of my world. I used 6 different textures and the GL_TEXTURE_CUBE_MAP texture parameter to display the skybox, as well as another fragment and vertex shader for the skybox to get the color from the appropriate texture. I downloaded a skybox texture pack to try, but it wasn't high enough resolution, so I scrapped it. I couldn't really find any skybox texture pack that looked good with my world, so I abandoned that altogether and decided to solely map my own textures onto the skybox (which is what I did with the clouds).

Day / Night Cycle

I also implemented a day/night cycle to simulate the various lighting conditions on the terrain as the sun changes position throughout a day. The terrain used the angle between the sun vector and each normal vector to compute the amount of color for a given fragment (color based upon height of terrain). I also modified the skybox to simulate the position of the sun and added white to the sky pixels based upon each fragment's distance to the sun's position. Surprisingly, this somehow also created a cool ring effect a little distance away from the sun, which I thought was pretty cool, so I left it in.

Camera Controls

I also made the camera controls extremely smooth by giving the camera a velocity that updated its position each frame. The camera's horizontal and vertical velocities would be set when the w,a,s,d keys are pressed, and would be set to 0 when these keys were unpressed. This removed the jagged movement of the camera that is seen when you updated based upon the GLFW_REPEAT status (since GLFW has to wait a specified amount of time before it knows that the key was pressed rather than simply clicked).

Lessons Learned

  • Making a good website takes longer than I thought (I would have liked to make this much better).
  • There are a lot of really awesome OpenGL Tutorial sites that can teach a wide variety of cool concepts.
  • Creating a virtual world that looks like the real world is extremely complex. In my implementation, I simply created some mountains and small lakes. There were no rivers, no oceans, no large open plains, no caves, no overhangs, and no cliffs. Creating terrain with all of these features while also maintaining high cpu performance is incredibly difficult. I was already experiencing lag after just 9 100x100 chunks (which is why I went down to using 50x50 chunks).
  • Clouds were easier to implement than anticipated, albeit they were 2D clouds. 3D clouds would have been significantly harder to create (and that is what I wanted to create when I started this project). The 2D animated clouds that I created required very little additions to the code that I already had prior to working on clouds, yet the clouds are one of the most visually appealing aspects of my project. I think the fact that they change shape over time is what awes people.
  • Procedural generation using Perlin noise is a really simple and cool technique that can add to a lot of awesome features for a game or graphics project. Whether it is terrain and animating clouds, awesome textures, or water ripples, Perlin noise can be used to make an environment more accurately mimic the subtle intricacies of the real world.

Future Work

If I find the time to work on this project more, I would like to look into Simplex noise, which is Ken Perlin's improved version of Perlin noise. It is supposed to work better for higher dimensions of noise, such as 4D, 5D, 6D and so on, and thus could work well for creating 3D animating clouds (since the animation part uses another dimension for time). I would also like to render realistic 3D animating clouds rather than simply 2D animating clouds, which would require research into how to display a 3D cloud (I suspect billboarded sprites could work well). I would also like to add biomes to the terrain to make it seem more realistic. To do this, I would create several noise maps of varying frequencies and overlay them on top of one another with different multipliers (higher multiplier the lower the frequency). This would create large variations in height, while also maintaining the fine detail created by the higher frequency noise (there is a great tutorial on this posted at the bottom of the page). And finally, I would like to create better trees, because mine don't look anything like real trees, haha. To create realistic trees, I would need to generate the vertex positions for each trunk myself rather than using a object file as I am currently (real trees aren't simply a composite of cylinders). I would also use Perlin noise to create a nice wood texture and apply that to the tree trunk so that it appeared more realistic.

Resources

  • A C++ noise library which includes Perlin noise and other types of noise generating algorithms http://libnoise.sourceforge.net/index.html
  • An awesome website that clearly explains how to create realistic terrain http://www.redblobgames.com/maps/terrain-from-noise/
  • How to create realistic terrain with rivers, roads, and other interesting features http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/
  • How to make a realistic sky with clouds and a sun http://freespace.virgin.net/hugo.elias/models/m_clouds.htm
  • L-System Wikipedia article from when I first created my trees https://en.wikipedia.org/wiki/L-system
  • A really informative explanation of how Perlin noise works http://flafla2.github.io/2014/08/09/perlinnoise.html
  • A website with a lot of free skyboxes http://www.custommapmakers.org/skyboxes.php
  • A really great OpenGL tutorial website http://learnopengl.com
  • Another OpenGL tutorial website http://ogldev.atspace.co.uk/index.html
  • Ken Perlin's NYU homepage with old projects and current classes he teaches http://mrl.nyu.edu/~perlin/
  • No Man's Sky http://www.no-mans-sky.com/about/
  • Minecraft https://minecraft.net