Computer Science Canada

random map generator
Author:  Raknarg [ Wed Dec 18, 2013 2:13 pm ]
Post subject:  random map generator
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()
Author:  Raknarg [ Wed Dec 18, 2013 2:35 pm ]
Post subject:  RE:random map generator
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)
Author:  Zren [ Wed Dec 18, 2013 6:39 pm ]
Post subject:  Re: random map generator
Because everything's better with pictures.

Posted Image, might have been reduced in size. Click Image to view fullscreen.
Posted Image, might have been reduced in size. Click Image to view fullscreen.

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.

Posted Image, might have been reduced in size. Click Image to view fullscreen.
Author:  Raknarg [ Wed Dec 18, 2013 6:50 pm ]
Post subject:  RE:random map generator
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.
Author:  Zren [ Wed Dec 18, 2013 10:01 pm ]
Post subject:  Re: RE:random map generator
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.
Author:  Raknarg [ Wed Dec 18, 2013 10:06 pm ]
Post subject:  RE:random map generator
So why does it do that?
Author:  Dreadnought [ Thu Dec 19, 2013 3:13 am ]
Post subject:  Re: random map generator
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.
Author:  Raknarg [ Thu Dec 19, 2013 10:24 am ]
Post subject:  RE:random map generator
Oh wow, that's interesting. I'll keep that in mind for the future.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy