T w e n t y S i d e d

UPDATE 2/20/2006: After about a month, the project is now finished. You can go through the series and read my explanations for each step, or you can just page through and gander at the pretty pictures. If you’re the impatient sort, you could just jump to part 10 right now and see how it turned out.

My goal is to write a terrain engine from the ground up, using entirely new code. In most situations, something like this would be a component of a computer game. I will approach this project as if it was.

I’ve worked with several terrain rendering engines in the past. In my professional work, I maintain a large codebase that includes terrain rendering code. I’ve also messed with the Unreal Engine, which has an attractive terrain system. On the right are a few random terrain renders from different engines that I gathered up via Google image search. This is just to give an idea of where this project is headed, although I have a long way to go before I can make anything like those images.

I’m doing this in the interest of self-education – I don’t have a purpose in mind for this, although I will be setting goals and writing code as if this were part of a larger project. That means writing clean code (as opposed to slapdash prototype code) and being careful with processing power and memory usage, even though I’ll have plenty.

The first step is deciding what sort of terrain engine I want to write. If this were part of a game, how would the engine be used? Will it be viewed from ground level, like a first-person game, or will it be viewed from above as in a real-time strategy or a sim game? Even though this thing will not really be used in a game, I need to pretend that it will be, in order to know how to optimize things. So what’s the difference?

In a first-person game, nearby hills may block your view of far-off scenery. Fog or darkness usually limits visibility, to prevent seeing all the way to the horizon. You usually can’t see more than a mile (and usually much less than that) and the landscape is often very hilly. If I go this direction, I’ll have to write code for figuring out what areas are blocked by nearby hills and not rendering those parts. Terrain needs to look great up close: the player view is almost never more than six feet from the ground. (their own eye height) The world needs to be richly detailed and sharply rendered. In the images on the right, the third from the top is of Unreal Tournament, which is this sort of game.

By contrast, the other sort of game is usually viewed from an overhead perspective. The view distance is far gearter, but the ground doesn’t need to be quite as detailed since the user never gets very close to it. However, these sort of games usually require the ability to draw the entire landscape at once. In the images on the right, the topmost is from Black & White, which is this sort of game.

I don’t want to design a program that can do both but is good at neither. Since I have experience with the first type (first-person views) I’ll shoot for the other type and design this program to be good at rendering overhead views of terrain.

Techical info: I'm programming in C++ and using OpenGL for the rendering. While it is common in games to begin writing them with the expectation that computers will be twice as fast and have twice as much memory by the time you finish, I'm making the machines of today my target platform. I don't want to get sloppy.

The first step is a bit dull. I set up a project, add a seperate console window for debugging (not pictured), made it so I can fly around the terrain using the mouse, and a bunch of other very dull stuff.

Then I make the very first iteration of the terrain engine. For testing, I’m going to make the map a grid of 512 x 512 squares. This is not unreasonable. At this point, I’m making no attempt to optimize whatsoever. I just send the raw grid of data for rendering. The result is:

The most boring image ever!

512 x 512 squares comes to 262,144 squares, each of which is divided into two triangles for rendering. So, we’re looking at 524,288 total polygons. Each polygon is made up of three vertices (points), and so I send 1,572,864 vertices for rendering. That is a lot of data. Modern graphics cards can handle this with no problem, but once we start adding some stuff like trees, cities, alien armies, bikini girls, giant robots, pokemon, or whatever the hell else to the scene, we are really going to run out of processing power very fast. This “engine” is useless in its current form, unless all you want to do is look at terrain.

Before I can do anything interesting, I need some hills! Most games use terrain that was created by an artist, which means very unrealistic hills shaped like squashed hemispheres rising out of flat areas, elevated bowl-like depressions, and other nonsense. That looks passable when you’re on the ground, but looks fake from above. This sort of data also tends to be easier to optimize. I don’t want that.

I don’t want to wuss out, so I want something that looks real. This means using either USGS survey data or terrain created with an erosion simulator. I prefer the latter, since I can still control the overall shape of the world. I have some fabricated data left over from another project and it was easy to bring it over for this one.

A common approach is to keep the elevation data as a big greyscale image. This makes it easy to edit, and easy to “see” what the land looks like outside of the program. I’ll use a bitmap (windows BMP files are a good choice since they are easy to load, easy to create, and have lossless compression) where each pixel represents a single point on our grid. The brighter the pixel, the higher the point. That’s a good start, but greyscale BMP files don’t have very much depth. Each dot has a value between zero (totally black) and 255 (totally white). When you’re using the data to store high-resolution elevation data, 256 distinct values isn’t enough. If you want to really stretch the elevations out, so that you can have deep valleys and high mountains, then the terrain will end up looking like “steps”. This is very bad. It looks fake, and the jagged shapes will work hell on any attempt to simplify the terrain. To get around this, I’m still using a BMP file, but I’m using all three color channels. The BMP is really made up of three seperate images like so:

The red channel is the “overall” shape of the terrain. This channel is used for making the mountains and valleys. In this case, I just have a single bright blob in the middle. This will create a large gradual rise in the middle of the map, like a large (mountain-sized) pitcher’s mound. The green channel is our “real” elevation data, which has realistic hills like you would see in the real world. The blue channel is just uniform noise.

The red channel deals with values on the scale of hundreds of meters. The green channel deals with values of dozens of meters. The blue channel deals with values on the meter and sub-meter level. This is arbitrary: I could make the channels work on any scale I want, it’s just that this setup seems to be easy to work with and likely to generate some nice looking landscapes. These three channels are combined to form one composite image, which will be used to describe the shape of the terrain in our world.

This is a much reduced version. The original is 1024 x 1024. I’m only using one-fourth of it (since my world is 512 x 512 right now) but the rest of the data is there in case I want to go larger.

So I drop the new data into place. The result:

Not bad.

You can see how the grid of squares forms the landscape. The program pulls up the points that make up this grid, deforming it. This is a bit like throwing a blanket over something and determining its shape by observing how the blanket falls. This is the most common way to make terrain by far. I’m sure other methods exist, but I’ve never seen them in action.

Note one drawback: We only pull points up and down, but never move them horizontally. This means that we can never have things like an overhanging cliff or even a sheer vertical cliff. I don’t plan to re-invent the wheel here and try to find a way around this. Most people don’t notice these limitations, and overcoming them would require something far more sophisticated than what I’m planning. In games, if the designer really needs a sheer cliff or overhang, they usually add an object to the world (just like they would add a building or a tree) that creates the shape they need.

That’s it for our first update. Next time I’ll be taking this terrain and trying to render it using less polygons while retaining the smooth appearance.

Shamus Young is a programmer, an author, and nearly a composer. He works on this site full time. If you'd like to support him, you can do so via Patreon or PayPal.