Re: [pygame] [Pygame] Generating a map

[R. Alan Monroe]

> talking a little recently about random terrain generation. One technique
> worth looking at is "Perlins noise," one way of implementing which is to
> draw various surfaces full of random data, overlay them with different
> "weights," and use the result to decide gameplay features such as the
> height of terrain.


After a LOT of trial and error, I managed to implement a proper Perlin
noise routine and draw a heightfield with it. Run main2D.py. I was
surprised at how slow it is.

Alan#http://freespace.virgin.net/hugo.elias/models/m_perlin.htm
#~ http://www.noisemachine.com/talk1/17.html

import random
import math

#===

p=[x for x in range(100)]
random.shuffle(p)
rg=[x/16.0 for x in range(100)]
random.shuffle(rg)
g=[ (math.cos(x), math.sin(x) ) for x in rg]



def noiser(x):
return g[x % 100]

def noiser2(x,y):
return g[ ( x + p[y%100] ) %100 ] 


#===
#===
#===



def interpolatednoiser(n):
intn = int(n)
fracn = n - intn
v1=noiser(intn) / 100.0
v2=noiser(intn + 1) / 100.0
ft = fracn * math.pi#cos interp
f = (1.0 - math.cos(ft)) * .5
return  v1*(1-f) + v2*f


def interpolatednoiser2(x, y):
intx = int(x)
fracx = x - intx
inty = int(y)
fracy = y - inty

gx, gy = noiser2(intx, inty)
v1 = (gx*fracx) + (gy*fracy)

gx, gy = noiser2(intx + 1, inty)
v2 = (gx*(fracx-1)) + (gy*fracy)

gx, gy = noiser2(intx, inty +1)
v3 = (gx*fracx) + (gy*(fracy-1))

gx, gy = noiser2(intx + 1, inty + 1)
v4 = (gx*(fracx-1)) + (gy*(fracy-1))

ftx = fracx * math.pi#cos interp
fx = (1.0 - math.cos(ftx)) * .5
midx1=  v1*(1-fx) + v2*fx  
midx2 = v3*(1-fx) + v4*fx 
fty = fracy * math.pi#cos interp
fy = (1.0 - math.cos(fty)) * .5
return  (midx1*(1.0-fy)) + (midx2 * fy)



#===
#===
#===

def perlin1(x,oct=6,per=0.7):
total=0
j=0
for i in range(oct):
freq = 2**i
amp = per**(i*2)
j = interpolatednoiser( x * freq) * amp
total += j
return total

def perlin2(x, y, oct=6,per=0.9):
total=0
for i in range(oct):
freq = 2**i
amp = per**i  #(i*2)
total += interpolatednoiser2( x * freq, y*freq) * amp
return total

#===
#===
#===

def testperlin1():
for x in range(25):
y=perlin1(x, 4)
z=int(y*50)
print y

def testperlin2():
for y in range(10):
row = []
for x in range(10):
z = perlin2(x/4.0,y/4.0, 4)
row.append(z)
print "%3.3f" %(z,),
print


if __name__ == "__main__":
#print p
#print g
#testperlin1()
testperlin2()


import pygame
import math
from pygame.locals import *

import perlin


def main():
pygame.init()
screen = pygame.display.set_mode((1024,768) )

stretch=50.0
zoom=6
octaves=4
persist=0.7
minc=255
maxc=0
screen.fill( (0,0,0) )
for y in range(400):
for x in range (400):
p=perlin.perlin2(x/stretch, y/stretch, octaves, persist ) 
#*(y/400.0) )
z = p*170 +128 #- 30 #classic
c=int(z)
if c>maxc:
maxc=c
if c255:
c=255
if c<=0:
c=0
pygame.draw.line(screen, (c,c,c), (x+y/3, y + 20), (x+y/3, y + 
(20-(z/4))) ) #grayscale
screen.set_at( (x+512,y), (c,c,c) )

pygame.display.update()
event = pygame.event.poll()
if event.type == QUIT or (event.type == KEYDOWN and event.key == 
K_ESCAPE):
break

print "minc:", minc, " maxc:",maxc

while 1:
event = pygame.event.wait()
if event.type == QUIT or (event.type == KEYDOWN and event.key == 
K_ESCAPE):
break
if (event.type == KEYDOWN and event.key == K_o):
octaves += 1



main()

Re: [pygame] [Pygame] Generating a map

[Kris Schnee]

Screenshots:
http://kschnee.xepher.net/pics/070808island.jpg
http://kschnee.xepher.net/pics/070808nations.jpg

Here's a working version of the diamond-square algorithm code for your
use, using a power-of-two + 1 approach:
http://kschnee.xepher.net/code/diamond_square.py

I tried to implement the idea of reducing the randomness by a factor of
about 1.41 (square root of 2) between each step, but it looks from this
code like I accidentally didn't actually use it! I don't see the ridge
effect mentioned earlier though; the result looks good. The height
values are now 0.0 to 1.0, for arbitrary smoothness. Watching the
program go is fun. If you don't have it display each step, though, it
can generate 513x513 terrain in about 5 seconds.

The code also includes an ErodeTerrain function based on that paper, but
it doesn't seem to work right, consistently blurring stuff towards the
right instead of all around. The error is probably something stupid.

See also:
http://kschnee.xepher.net/code/shrubbery.py

The main attraction here is a function (PaintTerrain) that color-codes a
loaded map based on height values, making it look like an island
landscape. Also included are a function for painting some "national
borders" using a Voronoi variant, and stuff for
loading/saving/converting heightmaps. The screenshots above are from
feeding diamond-square data into this. PaintTerrain is a simple way to
try rendering any experiment with heightmaps.

In hindsight, maybe it should look at slopes as well as absolute 
heights. Another upgrade would be to make the terrains relative. Pick, 
say, 100 regularly spaced points on the map, sort the heights, and set 
the water level such that N% of them are below it.


Also:
http://kschnee.xepher.net/code/voronoi.py

This one's a demo of the Voronoi algorithm for making a bubble sort of
thing. It's not a good implementation, and it includes commented-out
earlier attempts that produced weird but interesting results.

As I've said, I've been wanting to make island landscapes for game
purposes, specifically 1000x1000 maps with a terrain type for each tile.
The result from the above two programs looks better than my ad-hoc
island maker, but there are some problems for my purposes: it needs
smoothing, it's a weird size, and there's no guarantee that the
"islands" won't be right against the map edge even when the DS code is
seeded with zeroes at the corners. I could crop, force the edges down in
some efficient way, and apply smoothing, scale2x, and erosion, maybe. Or
just use fewer, bigger tiles; or even use a genuinely smaller map size.
Thoughts?

Kris
"...Only slightly higher, so we get a two-level effect, with a little
path running down the middle."

Re: [pygame] [Pygame] Generating a map

[massimo s.]

DR0ID ha scritto:
> Hello again
> 
> Out of curosity I have written my own version, I think it should look
> like the attached picture.

Looks eerily like the radar Titan images from Cassini!

m.

Re: [pygame] [Pygame] Generating a map

[Dave LeCompte (really)]

"Kris Schnee" <[EMAIL PROTECTED]> wrote:
> 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 would probably have some sort of scale factor based on the scale of the
"bubble/ridge" features - perhaps scanning the map for average "bubble"
size.


> I see that  has a Python
> implementation of Voronoi code as a "Crystalize" filter for images.

I adapted the Voronoi/Delaunay code from Graphics Gems IV, it was pretty
easy. I have yet to make heavy use of it, but I've already used it to draw
some "organic" looking diagrams.

Documentation here: http://www.meatengine.com/overview.html#math-voronoi
Download here: http://www.meatengine.com/


> 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.

Yeah, you have to be careful with your indices - I haven't looked at your
code, but I typically make my diamond-square arrays 2^n+1, so 257x257 in
your case. I don't use wrap around, which you mention, so maybe you're OK
in starting with 256x256 - that additional column and row could wrap
around back to row or column #0.


Another thing that I struggled with for a long time was how to manage the
scale of my displacements with diamond-square. There are two steps in
diamond-square; the diamond and the square (of course). From one diamond
step to the next diamond step, and from one square step to the next square
step, the linear distances that you're working with goes down by a factor
of two - so, if you're trying to get the most self-similar landscapes, the
displacement scale should also go down by a factor of two.

The insight that I was missing, though, is that really the diamond and the
square steps are closely related, and should be considered as doing the
same operation, but with a 45 degree rotation. Once you see that, you can
see that the linear distances go down by a factor of sqrt(2) between steps
(diamond to square or square to diamond), with a combined factor of two
over a pair of steps. So, in order for the features to scale properly, the
displacement scale should be divided by root two. When I wasn't doing
this, I was getting really nasty seams aligned with the x and y axes - not
immediately noticeable, but when I lit the terrain, I'd see a ridge
running right along the middle of my data set, straight up the y axis.

Your mileage will vary, but this was something I've seen over and over
again, not only in my own fractal subdivision (diamond-square)
implementations, but other peoples', as well. An example is here:

http://www.bigdicegames.com/SpareTime/Images/Terrain/fracsubdseams.png

Just to be clear: the data in that image come from one of my own (failed)
experiments, but I'm using Terragen to render it. Terragen's own terrain
generation doesn't suffer from that bug.

-Dave LeCompte

Re: [pygame] [Pygame] Generating a map

[Kris Schnee]

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  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, [EMAIL PROTECTED]
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),r

Re: [pygame] [Pygame] Generating a map

[Dave LeCompte (really)]

[EMAIL PROTECTED] wrote:

> I don't know of a tutorial on exactly what you want, but we've been
> talking a little recently about random terrain generation. One technique
> worth looking at is "Perlins noise,"

This is a good tool to have in your arsenal - for Perlin's own presentation:
http://www.noisemachine.com/talk1/

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


One thing I've had a hard time finding good references for is a means for
procedurally modeling the effect of glaciers on a heightfield terrain.
River erosion is pretty well covered, and you get "V"-shaped valleys as a
result of rivers. Glaciers behave differently, and their valleys tend to
be more "U" shaped.

I've tinkered with World Machine [http://www.world-machine.com/] and
Terragen [http://www.planetside.co.uk/terragen/] to play around with
terrain, but I'd like to be able to drive the whole process from within my
games, and there are a few pieces that I'm not sure how I'd implement.
Like glaciers.


-Dave LeCompte

Re: [pygame] [Pygame] Generating a map

[kschnee]

On Mon, August 6, 2007 7:06 pm, Jérôme Brilland wrote:
> Hello,
>
>
> I would like to develop a strategy game using Python and Pygame. I would
> like to know if it's possible to generate a random map divided into regions
> with Pygame. Is there a tutorial for this feature ?

I don't know of a tutorial on exactly what you want, but we've been
talking a little recently about random terrain generation. One technique
worth looking at is "Perlins noise," one way of implementing which is to
draw various surfaces full of random data, overlay them with different
"weights," and use the result to decide gameplay features such as the
height of terrain.

I built a crude terrain generator with an ad-hoc method. I think that the
code for it is "castor.py" in
. The results
look like this: 

It'd be helpful to know what kind of features you want to focus on, and
whether the terrain is to be 2D or 3D.

Re: [pygame] [Pygame] Generating a map

[Ian Mallett]

On 8/6/07, Jérôme Brilland <[EMAIL PROTECTED]> wrote:
>
> Hello,
>
> I would like to develop a strategy game using Python and Pygame. I would
> like to know if it's possible to generate a random map divided into
> regions with Pygame. Is there a tutorial for this feature ?
>
> Thanks
> Jérôme Brilland


I don't know of a tutorial to do this, but you could make an array of tiles
and add instances of a terrain class at an x and y coord.:
pseudocode:

class terrain:
  def __init__(self,x,y,terrain_type):
self.x = x
self.y = y
self.terrain_type = terrain_type
terrains = []
x_dimension = 5; y_dimension = 5 #This can obviously be changed

y_coord = 0
while y_coord < y_dimension:
  x_coord = 0
  while x_coord < x_dimension:
terrains.append(  terrain(x_coord, y_coord, math.randint(1,6))  )
x_coord += 1
  y_coord += 1

#(later)

for terrain in terrains:
  if terrain.terrain_type == 1:
#draw terrain type 1 at pos (terrain.x,terrain.y)
  elif terrain.terrain_type == 2:
#draw terrain type 2 at pos (terrain.x,terrain.y)
  .
  .
  .
  .

[pygame] [Pygame] Generating a map

[Jérôme Brilland]

Hello,

I would like to develop a strategy game using Python and Pygame. I would
like to know if it's possible to generate a random map divided into
regions with Pygame. Is there a tutorial for this feature ?

Thanks
Jérôme Brilland