Basic island generation

Years ago I wrote on a now-lost blog about generating island outlines. I'll re-share my method here over the next few posts, and I hope to add something to the original algorithms.

The most basic approach is to push and pull the vertices of a regular N-gon, subdivide the sides, push and pull the new points, then repeat the subdivision process as many times as necessary.

To create a regular N-gon, we divide 360° by the number of sides and output polar coordinates:

(defn regular-ngon [sides]
  (for [angle (range 0 360 (Math/ceil (/ 360 sides)))]
    [1 angle]))

Here's a function to convert polar coordinates to cartesian coordinates:

(defn cartesian [r angle]
  [(* r (Math/sin (Math/toRadians angle)))
   (* r (Math/cos (Math/toRadians angle)))])

Use these functions like this:

(let [rng (java.util.Random. 1)
      sides (.nextInt rng 3 9)]
  (->> sides
    regular-ngon
    (map (partial apply cartesian))))

While the N-gon draws fine as a filled shape, the black stroke shows that it's actually missing its last side. That happens because the last point doesn't loop back around to the line's beginning. We can easily fix that:

(defn loop-around [coll]
  (concat coll [(first coll)]))

(let [rng (java.util.Random. 1)
      sides (.nextInt rng 3 9)]
  (->> sides
    regular-ngon
    (map (partial apply cartesian))
    loop-around))

We push and pull vertices by adjusting the polar coordinate's radius:

(defn irregularize [rng dr polar-coords]
  (for [[r angle] polar-coords]
    [(+ r (.nextDouble rng (- dr) dr)) angle]))

(let [rng (java.util.Random. 1)
      sides (.nextInt rng 3 9)]
  (->> sides
    regular-ngon
    (irregularize rng 0.35)
    (map (partial apply cartesian))
    loop-around))

To subdivide sides, here's a higher-order function that interpolates between pairs of items without knowing about how do to the actual interpolation:

(defn subdivide-with [f coll]
  (-> coll
    (->> (partition 2 1))
    (->> (mapcat (fn [[a b]]
                   [a (f a b)])))
    (concat [(last coll)])
    doall))

The final doall forces evaluation of the lazy sequence and maintains the order of calls to the methods of java.util.Random. Without it, going from one subdivision of the N-gon's sides to two produces very different islands because, while the random numbers occur in the same sequence, they're used for different calculations. doall ensures the same numbers are used the same way, regardless of the number of subdivisions.

The process for subdividing a side is to find the side's midpoint and perpendicular, then slide the midpoint along the perpendicular by a random amount:

(defn offset-midpoint [rng [x1 y1] [x2 y2]]
  (let [mx (/ (+ x1 x2) 2)
        my (/ (+ y1 y2) 2)
        vx (- (- y1 y2))
        vy (- x1 x2)
        s (.nextDouble rng -0.5 0.5)]
    [(+ mx (* s vx))
     (+ my (* s vy))]))

We'll want to subdivide repeatedly, so here's another higher-order function that invokes an operation on its previous result a given number of times:

(defn iterate-n-times [f init n]
  (reduce
    (fn [acc _]
      (f acc))
    init
    (range n)))

I've called it iterate-n-times since it's conceptually related to Clojure's built-in iterate function, which creates a sequence by repeatedly applying a function to the previous result. In fact, we could have implemented iterate-n-times more simply as (nth (iterate f init) n), but using reduce prevents any possibility of Clojure's lazy sequence evaluation generating more values than we need. Often that's not a problem, but in our case each subdivision doubles the number of points in the list, so the collection size grows exponentially.

To produce an island, we repeatedly subdivide until we get a result we like:

(let [rng (java.util.Random. 1)
      sides (.nextInt rng 3 9)
      verts (->> sides
              regular-ngon
              (irregularize rng 0.35)
              (map (partial apply cartesian))
              loop-around)]
  (iterate-n-times
    #(subdivide-with (partial offset-midpoint rng) %)
    verts
    8))

Below is a progression from our irregular N-gon above to a more interesting island, with all but the first and last images showing an outline of the previous iteration for comparison:

This relatively simple approach is able to generate fairly believable islands, including bays, coves, and eroding peninsulas.

Different random seeds produce different islands:

Because we start with a regular N-gon, this method tends to generate rounder islands, but it hardly precludes the possibility of narrow, rocky-looking peninsulas reaching into the sea.

If you'd like to experiment with different styles of islands, try starting with an irregular N-gon drawn from randomly choosen coordinates. Feel free to email me with anything interesting you find.

The drawback of this approach's simplicity is that all the islands have very consisent boundary textures. To fix that, we'll add some variation in the next post.