Diamond-Square explanation

Diamond-Square example

de Casteljau explanation

de Casteljau triangle

Putting patches together

Smoothing the borders

Retaining regularity

Non-flat center

One of the problems with constructing large interactive worlds for MMOG's and simulators is simply creating the terrain. For these situations the world must be enormous. Therefore, manually adding all of the vertices for the terrain becomes prohibitive. Thus the goal of generating terrain randomly. One might first imagine simply choosing random heights for each coordinate. As you see, this produces unappealing results.

A solution to this problem is the Diamond-Square algorithm. With this algorithm, one starts by fixing the corners of the map (this forms the "square" part of the algorithm). Then the center point is given a height that is the average of the corners plus some random amount. The next step is to use two consecutive corners with the new center value to define the height of the point in the center of the edge (it doesn't look like a "diamond" until you get away from the edge and start to see all four corners). Each new random value should have a range proportional to the distance the point is from its defining values.