Jump to content

  • Log In with Google      Sign In   
  • Create Account


2D Top down Ascii Procedural Terrain Gen


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
8 replies to this topic

#1 CainJ   Members   -  Reputation: 102

Like
0Likes
Like

Posted 29 November 2012 - 07:32 PM

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 :P

Sponsor:

#2 Khatharr   Crossbones+   -  Reputation: 2941

Like
0Likes
Like

Posted 29 November 2012 - 08:12 PM

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.

Edited by Khatharr, 29 November 2012 - 08:51 PM.

void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

#3 CainJ   Members   -  Reputation: 102

Like
0Likes
Like

Posted 29 November 2012 - 10:02 PM

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

#4 Telcontar   Members   -  Reputation: 887

Like
0Likes
Like

Posted 29 November 2012 - 10:02 PM

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.

I Create Games to Help Tell Stories | Writing Blog


#5 CainJ   Members   -  Reputation: 102

Like
0Likes
Like

Posted 29 November 2012 - 10:52 PM

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

#6 Khatharr   Crossbones+   -  Reputation: 2941

Like
0Likes
Like

Posted 30 November 2012 - 12: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.
void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

#7 r1ckparker   Members   -  Reputation: 389

Like
0Likes
Like

Posted 30 November 2012 - 07:26 AM

Have you thought about Fractals?

If you have a grid (say 50x50) and 10 land types (eg tree, grass, bush, water) etc

Drop a random 'seed' items at each corner (0,0 50,0 0,50 and 50,50)

This is the starting-point for the iterative subdivision routine, which is in two steps:

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.
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.

This web site explains it

http://www.gameprogrammer.com/fractal.html

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

So you would end up with something like this but instead of a height map, a terrain map

Posted Image

#8 Telcontar   Members   -  Reputation: 887

Like
0Likes
Like

Posted 30 November 2012 - 10:56 PM

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)

I Create Games to Help Tell Stories | Writing Blog


#9 hunpro   Members   -  Reputation: 813

Like
0Likes
Like

Posted 01 December 2012 - 04: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.)




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS