By Mike Anderson30th 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 realistic-looking landscapes. For example, real coastlines frequently exhibit fractal-like 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 AlgorithmOne of the distinctive properties of fractal images is self-similarity. 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. ExampleBelow shows the iterations for a 16*16 grid. For viewing convenience, the larger tiles have been completely filled with the colour from the top-left 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: a-------b####### --------######## --------######## --------######## --------######## --------######## --------######## --------######## 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 pre-set 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 CodeHere'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(); } } ConclusionWell, I hope I've given you a quick way to get some good-looking 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: |