Nasa's Space Shuttle Atlantis Transiting the SunA Simple 2D Terrain ModelTank Wars in G3DCreamy Swiss-style (Vegan) Chicken and Mushroom Pepper StewSpooky Case of the Wem GhostReading Email with PHP and IMAP/POP3
Mon 04 Jun 2007
5:00PM
compton
5:00PM
compton
A Simple 2D Terrain Model
I now want to look into how terrain can be modelled in a 3D game. My feeling is that the terrain model must support a couple of functions, as a minimum. These are elevation(x,y,z), which returns the height of terrain below the co-ordinates passed in, and slope(x,y,z), which returns the slope of the terrain at the specified point.
If we consider a simple single-level terrain, then we can say y = elevation(x,z). In other words the elevation function returns the height (y) for a point at (x, z).
The slope at a given point can be thought of as the rate of change of y with respect to x and z, ie the differential of y = elevation(x,z). 2D differentials are fairly straightforward to calculate using Newtonian calculus. I'm not so sure about 3D ones however.
There are other ways to get the slope though. If the terrain is represented as a triangular mesh, which is pretty much the only way to do it, the slope is the slope of the triangle at a given point. The elevation can be found from the mesh also: first determine which triangle is below the specified point, and then determine the height at the point using simple linear algebra.
My plan now is to read up about terrain modelling on the web.
If we consider a simple single-level terrain, then we can say y = elevation(x,z). In other words the elevation function returns the height (y) for a point at (x, z).
The slope at a given point can be thought of as the rate of change of y with respect to x and z, ie the differential of y = elevation(x,z). 2D differentials are fairly straightforward to calculate using Newtonian calculus. I'm not so sure about 3D ones however.
There are other ways to get the slope though. If the terrain is represented as a triangular mesh, which is pretty much the only way to do it, the slope is the slope of the triangle at a given point. The elevation can be found from the mesh also: first determine which triangle is below the specified point, and then determine the height at the point using simple linear algebra.
My plan now is to read up about terrain modelling on the web.
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 | |
Related Articles
Tank Wars in G3DExternal Links
Java game development framework with a unified API supporting Android/iOS/Javascript JavaScript Box2D hits the browser/xkcd/ METAR
