Random Walk Map Generation

I experimented a little with generating world maps. A common approach it to use Perlin noise, which can result in astonishing landscapes. I wanted to see if it is possible to create a world map with a much simpler approach: slightly modified random walks.

My algorithm can be described in five trivial steps:

1. Place N (e.g. 10) arbitrary start points with elevation 'height' (e.g. 500)
2. For each point P in the map, choose a random neighbor P'.
3. Calculate their difference in elevation minus one: diff = P.height - P'.height - 1
4. If diff > 0, move that amount of elevation to the neighbour P'. (i.e. P.height -= diff; P'.height += diff;).
5. Go back to step 2.

The most notable difference to the classical random walk is that due to the condition in step 4, the algorithm does not like to revisit nodes it has visited before. Note that step 2 can be optimized by focusing on the known hot spots.

Doing this on a 640x480 map with 10 start points looks as follows.

Starting with 10 islands

Islands are growing

Some of the islands connected

First larger landmasses emerge

Final map

What are the advantages of the random walk approach?

• It is trivial to implement.
• The two parameters (number of start locations and their height) allow to intuitively tune the number of islands as well as their size.
• The algorithm can be applied to any graph or topology. Unlike with the Perlin approach, no coordinate system is required. All that's needed is a set of connected nodes.

The main disadvantage of this approach is that it is computationally expensive when generating large landmasses as the same nodes are revisited often.

Quick Google App Engine RSA Benchmark

Update: Please read Strom's comment. He explains everything. I wasn't aware of the 15 minutes rule.

Generating a 2048-Bit RSA key with the Google APP Engine takes about 10 seconds at average. On my PC, it takes 2 seconds. I called the service six times on a clean app engine account. This resulted in 0.30 frontend machine hours being consumed. So even though I used the CPU for one minute in total, Google charges about 20 minutes (0.3 hours).

At a price of 0.08$ per hour, generating a 2048-Bit RSA key costs about half a cent. Or in other words: my cpu (intel i7, 2.8 GHz) can do about one app engine machine hour in 40 seconds. This means, doing one hour of heavy-duty calculations on my CPU would cost me about 8$ of frontend machine hours at Google.

My conclusion: Google app engine is too expensive for my intended application, unless backend machine hours differ significantly from frontend machine hours.

For reference, the core code of my servlet:

KeyPairGenerator kpg = KeyPairGenerator.getInstance("RSA");
kpg.initialize(2048);
KeyPair kp = kpg.genKeyPair();