Snowballin’ Technical Post-Mortem: Procedural Terrain Generation Tutorial

December 16th, 2015 10:33 pm

This was my third time competing in Ludum Dare and this is my first post-mortem. Rather than just give vague “what went well” and “what went wrong” I thought I’d give some insights into the most technical area of my game. I’m a coder at heart. I work full-time as a software engineer, I’m a _terrible_ artist, and I don’t know how to compose music. So, naturally, most of the focus in making my game was on programming. I wrote almost 800 lines of code in two days (not necessarily a good thing :P).

This post-mortem is meant as a small insight for beginner/intermediate programmers who are curious about how I implemented the terrain generation in Snowballin’. You might want to try playing the game  or looking at the GIF below before reading to understand the context. The source code for this game is linked in my compo entry and can be found here. I’ll be giving a high level overview in this guide with references to the corresponding code if you want to check out my implementation. It’s all done in C#/Unity3D. Be forewarned: this code is hacky. But it works

Overview

The terrain is generated a section at a time, so let’s look into what it takes to generate a section (from here on called a “slice” since that’s what I called it in code). A slice is simply composed of a mesh and an object to store some data. The mesh is what we need to generate in order to give a physical form to the slice. A mesh has a few different pieces to it, most importantly in this case are vertices, triangles (tris), and normals. The vertices are just points in space, triangles are set of three vertices that get connected together to create a single face, and normals are vectors which dictate how light should be reflected at the vertices. You can read up more about meshes in Unity’s doc here.

Flat mesh generation

The mesh generation occurs in the SlopeSliceGenerator class (SlopeSliceGenerator::MakeMeshSlice()). For our purposes, we need a collection of vertices spaced out in a grid (SlopeSliceGenerator::MakeVertices()) and tris connecting them together(SlopeSliceGenerator::MakeTris()). Normals can be automatically recalculated from Unity. One important note is that normals are defined on vertices, so if vertices are shared between faces, so will the lighting information. This will result in lighting that is “smoothed out” and is great for things like spheres look continuous. However, for our low poly terrain to look good, we don’t want things to be “smooth” but “hard.” So, we ensure that each tri is defined using a unique set of vertices so that normals aren’t shared across faces (SlopeSliceGenerator::UnshareVerts). This is how you get that signature low-poly 3D look. If you’re looking at the source code and it doesn’t make any sense I recommend the following exercise: grab a piece of paper and make a flat 3×4 grid of dots. Try to come up with an algorithm to go through the dots and number them appropriately, considering the ideas that I’ve presented here. Note that I found it a lot easier to share vertices between faces and then do another pass to duplicate them – although this isn’t the most efficient. This will help you figure out how to get the positions for objects on the x-z (horizontal) plane. If you get stuck, take a look at the illustrated example here

Generating vertex height

Once you have the x-z (horizontal) position, you need to figure out some kind of height (SlopeSliceGenerator::HeightFunction()). We want two things with our height: some rolling hills/slopes to break the monotony of a flat plane and some bumpiness to give the terrain a nice “texture.” For the hills, we use a “Perlin noise generator.” Perlin noise is a special function which takes in two parameters (i.e. x and z) and returns value. It has many applications, one of which is that it can be used nicely to make some “random” hills. We can pass in our vertex’s position in order to get a height value out of this, and then we can add a position independent random height to it for the chopiness.

Considering neighboring slices

One detail we have to deal with is making the slices seamless as new slices will border existing slices. As an example, lets say we’re generating a new slice in front of an existing one. This means that the vertices forming the back of the new slice need to have the same exact position as the vertices from the existing slice. Since this is a grid (from a top-down view) the x-z positions aren’t a problem but the y (height) position is. Although we could recalculate the height from the Perlin noise generator by passing in the same x-z position, we had added a random height for choppiness. This problem was solved simply by storing the position information about the edge vertices within the SlopeSlice class and passing in information about any existing surrounding slices when creating a new one. (Note: in my implementation I stored the full Vector3 vertex position, but in the end I just needed the height).

Finding neighboring slices

Now the challenge becomes finding existing neighboring slices when generating a new one (SlopeManager::GenSurroundingSlices()). I went through three different solutions, trying different things when I saw each one fail. In the end this could have worked with all three, but I wasn’t thinking straight and thought starting from scratch was a better idea than fixing minor bugs :). I’ll give a quick recap of them all to give you some ideas on how to solve this problem. Solution one: knowing the general area of the new slice and the length and width of each slice (it’s constant), use a raycast to the left, right, and back of the new slice position to find existing slices. Why it didn’t work: I probably was testing to the left, back, and right of the corner of the new slice rather than the center, causing it to sometimes miss. Solution two: every time I generated a new slice, I stored a reference to the slices around it that I knew of. You know the starting point, and you know one neighbor at each generation. Then you can do something like: I’m generating a slice in front of this one (known neighbor) if there’s a slice to my right and that has a slice in front of it, then the slice in front of me has a slice to its right. In computer science, this is called a graph) and is one of the most useful data structures ever created. Why it didn’t work: there are more ways to get from point A to point B than just one; however I didn’t want to do a full graph search in order to find neighboring slices (or, in graph terms, nodes) because I was worried it would be too expensive and I didn’t feel like implementing it (dumb reasons). Note: The actual reason my “naive” search didn’t work is because I was originally generating slices forward first, then sideways. I assume that the slice I’m generating is the forwardmost slice, which was not the case. I didn’t fix this until I did solution three, but it also broke that solution for a while. Solution three: Each slice has an x, z position stored. I have my SlopeManager store a Dictionary (a.k.a Map, close contender for most important data structure), which is like an array except instead of needing to use integers to store/access elements, you can store/access elements using whatever type of data you want! For example, I can enter these x, z values and get back the slope. Now I can easily look to the left/right/behind a new position to get the neighbors! Note: if you’re unfamiliar with maps/dictionaries and graphs, go read up on them! Especially maps/dictionaries. You can get an insane amount of value from using them without needing to be a more advanced programmer.

Reusing existing slices

There’s one more little detail we do for optimization: once a player has passed a slope we don’t really need it anymore. If we keep it all the extra slices around, the game will get slower and slower as the player continues. It only has to stick around long enough that it’s no longer in view of the camera. When we generate a new slice, we could just do something like calling FindObjectsOfType<SlopeSlice>() and iterating through the results to find the irrelevant ones, but the performance would be pretty bad and it would get worse the more objects you try to fit in the world at once. Instead, we just keep a Queue) of the slices we’ve created. A Queue is just like an array or list, but it behaves like waiting in line at the store: the first person in the line is the first person out, and more and more people can keep piling up in the line. When generating a new slice, we just check if the first slice in the queue (which is the oldest slice that’s been generated) is still relevant. If it is, we create a brand new slice. If it’s not, we remove it from the Queue and reuse it.

Final touches

Once a slice is generated, we just tilt it at an angle to get our downward slope, place it in the world, and give it a nice little “popup” animation so that it doesn’t just appear suddenly!

This was my first time doing procedural mesh generation and procedural terrain generation. For anyone who’s looking at this going, “how would I even know where to start?!” I’ve layed out the steps in the order in which I solved them. That means that I thought about the whole problem: then went and attacked the simplest and smallest piece that I could without worrying about anything else. Once I solved that piece, I added the next layer of complexity until I arrived at the finished product. The very first iteration I had of the terrain generation was just a flat plane! This problem solving process of breaking down complex problems into the smallest pieces possible and iterating on them is applicable not only to any piece of software you ever intend to write, but any problem you ever intend to solve!