Random Map Generator

[Raknarg]

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()

[smool]

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

[Insectoid]

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.

[Raknarg]

@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

[Insectoid]

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.

[Raknarg]

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

[Insectoid]

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.