[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: [pygame] [Pygame] Generating a map



Dave LeCompte (really) wrote:
Also, there's a pretty good paper about the tricks that the "Tribal
Trouble" guys used to make their terrain here:
http://oddlabs.com/download/terrain_generation.pdf

That paper was really useful. I was able to implement a version of the Voronoi (bubble/ridge thing) with some fiddling, and accidentally made what appears to be a fractal by accident. It's attached as "my_generation.py" if you want to see the messy code. The part that was hard to figure out was what the paper described as:
height = (distance to nearest point)*(arbitrary constant 1)
The distance ranges from 0 to many thousands, so what's a good way to convert that to a 0-255 range or the 0.0-1.0 range used in the paper? I ended up doing it in an arbitrary way.

I see that <http://home.scarlet.be/zoetrope/voronoi/> has a Python implementation of Voronoi code as a "Crystalize" filter for images.

I also tried to implement a diamond-square algorithm, but something's not quite right about it. If I force the squares to be higher than normal (adding 64 to the height values), I can see that it's calculating all the pixels in the image, but normally most of the image ends up black. The code for that is attached as "my_generation3.py"; anyone know how to fix it? The problem seems to be that I'm using a 256x256 bitmap, and the calculation of each cell's "neighbors" is off by one pixel or something where it wraps around the edges, so that it finds zeroed pixels instead of the already-calculated ones.
"""
Terrain generation experiments (1)
Public domain. Based on an academic paper:

Realtime Procedural Terrain Generation
Realtime Synthesis of Eroded Fractal Terrain for Use in Computer Games
Jacob Olsen, xenorg@xxxxxxxxxxxx
Department of Mathematics And Computer Science (IMADA)
University of Southern Denmark
October 31, 2004

This is a quick and dirty implementation of some of the "Voronoi" algorithm
mentioned in the above paper, for terrain generation. This code was done
by Kris Schnee late one night and should not be blamed on the authors.
"""

import pygame
pygame.init()
import random
random.seed("Next My Generation") ## Song title I was listening to
screen = pygame.display.set_mode((512,512))

#### Here's one way of generating some random static.
##t_random = pygame.surface.Surface((256,256))
##t_random.fill((0,0,0))
##for y in range(0,256):
##    for x in range(0,256):
##        c = random.randint(0,128)+random.randint(0,64)+random.randint(0,32)+random.randint(0,16)+random.randint(0,8)
##        t_random.set_at((x,y),(c,c,c))
##
##for r in range(5):
##    for y in range(1,255):
##        for x in range(1,255):
##            n = (t_random.get_at((x,y-1))[0]+t_random.get_at((x,y+1))[0]+
##                 t_random.get_at((x-1,y))[0]+t_random.get_at((x+1,y))[0])/4
##
##            h = t_random.get_at((x,y))[0]
##            if n > h+16:
##                h += 16
##                t_random.set_at((x,y),(h,h,h))
##            elif n < h-16:
##                h -= 16
##                t_random.set_at((x,y),(h,h,h))
##t_random = pygame.transform.scale2x(t_random)
##pygame.image.save(t_random,"smoothed_static.bmp")
## Once you generate this using the above code, just use this line:
##t_random = pygame.image.load("smoothed_static.bmp").convert()


#### This chunk of code doesn't do what it's supposed to,
#### but the effect is cool. A fractal?
##import pygame
##pygame.init()
##import random
##random.seed("Next My Generation")
##screen = pygame.display.set_mode((512,512))
##
##voronoi = pygame.surface.Surface((500,500))
##voronoi.fill((0,0,0))
##for zy in range(0,512,100):
##    for zx in range(0,512,100):
##        f1 = (random.randint(zx,zx+0),random.randint(zy,zy+0))
##        for y in range(zy,zy+99):
##            for x in range(zx,zx+99):
##                dist_approx = pow(zx-x,2) + pow(zy-y,2)
##                h = dist_approx
##                voronoi.set_at((x,y),h) ## Try multiplying h by a power of 2!
##
##screen.blit(voronoi,(0,0))
##pygame.display.update()



#### Another neat glitch effect, kind of like brushed steel.
##t_voronoi = pygame.surface.Surface((512,512))
##t_voronoi.fill((0,0,0))
##for zy in range(0,512,128):
##    for zx in range(0,512,128):
##        f1x,f1y = (random.randint(zx,zx+127),random.randint(zy,zy+127))
##        f2x,f2y = (random.randint(zx,zx+127),random.randint(zy,zy+127))
##        for y in range(zy,zy+128):
##            for x in range(zx,zx+128):
##                dist_approx_1 = pow(f1x-x,2) + pow(f1y-y,2)
##                h1 = int((dist_approx_1 / 32768.0) * 256)
##                dist_approx_2 = pow(f2x-x,2) + pow(f2y-y,2)
##                h2 = 1 / (int((dist_approx_2 / 32768.0) * 256)+1)
##                c = h1-(h2/2)
##                t_voronoi.set_at((x,y),(c,c,c))


t_voronoi = pygame.surface.Surface((512,512))
t_voronoi.fill((0,0,0))
feature_points = []
for zy in range(0,512,128):
    for zx in range(0,512,128):
        f1x,f1y = (random.randint(zx,zx+127),random.randint(zy,zy+127))
        feature_points.append((f1x,f1y))
##        f2x,f2y = (random.randint(zx,zx+127),random.randint(zy,zy+127))

for y in range(0,512):
    for x in range(0,512):
        closest = 99999
        for point in feature_points:
            dist_approx_1 = pow(point[0]-x,2) + pow(point[1]-y,2)
            if dist_approx_1 < closest:
                closest = dist_approx_1
        ## Base the height on the distance to the nearest feature point.
        ## I don't have this part down in an ideal way.

        ## This line version doesn't work.
##        h1 = int((1-(closest/262144.0)) * 256)-1
        ## This version gives little circles.
##        h1 = [0,255][closest < 100]
        ## This version gives dark bubbles on white.
##        h1 = (closest/10000.0)*256
        ## White bubbles on black.
        h1 = (1-(closest/20000.0))*256
        ## Fuzzy; reminds me of some cheese I left in the fridge too long.
##        h1 = (1-(float(closest)/random.randint(3000,40000)))*256

        h1 = max(min(h1,255),0)
        c = h1
        t_voronoi.set_at((x,y),(c,c,c))

## Render the Voronoi terrain.
terrain = t_voronoi
screen.blit(terrain,(0,0))

#### Alternative: Blend it with some random static.
##t_voronoi.set_alpha(200)
##t_random.blit(t_voronoi,(0,0))
##terrain = t_random
##screen.blit(terrain,(0,0))

pygame.display.update()
"""
Terrain generator using diamond-square algorithm.
Something is not quite right here, because the points in one phase or
the other are off by one, causing them to find zero values instead of the
points they're supposed to find. I'm using a 256x256 map, which maybe should
be 255x255, but am not quite sure how it's meant to work.
"""

KLUDGE = 64 ## ( >0 makes the pattern visible despite being flawed )

import pygame
pygame.init()
import random
random.seed("Next My Generation")
size = 256
screen = pygame.display.set_mode((size,size))
screen.fill((64,0,0))

def DisplayAsImage(heightmap):
    screen.fill((64,0,0))
    terrain = pygame.surface.Surface((size,size))
    terrain.fill((0,0,0))
    for y in range(size):
        for x in range(size):
            h = heightmap[x][y]
            terrain.set_at((x,y),(h,h,h))

    screen.blit(terrain,(0,0))
    pygame.display.update()


heightmap = []
for x in range(size):
    heightmap.append([])
    for y in range(size):
        heightmap[-1].append(0)
##        heightmap[-1].append(random.randint(0,255)) ## Placebo.
for point in ((0,0),(size-1,0),(0,size-1),(size-1,size-1)):
    heightmap[point[0]][point[1]] = 128

cell_size = size
half_cell_size = cell_size/2
chaos = 128
iteration = 0

while cell_size > 0:
##for n in range(1):
    print "Iteration: "+str(iteration)
    iteration += 1
    for anchor_y in range(0,size,cell_size):
        for anchor_x in range(0,size,cell_size):
##            print "Anchor: "+str((anchor_x,anchor_y))
            center_x = anchor_x - 1 + half_cell_size
            center_y = anchor_y - 1 + half_cell_size

            ## The "square" phase: calculate the center point.
##            print "Center: "+str((center_x, center_y))
            neighbors = ((anchor_x,anchor_y),
                         (anchor_x+cell_size-1,anchor_y),
                         (anchor_x,anchor_y+cell_size-1),
                         (anchor_x+cell_size-1,anchor_y+cell_size-1))
            try:
                average_height = sum((heightmap[n[0]][n[1]] for n in neighbors))/4
            except:
                print neighbors
                raise "Oof."
##            print "Average: "+str(average_height)
            h = average_height + random.randint(-chaos,chaos)+KLUDGE
            h = max(min(h,255),0) ## Keep within 0-255 range.
            heightmap[center_x][center_y] = h
            
            ## The "diamond" phase: calculate the edge points.
            edge_points = ((center_x,0),
                           (0,center_y),
                           (size-1,center_y),
                           (center_x,size-1))
            for point in edge_points:
##                print "Edge point: "+str(point)
##                neighbors = [(point[0],point[1]-half_cell_size),
##                             (point[0]-half_cell_size,point[1]),
##                             (point[0]+half_cell_size,point[1]),
##                             (point[0],point[1]+half_cell_size)]
                neighbors = [[point[0],point[1]-half_cell_size],
                             [point[0]-half_cell_size,point[1]],
                             [point[0]+half_cell_size,point[1]],
                             [point[0],point[1]+half_cell_size]]
                for n in range(4):
                    neighbor = neighbors[n]
                    if neighbor[0] < 0:
                        neighbors[n][0] += size
                    elif neighbor[0] > 255:
                        neighbors[n][0] -= size
                    if neighbor[1] < 0:
                        neighbors[n][1] += size
                    elif neighbor[1] > 255:
                        neighbors[n][1] -= size

##                ## Kludge to keep first-round points within bounds.
##                if neighbors[2][0] >= size:
##                    neighbors[2] = (point[0]-half_cell_size-1,point[1])
##                if neighbors[3][1] >= size:
##                    neighbors[3] = (point[0],point[1]-half_cell_size-1)
##                print "  Neighbors: "+str(neighbors)
                try:
                    average_height = sum((heightmap[n[0]][n[1]] for n in neighbors))/4
                except:
                    print neighbors
                    raise "Eek!"
                h = average_height + random.randint(-chaos,chaos)
                h = max(min(h,255),0) ## Keep within 0-255 range.
                heightmap[point[0]][point[1]] = h

    cell_size /= 2
    half_cell_size /= 2
    chaos = max(chaos/2,1)
    DisplayAsImage(heightmap)