Monday, July 16, 2012

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.

Sunday, April 15, 2012

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();

Friday, April 24, 2009

Use positive expressions

When striving for clear and concise articulation, in programming or in natural languages, try to express yourself with as few negations as possible. Negations leed to confusion. Our brain does not handle them well.

Example 1: It is better to ask "may I sit here?" than "is this seat taken?". Try it. The latter question will confuse some people. They might answer "no" even though the seat is taken and vice versa, especially if you mumble and all they understand is your intention to take that seat. Their brain translates the question to "should I allow the guy to take that seat?".

Example 2: if a newspaper writes "Senator Smith never smoked pot", the number of people thinking that Senator Smith smoked pot might grow because all they might remember is "senator smith" and "pot". Negative associations rarely work.

When programming, it is essential to write clear and understandable code. Avoiding the not operator helps.
  • It is better to write "if x==7 then a else b" than "if x!=7 then b else a".
  • It is also better to create a method "list.hasItems" than "list.isEmpty".
  • It is better to have a checkbox that says "cache thumbnails" and is enabled by default than a checkbox "do not cache thumbnails" that is disabled by default (as found in the folder options of Windows).
You get the idea. Internalize it.