Generating Islands with Love2d and Box2d

Recently I’ve been back dabbling in some development with Love, and in my project I came to a point where I needed some islands generated in my game world.

On the surface, I could just generate n points and form islands around those, but at the time of implementing this, I wanted to provide a strict “budget” of islands - n islands of xl size, m islands of lg size, and so on.

Rather than agonise over an algorithm that’d shuffle squares away from one another, I instead opted for an inbuilt tool - box2d. Love provides access to this awesome library via its love.physics module, making full physics simulations pretty painless.

Running the simulation for a bit, this is what I’ve ended up with:

And applying some noise and a falloff equation, we can get this out the other side:

How, What?

What we’re doing is abusing love.physics to generate a bunch of blocks in the dead center of our screen. We then then run the simulation until it resolves everything, align it to the tile grid, then for every box, generating the landmass.

Here’s the physics part in action:

Disclaimer

I guess before we get started and you go a-copying this work, a small side-note.

Box2d is only kinda deterministic - given the same input, and binary, it should reproduce the same simulation.

To nitpick, though, this isn’t always going to be the case. Depending on the binary or platform it’s run on, floating point numbers might cause slight differences. At that point it’s getting into some hairy stuff well above my pay grade - but it’s something to keep in mind.

With that outta the way, let’s get setup

Setup

We’ll keep everything in a single main.lua file for this tutorial. Let’s start with some skeletons of what we want.

-- ==============================================
-- World Generation
-- ==============================================

local getIslandBudget()
end

local function generateNoise(x, y)
end

-- ==============================================
-- Physics
-- ==============================================

local world -- physics world

local function physicsBody(x, y, size)
end

-- ===============================================
-- Entrypoint
-- ===============================================

local function generate(world)
end

local function generateHeightMaps()
end

-- ==============================================
-- Love functions
-- ==============================================

function love.load()

  generate()
end

function love.update(dt)
end

function love.draw()
end

Physics

We’ll start with setting up our physics. The Box2d concepts we care about here are Worlds, Bodies, Shapes and Fixtures:

• Worlds are where Bodies live, and are responsible for gravity (which we don’t care about) and tuning the simulation.
• Bodies control of mass, velocity, rotation etc.
• Shapes give bodies shapes (think box, circle, polygon).
• Fixtures, which attach shapes to bodies, and control friction.

I’m ignoring collisions here as we’re not going to deal with those, but they’re probably the other major concept we’re missing here. The love.physics wiki page has an awesome breakdown.

Going in barebones, we just need to add the following to our love.load function.

function love.load()
-- Initialise to have no x or y gravity.
  world = love.physics.newWorld(0, 0)
end

We also need the world to update in our game loop, so we’ll call it in love.update:

function love.update(dt)
  world:update(dt)
end

Next, we’ll setup our physicsBody function to create our objects to simulate:

local function physicsBody(x, y, size)
  local body = love.physics.newBody(world, x, y)
  local shape = love.physics.newRectangleShape(size, size)
  local fixture = love.physics.newFixture(body, shape)
end

And with that, we now need something, or somethings to simulate.

Island Generation

I mentioned in the opening, I wanted the ability to define a ‘budget’ of islands that could be spawned in. This allows me to control, say, one big island, a couple medium sized, and a bunch of small ones per zone.

Simple enough, we just define a function that returns a table of sizes we then pass to physicsBody.

local XL = 17
local LG = 9
local MD = 7
local SM = 5
local XS = 3

local function getIslandBudget()
  local budget = { XL }

  for i = 1, 6 do
    table.insert(budget, LG)
  end

  for i = 1, 12 do
    table.insert(budget, MD)
  end

  for i = 1, 8 do
    table.insert(budget, SM)
  end

  for i = 1, 12 do
    table.insert(budget, XS)
  end

  return budget
end

You can tweak the numbers as you see fit, what matters is we now have a table containing a bunch of different island sizes that we can pass to our physics simulation and get shuffling.

Tying them together

You’ll notice that the values in the island budget are rather small. This is because in my game, island sizes are measured in their Chunk size. Chunks are an optimisation method for large games (again, think Minecraft), and in my project they’re 32 tiles wide. Since we’re not actually making a game, we’ll just call a Chunk 32 pixels wide and high.

local CHUNK_SIZE = 32

local function generate()
  -- get the island budget
  local islands = getIslandBudget()

  -- Then turn them into physics objects
  for i, island in ipairs(islands) do
    physicsBody(
      love.graphics.getWidth() / 2,
      love.graphics.getHeight() / 2,
      island
      )
  end
end

So we can actually see our islands, lets draw them in our love.draw function. To make this easier, lets modify physicsBody to return a table, and we’ll store that in a file-scoped local to make it easier to access.

local world

local function physicsObject(x, y, chunkSize)
  local size = chunkSize * CHUNK_SIZE
  local body = love.physics.newBody(world, x, y)
  local shape = love.physics.newRectangleShape(size, size)
  local fixture = love.physics.newFixture(body, shape)

  -- make sure the collisions don't cause our squares to rotate
  body:setFixedRotation(true)

  return {
    body = body,
    shape = shape,
    fixture = fixture,
    chunkSize = chunkSize,
    size = size
  }
end

And then we modify generate as so:

local physicsObjects = {}

local function generate()
  -- ...
    for i, island in ipairs(islands) do
    local physObj = physicsObject(
      love.graphics.getWidth() / 2,
      love.graphics.getHeight() / 2,
      island
      )
    table.insert(physicsObjects, physObj)
  end
end

When we go to render them, physics Bodies have their position origin in the center of the body, so we’ll have to shift it to the top-left, which is what love.graphics.rectangle expects. While we’re here, we’ll also change the colour depending on island size:

function love.draw()
  for i, physObj in ipairs(physicsObjects) do
    local bx, by = physObj.body:getPosition()
    local x = bx - physObj.size / 2
    local y = by - physObj.size / 2
        love.graphics.setColor(
          physObj.chunkSize / XL,
          (physObj.chunkSize / XL) / 2,
          physObj.chunkSize / XL
          )
    love.graphics.rectangle(
      "fill", x, y, physObj.size, physObj.size
      )
  end
end

Running this, and we get… this:

By default, if everything is at the same position, box2d seems to resolve them to pop upwards. Sure, over time they spread out a little, but it’s not very “spread out”. Easiest solution to this is adding a little variation on the body’s position when we create it:

local physObj = physicsObject(
  (love.graphics.getWidth() / 2) + love.math.random(-16, 16),
  (love.graphics.getHeight() / 2) + love.math.random(-16, 16),
  island
  )

Nice.

It’s preferable to fuzzy up the initial position, rather than applying a force to a physics object, as we need to have our bodies ‘sleep’ as soon as possible. In my experiments, applying a linear impulse and messing with restitution, mass, friction etc. just ended up more pain than it was worth.

Sleeping

Now we have a little bit of a spread going on, we want to make sure they’re not overlapping one another before moving onto the next step of actually generating the height maps.

Thankfully, box2d has the notion of sleeping - if a physics object hasn’t moved in a few cycles, it’ll be put to “sleep”. If all our bodies are sleeping, then we know that all the collisions have been resolved, and we can proceed.

local sleeping = false

local function allSleeping(bodies)
  for i, body in ipairs(bodies) do
    if body:isAwake() then
      return false
    end
  end
  return true
end

function love.update(dt)
  world:update(dt)

  if allSleeping(world:getBodies()) then
    sleeping = true
  end
end

It’d also be wise to stop updating our physics simulation, as when we snap the grid, we don’t want it to start resolving again, sleeping again, resolving etc.

if not sleeping then
  world:update(dt)
end

Snapping

This step is probably dependent on your game design, but if you’re running a large simulated world, you may want to store this stuff as “chunks” - a grouping of tiles that can be loaded and unloaded depending on where players are, and save on CPU cycles keeping them updated in your game.

I wanted my islands to align themselves to the nearest chunk boundary, just to avoid any extra complications. To do this, I just wait for the simulation to sleep, then call a function on every body’s position to put them at the nearest chunkSize divisible position.

Here is the code I use:

local function round(n)
  -- Kinda wild that lua doesn't have math.round
  return math.floor(n + 0.5)
end

function love.update(dt)
  world:update(dt)

  if allSleeping(world:getBodies()) then
    sleeping = true
    for i, body in ipairs(world:getBodies()) do
      local bx, by = body:getPosition()
      body:setPosition(
        round(bx / CHUNK_SIZE) * CHUNK_SIZE,
        round(by / CHUNK_SIZE) * CHUNK_SIZE
        )
    end
  end
end

Noise Generation

After all this, we now have a spread of boxes, but they don’t make very good islands. The stock standard way to do this is with noise functions.

I think this subject has been done to death, and I’d probably butcher it, so instead I’d recommend taking a look at Sebastian Lague on Youtube. He has a tutorial series on noise generation in Unity, but the concepts can easily be brought over to Love2d.

Helpfully, Love does contain its own noise implementation, love.math.noise, so the following is my bog standard implementation of a layered noise function. We’ll put it in the skeleton for generateNoise we made earlier

I’ve seeded the values for octaves, persistence and scale as per what’ll look nice here, but play around with them in your own code to your liking.

local octaves = 8
local persistence = 0.5
local scale = 0.01

local function generateNoise(x, y)
  local sum = 0
  local amplitude = 1
  local frequency = scale

  local noise = 0
  for i = 1, octaves do
    noise = noise + love.math.noise(x * frequency, y * frequency) * amplitude
    sum = sum + amplitude
    amplitude = amplitude * persistence
    frequency = frequency * 2
  end

  return noise / sum
end

On the wiki page for love.math.noise it warns us that passing integer values will return the same results, but in our example, since frequency is less than one we’ll get that. You may want to add a little bit of random variation to the values you pass in, or just a + 0.1 if you wish.

Applying the noise

We’ll now want to use this generateNoise function on each of our islands, and generate a height map to use when it comes to drawing them.

For simplicity, I’m going to create a new table called islandHeightMaps, but in a game you might apply this noise to an underlying chunk implementation, or some global heightMap - depends on your game.

We’ll build out our generateHeightMaps function.

local islandHeightMaps = {}

local function generateHeightMaps()
  for i, physObj in ipairs(physicsObjects) do
    local size = physObj.size
    local result = {}
    for y = 0, size do
      if not result[y] then
        result[y] = {}
      end
      for x = 0, size do
        result[y][x] = generateNoise(x, y)
      end
    end

    table.insert(islandHeightMaps, result)
  end
end

Then call it when we find out if the simulation is sleeping:

  if allSleeping(world:getBodies()) then
    sleeping = true
    for i, body in ipairs(world:getBodies()) do
      local bx, by = body:getPosition()
      body:setPosition(
        round(bx / CHUNK_SIZE) * CHUNK_SIZE,
        round(by / CHUNK_SIZE) * CHUNK_SIZE
        )
    end
    -- We could spin this into the previous snapping loop, but for the sake
    -- of separation/explaining, we'll just loop over it again.
    generateHeightMaps()
  end
end

And so we can see whats happening, lets draw them in our love.draw function.

function love.draw()
  for i, physObj in ipairs(physicsObjects) do
    local bx, by = physObj.body:getPosition()
    local x = bx - physObj.size / 2
    local y = by - physObj.size / 2

    if not sleeping then
        love.graphics.setColor(
          physObj.chunkSize / XL,
          (physObj.chunkSize / XL) / 2,
          physObj.chunkSize / XL
          )
    love.graphics.rectangle(
      "fill", x, y, physObj.size, physObj.size
      )
    else
      local heightMap = islandHeightMaps[i]
      for hy = 0, physObj.size do
        for hx = 0, physObj.size do
          local height = heightMap[hy][hx]
          love.graphics.setColor(height, height, height)
          love.graphics.points(hx + x, hy + y)
        end
      end
    end
  end
end

Oh, err - that kinda looks all the same, don’t it? That would be because we’re passing it the same values every run. There are a ton of ways to fix this, but the easiest might be just setting a random x and y offset value, and passing that into generateNoise:

-- in generateHeightMaps:
local xOffset = love.math.random(-1024, 1024)
local yOffset = love.math.random(-1024, 1024)

for y = 0, size do
  if not result[y] then
    result[y] = {}
  end
  for x = 0, size do
    result[y][x] = generateNoise(x + xOffset, y + yOffset)
  end
end

That looks a little more varied. Lets add a little colour. This function will take in a height value, and return a colour that denotes a land feature.

local colours = {
  { 0.2, 0.46, 0.08, 1 }, -- deep water
  { 0.14, 0.28, 0.53 }, -- shallow water
  { 0.25, 0.39, 0.65, 1 }, -- beach
  { 0.96, 0.95, 0.65, 1 }, -- grass
}

local function determineColour(height)
  if height <= 0.20 then
    return colours[2]
  elseif height > 0.2 and height <= 0.3 then
    return colours[3]
  elseif height > 0.3 and height < 0.33 then
    return colours[4]
  else
    return colours[1]
  end
end

And where we draw the height, we change the code to this:

local height = heightMap[hy][hx]
love.graphics.setColor(determineColour(height))
love.graphics.points(hx + x, hy + y)

Which will give us something like this:

Falloff

These boxes still don’t quite look like islands, rather one great big square landmass. What we want to do is influence the height calculation to give us a smaller number the closer we’re to the edge of the island.

A simple approach is to just do it by the distance from the center of the island, which could work!

Lets define a stock standard distance function we’ll use in generateHeightMaps to apply a falloff to our islands.

The gist here is, we want to find out how far away our point is from the center of the island. We’ll convert it into a percentage, then multiply our noise by the inverse of that value: (1 - percentage)

Here’s the code:

local function distance(x1, y1, x2, y2)
  local dx = x2 - x1
  local dy = y2 - y1
  return math.sqrt(dx * dx + dy * dy)
end

local function generateHeightMaps()
  for i, physObj in ipairs(physicsObjects) do
    local size = physObj.size
    local result = {}
    local xOffset = love.math.random(-1024, 1024)
    local yOffset = love.math.random(-1024, 1024)
    for y = 0, size do
      if not result[y] then
        result[y] = {}
      end
      for x = 0, size do
        local noise = generateNoise(x + xOffset, y + yOffset)
        local dist = distance(size / 2, size / 2, x, y) / (size / 2)
        result[y][x] = noise * (1 - dist)
      end
    end
    table.insert(islandHeightMaps, result)
  end
end

Bada bing, bada boom:

You can make it look like they’re in a large ocean by putting a love.graphics.clear(colours[2]) at the top of love.draw

Those sure look like islands to me!

Different Falloff

Using distance definitely works! But it does often end up in pretty rounded island shapes, and quite a ways from the edge of our island. There are a couple ways to fix this (but we won’t go over in this post)

• Use a varying array of signed distance fields to generate masks
• Use a different equation. Tools like Desmos help with this.
• Just play with the numbers!

I often like option number 3

Conclusion

In this post I’ve described a way to generate islands using box2d and Love. You can find the full code as a gist here.

The approach is pretty naive, but a fun way to explore all the little bits of procedural generation in a pretty dumb manner that’s easy to understand and implement.

Ultimately I didn’t end up using this method for my world generation, instead I opted for various the random points method to allow for more interesting islands. Becoming pedantic over island budgets didn’t really work out from a game design perspective, but that’s a story for another time.

Here’s an early output of a method I was testing out:

But thanks for reading! Hopefully I can share more dumb programming tricks in the future!