So I wrote a simple script to render some Perlin noise. It's a fast hack, lot's of redundant code. It works and also shows that Python is kinda slow when dealing with large 2-dimensional arrays. Of course using linked lists as arrays is a bad idea. (I later learned that access by index for Python lists is O(1)). So what I'm going to do here is to try out Numpy to optimize my code.
Update: Some benchmarking of my original script and Manu's numpy version. Thanks, Manu!
Original script: 42.360 seconds
import random
import math
import pygame
from pygame.locals import *
class GFX():
def __init__(self):
pygame.init()
self.display_flags = DOUBLEBUF
rect = self.width, self.height = 640, 480
if pygame.display.mode_ok(rect, self.display_flags):
self.screen = pygame.display.set_mode(rect, self.display_flags)
def linear_interp(a, b, x):
return a * (1 - x) + b * x
def cosine_interp(a, b, x):
f = (1 - math.cos(x * math.pi)) * 0.5
return a * (1 - f) + b * f
def cubic_interp(v0, v1, v2, v3, x):
p = (v3 - v2) - (v0 - v1)
Q = (v0 - v1) - p
R = v2 - v0
S = v1
return P * x ** 3 + Q * x ** 2 + R * x + S
class Arr:
def __init__(self):
self.arr = None
def size(self, w, h):
# Sanity checks
if w > 400 or h > 400:
raise Exception("Array size too large.")
self.arr = [[0] * w for i in range(h)]
def noise(self, w, h):
# Sanity checks
if w > 400 or h > 400:
raise Exception("Array size too large.")
print "noise"
# Create 2D array
self.arr = [[0] * w for i in range(h)]
# Fill it with noise
for i in range(h):
for j in range(w):
r = random.random()
self.arr[i][j] = r
def smooth(self, ite):
print "smooth"
h = len(self.arr)
w = len(self.arr[0])
for ps in range(ite):
x, y = 0, 0
for i in self.arr:
for j in i:
lp = self.arr[(x - 1) % w][y]
rp = self.arr[(x + 1) % h][y]
up = self.arr[x][(y - 1) % h]
dp = self.arr[x][(y + 1) % h]
mp = self.arr[x][y]
self.arr[x][y] = (lp + rp + up + dp + mp) / 5
x += 1
x = 0
y += 1
def normalize(self):
print "normalize"
h = len(self.arr)
w = len(self.arr[0])
x, y = 0, 0
max = 0
min = 1
# Find min and max
for i in self.arr:
for j in i:
val = self.arr[x][y]
if val > max:
max = val
if val < min:
min = val
x += 1
x = 0
y += 1
x, y = 0, 0
mult = 1 / (max - min)
for i in self.arr:
for j in i:
self.arr[x][y] -= min
self.arr[x][y] *= mult
x += 1
x = 0
y += 1
return self.arr
def add(self, arr2):
w = len(self.arr)
h = len(self.arr[0])
x, y = 0, 0
for j in self.arr:
for i in j:
self.arr[x][y] += arr2.arr[x][y]
x += 1
x = 0
y += 1
def div(self, val):
x, y = 0, 0
for j in self.arr:
for i in j:
self.arr[x][y] /= val
x += 1
x = 0
y += 1
def cosine_resize(self, mult):
# Sanity checks
if len(self.arr) * mult > 400:
raise Exception("Array size too large (tried resizing).")
print "linear resize"
h = len(self.arr)
w = len(self.arr[0])
w2 = w * mult
h2 = h * mult
arr_new = [[0] * w2 for i in range(h2)]
x, y = 0, 0
for i in self.arr:
for j in i:
p0 = self.arr[x][y]
p1 = self.arr[(x + 1) % w][y]
p2 = self.arr[x][(y + 1) % h]
p3 = self.arr[(x + 1) % w][(y + 1) % h]
for ny in range(mult):
for nx in range(mult):
v0 = cosine_interp(p0, p1, float(nx) / mult)
v1 = cosine_interp(p2, p3, float(nx) / mult)
arr_new[x * mult + nx][y * mult + ny] = cosine_interp(v0, v1, float(ny) / mult)
x += 1
x = 0
y += 1
self.arr = arr_new
def render_arr(screen, arc):
print "render"
x, y = 0, 0
arr = arc.arr
size = len(arr)
for i in range(screen.get_height()):
for j in range(screen.get_width()):
val = arr[x % size][y % size]
if val > 1:
val = 1
if val < 0:
val = 0
val = int(val * 255)
val = val % 256
color = (val, val, val)
screen.set_at((x, y), color)
x += 1
x = 0
y += 1
gfx = GFX()
run = 1
clock = pygame.time.Clock()
pw, ph = 256, 256
depth = 5
arr = []
farr = Arr()
farr.size(pw, ph)
# Generate perlin noise
for i in range(depth):
arr.append(Arr())
d = 2 ** i
arr[-1].noise(pw / d, ph / d)
arr[-1].smooth(3)
arr[-1].cosine_resize(d)
arr[-1].div(2 ** (depth - i))
farr.add(arr[-1])
farr.normalize()
render_arr(gfx.screen, farr)
while run:
events = pygame.event.get()
for event in events:
if event.type == QUIT:
run = 0
pygame.display.flip()
clock.tick(60)
Numpy:
00.639 seconds!
import random
import math
import time
import numpy
import pygame
from pygame.locals import *
class GFX():
def __init__(self):
pygame.init()
self.display_flags = DOUBLEBUF
rect = self.width, self.height = 256, 256
if pygame.display.mode_ok(rect, self.display_flags):
self.screen = pygame.display.set_mode(rect, self.display_flags)
def linear_interp(a, b, x):
return a * (1 - x) + b * x
def cosine_interp(a, b, x):
f = (1 - math.cos(x * math.pi)) * 0.5
return a * (1 - f) + b * f
def cubic_interp(v0, v1, v2, v3, x):
p = (v3 - v2) - (v0 - v1)
Q = (v0 - v1) - p
R = v2 - v0
S = v1
return P * x ** 3 + Q * x ** 2 + R * x + S
class Arr:
def __init__(self, w, h):
self.arr = numpy.zeros((w, h), float)
def size(self, w, h):
# Sanity checks
if w > 400 or h > 400:
raise Exception("Array size too large.")
self.arr = [[0] * w for i in range(h)]
def noise(self, w, h):
# Sanity checks
if w > 400 or h > 400:
raise Exception("Array size too large.")
print "noise"
# Create 2D array
self.arr = numpy.random.random_sample((w, h))
def smooth(self, ite):
print "smooth"
for i in range(ite):
soften = numpy.array(self.arr)
soften[1:,:] += self.arr[:-1,:]
soften[0,:] += self.arr[-1,:]
soften[:-1,:] += self.arr[1:,:]
soften[-1,:] += self.arr[0,:]
soften[:,1:] += self.arr[:,:-1]
soften[:,0] += self.arr[:,-1]
soften[:,:-1] += self.arr[:,1:]
soften[:,-1] += self.arr[:,0]
self.arr = soften / 5
def normalize(self):
print "normalize"
self.arr = (self.arr - self.arr.min()) / (self.arr.max() - self.arr.min())
return self.arr
def add(self, arr2):
self.arr += arr2.arr
def div(self, val):
self.arr /= val
def cosine_resize(self, mult):
# Sanity checks
if len(self.arr) * mult > 400:
raise Exception("Array size too large (tried resizing).")
print "linear resize"
w, h = self.arr.shape
w2, h2 = w*mult, h*mult
arr_new = numpy.zeros((w2, h2), float)
p0 = numpy.copy(self.arr)
p1 = numpy.zeros((w, h), float)
p1[:-1, :] = self.arr[1:, :]
p1[-1, :] = self.arr[0, :]
p2 = numpy.zeros((w, h), float)
p2[:, :-1] = self.arr[:, 1:]
p2[:, -1] = self.arr[:, 0]
p3 = numpy.zeros((w, h), float)
p3[:-1, :-1] = self.arr[1:, 1:]
p3[-1, :] = self.arr[0, :]
p3[:, -1] = self.arr[:, 0]
for nx in range(mult):
v0 = linear_interp(p0, p1, float(nx)/mult)
v1 = linear_interp(p2, p3, float(nx)/mult)
for ny in range(mult):
arr_new[nx::mult, ny::mult] = linear_interp(v0, v1, float(ny)/mult)
self.arr = arr_new
gfx = GFX()
run = 1
clock = pygame.time.Clock()
# run through 10 times for benchmarking purposes
t0 = pygame.time.get_ticks()
for it in xrange(10):
pw, ph = 256, 256
depth = 5
farr = Arr(pw, ph)
# Generate perlin noise
for i in range(depth):
d = 2 ** i
arr = Arr(pw,ph)
arr.noise(pw/d, ph/d)
arr.smooth(3)
arr.cosine_resize(d)
arr.div(2.**(depth-i))
farr.add(arr)
farr.normalize()
pygame.surfarray.use_arraytype("numpy")
print farr.arr.shape
tarr = numpy.zeros((256,256,3))
tarr[:,:,0] = farr.arr
tarr[:,:,1] = farr.arr
tarr[:,:,2] = farr.arr
pygame.surfarray.blit_array(gfx.screen, (tarr *256).astype(int))
print "elapsed: ",pygame.time.get_ticks()-t0
while run:
events = pygame.event.get()
for event in events:
if event.type == QUIT:
run = 0
pygame.display.flip()
clock.tick(60)
