Computer Science Canada

Random Map Generator

Author:  Raknarg [ Thu Jan 02, 2014 8:35 pm ]
Post subject:  Random Map Generator

I decided this deserved a new post on its own.

It results in the same thing as my previous program, however now it performs the task iterively rather than recursively. On small depths, there's no noticeable difference. At depth 9, the new version is about a second faster or so. At depth 10, it is twice as fast.

With the new version it finds each point mathematically without having to generate a new array each time and do a lot of value swapping within the array.

As before, uses pygame. Also as before, neat results.


Does anyone have ideas on making a map witha custom size? I could make a huge map and basically crop it, but that seems unnecessary.

Python:

from __future__ import division
from random import randint, random
import math
import pygame
import sys

# If n + modifier is out of range, it generates the index it should be at (otherwise it never gets the right number).
def mod (n, modifier, maxVal):
    if n+modifier < 0:
        return modifier - 1
    elif n+modifier > maxVal:
        return modifier
    else:
        return n + modifier
# Generates a random real value
def randreal(minVal, maxVal):
    return (maxVal-minVal) * random() + minVal
# Takes the average of the corners surrounding the point
"""
x . x
. o .
x . x
"
""
def square (i, j, minVal, maxVal, r, currentSize, currentMap):
    return round(min(maxVal, max(minVal, (currentMap[i-currentSize][j-currentSize] + currentMap[i-currentSize][j+currentSize] + currentMap[i+currentSize][j-currentSize] + currentMap[i+currentSize][j+currentSize]) / 4 + (randreal(-r, r) * (maxVal-minVal)))))
# Takes the average of the adjacent points surrounding.
"""
. x .
x o x
. x .
"
""
def diamond (i, j, minVal, maxVal, r, currentSize, currentMap):
    return round(min(maxVal, max(minVal, (currentMap[i][mod(j, -currentSize, len(currentMap)-1)] + currentMap[i][mod(j, currentSize, len(currentMap)-1)] + currentMap[mod(i, -currentSize, len(currentMap)-1)][j] + currentMap[mod(i, currentSize, len(currentMap)-1)][j]) / 4 + (randreal(-r, r) * (maxVal-minVal)))))

# Generates a randomized (2**depth)+1 x (2**depth)+1 map
def generate_map (minVal, maxVal, r, depth):
    size = int(2**depth + 1)
    newMap = [["empty" for j in range(size)] for i in range(size)]

    # First four corners are always hard coded as such
    newMap[0][0] = randreal(minVal, maxVal)
    newMap[0][size-1] = randreal(minVal, maxVal)
    newMap[size-1][0] = randreal(minVal, maxVal)
    newMap[size-1][size-1] = randreal(minVal, maxVal)


    for n in range(depth+1)[::-1]:
        if n == 0:
            break

        # Couldn't think of a good name for it
        currentSize = (2**n+1) // 2

        # Needs to do diamond and square algorithms at each step
        for repeat in range(2):
            for i in range(size):
                for j in range(size):
                    # Square Algorithm
                    if repeat == 0:
                        #This formula ensures it always gets a point whose corners (at a range) are already filled
                        if ((i%(2**n)+1) == currentSize+1 and (j%(2**n)+1) == currentSize+1) and newMap[i][j] == "empty":
                            newMap[i][j] = square(i, j, minVal, maxVal, r, currentSize, newMap)
                    # Diamond Algorithm
                    if repeat == 1:
                        #This formula ensures it always gets a point whose adjacent points (at a range) are already filled
                        if (i%(2**n) % currentSize == 0 and j%(2**n) % currentSize == 0) and newMap[i][j] == "empty":
                            newMap[i][j] = diamond(i, j, minVal, maxVal, r, currentSize, newMap)
    return newMap

def scaler(min, max, n):
    return (n-min)/(max-min)
#produces a colour given a number and a range
def colour(n, r):
    scale = scaler(r[0], r[1], n)
    # Fire
    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)
   

class MapGenerator(object):
    def __init__(self, minVal, maxVal, r, depth):
        # Display Settings
        self.width = 700
        self.height = 700
        self.screen = pygame.display.set_mode((self.width, self.height), pygame.DOUBLEBUF)

        self.range = (minVal, maxVal)
        self.randomMap = generate_map(minVal, maxVal, 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(self.screen, colour(self.randomMap[i][j], self.range), pygame.Rect(math.floor(i*scalex), math.floor(j*scaley), math.ceil(scalex), math.ceil(scaley)))
                #pygame.draw.line(self.screen, colour(self.randomMap[i][j], self.range), [i*2,j*2], [i*2,j*2+1])
                #pygame.draw.line(self.screen, colour(self.randomMap[i][j], self.range), [i*2+1,j*2], [i*2+1,j*2+1])
        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, 100, 0.25, 8).run()
pygame.quit()
sys.exit()

Author:  smool [ Sat Jan 04, 2014 10:43 am ]
Post subject:  RE:Random Map Generator

Very nice. I can imagine all the math and logic was annoying to debug

Author:  Insectoid [ Sat Jan 04, 2014 11:49 am ]
Post subject:  RE:Random Map Generator

I've been meaning to implement diamond-square myself for a while, but as usual I never get around to it. Closest I've come so far is a 2d fractal mountain silhouette.

Author:  Raknarg [ Sat Jan 04, 2014 8:41 pm ]
Post subject:  RE:Random Map Generator

@Instectoid I've been trying to figure out how to do this for a long time, the other night I just pulled out a piece of paper and figured it out by a fluke. Do you mean midpoint displacement?

@smool yeah it was a bit annoying cause there were some exceptions and such I had to handle that I didn't know about, but the majority of the math kindof just came to me all at once

Author:  Insectoid [ Sat Jan 04, 2014 9:15 pm ]
Post subject:  RE:Random Map Generator

http://en.wikipedia.org/wiki/Diamond-square_algorithm

"It is a slightly better algorithm than the three-dimensional implementation of the midpoint displacement algorithm"

I saw your functions named diamond and square and assumed, given that this is a map/terrain generator, that this is an implementation of this algorithm. I can't be bothered to go through your code to find out how similar it is, but even coming up with diamond and square function names in this context is an impressive coincidence.

Author:  Raknarg [ Sat Jan 04, 2014 9:27 pm ]
Post subject:  RE:Random Map Generator

No it is the diamond square algorithm, but you mentioned "2d fractal mountain silhouette" so I assumed you meant a midpoint displacement rendering of a mountain

Author:  Insectoid [ Sat Jan 04, 2014 10:54 pm ]
Post subject:  RE:Random Map Generator

Oh, yeah, I did one of those. Midpoint displacement. Yeah. I keep meaning to add more procedural stuff to it to create a complete scene, but I'm far too lazy to actually finish it.


: