Generating heightmap terrain with Swift
I’ve had a bit of spare time lately, time off from work for our #3 baby, and I’ve always been a fan of games with heightmap terrain, so I decided to see how I could generate it with Swift. This post is just a bit of fun, you can skim this one :)
Algorithm
It’s called the Diamond-square algorithm and basically it works by repetitively dividing by diamonds then squares. Now this sounds like a good contender for a recursive algorithm, which I initially tried, but that doesn’t work because it goes depth-first instead of breadth-first, so a good old for-loop actually works better.
Terrain model
Firstly you need a model object to handle the two-dimensional heightmap. Basically it’s a wrapper around an array of floats with some convenience accessors:
class Terrain {
var array: [Float]
let size: Int
/// Creates a new terrain of the given width and height.
init(size: Int) {
self.size = size
array = [Float](count: size*size, repeatedValue: 0)
}
/// Sets one point to a given height value.
func set(x x: Int, y: Int, value: Float) {
array[y * size + x] = value
}
/// Gets the height at a point.
func get(x x: Int, y: Int) -> Float {
return array[y * size + x]
}
/// Gets a point safely, returning nil if it's clipped outside the area.
func getClipped(x x: Int, y: Int) -> Float? {
if x >= 0 && y >= 0 && x < size && y < size {
return get(x: x, y: y)
} else {
return nil
}
}
}
Notice that this uses class semantics, not value semantic (eg it’s not a struct). This is because it has to be mutated a lot and isn’t a great candidate for functional programming as far as I can see
Diamond-square steps
Next we need to implement the diamond and square steps. I’m not going to explain how these work (I’ll probably confuse you more!) - so read the wiki entry if you’re unfamiliar.
Notice that these steps are implemented as an extension. This is to keep the code separate from the code above, as this generation code is really auxiliary (eg you might simply load the map from disk and not need to generate it). Nice design principle to keep in mind: If it’s not core functionality, consider putting it in an extension.
/// Returns in the range -1..1
func frand() -> Float {
return Float(drand48() * 2 - 1)
}
extension Terrain {
/// Sets the midpoint of the square to be the average of the four corner points plus a random value.
/// x,y are the top left values.
func diamond(x x: Int, y: Int, size: Int, randomScale: Float) {
let tl = get(x: x, y: y)
let tr = get(x: x + size, y: y)
let bl = get(x: x, y: y + size)
let br = get(x: x + size, y: y + size)
let avg = (tl + tr + bl + br) / 4
set(x: x + size/2, y: y + size/2, value: avg + frand() * randomScale)
}
/// Sets the midpoints of the sides of the square to be the average of the 3 or
/// 4 horiz/vert points plus a random value.
func square(x x: Int, y: Int, size: Int, randomScale: Float) {
// Get all the inputs.
let half = size/2
let tl = get(x: x, y: y)
let tr = get(x: x + size, y: y)
let bl = get(x: x, y: y + size)
let br = get(x: x + size, y: y + size)
let m = get(x: x + half, y: y + half)
let above = getClipped(x: x + half, y: y - half)
let below = getClipped(x: x + half, y: y + size + half)
let left = getClipped(x: x - half, y: y + half)
let right = getClipped(x: x + size + half, y: y + half)
// Set the sides.
set(x: x + half, y: y, value: average(tl, tr, m, above) + frand() * randomScale) // Top
set(x: x + half, y: y + size, value: average(bl, br, m, below) + frand() * randomScale) // Bottom
set(x: x, y: y + half, value: average(tl, bl, m, left) + frand() * randomScale) // Left
set(x: x + size, y: y + half, value: average(tr, br, m, right) + frand() * randomScale) // Right
}
/// Average of the 3 or 4 inputs.
private func average(a: Float, _ b: Float, _ c: Float, _ d: Float?) -> Float {
if let d = d {
return (a+b+c+d) / 4
} else {
return (a+b+c) / 3
}
}
}
Generation
Next is the actual generator that iterates through the diamond-square steps to create a new map. I initially wrote this to use recursion but it ended up being depth-first not breadth-first and the generated terrain was terrible. I’m sure a haskell guru could make this beautiful.
extension Terrain {
/// The height/width is 2^detail+1.
/// Eg detail=8 -> size=257 -> ~1/4 megabyte
/// https://en.wikipedia.org/wiki/Diamond-square_algorithm
/// Roughness 1 = rough, 0 = flat. 0.6 looks good.
static func generatedTerrainWithDetail(detail: Double, roughness: Float) -> Terrain {
let size = Int(round(pow(2, detail) + 1)) // Will be the number of array elements in each dimension (odd number).
let max = size - 1 // The maximum index.
let map = Terrain(size: size)
// Initial corner values.
map.set(x: 0, y: 0, value: frand())
map.set(x: max, y: 0, value: frand())
map.set(x: 0, y: max, value: frand())
map.set(x: max, y: max, value: frand())
// Fill it in.
for var subSize = max, randomScale: Float = 1; subSize > 1; subSize /= 2, randomScale *= roughness {
for var y = 0; y < max; y += subSize {
for var x = 0; x < max; x += subSize {
map.diamond(x: x, y: y, size: subSize, randomScale: randomScale)
}
}
for var y = 0; y < max; y += subSize {
for var x = 0; x < max; x += subSize {
map.square(x: x, y: y, size: subSize, randomScale: randomScale)
}
}
}
return map
}
}
In a future post, I might write about how to render this using SceneKit.
Thanks for reading!
Thanks for reading! And if you want to get in touch, I'd love to hear from you: chris.hulbert at gmail.
Chris Hulbert
(Comp Sci, Hons - UTS)
Software Developer (Freelancer / Contractor) in Australia.
I have worked at places such as Google, Cochlear, Assembly Payments, News Corp, Fox Sports, NineMSN, FetchTV, Coles, Woolworths, Trust Bank, and Westpac, among others. If you're looking for help developing an iOS app, drop me a line!
Get in touch:
[email protected]
github.com/chrishulbert
linkedin
