I am currently stumped by an artefact in my code. It appears to produce very sharp points in a grid pattern that have a noticeable difference in value to their neighbours.
I am following the blog post at http://www.bluh.org/code-the-diamond-square-algorithm/ and converting from whichever language they are using (assuming either C# or Java), and have double-checked that what I am doing should match.
Is there any chance that someone could have a browse over this, and see what I'm doing wrong? I've stepped through it at smaller levels, and stopped it on specific iterations of the algorithm (by unrolling the top loop, and explicitly calling the algorithm a set number of times) and everything seems to work until we get to the very last set of points/pixels.
I use a class (called Matrix) to access the list, and wrap any out of bounds values.
The code for the algorithm is as follows:
class World :
def genWorld (self, numcells, cellsize, seed):
random.seed(seed)
self.dims = numcells*cellsize
self.seed = seed
self.cells = Matrix(self.dims, self.dims)
# set the cells at cellsize intervals
half = cellsize/2
for y in range(0, self.dims, cellsize):
for x in range(0, self.dims, cellsize):
self.cells[x,y] = random.random()
scale = 1.0
samplesize = cellsize
while samplesize > 1:
self._diamondSquare(samplesize, scale)
scale *= 0.8
samplesize = int(samplesize/2)
# I need to sort out the problem with the diamond-square algo that causes it to make the weird gridding pattern
def _sampleSquare(self, x, y, size, value):
half = size/2
a = self.cells[x-half, y-half]
b = self.cells[x+half, y-half]
c = self.cells[x-half, y+half]
d = self.cells[x+half, y+half]
res = min(((a+b+c+d+value)/5.0), 1.0)
self.cells[x, y] = res
def _sampleDiamond(self, x, y, size, value):
half = size/2
a = self.cells[x+half, y]
b = self.cells[x-half, y]
c = self.cells[x, y+half]
d = self.cells[x, y-half]
res = min(((a+b+c+d+value)/5.0), 1.0)
self.cells[x, y] = res
def _diamondSquare(self, stepsize, scale):
half = int(stepsize/2)
for y in range(half, self.dims+half, stepsize):
for x in range(half, self.dims+half, stepsize):
self._sampleSquare(x, y, stepsize, random.random()*scale)
for y in range(0, self.dims, stepsize):
for x in range(0, self.dims, stepsize):
self._sampleDiamond(x+half, y, stepsize, random.random()*scale)
self._sampleDiamond(x, y+half, stepsize, random.random()*scale)
and is called with:
w = World()
w.genWorld(16, 16, 1) # a 256x256 square world, since the numcells is multiplied by the cellsize to give us the length of ONE side of the resulting grid
then I save to file to check the result:
file = io.open("sample.raw",'wb')
arr = [int(i * 255) for i in w.cells.cells] # w.cells.cells should not have a value >= 1.0, so what's going on?
ind = 0
for a in arr:
if a > 255:
print ("arr["+str(ind)+"] ::= "+str(a))
ind += 1
file.write(bytearray(arr))
file.close()
which gives the result:
EDIT: Okay, so it appears that I managed to get it working. I swapped from using functions for working out the diamond and square steps to doing it all in the _diamondSquare() function, but this wasn't the only thing. I also found out that random.random() provides values in the range [0.0 ->1.0), when I was expecting values in the range [-1.0 -> 1.0). After I corrected this, everything started working properly, which was a relief.
Thanks for the advice everyone, here's the working code in case anyone else is struggling with something similar:
Random Function
# since random.random() gives a value in the range [0.0 -> 1.0), I need to change it to [-1.0 -> 1.0)
def rand():
mag = random.random()
sign = random.random()
if sign >=0.5:
return mag
return mag * -1.0
Matrix class
class Matrix:
def __init__(self, width, height):
self.cells = [0 for i in range(width*height)]
self.width = width
self.height = height
self.max_elems = width*height
def _getsingleindex(self, ind):
if ind < 0:
ind *= -1
while ind >= self.max_elems:
ind -= self.max_elems
return ind
def _getmultiindex(self, xind, yind):
if xind < 0:
xind *= -1
if yind < 0:
yind *= -1
while xind >= self.width:
xind -= self.width
while yind >= self.height:
yind -= self.height
return xind + (yind*self.height)
def __getitem__(self, inds):
# test that index is an integer, or two integers, and throw an indexException if not
if hasattr(inds, "__len__"):
if len(inds) > 1:
return self.cells[self._getmultiindex(int(inds[0]), int(inds[1]))]
return self.cells[self._getsingleindex(int(inds))]
def __setitem__(self, inds, object):
# test that index is an integer, or two integers, and throw an indexException if not
if hasattr(inds, "__len__"):
if len(inds) > 1:
self.cells[self._getmultiindex(int(inds[0]),int(inds[1]))] = object
return self.cells[self._getmultiindex(int(inds[0]),int(inds[1]))]
self.cells[self._getsingleindex(int(inds))] = object
return self.cells[self._getsingleindex(int(inds))]
def __len__(self):
return len(self.cells)
The Actual Diamond-Square Generation
# performs the actual 2D generation
class World:
def genWorld (self, numcells, cellsize, seed, scale = 1.0):
random.seed(seed)
self.dims = numcells*cellsize
self.seed = seed
self.cells = Matrix(self.dims, self.dims)
mountains = Matrix(self.dims, self.dims)
# set the cells at cellsize intervals
for y in range(0, self.dims, cellsize):
for x in range(0, self.dims, cellsize):
# this is the default, sets the heights randomly
self.cells[x,y] = random.random()
while cellsize > 1:
self._diamondSquare(cellsize, scale)
scale *= 0.5
cellsize = int(cellsize/2)
for i in range(len(mountains)):
self.cells[i] = self.cells[i]*0.4 + (mountains[i]*mountains[i])*0.6
def _diamondSquare(self, stepsize, scale):
half = int(stepsize/2)
# diamond part
for y in range(half, self.dims+half, stepsize):
for x in range(half, self.dims+half, stepsize):
self.cells[x, y] = ((self.cells[x-half, y-half] + self.cells[x+half, y-half] + self.cells[x-half, y+half] + self.cells[x+half, y+half])/4.0) + (rand()*scale)
# square part
for y in range(0, self.dims, stepsize):
for x in range(0, self.dims, stepsize):
self.cells[x+half,y] = ((self.cells[x+half+half, y] + self.cells[x+half-half, y] + self.cells[x+half, y+half] + self.cells[x+half, y-half])/4.0)+(rand()*scale)
self.cells[x,y+half] = ((self.cells[x+half, y+half] + self.cells[x-half, y+half] + self.cells[x, y+half+half] + self.cells[x, y+half-half])/4.0)+(rand()*scale)
Main Function (added for completeness)
# a simple main function that uses World to create a 2D array of diamond-square values, then writes it to a file
def main():
w = World()
w.genWorld(20, 16, 1)
mi = min(w.cells.cells)
ma = max(w.cells.cells) - mi
# save the resulting matrix to an image file
file = io.open("sample.raw",'wb')
maxed = [(i-mi)/ma for i in w.cells.cells]
arr = [int(i * 255) for i in maxed]
file.write(bytearray(arr))
file.close()
