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
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 Algorithm
=====================

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


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 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 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 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:
  mike@mikera.net