random map generator

[Raknarg]

I know it's not anything new, but I'm pretty proud of it as I've been trying to figure this out for a very long time.

A while ago I looked up the square diamond algorithm for map generation, and it made sense but I could not put it in code. However, this morning I realized I could do something like it in the opposite direction. Basically with a square diamond algorithm you're supposed to start with a map, and fill in the gaps as you go. However what I did here was start with a 2x2 square and progressively make it bigger as I go, creating gaps and filling it in like the square diamond method is supposed to. Produces great results.

Note I use pygame to display it, so if you don't have it it will not show anything, but the algorithm still works. It seems fairly fast as well, even though I think it's probably fairly inefficient.

Python:

from __future__ import division from random import randint, random import pygame import sys # Shifts an element in a from shiftID to position shiftTargetID def shift_down(a, shiftID, shiftTargetID):     newa = a     for i in range(shiftTargetID+1, shiftID+1)[::-1]:         temp = newa[i]         newa[i] = newa[i-1]         newa[i-1] = temp             return newa # Takes in a (2**n)+1 x (2**n)+1 map and converts it to a (2**(n+1))+1 x (2**(n+1))+1, with all the old data surrounded 0's def scale_map(m):     newm = m     initsize = len(m)     for i in range(initsize):         ID = 0         while len(m[i]) < initsize*2 - 1:             m[i].append(0)             m[i] = shift_down(m[i], len(m[i])-1, ID+1)             ID += 2     ID = 0     while len(m) < initsize*2 - 1:         m.append([0 for i in range(len(m[0]))])         m = shift_down(m, len(m)-1, ID+1)         ID += 2             return newm def randreal(min, max):     return (max-min) * random() + min # Generates a randomized (2**depth)+1 x (2**depth)+1 map def generate_map (min, max, r, depth, n=0, m=[[]]):     newm = m     if n > depth:         return m     elif n == 0:         newm = [[randint(min, max), randint(min, max)],[randint(min, max), randint(min, max)]]     else :         newm = scale_map(newm)         for i in range(len(newm)):             for j in range(len(newm)):                 if i%2 == 1 and j%2 == 1:                     newm[i][j] = (newm[i-1][j-1] + newm[i-1][j+1] + newm[i+1][j-1] + newm[i+1][j+1]) / 4 + (randreal(-r, r) * (max-min))                     newm[i][j] = round(newm[i][j], 2)                     if newm[i][j] > max:                         newm[i][j] = max                     elif newm[i][j] < min:                         newm[i][j] = min         for i in range(len(newm)):             for j in range(len(newm)):                 if (i%2 == 0 and j%2 == 1) or (i%2 == 1 and j%2 == 0):                     newm[i][j] = (newm[i][(j-1)%len(newm)] + newm[i][(j+1)%(len(newm)-1)] + newm[(i-1)%len(newm)][j] + newm[(i+1)%(len(newm)-1)][j]) / 4 + (randreal(-r, r) * (max-min))                     newm[i][j] = round(newm[i][j], 2)                     if newm[i][j] > max:                         newm[i][j] = max                     elif newm[i][j] < min:                         newm[i][j] = min                             return generate_map(min, max, r, depth, n+1, newm) #produces a colour given a number and a range def colour(n, r):     scale = (n-r[0])/(r[1]-r[0])     return (scale*255, scale*255, scale*255) class MapGenerator(object):     def __init__(self, min, max, r, depth):         # Display Settings         self.width = 700         self.height = 700         self.screen = pygame.display.set_mode((self.width, self.height), pygame.DOUBLEBUF)         self.range = (min, max)         self.randomMap = generate_map(min, max, r, depth)     def run(self):         scalex = self.width / len(self.randomMap)         scaley = self.height / len(self.randomMap)                 for i in range(len(self.randomMap)):             for j in range(len(self.randomMap)):                 #pygame.draw.rect(Surface, color, Rect(left, top, width, height))                 pygame.draw.rect(self.screen, colour(self.randomMap[i][j], self.range), pygame.Rect(i*scalex, j*scaley, scalex, scaley))         pygame.display.flip()                 running = True         while running:             event = pygame.event.wait()             if event.type == pygame.QUIT:                 running = False             else:                 pass #min, max, randomness, depth level (2**n-1 squares wide). A higher r means a me fractal map. MapGenerator(1, 10, 0.15, 7).run() pygame.quit() sys.exit()

[Raknarg]

For some cool colours you can replace the colour def with this:

Python:

def scaler(min, max, n):     return (n-min)/(max-min) def colour(n, r):     scale = scaler(r[0], r[1], n)     #print scale     if scale <= 0.2:         return (scaler(0, 0.2, scale)*128, 0, scaler(0, 0.2, scale)*128)     elif scale <= 0.4:         return ((1-scaler(0.2, 0.4, scale))*128, 0, 127 + (scaler(0.2, 0.4, scale)*128))     elif scale <= 0.6:         return (0, scaler(0.4, 0.6, scale)*255,(1-scaler(0.4, 0.6, scale))*255)     elif scale <= 0.8:         return (scaler(0.6, 0.8, scale)*255, 255, 0)     elif scale <= 1:         return (255, 255, scaler(0.8, 1, scale)*255)

EDIT: or if you like fire

Python:

if scale <= 0.25:         return (scaler(0, 0.25, scale)*255, 0, 0)     elif scale <= 0.5:         return (255, scaler(0.25, 0.5, scale)*128, 0)     elif scale <= 0.75:         return (255, 127 + scaler(0.5, 0.75, scale)*128,0)     elif scale <= 1:         return (255, 255, scaler(0.75, 1, scale)*255)

[Zren]

Because everything's better with pictures.




Pretty neat!

~

Python:

def generate_map (min, max, r, depth, n=0, m=[[]]):

Never use [] / lists / objects / pointers in a functions definition (as a default) in python. The default object is static over all calls to the function. Use m=None and if m is None: m = [[]]. You got away with it this time as you were reassigning m at the start anyways.

~

Tip:

Python:

newm = [[randint(min, max), randint(min, max)],[randint(min, max), randint(min, max)]] => newm = [[randint(min, max) for x in range(2)] for y in range(2)]

Also, you can floor() (x1, y1) and ceil() (x2, y2) when drawing the tiles with real numbers. That way you don't get the black borders (as they'll overlap instead of falling short).

~

I modded it to be iterative instead of recursive to watch it in progress. It get's fairly slow after round 7 deep, it pretty much dies by depth = 9.

[Raknarg]

Oh thanks. What would happen if I didn't reassign it?

And thanks, I was wondering how to get rid of those lines. I ended up just using lines, that's a smarter idea.

And yes due to the nature of this algorithm, it's not really feasible to go past depth of 7 or 8 because after that it wont even really fit on my screen, and it's super slow. If I started with a map and working inward instead of constantly expanding it it would likely be faster, because I would't be doing all this array shifting and resizing.

I'm also trying to figure out a way to do this without it being a square. The only problem seems to be getting the program to know which pixels to get it's data from. I'll look into seeing if I can rewrite it so its faster and scaleable.

I could just resize a square image but that just feels like cheating, and it wouldn't look as good.

[Zren]

Raknarg @ Wed Dec 18, 2013 6:50 pm wrote:

Oh thanks. What would happen if I didn't reassign it?

Fun times.

Python:

def listWith2(a=[]):     a.append(2)     return a print listWith2() print listWith2() print listWith2() print listWith2()

code:

[2] [2, 2] [2, 2, 2] [2, 2, 2, 2]

It's hell to debug if you don't know about it beforehand.

[Raknarg]

So why does it do that?

[Dreadnought]

Raknarg wrote:

So why does it do that?

First, objects in python are either immutable such as numbers, strings and tuples (the last two might surprise you) or mutable such as lists and dictionaries. Immutable objects cannot be modified and mutable ones can, for example

Python:

def AddOneToNum(num):         num += 1 >>> a = 7 >>> AddOneToNum(a) >>> a 7 def AddOneToList(lst):         lst += [1] >>> b = [7] >>> AddOneToList(b) >>> b [7, 1]

So lists objects can be modified, so what? Shoudn't a new list be created every time we call our function?

Well, functions are first class values in python (i.e. they are objects) and def is an executable statement that creates a function object and binds it to an identifier (the function name). Hence why we can't have functions and other values with the same identifier (name).

Python:

a = 6 >>> def a():         return 0 >>> a <function a at 0x00000000037937C8>

According to the documentation for function definitions "default parameters are evaluated when the function definition is executed" which makes sense since def has to create a function object with a default value for arguments that makes sense at the time the function was defined, for example

Python:

>>> a = 5 >>> def f(num = a):         return num >>> a = 7 >>> f() 5     # < ---- Not the current value of a

So hopefully, you can see why a default parameter has to be evaluated when the function definition is executed. Now what happens when we have a mutable value as our default? We create the mutable object once and every time we call the function the default value for the argument is the same object (which we can modify). Here's an example like Zren's which shows that the list is only created once.

Python:

>>> # Idea shamelessly borrowed from http://stackoverflow.com/questions/1132941/least-astonishment-in-python-the-mutable-default-argument >>> def a():         print("Creating empty list")         return []         >>> def f(lst=a()):         lst.append(7)         print(lst)         Creating empty list    # <---- Notice that it happens right away and only once >>> f() [7] >>> f() [7, 7] >>> f() [7, 7, 7]

Hopefully, this explains everything. It really is one of those things that is unexpected for almost everybody the first time they encounter it.

[Raknarg]

Oh wow, that's interesting. I'll keep that in mind for the future.