Subscribe to The Gamer's Algorithms to Goove By        RSS Feed

Brute Force Terrain

Icon Leave Comment
Now, one of the first things that I wanted to do when I got into 3D game programming, was have some ground to walk on. You could just throw a flat plane model down at ground level, keep the camera at exactly some height above that, move the camera around, and call it ground. But in 3D, we often want to see some hills and such.

I really struggled with this for a long time and thought, "How am I supposed to do this?" Can I just make a mesh in 3D Studio Max and then import it into my game? How would you do collision detection to make the camera "walk" over the terrain? I read a bunch of solutions in many many different books and although I probably absorbed a few things, I never could figure out what they were doing. It just really made no sense to me. And then one day I got tired of being "sick and tired" of not understanding it. So, I said to myself, "You know, I've been programming computers for a very long time, and there's never a right way to do something. The way that it works is you dream something up as a programmer, and you code it, and if it does what it's supposed to, then it does what it's supposed to. It doesn't really matter how you code it, as long as it works. Why should game programming be any different?"

Well, maybe part of the reason that I thought it might be different is that I kept seeing books explaining these algorithms, mostly written in code that I wasn't understanding.

So, I said, "Hey. I'm just going to do it. I've got an idea of how to make it work, and I'm just going to code it and see if it does." Well, to make a long story short. It did. It not only worked, but I used my concept for quite awhile. And I found that after I did it, I understood what the books had been trying to teach me all along. And now, I'm finding even better ways to do it that are more efficient and run faster, but my way ran just fine. I never really had a problem with it. And the advanced methods, really build off of what I was doing anyway.

So, if you feel like you can't understand something, go try and code it. You may find that the attempt to code it makes it easier to understand the problem that you're trying to solve. Fail, and you will learn from your failures. Wasn't it Thomas Edison who was asked "Weren't you demotivated by all your failures? You failed 1,000 times before you made the first light bulb" and I believe Edison replied something like, "I didn't fail 1,000 times. I mere discovered 1,000 ways not to make a light bulb".

Anyway, let's get into the algorithm for a brute force terrain. By brute force, I mean that it does not use advanced Continuous Level of Detail algorithms to make the terrain even larger and more efficient. In other words, the "brute force" terrain is you basic simple beginner's level terrain.

So, the concept begins with a "grid". I'm sure you've seen examples of a wireframe terrain grid. You can see some examples on my website in the masthead, the background, and on this page.

Basically, you start out with basically a flat plane that is madeup of squares. The squares are called quads, which is short for quadrilateral. Each square is made up of two triangles because all that a graphics card really knows how to draw are triangles, lines, and points. Basically, everything else the graphics card draws is made up of triangles. So, it takes two triangles to make a square. So, every grid quad is two triangles.

Now it's actually the corners of the grid squares, or grid quads, that are at the heart of this whole thing. You can think of those corners as points. Maybe, in your mind for a moment, imagine the flat grid of squares, millions of squares all arranged to make a flat plane. Now imagine the squares, or quads, are removed and all that is left behind are the corner points. That is actually the grid. Those points are the grid. Everything we do with the grid, uses those corner points.

When we draw the grid, we draw triangles between those corner points in order to draw the grid squares. The corner points become the vertices that we use to draw our triangles with (every triangle has 3 vertices which are the positions and other data for color and texturing and such - but the vertices are always at the corner points of our triangles that we draw).

It's very important that the grid is composed as squares. Rectangles or rhomboids are not going to cut it. We use the fact that the quads are square for collision detection and other things. So, it's very important to have all the corner points equal distance from one another so that they are square.

Another thing that will not matter at first, but will matter later is that you need the hypotenuses, or the center line created by the two triangles in the quad, to go from positions 1,0 to 0,1 and not from position 0,0 to 1,1. Or for another quad not centered at the origin (0,0) that might be from 28,29 to 29,28 rather than from 28,28 to 29,29. The best terrain collision algorithm that I've seen depends on the center lines being drawn in that direction. I'll probably cover that algorithm later.

So, great! We have this flat plane grid. "How is that a so called hilly terrain?" Well, I'm glad you asked. :-)

First of all, the positions of the grid are going to be related to an X,Y,Z axis. Let's choose Y to be the up-down axis. So, Y is always zero here for our plane. X and Z are the horizontal positions used to represent the corners of our grid quad and they are always regularly spaced apart to form squares. So, they might all be 1 unit apart. So, you could write a simple for loop to set their X positions and another for loop to set their Z positions. Their Y position is always 0.

So, here's where the "magic" comes in. Instead of setting Y to always be zero, how about we feed the Y value from a 2 dimensional array, that lines up perfectly with our grid coordinates. By that, I mean array position [20,32] represents the grid corner that we are going to draw at X=20 and Z=32. And array position [20,32] can hold our Y value.

Now our array positions must be integers, the Y values in the array can be real numbers with decimal places. And we can later do some math to scale our grid corner positions to different sizes, but to get started we probably want to make our grid corners line up perfectly with the integer values that they represent in our 2D array of heights.

This array is "essentially" what we would call a "height map" because it maps heights of the terrain.

There are several different methods for populating the heights of the grid corners in the array, including loading them from an image file (which is also often called a height map but is simply used to load height data into the exact same array).

But that's basically the whole algorithm. With UV coordinates stored in your vertices you can paint a grass texture or something across your terrain. You can wrap that texture to repeat it many times across the terrain to make a small texture cover a large terrain. There are High Level Shader Language algorithms to multi-texture the terrain. And you really need some sort of collision algorithm. But basically, what we've covered here will give you a terrain. That is the algorithm.

Now, there are a couple of additional steps you may want to take. The way we've discussed it so far, the terrain is all in the positive X and Z quadrant and the corner is at 0,0. One of the next steps you may want to take is to center the grid to the origin at 0,0(,0 assuming height). The way you do this is get half of the size of the grid width in vertices and offset (move) the grid by that amount in the negative X direction. And then do the same in the -Z direction. Then your math has to be adjusted to match the array up with the shifted grid positions, but it still works the same.

Anyway, hope that helps you code your first terrain mesh! Enjoy!

0 Comments On This Entry


Trackbacks for this entry [ Trackback URL ]

There are no Trackbacks for this entry

June 2019

16 17 1819202122


    Recent Entries

    Search My Blog

    0 user(s) viewing

    0 Guests
    0 member(s)
    0 anonymous member(s)