Jump to content
  • Advertisement
Sign in to follow this  
HelloSkitty

Terrain Generation Alogrithms

This topic is 2359 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So for a school project, I need to come up with an algorithm that generates a grid of integers that follow the subjective rules:

The next time the program is run, a different terrain will be made.
It is continuous (not jagged)
It is not consistent (no flat planes)

The terrain is stored in a 2D array of sizable magnitude, I used an 800x800 int array.

While I know there is some randomized sine wave function that many people use to generate terrains randomly (and I suspect that is what everyone else in my class is using) I am aiming for a unique flavor. So what occurred to me was taking an old project I wrote on Langston's Ant and modifying it a bit:

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Image;
import java.util.ArrayList;


public class Grid {

int[][] grid=new int[800][800];
ArrayList<Ant> ants=new ArrayList<Ant>();
Ant a;
int numberOfColors;
Color[] colors;
Display frame;

Grid() {
frame=new Display(this);
}

void createAnt() {
boolean[] rule=Grid.decToBin(2);
a=new Ant(400,400,rule);
a.addToGrid(this);
ants.add(a);
}

static boolean[] decToBin(int n) {
int length=(int) (Math.log(n)/Math.log(2))+1;
boolean[] array=new boolean[length];
for (int i=array.length-1;i>-1;i--) {
if (n%2==1) {
array=true;
} else array=false;
n/=2;
}
return array;
}

static int binToDec(boolean[] array) {
int n=0;
for (int i=0;i<array.length;i++) {
n*=2;
if (array) {
n++;
}
}
return n;
}

void moveAnt() {
try {
OUTER:for (Ant a:ants) {
switch(a.orientation) {
case(0) : a.X++;break;
case(90) : a.Y--;break;
case(180) : a.X--;break;
case(270) : a.Y++;break;
}
if (a.X==0 || a.Y==0 || a.X==800 || a.Y==800) {
System.out.println("Ant "+Grid.binToDec(a.rule)+" has fallen off");
frame.randomAnt();
frame.randomAnt();
ants.remove(a);
continue OUTER;
}
if (a.rule[grid[a.Y][a.X]%a.rule.length]==true) {
a.turnRight();
} else a.turnLeft();
stepColor(a);
}
}
catch (Exception e) {}
}

void stepColor(Ant a) {
grid[a.Y][a.X]++;
Graphics g=frame.getGraphics();
g.setColor(colors[grid[a.Y][a.X]%colors.length]);
g.fillRect(a.Y,a.X,1,1);
}

void draw() {
Image I=frame.createImage(800,800);
Graphics g=I.getGraphics();
g.setColor(colors[0]);
g.fillRect(0,0,800,800);
for (int i=0;i<800;i++) {
for (int j=0;j<800;j++) {
g.setColor(colors[grid[j]%colors.length]);
g.fillRect(i, j, 1, 1);
}
}
g=frame.getGraphics();
g.drawImage(I, 0, 0, null);
}

void createColorsMono() {
numberOfColors=2;
colors=new Color[numberOfColors];
colors[0]=Color.WHITE;
colors[1]=Color.BLACK;
}

void createColorsGrad() {
numberOfColors=256;
colors=new Color[256];
for (int i=0;i<256;i++) {
colors=new Color(255-i,255-i,255-i);
}
}

void createColorsRainbow() {
numberOfColors=1280;
colors=new Color[1280];
int R=255,G=0,B=0;
for (int i=0;i<256;i++) {
colors=new Color(R,G,B);
G++;
}
G--;
for (int i=0;i<256;i++) {
colors[256+i]=new Color(R,G,B);
R--;
}
R++;
for (int i=0;i<256;i++) {
colors[512+i]=new Color(R,G,B);
B++;
}
B--;
for (int i=0;i<256;i++) {
colors[768+i]=new Color(R,G,B);
G--;
}
G++;
for (int i=0;i<256;i++) {
colors[1024+i]=new Color(R,G,B);
R++;
}
}

void clear() {
ants.clear();
for (int i=0;i<800;i++) {
for (int j=0;j<800;j++) {
grid[j]=0;
}
}
Graphics g=frame.getGraphics();
g.setColor(Color.WHITE);
g.fillRect(0,0,800,800);
}

public static void main(String[] args) {
Grid g=new Grid();
//g.createAnt();
g.createColorsGrad();
while (true) {
//g.draw();
g.moveAnt();
}
}

}



public class Ant {

boolean[] rule;
boolean fellOff=false;
int X;
int Y;
int orientation=0;
final int EAST=0;
final int NORTH=90;
final int WEST=180;
final int SOUTH=270;
final boolean LEFT=false;
final boolean RIGHT=true;
Grid grid;

Ant(int a,int b,boolean[] rules) {
X=a;
Y=b;
rule=rules;
}

void addToGrid(Grid g) {
grid=g;
}

void turnLeft() {
int temp=0;
switch(orientation) {
case EAST:temp=NORTH;break;
case NORTH:temp=WEST;break;
case WEST:temp=SOUTH;break;
case SOUTH:temp=EAST;break;
}
orientation=temp;
}

void turnRight() {
int temp=0;
switch(orientation) {
case EAST:temp=SOUTH;break;
case SOUTH:temp=WEST;break;
case WEST:temp=NORTH;break;
case NORTH:temp=EAST;break;
}
orientation=temp;
}

}



import java.awt.Graphics;
import java.awt.event.KeyEvent;
import java.awt.event.KeyListener;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.util.Random;

import javax.swing.JFrame;


public class Display extends JFrame implements KeyListener,MouseListener{

private static final long serialVersionUID = -3672207887596694900L;
int input=0;
Grid grid;

Display(Grid g) {
grid=g;
this.setSize(800,800);
this.setVisible(true);
this.addKeyListener(this);
this.addMouseListener(this);
}

public void keyPressed(KeyEvent arg0) {}

public void keyReleased(KeyEvent arg0) {}

public void keyTyped(KeyEvent e) {
if (e.getKeyChar()>='0' && e.getKeyChar()<='9') {
input*=10;
input+=e.getKeyChar()-'0';
return;
}
if (e.getKeyChar()==' ') {
grid.clear();
return;
}
if (e.getKeyChar()=='z') {
grid.createColorsGrad();
return;
}
if (e.getKeyChar()=='x') {
grid.createColorsMono();
return;
}
if (e.getKeyChar()=='c') {
grid.createColorsRainbow();
return;
}
if (e.getKeyChar()=='q') {
input=Math.abs(new Random().nextInt());
return;
}
if (e.getKeyChar()=='r') {
randomAnt();
}
if (e.getKeyChar()=='p') {
grid.draw();
return;
}
}

public void randomAnt() {
input=Math.abs(new Random().nextInt());
grid.ants.add(new Ant(Math.abs(new Random().nextInt()%800),Math.abs(new Random().nextInt()%800),Grid.decToBin(input)));
}

public void mouseClicked(MouseEvent e) {
if (input!=0) {
Ant a=new Ant(e.getY(),e.getX(),Grid.decToBin(input));
grid.ants.add(a);
System.out.println("Ant "+input+" is born!");
input=0;
}
}

public void mouseEntered(MouseEvent arg0) {}

public void mouseExited(MouseEvent arg0) {}

public void mousePressed(MouseEvent arg0) {}

public void mouseReleased(MouseEvent arg0) {}

public void paint(Graphics g) {
g.setColor(grid.colors[0]);
g.fillRect(0,0,800,800);
for (int i=0;i<800;i++) {
for (int j=0;j<800;j++) {
g.setColor(grid.colors[grid.grid[j]]);
g.fillRect(i, j, 1, 1);
}
}
}

public void repaint() {
paint(this.getGraphics());
}

}



(Z, X, and C toggle the display type, P redraws the grid, R places a random ant, Q sets a random number rule, Typing a number sets a number rule, clicking places an ant with given rule onto the grid where the click was)

Simply, it runs a cellular autonoma, Langston's Ant, on a grid 800x800, and every time one ant falls off, 2 more ants of a random rule are put in random locations on the grid. It generated some maps that I could consider pretty (they are attached), but I was wondering if there were any other innovative ways to generate a terrain mapping besides using the cliche (maybe it's not cliche, but that's how I think of it when everybody I know uses it) random sine wave function. Perhaps I could splice two different algorithms and run them on the same grid simultaneously and have a completely different map.

The positives I see with this are that the borders of the grid are barely touched, providing a confortable border.

However, one thing I want to fix (this is why I'm looking for other algorithms) is that the isobars (colored picture) seem too square. So are there any algorithms that might go well when run simultaneously with this one?

Share this post


Link to post
Share on other sites
Advertisement

So for a school project, I need to come up with an algorithm that generates a grid of integers that follow the subjective rules:

The next time the program is run, a different terrain will be made.
It is continuous (not jagged)
It is not consistent (no flat planes)

The terrain is stored in a 2D array of sizable magnitude, I used an 800x800 int array.

While I know there is some randomized sine wave function that many people use to generate terrains randomly (and I suspect that is what everyone else in my class is using) I am aiming for a unique flavor. So what occurred to me was taking an old project I wrote on Langston's Ant and modifying it a bit:


(Z, X, and C toggle the display type, P redraws the grid, R places a random ant, Q sets a random number rule, Typing a number sets a number rule, clicking places an ant with given rule onto the grid where the click was)

Simply, it runs a cellular autonoma, Langston's Ant, on a grid 800x800, and every time one ant falls off, 2 more ants of a random rule are put in random locations on the grid. It generated some maps that I could consider pretty (they are attached), but I was wondering if there were any other innovative ways to generate a terrain mapping besides using the cliche (maybe it's not cliche, but that's how I think of it when everybody I know uses it) random sine wave function. Perhaps I could splice two different algorithms and run them on the same grid simultaneously and have a completely different map.

The positives I see with this are that the borders of the grid are barely touched, providing a confortable border.

However, one thing I want to fix (this is why I'm looking for other algorithms) is that the isobars (colored picture) seem too square. So are there any algorithms that might go well when run simultaneously with this one?


Nice pictures! Anyways, I would recommend looking into Perlin's noise. Here's an implementation that uses that idea in Python:



def generateWhiteNoise(w, h):
noise = [[0 for _ in range(w)] for _ in range(h)]
for i in range(w):
for j in range(h):
noise[j] = random.random()
return noise

def generateSmoothNoise(baseNoise, octave):
width = len(baseNoise)
height = len(baseNoise[0])
smoothNoise = [[0 for _ in range(width)] for _ in range(height)]
samplePeriod = 1 << octave #2^octave
sampleFreq = 1.0 / samplePeriod
for i in range(width):
samplei0 = int((i / samplePeriod) * samplePeriod)
samplei1 = int((samplei0 + samplePeriod) % width)
hor_blend = (i - samplei0) * sampleFreq
for j in range(height):
samplej0 = int((j / samplePeriod) * samplePeriod)
samplej1 = int((samplej0 + samplePeriod) % height)
vert_blend = (j - samplej0) * sampleFreq
top = interpolate(baseNoise[samplei0][samplej0], baseNoise[samplei1][samplej0], hor_blend)
bottom = interpolate(baseNoise[samplei0][samplej1], baseNoise[samplei1][samplej1], hor_blend)
smoothNoise[j] = interpolate(top, bottom, vert_blend)
return smoothNoise


def interpolate(x0, x1, alpha):
return x0 * (1 - alpha) + alpha * x1


The "white noise" is simply a function that returns a 2D array of randomly generated float (or double if you want) ranging from 0.0 to 1.0. While your terrain is not bad, I feel it is too symmetrical. This should give you a smooth randomness if you use it as height map.

Hope that helps,
CXD

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!