Terrain Following and Collision Avoidance

Generating a Fractal Landscape

My FractalMesh class utilizes a plasma fractal to generate a mesh of Point3d objects, centered at (0, 0) on the (x, z) plane, at intervals of 1 unit, extending out to WORLD_LEN/2 units in the positive and negative x- and z-directions. (In my code, WORLD_LEN is 64 units.) The y-coordinates of these points become their heights in the scene.

The objects are stored in a 2D array called mesh, with mesh[0][0] storing the back, left-most point in the scene. A row in mesh[][] stores all the points for a given z-value.

The mesh is generated using the algorithm described by Jason Shankel in "Fractal Terrain GenerationMidpoint Displacement" from Game Programming Gems. The mesh is seeded with four corner points, and a two-stage process is repeated until sufficient extra points have been created. In the first stage (the diamond step), the height of the midpoint of the four corner points is calculated by averaging their heights and adding a random displacement in the range -dHeight/2 to dHeight/2. For example, the height of the E point in Figure 26-8 is calculated this way:

E = (A + B + C + D)/4 + random(-dHeight/2, dHeight/2)

Figure 26-8. Mesh creation: first iteration

The next stage (the square step) is to calculate the heights of the midpoints of the four sides (F, G, H, and I in Figure 26-8). For example, G's height is:

G = (A + E + C + E)/4 + random(-dHeight/2, dHeight/2)

If a point is on an edge (as G is), then we can use a neighbor from the opposite edge by thinking of the mesh as wrapping around from left to right, and from top to bottom. That's why G's calculation uses E twice: once as the left neighbor of G and once as its right neighbor.

At the end of the two stages, the mesh can be viewed as four quarter-size squares (AFEG, FBHE, GEIC, EHDI). Now the process begins again, on each of the four smaller squares, as shown in Figure 26-9. The difference is that the sides of the squares are half the length of the original, and dHeight is divided by the flatness value (the number entered by the user at the start of FractalLand3D).

Figure 26-9. Mesh creation: second iteration

When flatness is > 2, dHeight will decrease faster than the sides of the squares, so after the initial creation of hills and valleys, the rest of the terrain will generally consist of smooth slopes between those features. When flatness < 2, the randomness will be a significant component of the height calculationshills and valleys will be affected by this randomness, resulting in a rockier landscape.

The creation of the corner points is done by makeMesh( ):

     private void makeMesh(  )     {       System.out.println("Building the landscape...please wait");       mesh[0][0] =    // back left         new Point3d( -WORLD_LEN/2, randomHeight(  ), -WORLD_LEN/2 );           mesh[0][WORLD_LEN] =    // back right         new Point3d( WORLD_LEN/2, randomHeight(  ), -WORLD_LEN/2 );           mesh[WORLD_LEN][0] =    // front left         new Point3d( -WORLD_LEN/2, randomHeight(  ), WORLD_LEN/2 );           mesh[WORLD_LEN][WORLD_LEN] =    // front right         new Point3d( WORLD_LEN/2, randomHeight(  ), WORLD_LEN/2 );           divideMesh( (MAX_HEIGHT-MIN_HEIGHT)/flatness, WORLD_LEN/2);     } 

randomHeight( ) selects a random number between the maximum and minimum heights fixed in the class.

divideMesh( ) carries out the diamond and square steps outlined abov, and continues the process by recursively calling itself. Here is the code in outline:

     private void divideMesh(double dHeight, int stepSize)     {       if (stepSize >= 1) {   // stop recursing once stepSize is < 1         // diamond step for all midpoints at this level         // square step for all points surrounding diamonds         divideMesh(dHeight/flatness, stepSize/2);       }     } 

divideMesh( )'s stepSize value starts at WORLD_LEN/2 and keeps being divided by 2 until it reaches 1. In order for the points to be equally spaced over the XZ plane, WORLD_LEN should be a power of 2 (it's 64 in my code).

divideMesh( ) stores the generated points as Point3d objects in mesh[][]. The Landscape object accesses the points by calling FractalMesh's getVertices( ) method. getVertices( ) creates vertices[] and stores references to mesh[][]'s points inside it, in counterclockwise quad order, starting with the bottom-left corner of the quad. For instance, when considering coordinate (x, z), it will copy the points in the order (x, z + 1), (x + 1, z + 1), (x + 1, z), (x, z). This is somewhat clearer by considering Figure 26-10.

The getVertices( ) method is:

     public Point3d[] getVertices(  )     {       int numVerts = WORLD_LEN*WORLD_LEN*4;       Point3d vertices[] = new Point3d[numVerts];       int vPos = 0;       for(int z=0; z<WORLD_LEN; z++) {         for(int x=0; x<WORLD_LEN; x++) {           vertices[vPos++] = mesh[z+1][x];     // counter-clockwise           vertices[vPos++] = mesh[z+1][x+1];   // from bottom-left 

Figure 26-10. Quad ordering for point (x, z)

           vertices[vPos++] = mesh[z][x+1];           vertices[vPos++] = mesh[z][x];         }       }       return vertices;     } 

Printing the Mesh

FractalMesh contains a printMesh( ) method for debugging purposes: it prints either the x-, y- or z-values stored in mesh[][] to a text file.

This method could easily be extended to store the complete mesh to a file. Landscape could then have the option to create its floor by reading in the mesh from the file rather than by using FractalMesh. This is similar to the way that Maze3D in Chapter 25 reads its maze information from a file created by the MazeGen application.

The advantage of this approach is that FractalLand3D could choose to reuse an existing landscape instead of generating a new one every time it was called.

Fixing the Randomness

The diamond and square steps use a random displacement in the range of -dHeight/2 to dHeight/2. This is implemented in two places in FractalMesh, randomRange( ) and randomHeight( ), using Math.random( ) suitably scaled (e.g., in randomRange( )):

     private double randomRange(double h)     // between -h and h     {  return ((Math.random(  ) * 2 * h) - h);  } 

This approach means that the landscape is different every time FractalLand3D is called, even when the same flatness value is supplied by the user.

An interesting alternative, suggested to me by Tom Egan, is to employ the Random.nextDouble( ) method instead. The advantage is that a Random object can be created with a specific seed, which is a number used to generate the sequence of random numbers. If two instances of Random are created with the same seed, and the same sequence of method calls is made for each, they will generate identical sequences of numbers. This means that the fractal will be the same each time, making the landscape the same as well. This property would be useful in games where the landscape must be fixed. The code changes would require a global Random object in FractalMesh:

     private Random rnd = new Random(1L);    // use a fixed seed 

Then randomRange( ) and randomHeight( ) would need their calls to Math.random( ) replaced by rnd.nextDouble( ). For example, randomRange( ) would become:

     private double randomRange(double h)     // between -h and h     {  return ((rnd.nextDouble(  ) * 2 * h) - h);  } 

Now when FractalLand3D is called with a given flatness value, the same landscape will be generated. However, the terrain will appear to be be random. You can still modify it by adjusting the flatness number.