This article was originally written for Darren Hebden's RLNews
30th October 1999
There's something special about fractals. Maybe it's the way that
infinitely complex shapes appear out of the simplest mathematical
formulae.....
Certainly beautiful, but why would you want to use them in your game?
The answer, quite simply, is that they are perfect for generating
realisticlooking landscapes. For example, real coastlines frequently
exhibit fractallike properties and fractal heightfields are often a
good first approximation to the contours of mountainous terrain.
Here I'm going to present a basic fractal algorithm that was
originally designed for generating random islands, seas and coastlines.
With a few minor alterations, it could easily be adapted to producing
all kinds of natural landscape patterns. My algorithm is vaguely based
on the familiar "plasma" type of fractal heightfield, but modified to
work with tiled maps.
I've included the source for a simple Java coastline generator applet
at the end of this article. If you are impatient and want to see the
thing working right away, just go to:
http://www.mikera.net/code/coastline.html
The Fractal Algorithm
=====================
One of the distinctive properties of fractal images is selfsimilarity.
That is, a zoomed in version will look similar to the whole image. This
algorithm achieves this effect by starting with a coarse map, and then
enhancing it by applying increasing levels of random detail.
Let's say that you are considering a square area of your map with the
corners labelled a, b, c and d :
a * b
* * *
c * d
Each map square can have a different colour. I used green for land and
blue for sea in the example applet.
The algorithm will then determine the map colours for the intermediate
points marked "*". It does this by randomly choosing a colour from one
of the adjacent corner squares. The "*" in the centre could take the
colour of either a, b, c or d.
Thus a possible final result might be:
a a b
c b d
c c d
We have now defined smaller squares on the map. The algorithm can then
be applied iteratively on a smaller scale. This process continues until
the desired level of detail is achieved.
a*a*b
*****
c*b*d
*****
c*c*d
Note that for convenience, it is helpful to have a map size that is a
power of two so that it can be repeatedly subdivided.
Example
=======
Below shows the iterations for a 16*16 grid.
For viewing convenience, the larger tiles have been completely filled
with the colour from the topleft corner, though this is not needed for
the algorithm to work.
In addition, the map is considered to be toroidal, i.e. the points on
the left edge are considered to be adjacent to those on the right edge,
and similarly for top and bottom.
Step 1:
ab#######
########
########
########
########
########
########
########
c#######d
########
########
########
########
########
########
########
(a, b, c and d mark the points that are coloured at the start. This
can be done randomly, or they can be preset to create land masses)
Step 2:
########
########
########
########
############
############
############
############
####
####
####
####
############
############
############
############
Step 3:
########
########
##########
##########
############
############
########
########
####
####
##
##
##########
##########
##########
##########
Step 4:
########
########
##########
########
############
###########
########
######
####
####
###
###
###########
##########
###########
#######
Et voila  one random continent ready to be populated with thriving
cities, dangerous mountain ranges and deep forests.
The Code
========
Here's a quick Java implementation of the fractal coastline algorithm.
It generates a new landscape each time the applet is repainted.
The makeFractal(step) method does all the actual work. This method
calls itself to handle finer detail levels.
========= CoastApp.java ==========
package kult.quest;
import java.awt.*;
import java.applet.*;
import java.awt.event.*;
public class CoastApp extends Applet {
// map size: must be a power of 2
public static final int size=128;
// allocate map storage
public int[] map= new int[size*size];
public void paint(Graphics g) {
super.paint(g);
// initial pattern (0=sea, 1=land)
setCell(0,0,0);
setCell(size/2,0,0);
setCell(0,size/2,0);
setCell(size/2,size/2,1);
makeFractal(size/4);
// draw the map
for (int y=0; y<size; y++) for (int x=0; x<size; x++) {
g.setColor( (getCell(x,y)==0) ? Color.blue : Color.green );
g.fillRect(x*2,y*2,2,2);
}
}
public void setCell(int x, int y, int c) {
map[x+size*y]=c;
}
public int getCell(int x, int y) {
return map[x+size*y];
}
// this routine builds the landscape....
// step = detail square width
public void makeFractal(int step) {
for (int y=0; y<size; y+=step) {
for (int x=0; x<size; x+=step) {
// The inner loop calculates (cx,cy)
// this is the point from which to copy map colour
// add random offsets
int cx=x+ ((Math.random()<0.5) ? 0 : step);
int cy=y+ ((Math.random()<0.5) ? 0 : step);
// truncate to nearest multiple of step*2
// since step*2 is the previous detail level calculated
cx=(cx/(step*2))*step*2;
cy=(cy/(step*2))*step*2;
// wrap around to reference world as torus
// also guarantees getCell() and setCell() are within bounds
cx=cx%size;
cy=cy%size;
// copy from (cx,cy) to (x,y)
setCell(x,y,getCell(cx,cy));
}
}
// recursively calculate finer detail levels
if (step>1) makeFractal(step/2);
}
// applet initialisation
public void init() {
super.init();
// repaint on mouse clicks
addMouseListener(new MouseAdapter()
public void mouseClicked( MouseEvent e ) {
repaint();
}
});
}
// main function allows applet to run as an application
public static void main(String[] args) {
// create a frame
Frame f = new Frame("Fractal Coastlines");
f.addWindowListener(new WindowAdapter() {
public void windowClosing(WindowEvent e) {
System.exit(0);
}
});
// set up frame and add applet
f.setSize(300,300);
f.setLayout(new BorderLayout());
CoastApp q=new CoastApp();
q.init();
f.add(q);
// go live....
f.show();
}
}
Conclusion
==========
Well, I hope I've given you a quick way to get some goodlooking
fractal landscapes. It is easy to extend this by adding different land
types (forests, deserts etc). You could also enhance the method to
include a height map by taking averages of adjacent points and adding
random offsets.
In fact, I've implemented a fractal algorithm to generate the World
Maps for Tyrant, my very own roguelike. You can see it in action at:
http://www.mikera.net/tyrant/
This uses essentially the same method as the one described above,
except that it uses a little bit of coding magic to make the landscapes
look more realistic and textured. While it's still far from perfect, it
does at least show there's scope for a lot of imaginative use of this
technique.
Happy Coding.
Mike.
Any questions or comments:
mike@mikera.net
