compton1:54 pm, Tuesday, 5 June 07 |
|
|
Very interesting report on a universe of planets, with terrain This is a pretty high-level implementation, very effective, but no cake walk. Nevertheless, it is useful reading.
This page of the documentation of the TerraGen product (which appears to be a tool for generating terrain models) refers to the two primary approaches for terrain modelling: procedural and heightfield. Procedural types use a mathematical function to power the elevation() function (or equivalent), while heightfield uses an array (or other data structure) to store arbitary elevations for given (x,z). Here's a good fairly low-level discussion of fractal terrain generation. The guy seems to be under a small misconception regarding fractals - they are not defined as shapes which contain the whole within the part, but shapes of fractional dimensionality. That is, neither 2D nor 3D, but somewhere inbetween. Anyway, the idea seems to be to create heightfield data from fractals - I think the reason being that graphics hardware can render heightfield data easily. The last URL discusses a simple method for generating terrain at random, the midpoint displacement algorithm. At least, this is the equivalent in 2D - in 3D, the algorithm is known as the diamond-square algorithm, according to that author. In 2D, the principle is simple - start with a single line, and displace its centre point upwards by a random amount. This makes two lines, in a simple pyramid. Then, repeat this with each of those two lines, to make four lines, and so on as desired. With each iteration, the random number used for the displacement is reduced. I implemented this 2D algorithm in ActionScript, in the following Flash movie: Click on the movie to give it focus, then press A to add terrain points. You can add as many points as you like, it will slow when there are many points of course, depending on your hardware's spec. Press C to clear the preceeding intermediate steps and just show the latest heightfield data. Press R to reset and start again. With this 2D case, finding elevation(x) is pretty straightforward. First, find which two heightfield points x lies between, then determine the gradient of the line between those two points (which is slope(x) incidentally, and a doddle to find for a straight line), and then you can find the elevation at x. There's an obvious shortcut here, if we are trying to find if an object at (x, y, z) is above ground or on it: if y is above both the two heightfield points it lies between, then it is above ground, and we could skip finding the gradient and other steps. |
|
compton10:53 am, Wednesday, 6 June 07 |
|
| So the 2D algorithim is fairly simple, and generates an acceptable attempt at a terrain profile in 7 iterations. It can easily make pretty long 2D terrain with wrap around, and rendering time is pretty good. Output can be tweaked by adjusting the decay - ie the rate at which the random number decreases. (I'm referring to the upper bound of the random number range of course.) As a 2D generator, it would be useful for a game such as Defender, because it can generate long terrain, and because it is 'wrap around', at least when you start with a horizontal line. | |
compton7:26 pm, Wednesday, 6 June 07 |
|
|
So I couldn't resist a quick go at that Midway classic, Defender. It's a good demo for the 2D terrain generator, and the terrain turns out to be pretty ideal for this particular type of side-scroller.
Click on the movie to give it focus if necessary. The controls are up and down arrow keys to move your ship up or down. Use the spacebar for forwards thrust, and press R to turn your ship around. Press Q to drop bombs. There are no enemies, or even any objectives. It shows the terrain in action though, a new terrain is generated at random each time it starts. It uses just 10 iterations of the displaced midpoint algorithm to generate a heightfield terrain comprising 1025 separate points. You can fly at full throttle for about 15 seconds before the terrain wraps, and it wraps seamlessly. Merely to provide an indication of when warp occurs, the terrain will change to a new random colour. A simple elevation-type function is implemented for detecting collision with the terrain, and it is reasonably efficient. I didn't bother with the additional refinement of checking the line gradients, it's not necessary here and would only add an extra performance hit. The elevation function, really collision function, takes three parameters. The first is the left most point to check (for the ship, this is the left side of the ship), the second is the right-most point, and the third is the object's y value. The function determines which terrain array indices lie in between the two x values, and iterates through those to determine if any are above the passed-in y value. If yes, it returns true, and there is a collision, otherwise it returns false. |
|
| Leave a comment | |
