Procedural Dungeon Generation #3

[a327ex]

This post will explain a technique for generating an overmap lightly inspired by the one in Slay the Spire. The general way it works is like this:

Physics Step

The first thing we want to do is generate the nodes that will make up our graph. The way I decided to do this was by spawning a bunch of box2d circles and letting the physics engine separate them as the simulation moves forwards. We create all those circles inside a rectangular boundary for this example and the way it looks is like this:

The code to make this happen is fairly simple. For instance, the function to create a circle looks like this:

circles = {}
local function create_physics_circle(x, y, radius)
    local circle = {}
    circle.body = love.physics.newBody(world, x, y, 'dynamic')
    circle.shape = love.physics.newCircleShape(radius)
    circle.fixture = love.physics.newFixture(circle.body, circle.shape)
    circle.radius = radius
    table.insert(circles, circle)
end

This is a pretty standard way of creating a physics circle with box2d and should be the same or similar everywhere. And then we create multiple of those physics circles like this:

radii = {}
for i = 1, 32 do table.insert(radii, 6) end
for i = 1, 18 do table.insert(radii, 8) end
for i = 1, 12 do table.insert(radii, 10) end
for i = 1, #radii do create_physics_circle(game_width/2 + 4*(2*love.math.random()-1), game_height/2 + 4*(2*love.math.random()-1), table.remove(radii, love.math.random(1, #radii))) end

Here there's a simple table full of different values 6, 8 and 10 which represent the different sizes for all possible circles. This way we can create a graph that already has differently sized circles which will correspond to different types of nodes in the overmap. One of the advantages of using the physics engine here is that we can create objects of different shapes and sizes, as well as play with the shape and size of the bounding object, and everything will still be neatly separated without any extra work.

After this we can move the simulation forward until we're happy with it. I choose 500 steps but you may choose a different number:

for i = 1, 500 do world:update(dt) end

After the simulation is done we can transform these physics objects into nodes that will make up the graph that represents the overmap:

graph = {}
for _, circle in ipairs(circles) do 
    circle.x, circle.y = circle.body:getPosition()
    table.insert(graph, {x = circle.x, y = circle.y, radius = circle.radius}) 
end
world:destroy()

Additionally we also destroy the physics world we previously created and all the bodies, fixtures and shapes with it. The only data structure we care about now is graph, which contains all the nodes as tables with x, y and radius attributes.

Pathing Step

In this step we'll take this graph, connect all nodes to their nearest neighbors, and then create the paths in the graph that will represent our final overmap. The first step is the connection of all nodes which looks like this:

And the code to achieve that is this:

for i, node_1 in ipairs(graph) do
    for j, node_2 in ipairs(graph) do
        if i ~= j and distance(node_1.x, node_1.y, node_2.x, node_2.y) < 1.1*(node_1.radius + node_2.radius) then
            if not node_1.neighbors then node_1.neighbors = {} end
            table.insert(node_1.neighbors, node_2)
        end
    end
end

Here we're just going through all nodes and for each node we're checking which other nodes are close enough and adding those nodes to a neighbors attribute. Now each node is a table with x, y, radius and neighbors, which is another table containing references to other nodes in the graph table.

The next two things we'll do is select the nodes that will make up our overmap. This will be divided into vertical and horizontal steps. The vertical step will pick a random at the top of our graph and walk randomly down until it can't do that anymore. We'll repeat this step twice.

The horizontal step will pick a randomly already selected node from one of the vertical steps and then walk randomly either left or right based on how far away the picked node is from left/right edge. If a node is further away from the left edge then we will walk left, otherwise we'll walk right.

All this put together looks like this:

For the purposes of these gifs each vertical step is colored red and green, and the horizontal steps are colored blue. The code to achieve the vertical step looks like this:

local function create_path_from_top_to_bottom(i)
    -- Pick a new node until one that isn't selected is picked
    local node = get_random_top_node()
    while node.selected do node = get_random_top_node() end
    node.selected = i

    -- Pick random neighbor down until no more random neighbors down can be picked
    local down = get_random_neighbor_down(node)
    while down do
        down.selected = i
        down = get_random_neighbor_down(down)
    end
end

This picks a top node until it picks one that isn't selected, and here we also set the selected attribute to the number passed in to the function. For the vertical step we'll call create_path_from_top_to_bottom(1) and create_path_from_top_to_bottom(2), and then when we draw each node we'll use these numbers to tell which step of the algorithm each node belongs to; this is done simply for educational/visual purposes. In reality we'd just set node.selected = true instead of a number and the logic would work the same.

After we pick a random node we walk down from it until we can't anymore. get_random_neighbor_down will go through the neighbors attribute of a node and return a random one that has a higher y attribute. If there are no neighbors nodes with a higher y attribute then it simply returns nil, and based on how we set this while loop up it means it will stop picking more nodes.

The same exact logic applies to the horizontal steps, just instead of picking a random top node we pick a random selected node, and we also need some additional logic to decide if we should walk left or right.

Final step

In the final step we'll take the nodes in our graph data structure and create the objects that will make our overmap in the game. The end result looks like this:

I'm not going to focus much on this step since it's the one that's most specific to whatever game, but the most important thing is the mapping from the physics world positions to the positions in the actual game. The way we initially created the boundary was like this:

boundary.x1, boundary.y1 = game_width/2 + 40, game_height/2 + 81
boundary.x2, boundary.y2 = game_width/2 - 40, game_height/2 - 81 

And so what this means is that the rectangle that defines the boundaries of our nodes have width 80 and height 162, centered at game_width, game_height. These numbers were not chosen randomly, because I want the overmap to have a width of 400 and a height of 810, as the size of one screen is 480x270 and this means that in terms of width the overmap will cover almost the whole screen (leaving some left over for potentially extra information on one of the sides) and in terms of height it will cover exactly 3 screens. All this means that when translating the positions of our graph nodes to actual world objects we just need to take these measurements into account, and that would look like this:

for _, node in ipairs(graph) do
    if node.selected then
        node.x = remap(node.x, game_width/2 - 40, game_width/2 + 40, 0, 400), 
        node.y = remap(node.y, game_height/2 - 81, game_height/2 + 81, -540, 270)
    end
end

Here the remap function changes the first value from its previous range to a new one. So, for instance, remap(5, 0, 10, 5, 0) returns 2.5. In this simple way we can change the position of our nodes to the position they should be in the world. And finally, now that we have all our nodes in their proper places we can create our game objects from the graph data structure. I won't go over this since it's specific to each game, but you should be able to continue from here by yourself. Good luck!

---

The source code for all this is available here. You can run it by using LÖVE and it's written in Lua. I tried to write it in the simplest way possible and without using anything too specific to Lua, so it should be easy to follow if you use other languages. To stop at each stage of the tutorial, simply remove the call to the next stage from the previous one, for example, remove the call to pathing_step if you want to stop at the end of physics_step to see what the circles look like after they're simulated.

[KowalewskajA]

Great to see ya still sharing your insights with us. I first saw the gif on Reddit and was hoping that you would write about it here. I am so glad you did :). I like the physics part remembered me off your Delauney Tut on Gamasutra ;).

[FlaminThunda]

Hey love your work. Would it be possible to see the full code for this. I am a complete noob at coding

[gingerbeardman]

@FlaminThunda the code is linked in the last paragraph of the OP, not far above your post!