🔒 Locked

2D Top down Ascii Procedural Terrain Gen

Started by Frost Byte Nov 30, 2012 at 1:32 AM 7 replies 5.7k views

Original Post

Nov 30, 2012 at 1:32 AM

I been programming since mid 80's, so the following can be shown to me in just about any language, and I'll be able to convert it.
Here is my dilema:
I am very nostalgic and many games that are written in "ascii" are still around today, and still very popular (L.O.R.D. for example, and the recent 2006 hit Dwarf fortress). So that should scale this to easy. I thought.

I spend many weeks looking up ways to make (what i thought) a simple, flat 2D terrain generator that I can use in a ascii game. And found all kinds of complex and really obscene algorithms and formulas that are not unlike driving a viper to to pick up your paper at the end of the drive.

So I gathered as much old-school skill I had and tried tons of variations of randomness to get a "grouping" style terrain, instead of the usual "paint-splatter" style. I tried the usual x,y method, perlin types but they were not laying out like I wanted (I even tried sin() math and that was pretty close, but too predictable, obviously) - they were more designed for 3D and in depth style graphic games.

The 2D I want is a TOP down (think of "droidcraft", "Don't starve" etc.. - those are the best i can think of off the top of my head). I only need like 6-10 tile types, and I can probably work out underground caves.

Any one else have an idea how to generate a fairly "logical" way of doing this, such as trees in a group, then maybe spread to some tall grass to plains, then maybe hills that turn into mountains etc...

here is an example of one run
http://imageshack.us/photo/my-images/850/randomexample.jpg/

this is NOT what i want, its too random and not logical.

Thanks for any ideas, I'll test them all :-) (or at least try)

ps
Yes I love Pascal!, but then I like basic too

Khatharr

Nov 30, 2012 at 2:12 AM

Are you looking for Perlin Noise?

You could map the distributions separately and then combine them into a final map.

edit - nvm, didn't see you mention that when I first read through. Sry

What, specifically, were the other methods doing that you didn't like? I don't understand what it is that you're trying to make happen that those methods aren't giving you. If it's tighter grouping to create 'clusters' of like objects then maybe you could generate a grid of noise for a set radius and then scale each tile by its distance from the center point?

For instance, a 5x5 grid represented by a 2D float array. Fill it with random values between 0 and 5 and then consider the center of the grid as the center of a circle with radius 6 or so. For each value in the array calculate (6 - distance from center point) and then scale the value by that amount. Once done just compare each value against a threshold value. If the value is greater than the threshold then place an entity in that position.

I haven't tested that, but by adjusting the aggressiveness of the 'distance from center' (exponential rather than linear, for instance), the range of the original values (0 to 100 instead of 0 to 5, maybe) and adjusting the threshold you could probably get pretty decent clusters even from random noise.

Frost Byte

Nov 30, 2012 at 4:02 AM

well lets see... hmm
the best way i can describe, I just saw a game tonight minicraft i think it was ( a quicky by notch), its that principal I am looking for.
example with just two entities - we'll say plains and desert. pretty simple matter of those grouping together regardless of the random factor. larger grid, more likley it will blend perfect.
however, start adding in, hills, water, mountains, grass etc.. now it gets more messy. the lines of seperation, if you will, become vague, and it looks like my screen shot. there are no areas.

I thought a 2D flat grid would be easy, however, it's just as complex as a 3D model. or maybe i have too many numbers in my head LOL.

so what I am looking for, is to be able to design a large 100x100 (that's large for ascii and all i want to work with for a test model) area that has definitive bioms. not random like in the image shown. but even perlin is leading to a dead end.

Maybe its the way I am plotting it out? I am useing a 2d array say small samples of 20x20 then cycling through with different radom formulas and putting them in the array (one of 5-7 different tiles, sand, dirt, trees, stone etc..). however, when i do, it just looks random, with trees. the actual biom is not definitive.

thanks for the reply..
(currently tinkering with a side scroll version, that was easy :-) )

Telcontar

Nov 30, 2012 at 4:02 AM

Midpoint displacement is the best alternative to perlin noise in my book (admittedly, my book has pretty much two chapters, and those are "Perlin noise" and "Midpoint displacement"). You can find plenty of articles. I have a good python implementation that I'll link to later when I have more time.

Frost Byte

Nov 30, 2012 at 4:52 AM

excellent please do - like the typical programer (especially multi-lingual) I have tons of projects im workin on lol

Khatharr

Nov 30, 2012 at 6:51 AM

If you're looking to generate biomes then you can use some method for creating 'macroscopic noise' to determine biome regions and then use perlin and midpoint displacement to fill in the actual biome areas centered around 'peak' areas or something. In other words, if you start with your 100x100 grid and dump in your baseline noise then you can scan through the grid for the cells with the highest values, then once you have enough cells with high values you use those positions as the center-point (and perhaps relative size/intensity) for generating the biome.

Telcon probably knows more about it than I do. I read some articles about random map gen a long time ago and don't really remember all of it.

r1ckparker

Nov 30, 2012 at 1:26 PM

[font=arial, helvetica, sans-serif]Have you thought about Fractals?[/font]

[font=arial, helvetica, sans-serif]If you have a grid (say 50x50) and 10 land types (eg tree, grass, bush, water) etc[/font]

[font=arial, helvetica, sans-serif]Drop a random 'seed' items at each corner (0,0 50,0 0,50 and 50,50)[/font]

[font=arial, helvetica, sans-serif]This is the starting-point for the iterative subdivision routine, which is in two steps:[/font]

[font=arial, helvetica, sans-serif]The diamond step: Taking a square of four points, generate a random value at the square midpoint, where the two diagonals meet. The midpoint value is calculated by averaging the four corner values, plus a random amount. This gives you diamonds when you have multiple squares arranged in a grid.[/font]

[font=arial, helvetica, sans-serif]The square step: Taking each diamond of four points, generate a random value at the center of the diamond. Calculate the midpoint value by averaging the corner values, plus a random amount generated in the same range as used for the diamond step. This gives you squares again.[/font]

[font=arial, helvetica, sans-serif]This web site explains it[/font]

[font=arial, helvetica, sans-serif]http://www.gameprogrammer.com/fractal.html[/font]

[font=arial, helvetica, sans-serif]Instead of assigning height values, you are assigning terrain types. The types would logically follow on from each other, so 0 might be grass, 1 might be a small bush, 2 a large bush, 3 a tree, 4 a tree in water, 5 a swamp, 6 water etc. Then when you generate your map you would have patches of similar terrain eg a forest surrounded by bushes, a lake surrounded by marsh etc[/font]

[font=arial, helvetica, sans-serif]So you would end up with something like this but instead of a height map, a terrain map[/font]

[font=arial, helvetica, sans-serif][/font]

Telcontar

Dec 1, 2012 at 4:56 AM

Okay, here is the code for two python scripts. The first implements the diamond-square algorithm (which is the algorithm described in the article r1ckparker linked to. That happens to be one of the articles I learned from as well. Very good - study it!). The second, while I have modified it a bit, is not my own, though I cannot remember exactly where I got it from. It outputs the heightmap as a bmp file.

I make no claims as to the robustness of this code and it isn't well commented (I never intended for it to be seen by others), but it should be good enough to learn from and as a starting point to tinker with. I've stripped out almost everything except for the actual diamond-square functions and some helpers. Find the meat of the algorithm at the bottom of the first script.

Diamond-square:


 #Aule
 #Function for generating a world heightmap using fractal algorithms
 import random
 from bmp import *
 #bmp.py must exist in same directory as this script
 size = 0
 start_Value = 0
 n = 0
 A = [[v]*n for x in xrange(n)]
 range_Mod = 1
 square_Side = n
 H = .5
 change = False
 normal = 0
 variation = 50
 start_Height = 0
 def gen(N_start=8, mapName="map", H_val=.5, norm=5, vary=40, start_H=5):
 if N_start > 12:
 print "That is a very large map. Please enter a value of 11 or less."
 return
 if N_start < 2:
 print "Let's think a tad larger, shall we?"
 return
 
 global n
 global square_Side
 global start_Value
 global A
 global range_Mod
 global size
 global H
 global change
 global normal
 global variation
 global start_Height
 
 H = H_val
 normal = norm
 variation = vary
 start_Height = start_H
 
 range_Mod = 1
 n = (2**N_start) + 1
 size = n
 v = 0
 
 A = [[start_Value]*n for x in xrange(n)]
 A[0][0] = start_Height
 A[0][size-1] = start_Height
 A[size-1][0] = start_Height
 A[size-1][size-1] = start_Height
 
 square_Side = n
 run() 
 print_BMP(mapName)
 def print_BMP(name="map"):
 create_BMP(A, size, name)
 def in_Array(point):
 """returns True if (x, y) is within the array"""
 if X(point) >= n:
 return False
 elif Y(point) >= n:
 return False
 elif X(point) < 0:
 return False
 elif Y(point) < 0:
 return False
 else:
 return True
 def get(point, square_Side=size):
 x = X(point)
 y = Y(point)
 if x >= n:
 x = square_Side/2
 if x < 0:
 x = (n-1)- (square_Side/2)
 if y >= n:
 y = square_Side/2
 if y < 0:
 y = (n-1)- (square_Side/2)
 return A[x][y]
 def get_Simple(point):
 x = X(point)
 y = Y(point)
 if in_Array(point):
 return A[x][y]
 else:
 return False
 
 def X(point):
 """Retrieves X coord from point tuple"""
 return point[0]
 def Y(point):
 """Retrieves Y coord from point tuple."""
 return point[1]
 def highest_Value():
 """Returns the most positive value in the array."""
 highest=0
 for row in A:
 for cell in row:
 if cell > highest:
 highest = cell
 return highest
 def highest_Coordinate():
 """Returns the most positive value in the array."""
 highest_val = 0
 highest_coord = (0, 0)
 for x, row in enumerate(A):
 for y, cell in enumerate(row):
 if cell > highest_val:
 highest_val = cell
 highest_coord = (x, y)
 return highest_coord
 def lowest_Value():
 """Returns the most negative value in the array."""
 lowest=0
 for row in A:
 for cell in row:
 if cell < lowest:
 lowest = cell
 return lowest
 def lowest_Coordinate():
 """returns tuple (x,y) of the lowest value, or False if not found."""
 lowest_val = 0
 lowest_coord = (0, 0)
 for x, row in enumerate(A):
 for y, cell in enumerate(row):
 if cell < lowest_val:
 lowest_val = cell
 lowest_coord = (x, y)
 return lowest_coord
 def get_Neighbors(current):
 """Returns a list with the eight neighboring coordinates of any point."""
 N = (current[0], current[1]-1)
 NE = (current[0]+1, current[1]-1)
 E = (current[0]+1, current[1])
 SE = (current[0]+1, current[1]+1)
 S = (current[0], current[1]+1)
 SW = (current[0]-1, current[1]+1)
 W = (current[0]-1, current[1])
 NW = (current[0]-1, current[1]-1)
 nList = [N, NE, E, SE, S, SW, W, NW]
 return nList
 def get_Cardinal_Neighbors(current):
 """Returns a list with the eight neighboring coordinates of any point."""
 N = (current[0], current[1]-1)
 E = (current[0]+1, current[1])
 S = (current[0], current[1]+1)
 W = (current[0]-1, current[1])
 
 nList = [N, E, S, W]
 return nList
 def diamond(point, square_Side):
 """Operates diamond step on four values around point.""" 
 p1 = X(point), Y(point) - (square_Side/2)
 p2 = X(point) + (square_Side/2), Y(point)
 p3 = X(point), Y(point) + (square_Side/2)
 p4 = X(point) - (square_Side/2), Y(point)
 points = [p1, p2, p3, p4]
 for p in points:
 if A[X(p)][Y(p)] != start_Value: #already set
 continue
 c1 = X(p), Y(p) - (square_Side/2)
 c2 = X(p) + (square_Side/2), Y(p)
 c3 = X(p), Y(p) + (square_Side/2)
 c4 = X(p) - (square_Side/2), Y(p)
 
 total_Points = 4
 point_Total = 0
 point_Total += get(c1, square_Side)
 point_Total += get(c2, square_Side)
 point_Total += get(c3, square_Side)
 point_Total += get(c4, square_Side)
 
 point_Average = point_Total/total_Points
 point_Value = int((point_Average + \
 random.normalvariate(normal, variation)*range_Mod))
 A[X(p)][Y(p)] = point_Value
 
 return
 def square(point, square_Side):
 """Operates square step around point."""
 if A[X(point)][Y(point)] != start_Value:
 print "Conflict",
 c1 = X(point) - (square_Side/2), Y(point) + (square_Side/2)
 c2 = X(point) + (square_Side/2), Y(point) + (square_Side/2)
 c3 = X(point) + (square_Side/2), Y(point) - (square_Side/2)
 c4 = X(point) - (square_Side/2), Y(point) - (square_Side/2)
 total_Points = 4
 point_Total = 0
 point_Total += get(c1)
 point_Total += get(c2)
 point_Total += get(c3)
 point_Total += get(c4)
 
 point_Average = point_Total/total_Points
 point_Value = int((point_Average + \
 random.normalvariate(normal, variation)*range_Mod))
 A[X(point)][Y(point)] = point_Value
 return
 def run():
 """Pretty self-explanatory, dont you think?"""
 global square_Side
 global range_Mod
 global H
 global change
 if square_Side < 3: #recursion end case
 return
 else:
 if (n == square_Side):
 squares = 1
 else:
 squares = n/(square_Side-1)
 for i in range(squares):
 for j in range(squares):
 x = square_Side/2 + ((square_Side-1)*i)
 y = square_Side/2 + ((square_Side-1)*j)
 point = x, y
 square(point, square_Side)
 for i in range(squares):
 for j in range(squares):
 x = square_Side/2 + ((square_Side-1)*i)
 y = square_Side/2 + ((square_Side-1)*j)
 point = x, y
 diamond(point, square_Side)
 #have now run one iteration. Decrement square_Side
 #and recalc range_Mod and keep going.
 if change and square_Side < ((n/8)+1):
 H = 0.8
 change = False
 
 square_Side = (square_Side/2)+1
 range_Mod = round(range_Mod * 2**-H, 2)
 run()
 def get_Max_Size():
 return n
 def get_Section(size_X, size_Y, startX=0, startY=0):
 """Returns a subsection of A from the origin (0, 0) to (size_X, size_Y)"""
 if size_X >= n or size_Y >= n:
 return False
 
 sub = [[0]*size_X for x in xrange(size_Y)]
 for x in range(size_Y):
 for y in range(size_X):
 sub[x][y] = A[x][y]
 return sub
 
 if __name__ == "__main__":
 gen()

bmp-drawing


 #Some key imports.
 #Struct is used to create the actual bytes.
 #It is super handy for this type of thing.
 import struct, random
 #Function to write a bmp file. It takes a dictionary (d) of
 #header values and the pixel data (bytes) and writes them
 #to a file. This function is called at the bottom of the code.
 def bmp_write(d,the_bytes, mapName):
 mn1 = struct.pack('<B',d['mn1'])
 mn2 = struct.pack('<B',d['mn2'])
 filesize = struct.pack('<L',d['filesize'])
 undef1 = struct.pack('<H',d['undef1'])
 undef2 = struct.pack('<H',d['undef2'])
 offset = struct.pack('<L',d['offset'])
 headerlength = struct.pack('<L',d['headerlength'])
 width = struct.pack('<L',d['width'])
 height = struct.pack('<L',d['height'])
 colorplanes = struct.pack('<H',d['colorplanes'])
 colordepth = struct.pack('<H',d['colordepth'])
 compression = struct.pack('<L',d['compression'])
 imagesize = struct.pack('<L',d['imagesize'])
 res_hor = struct.pack('<L',d['res_hor'])
 res_vert = struct.pack('<L',d['res_vert'])
 palette = struct.pack('<L',d['palette'])
 importantcolors = struct.pack('<L',d['importantcolors'])
 #create the outfile
 outfile = open(mapName + ".bmp",'wb')
 #write the header + the_bytes
 outfile.write(mn1+mn2+filesize+undef1+undef2+offset+headerlength+width+height+\
 colorplanes+colordepth+compression+imagesize+res_hor+res_vert+\
 palette+importantcolors+the_bytes)
 outfile.close()
 ################################### 
 def create_BMP(height_array, size, mapName):
 #Here is a minimal dictionary with header values.
 #Of importance is the offset, headerlength, width,
 #height and colordepth.
 #Edit the width and height to your liking.
 #These header values are described in the bmp format spec.
 #You can find it on the internet. This is for a Windows
 #Version 3 DIB header.
 d = {
 'mn1':66,
 'mn2':77,
 'filesize':0,
 'undef1':0,
 'undef2':0,
 'offset':54,
 'headerlength':40,
 'width':size,
 'height':size,
 'colorplanes':0,
 'colordepth':24,
 'compression':0,
 'imagesize':0,
 'res_hor':0,
 'res_vert':0,
 'palette':0,
 'importantcolors':0
 }
 #Function to generate a random number between 0 and 255
 def rand_color():
 x = random.randint(0,255)
 return x
 #Build the byte array. This code takes the height
 #and width values from the dictionary above and
 #generates the pixels row by row. The row_mod and padding
 #stuff is necessary to ensure that the byte count for each
 #row is divisible by 4. This is part of the specification.
 the_bytes = ''
 for row in range(d['height']-1,-1,-1):# (BMPs are L to R from the bottom L row)
 for column in range(d['width']):
 h = height_array[row][column]
 if h > 255:
 h = 255
 if h < 0:
 b = 255 - abs(h)
 g = 0
 r = 0
 else:
 b = h
 g = h
 r = h
 pixel = struct.pack('<BBB',b,g,r)
 the_bytes = the_bytes + pixel
 row_mod = (d['width']*d['colordepth']/8) % 4
 if row_mod == 0:
 padding = 0
 else:
 padding = (4 - row_mod)
 padbytes = ''
 for i in range(padding):
 x = struct.pack('<B',0)
 padbytes = padbytes + x
 the_bytes = the_bytes + padbytes
 
 #call the bmp_write function with the
 #dictionary of header values and the
 #bytes created above.
 bmp_write(d,the_bytes, mapName)

hunpro

Dec 1, 2012 at 10:50 PM

If you still have your Perlin code, you could try scaling the coordinates down, to make the values change slower, smoothing over many tiles. Typically there is some GetNoise(float x,float y) function, if you gave it the tile coordinates as x & y, then try GetNoise(x/1024.f,y/1024.f) for example. (my english is rusty, sorry.)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.