3D游戏地图的模拟程序

/* Written by: Paul E. Martz Copyright 1997 by Paul E. Martz, all right reserved Non-commercial use by individuals is permitted. */ #include <stdio.h> #include <stdlib.h> #include "math.h" #include "fractmod.h" #ifdef __cplusplus extern "C" { #endif /* Compiling with DEBUG defined can produce enormous amounts of output to stdout. Beware. #define DEBUG */ #ifdef _WINDOWS /* Was written for HPUX. Handle Win32 compiles */ #define random() rand() #define srandom(x) srand(x) #endif /* * randNum - Return a random floating point number such that * (min <= return-value <= max) * 32,767 values are possible for any given range. */ static float randnum (float min, float max) { int r; float x; r = random (); x = (float)(r & 0x7fff) / (float)0x7fff; return (x * (max - min) + min); } /* * fractRand is a useful interface to randnum. */ #define fractRand(v) randnum (-v, v) /* * avgEndpoints - Given the i location and a stride to the data * values, return the average those data values. "i" can be thought of * as the data value in the center of two line endpoints. We use * "stride" to get the values of the endpoints. Averaging them yields * the midpoint of the line. * * Called by fill1DFractArray. */ static float avgEndpoints (int i, int stride, float *fa) { return ((float) (fa[i-stride] + fa[i+stride]) * .5f); } /* * avgDiamondVals - Given the i,j location as the center of a diamond, * average the data values at the four corners of the diamond and * return it. "Stride" represents the distance from the diamond center * to a diamond corner. * * Called by fill2DFractArray. */ static float avgDiamondVals (int i, int j, int stride, int size, int subSize, float *fa) { /* In this diagram, our input stride is 1, the i,j location is indicated by "X", and the four value we want to average are "*"s: . * . * X * . * . */ /* In order to support tiled surfaces which meet seamless at the edges (that is, they "wrap"), We need to be careful how we calculate averages when the i,j diamond center lies on an edge of the array. The first four 'if' clauses handle these cases. The final 'else' clause handles the general case (in which i,j is not on an edge). */ if (i == 0) return ((float) (fa[(i*size) + j-stride] + fa[(i*size) + j+stride] + fa[((subSize-stride)*size) + j] + fa[((i+stride)*size) + j]) * .25f); else if (i == size-1) return ((float) (fa[(i*size) + j-stride] + fa[(i*size) + j+stride] + fa[((i-stride)*size) + j] + fa[((0+stride)*size) + j]) * .25f); else if (j == 0) return ((float) (fa[((i-stride)*size) + j] + fa[((i+stride)*size) + j] + fa[(i*size) + j+stride] + fa[(i*size) + subSize-stride]) * .25f); else if (j == size-1) return ((float) (fa[((i-stride)*size) + j] + fa[((i+stride)*size) + j] + fa[(i*size) + j-stride] + fa[(i*size) + 0+stride]) * .25f); else return ((float) (fa[((i-stride)*size) + j] + fa[((i+stride)*size) + j] + fa[(i*size) + j-stride] + fa[(i*size) + j+stride]) * .25f); } /* * avgSquareVals - Given the i,j location as the center of a square, * average the data values at the four corners of the square and return * it. "Stride" represents half the length of one side of the square. * * Called by fill2DFractArray. */ static float avgSquareVals (int i, int j, int stride, int size, float *fa) { /* In this diagram, our input stride is 1, the i,j location is indicated by "*", and the four value we want to average are "X"s: X . X . * . X . X */ return ((float) (fa[((i-stride)*size) + j-stride] + fa[((i-stride)*size) + j+stride] + fa[((i+stride)*size) + j-stride] + fa[((i+stride)*size) + j+stride]) * .25f); } #ifdef DEBUG /* * dump1DFractArray - Use for debugging. */ void dump1DFractArray (float *fa, int size) { int i; for (i=0; i<size; i++) printf ("(%.2f) ", fa[i]); printf ("\n"); } /* * dump2DFractArray - Use for debugging. */ void dump2DFractArray (float *fa, int size) { int i, j; for (i=0; i<size; i++) { j=0; printf ("[%d,%d]: ", i, j); for (; j<size; j++) { printf ("(%.2f) ", fa[(i*size)+j]); } printf ("\n"); } } #endif /* * powerOf2 - Returns 1 if size is a power of 2. Returns 0 if size is * not a power of 2, or is zero. */ static int powerOf2 (int size) { int i, bitcount = 0; /* Note this code assumes that (sizeof(int)*8) will yield the number of bits in an int. Should be portable to most platforms. */ for (i=0; i<sizeof(int)*8; i++) if (size & (1<<i)) bitcount++; if (bitcount == 1) /* One bit. Must be a power of 2. */ return (1); else /* either size==0, or size not a power of 2. Sorry, Charlie. */ return (0); } /* * fill1DFractArray - Tessalate an array of values into an * approximation of fractal Brownian motion. */ void fill1DFractArray (float *fa, int size, int seedValue, float heightScale, float h) { int i; int stride; int subSize; float ratio, scale; if (!powerOf2(size) || (size==1)) { /* We can't tesselate the array if it is not a power of 2. */ #ifdef DEBUG printf ("Error: fill1DFractArray: size %d is not a power of 2.\n"); #endif /* DEBUG */ return; } /* subSize is the dimension of the array in terms of connected line segments, while size is the dimension in terms of number of vertices. */ subSize = size; size++; /* initialize random number generator */ srandom (seedValue); #ifdef DEBUG printf ("initialized\n"); dump1DFractArray (fa, size); #endif /* Set up our roughness constants. Random numbers are always generated in the range 0.0 to 1.0. 'scale' is multiplied by the randum number. 'ratio' is multiplied by 'scale' after each iteration to effectively reduce the randum number range. */ ratio = (float) pow (2.,-h); scale = heightScale * ratio; /* Seed the endpoints of the array. To enable seamless wrapping, the endpoints need to be the same point. */ stride = subSize / 2; fa[0] = fa[subSize] = 0.f; #ifdef DEBUG printf ("seeded\n"); dump1DFractArray (fa, size); #endif while (stride) { for (i=stride; i<subSize; i+=stride) { fa[i] = scale * fractRand (.5f) + avgEndpoints (i, stride, fa); /* reduce random number range */ scale *= ratio; i+=stride; } stride >>= 1; } #ifdef DEBUG printf ("complete\n"); dump1DFractArray (fa, size); #endif } /* * fill2DFractArray - Use the diamond-square algorithm to tessalate a * grid of float values into a fractal height map. */ void fill2DFractArray (float *fa, int size, int seedValue, float heightScale, float h) { int i, j; int stride; int oddline; int subSize; float ratio, scale; if (!powerOf2(size) || (size==1)) { /* We can't tesselate the array if it is not a power of 2. */ #ifdef DEBUG printf ("Error: fill2DFractArray: size %d is not a power of 2.\n"); #endif /* DEBUG */ return; } /* subSize is the dimension of the array in terms of connected line segments, while size is the dimension in terms of number of vertices. */ subSize = size; size++; /* initialize random number generator */ srandom (seedValue); #ifdef DEBUG printf ("initialized\n"); dump2DFractArray (fa, size); #endif /* Set up our roughness constants. Random numbe