import java.applet.*;
import java.util.*;
import java.io.*;
import java.net.*;
import java.awt.*;
import java.awt.image.ColorModel;
import java.awt.image.MemoryImageSource;
/* portions of this code were adapted from the DitherTest applet */
/* midpoint subdivision codes adapted from Usenet and published references
* - Basic plasma from implementation by Andrea Griffini (Usenet)
* - Diamond-square subdivision adapted from implementation by
* Paul Martz (Usenet)
* - Offset-squares method adapted from 'moonbase' demo by James McNeill
*/
public class SubdivApplet extends Applet implements Runnable
{
/************************************************************
* Boilerplate methods to handle painting and initialization
************************************************************/
private int width = 256;
private int height = 256;
private double scalefactor = 1.0;
/* Frame only used for standalone apps
private static Frame my_frame = null;
*/
private int[][] heightfield;
private Random rgen;
private Image img;
private boolean started;
/* only things done in here are done for standalone program, not applet
public SubdivApplet()
{
setTitle("Midpoint Subdivision Fractal");
}
*/
public boolean handleEvent(Event evt)
{
if (evt.id == Event.WINDOW_DESTROY) System.exit(0);
return super.handleEvent(evt);
}
public boolean action( Event evt, Object arg)
{
return true;
}
/*static*/ String calcString = "Calculating...";
/*static*/ String calcMethod;
public void paint(Graphics g)
{
int w = size().width;
int h = size().height;
if (img == null) {
super.paint(g);
g.setColor(Color.black);
FontMetrics fm = g.getFontMetrics();
int x = (w - fm.stringWidth(calcString))/2;
int y = h/2;
g.drawString(calcString, x, y);
} else {
g.drawImage(img, 0, 0, w, h, this);
}
}
public void init()
{
int w = Integer.parseInt(getParameter("width"));
if (w < =0 || w > 256) w=width;
width=w;
height=w;
scalefactor = 256/width;
calcMethod=getParameter("method");
rgen = new Random();
started = false;
start();
}
/* main is used for a standalone program, not applet
public static void main(String args[])
{
SubdivApplet f = new SubdivApplet();
f.resize(width, height);
f.show();
my_frame = f;
rgen = new Random();
f.start();
}
*/
synchronized void BuildImage()
{
/* build the image for display -- greyscale */
int pixels[];
int i, j, a, index = 0, min, max;
// calculate range of values in heightfield
min = heightfield[0][0];
max = heightfield[0][0];
for (i=0;i < width;i++)
{
for (j=0;j < width;j++)
{
if (heightfield[i][j] < min) min = heightfield[i][j];
if (heightfield[i][j] > max) max = heightfield[i][j];
}
}
scalefactor = 255 / (max-min);
pixels = new int[width * height];
for (i=0;i < width;i++)
{
for (j=0;j < width;j++)
{
a = (int)((heightfield[i][j] - min) * scalefactor);
if (a < 0) a=0;
if (a > 255) a=255;
/*if (a > 255) a=255;*/
pixels[index++] = (255 << 24) | (a << 16) | (a << 8) | a;
}
}
img = createImage(new MemoryImageSource(width, height,
ColorModel.getRGBdefault(),
pixels, 0, width));
repaint();
}
/************************************************************
* Thread methods to handle processing in the background
************************************************************/
Thread kicker;
public /*synchronized*/ void start() {
if (!started) {
started = true;
kicker = new Thread(this);
kicker.start();
} else if ((kicker != null) && (kicker.isAlive()))
kicker.resume();
}
public /*synchronized*/ void stop() {
try {
if ((kicker != null) && (kicker.isAlive())) {
kicker.suspend();
}
} catch (Exception e) {
}
}
public void restart() {
try {
if (kicker != null) {
kicker.stop();
}
} catch (Exception e) {
}
kicker = null;
img = null;
started = false;
start();
}
public void run()
{
Thread me = Thread.currentThread();
me.setPriority(4);
if (calcMethod.equals("standard"))
DoPlasma(0.5, 0);
else if (calcMethod.equals("diamond-square"))
DoDiamondSquare(width);
else if (calcMethod.equals("offset-square"))
DoOffsetSquare(width);
}
/************************************************************
* Plasma implementations
************************************************************/
/*
Plasma example - basic midpoint subdivision on a grid
grid size is a power of 2 (width for this example)
integer math is used where possible
random distribution is uniform random
K is scaling factor (ratio of altitude variation to length),
H is constant noise factor, independent of area size;
typical values passed in are (0.5, 0.0) so that, with a width cell
grid, starting values range from -128..128. This still runs the
risk of overflow, but can still be acceptable.
altitude at each level is uniform random, + or - (h*K+H)/2
where h is the stepsize (length of area side)
*/
/* this used to return 'byte' instead of 'int' */
private int Rand1(int base,int delta)
{ int i;
i=base+(rgen.nextInt()%delta)-(delta/2);
/*if (i < -128) i=-128; if (i > 127) i=127;*/
return (int)i;
}
synchronized void DoPlasma(double K,double H)
{
int i,j,i2,j2,i3,j3,h,h2,delta,a,b,c,d;
/* Get the memory (widthxwidth bytes) */
heightfield = new int[width][width];
/* base value = 0, byte values are -128..127 */
for (i=0;i < width;i++) for (j=0;j < width;j++) heightfield[i][j]=0;
/* Plasma clouds computing */
for (h=width; h > 1; h=h2)
{
h2=h/2;
delta= (int)(h*K+H);
for (i=0; i < width; i+=h)
{ i2=((i+h)&(width-1));
for (j=0; j < width; j+=h)
{ /* Get corner heights (a=TL, b=TR, c=BL, d=BR) */
j2=((j+h)&(width-1));
i3=i+h2; j3=j+h2;
a=heightfield[i][j]; b=heightfield[i2][j];
c=heightfield[i][j2]; d=heightfield[i2][j2];
/* Central point */
heightfield[i3][j3]=Rand1((a+b+c+d)/4,delta);
/* Top point (only needed for top row) */
if (i==0)
heightfield[i3][j]=Rand1((a+b)/2,delta);
/* Left point (only needed for left column) */
if (j==0)
heightfield[i][j3]=Rand1((a+c)/2,delta);
/* Right point */
heightfield[i2][j3]=Rand1((b+d)/2,delta);
/* Bottom point */
heightfield[i3][j2]=Rand1((c+d)/2,delta);
}
}
}
BuildImage();
}
/****************************************************************
Plasma example - diamond-square midpoint subdivision on a grid.
The surface is iteratively computed by calculating the center point of
the initial square (where the four corners of the surface are the
corners of the square), then of the resulting diamonds, then of
squares again, etc.
Code adapted from 'fillSurf' example posted to Usenet by
Paul Martz (pmartz@dsd.es.com). Original source calculated
full 3D points; I have elided that for this version because the
underlying regular grid gives you that implicitly.
Original copyright notice:
Use this code anyway you want as long as you don't sell it for
money.
Paul Martz, 1995
****************************************************************/
private int avgyvals (int i, int j, int strut, int dim)
{
if (i == 0)
return ((heightfield[i][(j-strut)&(width-1)] +
heightfield[i][(j+strut)&(width-1)] +
heightfield[(i+strut)&(width-1)][j]) / 3);
else if (i == dim-1)
return ((heightfield[i][(j-strut)&(width-1)] +
heightfield[i][(j+strut)&(width-1)] +
heightfield[(i-strut)&(width-1)][j]) / 3);
else if (j == 0)
return ((heightfield[(i-strut)&(width-1)][j] +
heightfield[(i+strut)&(width-1)][j] +
heightfield[i][(j+strut)&(width-1)]) / 3);
else if (j == dim-1)
return ((heightfield[(i-strut)&(width-1)][j] +
heightfield[(i+strut)&(width-1)][j] +
heightfield[i][(j-strut)&(width-1)]) / 3);
else
return ((heightfield[(i-strut)&(width-1)][j] +
heightfield[(i+strut)&(width-1)][j] +
heightfield[i][(j-strut)&(width-1)] +
heightfield[i][(j+strut)&(width-1)]) / 4);
}
private int avgyvals2 (int i, int j, int strut, int dim)
{
int tstrut = strut/2;
return ((heightfield[(i-tstrut)&(width-1)][(j-tstrut)&(width-1)] +
heightfield[(i-tstrut)&(width-1)][(j+tstrut)&(width-1)] +
heightfield[(i+tstrut)&(width-1)][(j-tstrut)&(width-1)] +
heightfield[(i+tstrut)&(width-1)][(j+tstrut)&(width-1)]) / 4);
}
synchronized void DoDiamondSquare(int dim)
{
int i, j;
int strut, tstrut;
boolean oddline;
/* Get the memory (widthxwidth bytes) */
heightfield = new int[width][width];
/* base value = 0, byte values are -128..127 */
for (i=0;i < width;i++) for (j=0;j < width;j++) heightfield[i][j]=0;
/* initialize things */
strut = dim / 2;
/* seed the first y values */
/* we disregard this for direct comparison with other method.
oddline = false;
for (i=0; i < dim; i+=strut)
{
oddline = (!oddline);
for (j=0; j < dim; j+=strut)
{
if (!oddline) j+= strut;
heightfield[i][j] = Rand1(0, strut);
j+=strut;
}
}
*/
/* create fractal surface from seeded values */
tstrut = strut;
while (tstrut > 0)
{
oddline = false;
for (i=0; i < dim; i+=tstrut)
{
oddline = (!oddline);
for (j=0; j < dim; j+=tstrut)
{
if ((oddline) && (j==0)) j+=tstrut;
heightfield[i][j] =
Rand1(avgyvals (i, j, tstrut, dim), tstrut);
j+=tstrut;
}
}
if (tstrut/2 != 0)
{
for (i=tstrut/2; i < dim; i+=tstrut)
{
for (j=tstrut/2; j < dim; j+=tstrut)
{
heightfield[i][j] =
Rand1(avgyvals2(i, j, tstrut, dim), tstrut);
}
}
}
tstrut /= 2;
}
BuildImage();
}
/****************************************************************
Plasma example - offset square midpoint subdivision on a grid.
This method is similar to standard subdivision, but it is 'offset'
in that the new points at each level are offset from the previous
level by half the square size. The original corner points at level
x are only used once to form a weighted average, and then become the
center points of the new squares:
O O
O O
becomes
x x
O O
x x x x
x x x x
O O
x x
(Okay, so I don't do good ASCII squares; I hope you get the idea.)
It should be clear that this method includes some non-local context
when calculating new heights. With standard subdivision, the only
heights that can ever influence the area inside the original square
are the original corner points. With offset squares, most of the
new corner points lie outside the original square and therefore
are influenced by more distant points. This feature can be a problem,
because if you don't want the map to be toroidal (wrapped in both
x and y), you need to generate a large number of points outside the
final terrain area. For this example, I just wrap x and y.
Original copyright notice:
This code was inspired by looking at Tim Clark's (?) Mars demo; hence the name
"Moonbase". (Moonbase is also the name of our student-run Linux server.)
I believe the Mars demo is still available on x2ftp.oulu.fi. You are free
to use my code, my ideas, whatever. I have benefited enormously from the free
information on the Internet, and I would like to keep that process going.
James McNeill
mcneja@wwc.edu
****************************************************************/
synchronized void DoOffsetSquare(int width)
{
int row_offset = 0; // start at zero for first row
/* Get the memory (widthxwidth bytes) */
heightfield = new int[width][width];
/* base value = 0, byte values are -128..127 */
for (int i=0;i < width;i++) for (int j=0;j < width;j++) heightfield[i][j]=0;
for ( int square_size = width; square_size > 1; square_size /= 2 )
{
int random_range = square_size;
for ( int x1 = row_offset; x1 < width; x1 += square_size )
{
for ( int y1 = row_offset; y1 < width; y1 += square_size )
{
// Get the four corner points.
int x2 = (x1 + square_size) % width;
int y2 = (y1 + square_size) % width;
int i1 = heightfield[x1][y1];
int i2 = heightfield[x2][y1];
int i3 = heightfield[x1][y2];
int i4 = heightfield[x2][y2];
// Obtain new points by averaging the corner points.
int p1 = ((i1 * 9) + (i2 * 3) + (i3 * 3) + (i4)) / 16;
int p2 = ((i1 * 3) + (i2 * 9) + (i3) + (i4 * 3)) / 16;
int p3 = ((i1 * 3) + (i2) + (i3 * 9) + (i4 * 3)) / 16;
int p4 = ((i1) + (i2 * 3) + (i3 * 3) + (i4 * 9)) / 16;
// Add a random offset to each new point.
p1 = Rand1(p1, random_range);
p2 = Rand1(p2, random_range);
p3 = Rand1(p3, random_range);
p4 = Rand1(p4, random_range);
// Write out the generated points.
int x3 = (x1 + square_size/4) % width;
int y3 = (y1 + square_size/4) % width;
x2 = (x3 + square_size/2) % width;
y2 = (y3 + square_size/2) % width;
heightfield [x3][y3] = p1;
heightfield [x2][y3] = p2;
heightfield [x3][y2] = p3;
heightfield [x2][y2] = p4;
}
}
row_offset = square_size/4; // set offset for next row
}
BuildImage();
}
}