   Fractal Terrain - Midpoint displacement problem
  Well ive been trying to make a fractal terrain generator using the midpoint displacement algorithm and ive come up with a bit of a problem in my implementation. Basiclly I have a list of Squares made up of 4 Points. On every iteration I do this:void Terrain ::Generate(int iterations){for(int i=0; i&lt;iterations; i++){// Get current number of squares making up the terrainint size = squares.size();// Iterate over the current squaresfor(int j=0; j&lt;size; j++){// Get next square from the list and save it to tempSquare *temp = squares.front();// Remove the square from the listsquares.pop_front();// Subdivide into 4 smaller squaresSquare *subSquares[4];temp-&gt;SubDivide(subSquares, roughness, xMax, xMin, yMax, yMin);// Add the new squares to the end of the listfor(int k=0; k&lt;4; k++){squares.push_back(subSquares[k]);}}}}where SubDivide() looks like this:// Divides this square into 4 other squares using random midpoint displacementvoid SubDivide(Square *subSquares[], float roughness, float xMax, float xMin, float yMax,float yMin){// Find the midPoints of the squares edgesPoint *ab = a-&gt;MidPoint(b);Point *bc = b-&gt;MidPoint(c);Point *cd = c-&gt;MidPoint(d);Point *da = d-&gt;MidPoint(a);// Find the Centre of the squarePoint *m = ab-&gt;MidPoint(cd);// Add random displacements to the mid points if not on edgesif(ab-&gt;x != xMax && ab-&gt;x != xMin && ab-&gt;y != yMax && ab-&gt;y != yMin)ab-&gt;add(RandomDisplacement(roughness));if(bc-&gt;x != xMax && bc-&gt;x != xMin && bc-&gt;y != yMax && bc-&gt;y != yMin)bc-&gt;add(RandomDisplacement(roughness));if(cd-&gt;x != xMax && cd-&gt;x != xMin && cd-&gt;y != yMax && cd-&gt;y != yMin)cd-&gt;add(RandomDisplacement(roughness));if(da-&gt;x != xMax && da-&gt;x != xMin && da-&gt;y != yMax && da-&gt;y != yMin)da-&gt;add(RandomDisplacement(roughness));m-&gt;add(RandomDisplacement(roughness));// Create and store the sub squaressubSquares[0] = new Square(a, ab, m, da);subSquares[1] = new Square(ab, b, bc, m);subSquares[2] = new Square(da, m, cd, d);subSquares[3] = new Square(m, bc, c, cd);}Basiclly the problem is when 2 squares share a midpoint, the midpoint is calculated seperatly twice, giving two differnt heights and therefore making gaps in my terrain when i render. Any ideas on how i can fix this problem??   
  I actually just wrote a midpoint displacement class.  lemme know if you want me to post the code.  otherwise i'll continue trying to look through yours =)And i'm not sure I understand your problem.  If you implement the algorithm correctly, each point on the heightmap is only calculated once.  If you're calculating a height for the same place more than once there's a problem with your implementation.-me   ;  here's a good page with a description of the standard midpoint-displacement algorithm:http://www.gameprogrammer.com/fractal.html#diamond-me   ;  Its cause ive structured the grid into "Squares" rather than just a 2D array of points. I didnt really do much research before i started lol was just going on the half a page of details in the openGL green book. I cant be bothered rewritting it all tho, im pretty sure there must be a way to figure out if a mid point is shared that wont slow it down too much but i cant think straight, been trying to figure it out for too long.   ;  I strongly recommend re-writing it to use a 2d heightmap style grid instead of the squares list (you're essentially emulating Recursion with your list there BTW)Not only is the midpoint algorithm a lot easier to code for a flat grid, but that structure will also allow for much faster rendering of the terrain.When I first did my Diamond Squares (midpoint displacement) Terrain, I did an approach similar to yours, where I had a function that subdivided squares into smaller ones... and repeated for them till it hit a set limit...It was Incredibly slow, as the terrain size increases it would use up All the CPU cycles between vsynchs. (very bad)I switched to a grid method and not the terrain is a lot larger, has better details, and only uses about 15% of the CPU cycles between vsynchs.   ;  yeah, i think you're going to find that your algorithm doesn't produce the expected results.  anyway a mechanism by which you could "fix" it would perhaps be to store a m_visited member variable per each "square" or whatever.  So whenever you go to set the height of a location you first check it's m_visited state, if it's false you set the height and set m_visited = true;.  like i said though you're not using the correct algorithm so i don't know if it'll actually produce nice looking terrain.AFAIK you're turning a O(n) into an 0(n^2) so you're seriously screwing over performance.-me   ;  No you don t have to recode your grid implementationJust keep the 2D grid and use a 2d deterministic perlin noiseThis function returns the same pseudo random numbers for each pair of (X,Y) coordinates with the same seed value.I had the same problem a few weeks ago and this one solved it.//generates a 2d perlin noiseinline float32perlinnoise(int32 x, int32 y, int32 iSeed){int n = x + y*57 + iSeed*131;n = (n<<13)^n;return (1.0f - ((n * (n * n * 15731 + 789221) + 1376312589) &0x7fffffff)* 0.000000000931322574615478515625f);};;  Thanks Basiror, I tried using that function but i just seem to get a flat terrain. Do the x y coordinates have to be integer values as im using floating points? What kind of form does the seed take on, is it just a roughness factor which is the same over all the terrain? What kind of values have you been using for the seed to get good results? Thanks Neil;  The function returns values between -1.0f and 1.0f you need to multiply the results with your roughness factor.The seed is just to there to generate different noise distributions for equal x,y values.You need to convert the float x,y to integers anyways since the function is doing some integer arithmetic in the first few lines (<<,^,&)Hope that helps   ;  Nope still just gettig a flat square damn it.Point *PerlinNoise(float x, float y, float roughness, int seed){int n = int(x*100) + int(y*100)*57 + seed * 131;n = (n<<13)^n;n = (1.0f - ((n * (n * n * 15731 + 789221) + 1376312589) &0x7fffffff)* 0.000000000931322574615478515625f);Point *displacement = new Point(0.0, n*roughness, 0.0);return displacement;}using int(time(NULL)) as the seed, i multiplied x and y by 100 before making them ints as their floats in a fairly close range so thought i best spread them out a bit so i dont get all the same value.It just seems to return n=0.0 for all values of x and y, any ideas?   