"""Diamond Square Generates semi-random greyscale data suitable for game terrain or graphics, using the standard "Diamond Square Algorithm." By Kris Schnee Public Domain. """ import pygame pygame.init() import random random.seed("Island In the Sun") TERRAIN_SIZE = 513 ## A power of 2, plus 1. BACKGROUND_COLOR = (0,32,96) ## Just for display purposes. screen = pygame.display.set_mode((TERRAIN_SIZE+20,TERRAIN_SIZE+20)) def DisplayAsImage(heightmap): """Displays a square heightmap as an image. The range of values is assumed to be 0.0 to 1.0, in a 2D, square array. The range is converted to greyscale values of 0 to 255.""" size = len(heightmap) screen.fill(BACKGROUND_COLOR) terrain = pygame.surface.Surface((size,size)) terrain.fill((0,0,0)) for y in range(size): for x in range(size): h = int(heightmap[x][y] * 255) try: terrain.set_at((x,y),(h,h,h)) except: print "Error on x,y: "+str((x,y))+"; heightmap --> 0-255 value: "+str((heightmap[x][y],h)) screen.blit(terrain,(10,10)) pygame.display.update() def SaveImage(filename="terrain.bmp",border=False): """Save what's on the screen. Flying toasters not included.""" if border: pygame.image.save(screen,filename) else: s = pygame.surface.Surface((screen.get_width()-20,screen.get_height()-20)) s.blit(screen,(0,0),(10,10,TERRAIN_SIZE,TERRAIN_SIZE)) pygame.image.save(s,filename) def MakeHeightMap(size,random_data=False): """Generate random static or a blank map.""" heightmap = [] if random_data: for x in range(size): heightmap.append([]) for y in range(size): heightmap[-1].append( random.random() ) else: for x in range(size): heightmap.append([]) for y in range(size): heightmap[-1].append(0.0) return heightmap def MakeDiamondSquareTerrain(heightmap,show_in_progress=False,seed_values=(.5,.5,.5,.5)): """Make procedural terrain using the D/S Algorithm.""" size = len(heightmap) ## Seed the corners. corners = ((0,0),(size-1,0),(0,size-1),(size-1,size-1)) for n in range(4): point = corners[n] heightmap[point[0]][point[1]] = seed_values[n] ## Starting values. size_minus_1 = size - 1 ## For edge-wrapping purposes. cell_size = size-1 ## Examine squares of this size within the heightmap. cell_size_half = cell_size / 2 iteration = 0 ## How many times have we done the algorithm? (just FYI) chaos = 1.0 ## Total possible variation of a height from expected average. chaos_half = chaos * .5 ## Possible variation up or down. diamond_chaos_half = (chaos/1.414)*.5 ## Reduced by sqrt(2) for D step. ## (Wouldn't "Diamond Chaos Half" be a cool anime series title?) while cell_size > 1: ## For actual use. ## Begin the algorithm. print "Iteration: "+str(iteration) ## print "Chaos: "+str(chaos)+" C.Half: "+str(chaos_half)+" D.C.Half: "+str(diamond_chaos_half) iteration += 1 """Find the "anchor points" that mark the upper-left corner of each cell.""" for anchor_y in range(0,size-1,cell_size): for anchor_x in range(0,size-1,cell_size): ## Calculate the center of the cell. cx = anchor_x + cell_size_half cy = anchor_y + cell_size_half ## The "Diamond" phase. ## Find the center's diagonal "neighbors." neighbors = ([cx-cell_size_half,cy-cell_size_half], [cx+cell_size_half,cy-cell_size_half], [cx-cell_size_half,cy+cell_size_half], [cx+cell_size_half,cy+cell_size_half]) ## Correct for points outside the map. for n in range(4): neighbor = neighbors[n] if neighbor[0] < 0: neighbors[n][0] += size elif neighbor[0] > size: neighbors[n][0] -= size if neighbor[1] < 0: neighbors[n][1] += size elif neighbor[1] > size: neighbors[n][1] -= size average = sum([heightmap[n[0]][n[1]] for n in neighbors]) * .25 h = average - chaos_half + (random.random() * chaos) ## h = average ## Test: No randomness. h = max(0.0,min(1.0,h)) heightmap[cx][cy] = h ## The "Square" phase. ## Calculate four "edge points" surrounding the center. edge_points = ((cx,cy-cell_size_half), (cx-cell_size_half,cy), (cx+cell_size_half,cy), (cx,cy+cell_size_half)) for point in edge_points: neighbors = [[point[0],point[1]-cell_size_half], [point[0]-cell_size_half,point[1]], [point[0]+cell_size_half,point[1]], [point[0],point[1]+cell_size_half]] ## Correct for points outside the map. for n in range(4): neighbor = neighbors[n] if neighbor[0] < 0: neighbors[n][0] += size elif neighbor[0] > size_minus_1: neighbors[n][0] -= size if neighbor[1] < 0: neighbors[n][1] += size elif neighbor[1] > size_minus_1: neighbors[n][1] -= size average = sum([heightmap[n[0]][n[1]] for n in neighbors]) * .25 h = average - chaos_half + (random.random() * chaos) h = max(0.0,min(1.0,h)) ## h = average ## Test: No randomness. heightmap[point[0]][point[1]] = h ## End of iteration. Reduce cell size and chaos. cell_size /= 2 cell_size_half /= 2 chaos *= .5 chaos_half = chaos * .5 diamond_chaos_half = (chaos / 1.414) * .5 if show_in_progress: DisplayAsImage(heightmap) return heightmap def ErodeTerrain(heightmap,iterations=1,show_in_progress=True): """Not working yet; always seems to blur to the right.""" erosion_threshold = .5 count = 0 ycount1, ycount2 = 0,0 xcount1, xcount2 = 0,0 for n in range(iterations): print "Iteration: "+str(n) size = len(heightmap) for y in range(1,size-1): for x in range(1,size-1): neighbors = ((x,y-1), (x-1,y), (x+1,y), (x,y+1)) height_here = heightmap[x][y] slopes = ((height_here-heightmap[x][y-1]), (height_here-heightmap[x-1][y]), (height_here-heightmap[x+1][y]), (height_here-heightmap[x][y+1])) steepest_neighbor = 0 for n in range(0,4): if slopes[n] > steepest_neighbor: steepest_neighbor = n ## Debugging code. if steepest_neighbor == 1: xcount1 += 1 elif steepest_neighbor == 2: xcount2 += 1 elif steepest_neighbor == 0: ycount1 += 1 elif steepest_neighbor == 3: ycount2 += 1 else: raise "Huh? "+str(steepest_neighbor) steepest_slope = slopes[steepest_neighbor] steepest_neighbor = neighbors[steepest_neighbor] if steepest_slope > 0 and steepest_slope < erosion_threshold: heightmap[x][y] -= steepest_slope*.5 heightmap[steepest_neighbor[0]][steepest_neighbor[1]] += steepest_slope*.5 count += 1 if show_in_progress: DisplayAsImage(heightmap) print count print (xcount1,xcount2,ycount1,ycount2) return heightmap ## Autorun. import time heightmap = MakeHeightMap(TERRAIN_SIZE,False) start_time = time.time() heightmap = MakeDiamondSquareTerrain(heightmap,True,(0.0,0.0,0.0,0.0)) SaveImage("uneroded.bmp") ##heightmap = ErodeTerrain(heightmap,20,True) ##SaveImage("eroded.bmp") end_time = time.time() print "Generated terrain in "+str(end_time-start_time)[:5]+" seconds." DisplayAsImage(heightmap)