Procedural Generation in Godot - Part 7: Dungeons (part 2)

Tags: godot gamedev tutorial procgen

In this series, we’ll explore the applications of procedural generation to game development. While we’ll be using Godot 3.0 as our platform, much of the concepts and algorithms related to this subject are universal, and you can apply them to whatever platform you may be working on.

In this part, we’ll continue working on the random dungeon generator, adding corridors to connect the rooms.

You can watch a video version of this lesson here:

Connecting the rooms

In the last part we created a random collection of rooms, using the physics engine to ensure they are spread out and not overlapping. Now we need to figure out how to connect the rooms together.

There are many different ways to approach this, but we’re going to use the minimum spanning tree (MST) method. Given a set of points (represented as a graph), an MST identifies the minimum number of connections that connects all points with the shortest total path length.

We’ll be using Prim’s Algorithm to generate our MST. We’ll also use Godot’s AStar node to store the data, as it is a built-in graph data structure.

Start by adding a variable to store the data in:

var path  # AStar pathfinding object

Now in the make_rooms() function, as we cull the rooms, we want to create an array of the positions of the remaining rooms. We’ll pass this array to the MST algorithm.

    # cull rooms
    var room_positions = []
    for room in $Rooms.get_children():
        if randf() < cull:
            room.queue_free()
        else:
            room.mode = RigidBody2D.MODE_STATIC
            room_positions.append(Vector3(room.position.x, room.position.y, 0))
    yield(get_tree(), 'idle_frame')
    # generate spanning tree (path)
    path = find_mst(room_positions)

Now we get to where the action happens. See the comments below in the code for a summary of what’s happening. You can read the link above if you’re curious about the details of the algorithm.

func find_mst(nodes):
    # Prim's algorithm
    # Given an array of positions (nodes), generates a minimum
    # spanning tree
    # Returns an AStar object

    # Initialize the AStar and add the first point
    var path = AStar.new()
    path.add_point(path.get_available_point_id(), nodes.pop_front())

    # Repeat until no more nodes remain
    while nodes:
        var min_dist = INF  # Minimum distance found so far
        var min_p = null  # Position of that node
        var p = null  # Current position
        # Loop through the points in the path
        for p1 in path.get_points():
            p1 = path.get_point_position(p1)
            # Loop through the remaining nodes in the given array
            for p2 in nodes:
                # If the node is closer, make it the closest
                if p1.distance_to(p2) < min_dist:
                    min_dist = p1.distance_to(p2)
                    min_p = p2
                    p = p1
        # Insert the resulting node into the path and add
        # its connection
        var n = path.get_available_point_id()
        path.add_point(n, min_p)
        path.connect_points(path.get_closest_point(p), n)
        # Remove the node from the array so it isn't visited again
        nodes.erase(min_p)
    return path

Now we’ll have a path, so all that’s left is to draw it on the screen so we can see it. We’ll use CanvasItem.draw_line() to draw each connection in the AStar path.

func _draw():
    for room in $Rooms.get_children():
        draw_rect(Rect2(room.position - room.size, room.size*2),
                  Color(0, 1, 0), false)
    if path:
        for p in path.get_points():
            for c in path.get_point_connections(p):
                var pp = path.get_point_position(p)
                var cp = path.get_point_position(c)
                draw_line(Vector2(pp.x, pp.y),
                          Vector2(cp.x, cp.y),
                          Color(1, 1, 0, 1), 15, true)

Run the game and you should see a beautiful minimum spanning tree connecting your rooms!

alt

Conclusion

We’re almost there! We have a collection of rooms and a path connecting them. The final step is to convert all of this into a TileMap so that we can actually walk around the dungeon. We’ll do that in the next part.

Please comment below with your questions and suggestions.

Download the code for this lesson

Comments