Jump to content
  • Advertisement
  • entries
  • comments
  • views

Optimal Terrain Generation is a bitch

Sign in to follow this  


Well, this is my first journal entry. Before I get started in the technical aspects of game development, I feel I need to caveat myself to you. I am truly an idiot. I say that with full intellectual honesty & humility. I will make mistakes. Lots of them. And I will travel down a path which is a dead end. But, I'm okay with that -- Mistakes and dead ends are not a waste of time (I've got loads of time) -- I learn from them each time I make them and I also hone my skills. I think it's valuable to describe the various mistakes and dead end pathways taken while navigating the road of development, so that's going to be a major emphasis here. I'm hoping that if anyone follows the path I've taken, they can use my experiences to look ahead and see dead ends far before traveling down them.

With that out of the way, I'm working on creating an indie game about magic, kingdoms, armies, and intrigue. I have a reasonably detailed and concise idea on how it should all work out. I spent the better part of several days writing out a relatively detailed design document. I must warn you of a few traps here!!!
1. When brain storming creative game ideas, recognize your resource limitations and cut ideas appropriately.
2. Recognize your strengths and passions as well. Don't short yourself on this. Elaboration: I've been fantasizing about creating a game with a sufficiently complex magic system which requires a lot more strategic thinking to it than the typical magic spell casting systems found in games. It's a huge undertaking. In the past, I've taken a step back and said to myself, "You know, this may be a bit too much for one person to do. Maybe I should start a smaller project which I have a realistic chance of actually finishing."
And then I do just that: I start on a smaller project. I drive hard on it, but it's just not as exciting as the project I just put off. Don't get me wrong, it's exciting to some degree, but not a passion. I could continue to slave away when it stops being fun, but I feel the end product would be a half-assed piece of work which is not a labor of love and worthy of being played. My watered down projects never get very far, so if you find yourself contemplating the abandonment of an ambitious project to work on a smaller project, your shorting yourself. Don't do it*.
*Note: You also need to be very realistic about your limitations! you're not going to be creating a GTA5 on your own or some other similarly ambitious project. Those are the projects you want to kill before you even start on them.
3. Don't waste too much time on writing a game design doc.
All of the software developers who come from a waterfall software development life cycle (SDLC) background are probably screaming bloody murder at me for saying this, but hear me out. A design document has TWO purposes. First, it is a very good technique to organize and coagulate a nebulous idea. This in itself is very valuable. It gives ideas a bit more permanence and makes them less subject to being forgotten. Second, a design document is a form of communication between people. If you are going solo, or have a very small team, the amount of communication your design doc needs to convey is much smaller. So, in the agile SDLC's, there's a "sweet spot" for documentation which is called "Just barely good enough". This is what you want to aim for. Get a detailed enough general idea on what you want to create, but don't worry too much about crossing every "t" and dotting all your "i"'s. Design documents change over time, so you'd be wasting time detailing everything to too fine of a level of detail. Getting to that sweet spot is a bit of a nebulous marker, so how do you know you're at that point? I personally try to gauge whether I've got enough written down to work for a few months before having to add more.

Anyways, I've written my game design document for myself. The ideas have coalesced into a semi-solid state to the point that I can start breaking the project down into discrete tasks that can be completed independently and in parallel.

My game will have three primary "states". First, is the menu screen. This is pretty self-explanatory. Once a game has been started, the player will be playing in a large strategic map/world. Throughout the course of play in the strategic map, battles between mages will be waged. So, those battles will take place on a smaller tactical map. The interaction between these three states is somewhat minimal, so they'll be pretty much independent from each other. The primary form of communication will be by sending initialization settings from one state to another (ie, the strategic map sends details on who will be fighting to the tactical map). Anyways, all of this suggests that I'll need at least three different "game worlds". I use the term "game world" loosely to describe the model. I find the best way to architect games is by loosely using the MVC framework and trying to keep all of your objects loosely coupled. The strategic game world really doesn't care about the tactical game world and vice versa. I could "auto-calculate" the results of a tactical battle within the strategic world and it wouldn't care. The tactical world is just another function for it to call. Anyways, enough about that. The heart of my game is going to be the game play in the tactical world. It's the meat and potatoes of what makes my game "fun". So, I should begin by starting to flesh that out first. Where to begin? Well, if I'm going to have a pair of dueling mages, I first need to give them something firm to stand on. So, I'll have to create the earth beneath their feet. Now, before I start, I should remind you again that I am an idiot. I should be prototyping my game mechanics. To satisfy the requirements of giving my mages something to stand on in prototyping phase, I really just needed to give them a textured quad with a little bit of grass to stand on. Instead, I got carried away with creating terrain and went all out. Since this is a common problem for developers to work on, I'll detail out my terrain generation project details here:
So, I want to create a large, robust terrain map for my magicians to stand on.

Game Requirements: The terrain should be expansive, it should be convincing enough to be interpreted as terrain by the player, and it should impact game play mechanics in a meaningful way. I may want to deform the terrain in the future with certain types of spells.

Technical Requirements: It should not be taxing on the system resources. It should render quite fast and have a high level of responsiveness (ie, high frame rate). It should also support about a square kilometer of terrain.

How much can I get away with in terms of triangle size? The larger the triangle, the less contoured the terrain appears up close...

So, I decided I wanted to start from scratch in C# and XNA. I probably should use an existing game engine like Unity3D, but I'm not at all familiar with their tools. It would probably save me a lot of time in the long run and give me cross platform support, but for some unknown reason, I'm just going to be an idiot and go off on my own. Years from now when someone asks me what I'd do differently on my next project, I'll say that I'd use an existing game engine...

I've created my game worlds and I'm going to leave that out of this. It's not really worth mentioning since it's so easy to do.

The first challenge in creating terrain is to render a single triangle onto the screen.

The second step is to render a bunch of triangles in a grid-like pattern. Here's the first decision: Do you want to render them as (1) a triangle list or (2) as a triangle strip?
If you do (1):
-Each triangle will always have its own verticies. Since we're creating terrain, a lot of the verticies are shared. It would be a waste of RAM to duplicate verticies.
-This is also the easiest and fastest way to get a bunch of triangles up and running quickly.
If you do (2):
-With exception to the edges, each new triangle uses only one additional vertex. This is super sexy in terms of RAM.
-You have to be extra careful with the winding of your triangles. The clockwise and counter-clockwise winding flips with each triangle. It gets extra tricky when you get to the edge of your terrain since you have to re-use the same vertex three times to create a ghost triangle. In the image below, I've detailed out the verticies and the necessary order for the indicies to create a 4x4 terrain map.

Is this the best way to do it? Who knows, it works.

The third step is to give each of the triangles some elevation based off of an external heightmap file. I went crazy and decided that there shouldn't necessarily be a 1:1 relationship between a tile height and a corresponding pixel on a grayscale heightmap. If I want a 30x30 terrain object based on a 20x20 height map, I should be able to support that! This means that the resolution of the terrain gets worse as the resolution of the heightmap gets smaller (Oh hey, this sounds like I'm setting myself up for different levels of detail based on view distance!). In order to do this properly, I need to do a bit of linear interopolation between heightmap values. Getting this right was a bitch of a problem considering the variable dimensions (but hey, I'm dumb). I eventually got it and combined a bit of multi-texturing to get get the following result:

However, there's a problem!!! If my heightmap contains a lot of terrain with the same slope, I'm unnecessarily creating triangles for it! For example, if I have perfectly flat land which stretches into a 5x5 region, I'll create 25 tiles (~50 triangles) to represent it. Why not create just one 5x5 tile instead, using 2 triangles?? I dare say it's a clever idea which is probably not very original. Remember that this also adds another layer of complexity if we want to support deformable terrain: If the deformation happens within this 5x5 tile, we're going to have to recalculate the verticies in this region! Is the additional layer of complexity worth the savings in triangle counts? I went with a solid "yes". Why not? It sounds fun and like an interesting problem to puzzle over for a while. (Software engineering question: Is this a premature optimization? No. A triangle strip is limited to about 1 million triangles per draw call. It's easy to hit that limit with a 512x512 tiles terrain object without being a bit smarter about triangle conservation).

So, my instinct was to use a quad tree to break the terrain up into separate terrain objects based on slope. Is this a good idea??? If I have a very large terrain object with lots of variety in slope between tiles, the terrain becomes more expensive in terms of internal memory consumption! The other caveat to quad trees is that they generally work best when using squares which are a power of 2. A 20x20 terrain object is harder to divide into equal quarters since the third level results in a float instead of an int (20 / 2 = 10; 10 / 2 = 5; 5/2 = 2.5) while a 32x32 terrain object can be divided all the way to a 1x1 tile (32/2 = 16; 16/2 = 8; 8/2=4; 4/2 = 2; 2/2 = 1;)
The other problem with quad trees becomes "way too many draw calls". If a terrain mesh is at its highest level of detail (1x1 tiles), then each tile will be a separate draw call. This becomes really inefficient since a GPU is best at receiving large batches of triangles and rendering them all at once. Getting four verticies at a time is terrible for performance.

Anyways, this turns out to be a dead end due to the performance costs and non-optimal interaction with the hardware.
Sign in to follow this  


Recommended Comments

There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!