- Home /
Diamond Square Algorithm
For my project, I've implemented the Diamond Square algorithm to create a height map (currently out of quads) for me, but there are some bugs I can't identify in the code.
It seems that ONE value on top of the height map (shown here) doesn't get set, causing the black spot, and I can't figure out what causes the blocky appearance of the map either.
Any help is appreciated, and tips on increasing performance would be a great help too.
Edit: The black spot is supposed to be created on the "square" part of the function, but I can't find any problems with it as is.
Edit2: Ha! It seems I need to do "int level = squareSize.x - 1" to account for the extra space, so the black spot is solved. Code updated accordingly. Blocky problem still exists, however.
Example Height Map:
Algorithm Code:
public static float[,] DiamondSquare(int x, int y)
{
//Get the square + 1 size for our algorithm, to be cut down to x,y size at end.
Point squareSize = FindSquareSize(x,y);
float[,] squareValues = new float[squareSize.x, squareSize.y];
//Set the corner values.
squareValues[0, 0] = 0.5f;
squareValues[squareSize.x - 1, 0] = 0.5f;
squareValues[0, squareSize.y - 1] = 0.5f;
squareValues[squareSize.x - 1, squareSize.y - 1] = 0.5f;
float variation = 0.5f; //Roughness of the map. Decreases as the algorithm creates the map.
int level = squareSize.x - 1; //The current chunk the algorithm is working on. Whole, half, quaters, eighths, etc.
//Debug.Log("Initial level is: " + level);
//Do the algorithm here.
while(level > 1)
{
int halfstep = level / 2;
//Debug.Log("Half Step is: " + halfstep);
//Do Diamond.
for (int i = halfstep; i < squareSize.x; i += level)
{
for (int j = halfstep; j < squareSize.x; j += level)
{
//Bottom left is (0,0)
float a = squareValues[i - halfstep, j - halfstep]; //Bottom left.
float b = squareValues[i + halfstep, j - halfstep]; //Bottom Right.
float c = squareValues[i - halfstep, j + halfstep]; //Top Left.
float d = squareValues[i + halfstep, j + halfstep]; //Top Right.
float e = ((a + b + c + d) / 4f) + Random.Range(0f, 1f) * variation; //Center
squareValues[i, j] = e;
//Debug.Log("Did a Diamond!");
}
}
int currentColumn = 0;
//Do Square.
for (int i = 0; i < squareSize.x; i += halfstep)
{
currentColumn++;
//If this is an odd column.
if (currentColumn % 2 == 1)
{
for (int j = halfstep; j < squareSize.y; j += level)
{
float a, b, c, d, e;
bool threePoints = false;
try { a = squareValues[i, j + halfstep]; } //Top
catch { a = 0; threePoints = true; }
try { b = squareValues[i, j - halfstep]; } //Bottom
catch { b = 0; threePoints = true; }
try { c = squareValues[i - halfstep, j]; } //Left
catch { c = 0; threePoints = true; }
try { d = squareValues[i + halfstep, j]; } //Right
catch { d = 0; threePoints = true; }
if (threePoints)
{
e = ((a + b + c + d) / 3f) + Random.Range(0f, 1f) * variation;
}
else
{
e = ((a + b + c + d) / 4f) + Random.Range(0f, 1f) * variation;
}
squareValues[i, j] = e;
//Debug.Log("Did a Square!");
}
}
//Else this is an even column.
else
{
for (int j = 0; j < squareSize.y; j += level)
{
float a, b, c, d, e;
bool threePoints = false;
try { a = squareValues[i, j + halfstep]; } //Top
catch { a = 0; threePoints = true; }
try { b = squareValues[i, j - halfstep]; } //Bottom
catch { b = 0; threePoints = true; }
try { c = squareValues[i - halfstep, j]; } //Left
catch { c = 0; threePoints = true; }
try { d = squareValues[i + halfstep, j]; } //Right
catch { d = 0; threePoints = true; }
if (threePoints)
{
e = ((a + b + c + d) / 3f) + Random.Range(0f, 1f) * variation;
}
else
{
e = ((a + b + c + d) / 4f) + Random.Range(0f, 1f) * variation;
}
squareValues[i, j] = e;
//Debug.Log("Did a Square!");
}
}
}
//Reduce range and variation.
level /= 2;
variation /= 2;
}
Quad Maker:
private IEnumerator createHeightMap(float[,] heightArray)
{
for(int i = 0; i < heightArray.GetLength(0); i++)
{
for(int j=0; j < heightArray.GetLength(1); j++)
{
GameObject thisObject = GameObject.CreatePrimitive(PrimitiveType.Quad);
thisObject.transform.position = new Vector3(i, j, 0);
float value = heightArray[i,j];
thisObject.renderer.material.color = new Color(value, value, value, 1);
}
yield return new WaitForEndOfFrame();
}
yield return null;
}
Apologies, if this isn't the right place to post this.
Answer by Masterben135 · Aug 13, 2014 at 08:07 PM
Changing the line int level = squareSize.x
into int level = squareSize.x - 1
fixed the black spot problem, and tweaking the "variation" variable (start at a higher number, and drop off more quickly) seemed to fix the blocky-ness too, so enjoy the free code!