© The Author(s), under exclusive license to APress Media, LLC, part of Springer Nature 2023
C. PittProcedural Generation in Godothttps://doi.org/10.1007/978-1-4842-8795-8_8

8. Navigating in Generated Levels

Christopher Pitt1  
(1)
Durbanville, South Africa
 

So far, all our player movement has been through the use of arrow keys or similar. We’ve yet to create a click-to-move system, or any sort of enemy or NPC (nonplayable character) movement. Before we can do that, we need to build a foundation for pathfinding.

That’s going to be the focus of this chapter. We’re going to look at how Godot handles pathfinding and how we can build maps with obstacles that the player must navigate around.

Getting Set Up

Let’s create a new experiment in our experiment project, called NavigationExperiment. Follow all the same steps you did before to have this new experiment displayed as the default experiment. If you need a refresher, refer to Chapter 2 for how to set up new experiments.

Then, reuse any of the tile sets we’ve already used to create a basic TileMap and TileSet combo:

A screenshot of the scene window that lists the options under the file system, which has the highlighted navigation experiment with a square tile map.

Creating the TileMap

Increase the Transform ➤ Scale of NavigationExperiment to 3 × 3 and change Project Settings ➤ Window values so that the graphics resize along with the window. 640 × 480 pixels seems like a good window size. Refer to the previous chapter if you get stuck.

This gives us a good starting point for the navigation work we’re about to do.

Adding Basic Movement

Godot has a neat set of tools to help us work out the path we can take between points of interest. The main ones, which we need to add to our experiment, are NavigationRegion2D and NavigationAgent2D. The agent needs to be a child of the player sprite, while the region can be anywhere in the scene tree.

Once added, we will also need to enable Avoidance on the agent so that it can path around any obstacles, and Max Speed to 20 pixels per second:

A screenshot of the scene window that lists the options under the navigation experiment has the highlighted navigation agent with a square tile map and a sprite character.

Regions and agents

I’ve set the player up as a Sprite2D, but you can use a node that has a position property. The code that controls or interacts with these nodes looks like this:

This is from experiments/navigation_experiment.gd
extends GameExperiment
@onready var _player := $Sprite2d as Sprite2D
@onready var _agent := $Sprite2d/NavigationAgent2d as NavigationAgent2D
@onready var _destination := $Marker2d as Marker2D
func _ready() -> void:
    _agent.velocity_computed.connect(
        func(velocity: Vector2) -> void:
            _player.global_position += velocity
    )
    _agent.set_target_location(_player.global_position)
    await get_tree().create_timer(1.0).timeout
    _agent.set_target_location(_destination.global_position)
func _physics_process(delta: float) -> void:
    var next_location := _agent.get_next_location()
    var next_velocity := next_location - _player.global_position
    _agent.set_velocity(next_velocity)

You can think of the NavigationAgent2D as the controller for the movement of the player. It communicates with the NavigationServer to work out the appropriate path between points of interest. It can also send movement or positional information back to the scene where things are moving.

In this case, we can listen for the velocity_computed signal and use the velocity it returns to move the player around the screen. To make sure this signal happens, check the Avoidance Enabled check box in the properties inspector pane.

Signals are the perfect place to use lambda functions, but we can also define named functions and connect them to the same signals. Do what feels best for you.

We need to call the agent's get_next_location method inside the physics process. This gets the next position on the path for the player to travel. It also allows the agent to check if there will be any collisions and adjust the path.

To work out what the new velocity should be, we take the next position along the path and subtract the player’s position. This is the velocity the NavigationAgent2D needs to work out where to move next.

Adding Navigation to Tile Maps

It’s not essential to have a NavigationRegion2D in order for this click-to-move functionality to work. It’s just the simplest way to get started. If you prefer, you can also add this navigation region data to your tile maps.

Let’s test this out by adding the data to our tile map:
  1. 1.

    Select the tile map and change Navigation Visibility Mode to Force Show.

     

A screenshot of the inspector window that lists the options under the tile map with the highlighted navigation visibility mode and force show.

  1. 2.

    Click the Tile Set drop-down, and scroll down to Navigation Layers.

     

A screenshot of the inspector window that lists the options under the tile map, which has the highlighted tile set with the selected square, size, and navigation layers.

  1. 3.

    Click Add Element.

     

A screenshot of the tile set dialog box that lists the options under navigation layers with a keypad of numbers ranging from 1 to 24.

  1. 4.

    Click the Tile Set tab at the bottom of the screen.

     
  2. 5.

    Click the paint brush icon, and select the Navigation Layer 0 we just created.

     

A screenshot of the tile window that lists the options under paint properties with the navigation layer and the tile set with different patterns of tiles on the right.

  1. 6.

    Click on the tiles that you want to be navigable.

     

A screenshot of the paint properties window that lists the options under the painting with a highlighted square shaped pattern.

  1. 7.

    Once we remove the NavigationRegion2D, the map should resemble this:

     

A screenshot of the scene window that lists the options under the navigation experiment with the highlighted navigation region 2 D, along with an opened square shaped tile map and a sprite character.

Navigation data in tile sets

We don’t even have to change the code for the NavigationAgent2D to use this new navigation data. We only have to delete the NavigationRegion2D and re-run the game. The player character will now move around the walls instead of through them.

Adding Obstacle Nodes

We could build entire games using only these tile set navigation properties; but our games might need tile sets and obstacle nodes.

The simplest approach is to add more NavigationAgent2D nodes to the map. The player will then attempt to avoid them, though sometimes the pathing is a bit buggy:

A screenshot of the scene window that lists the options under the navigation experiment with an opened square shaped tile map, along with three sprite characters.

Avoidance with other NavigationAgent2D nodes

We can try to replicate this same navigation data using many NavigationRegion2D nodes. It’s going to be a pain in the butt to position them all next to each other and with straight lines:

A screenshot of the scene window that lists the options under the navigation experiment, which has an opened square shaped tile map with three sprite characters.

Navigation data in nodes

Furthermore, the navigation is still buggy. It would be better if we could use collision polygons to carve out non-navigable areas of the navigation rectangle.

Before we jump into the code required to do this, let’s change our obstacles to Area2D nodes with CollisionPolygon2D colliders. We should also add another Area2D node for the walls:

A screenshot of the scene window that lists the options under the navigation experiment, which has a highlighted navigation agent and area with a square shaped tile map and three sprite characters.

Adding colliders for non-navigable areas

Add each of these to a group. Make it something that you’ll remember, which describes what the purpose of being in this group is:

A screenshot of the node dialog box that lists the options under groups and has the option to manage groups with the non navigable entity.

Adding non-navigable areas to the same group

Now, we can find these nodes and cut them out of the navigation region using code:

This is from experiments/navigation_experiment.gd
@onready var _region := $NavigationRegion2d as NavigationRegion2D
func cut_out_areas() -> void:
    var outlines := []
    for node in get_tree().get_nodes_in_group("non_navigable_entity"):
        var node_outline := PackedVector2Array()
        var node_collider := node.get_node("CollisionPolygon2d") as CollisionPolygon2D
        var node_polygon := node_collider.get_polygon()
        for vertex in node_polygon:
            node_outline.append(node.transform * vertex)
        outlines.append(node_outline)
    for outline in outlines:
        _region.navpoly.add_outline(outline)
    _region.navpoly.make_polygons_from_outlines()
func _ready() -> void:
    cut_out_areas()
  # ...

When the experiment loads up, we now call cut_out_areas, which loops through each of the grouped nodes and adds their outlines to an array.

We combine these with the outlines in the _region.navpoly so that they are excluded from the starting region polygon.

If you use this approach in your games, don’t forget to call make_polygons_from_outlines, or your navigation region won’t update.

Here’s what this looks like, with Debug ➤ Visible Navigation enabled:

A screenshot of the experiment d e b u g window, which has an opened square shaped tile map with three sprite characters.

Cutting outlines out of a NavigationPolygon2D

Unfortunately, while the NavigationAgent2D movement is nicer, there are significant drawbacks to this approach, the main one being that the outlines can never touch.

Godot has this nasty habit of ignoring overlapping outlines. You're likely to see the error NavigationPolygon: Convex partition failed! If you leave gaps to avoid this, the player will move straight through the gaps, ignoring the intended route.

Merging Polygons

The most bullet-proof solution I’ve come across is to
  1. 1.

    Group overlapping polygons together

     
  2. 2.

    Combine them into single polygons

     
  3. 3.

    Add those polygons as outlines to the navpoly

     

It’s a mission.

Let’ start by creating a method to find intersecting polygons:

This is from experiments/navigation_experiment.gd
var auto_number = 0
func find_intersections(node, nodes, groups, group_id = null) -> Dictionary:
    var node_collider := node.get_node("CollisionPolygon2d") as CollisionPolygon2D
    var node_polygon := node_collider.get_polygon()
    for other_node in nodes:
        if other_node == node:
            continue
        var other_node_collider := other_node.get_node("CollisionPolygon2d") as CollisionPolygon2D
        var other_node_polygon := other_node_collider.get_polygon()
        var result := Geometry2D.intersect_polygons(node_polygon * node.transform, other_node_polygon * other_node.transform)
        if result.size() > 0:
            if group_id == null:
                group_id = auto_number
                groups[group_id] = []
                groups[group_id].append(node)
                nodes.erase(node)
                auto_number += 1
            groups[group_id].append(other_node)
            nodes.erase(other_node)
    return {
        "nodes": nodes,
        "groups": groups,
    }

This method accepts a reference node, which is any node that has a CollisionPolygon2D in it. It also accepts an array of nodes to compare with. It loops through all the comparable nodes to see if any of them intersect with the subject node.

If it finds intersections, it adds both nodes to the groups array. If there is no group_id, it creates a new group from the subject node and all others from the list of comparable nodes that intersect with it.

Here’s how you can think of it working:

A diagram of how node 1 is compared to node 2 and moved into group 1. After node 2 is removed from group 1, the increment group i d value for the remaining grouping is computed.

Grouping intersecting polygons

Let’s also add a helper to simplify how we get outlines from collision polygons:

This is from experiments/navigation_experiment.gd
func get_outline(node) -> PackedVector2Array:
    var node_outline := PackedVector2Array()
    var node_collider := node.get_node("CollisionPolygon2d") as CollisionPolygon2D
    var node_polygon := node_collider.get_polygon()
    for vertex in node_polygon:
        node_outline.append(node.transform * vertex)
    return node_outline

We’ve already seen this code in action, but we’re going to perform the same operation many times; so it’s better to extract it to this helper method.

We can refactor the cut_out_areas method to combine intersecting groups of polygons into single polygons and add all the resulting outlines to the navpoly:

This is from experiments/navigation_experiment.gd
func cut_out_areas() -> void:
    var nodes := get_tree().get_nodes_in_group("non_navigable_entity")
    var groups := {}
    for node in nodes:
        var result := find_intersections(node, nodes, groups)
        nodes = result.nodes
        groups = result.groups
    for key in groups.keys():
        for node in groups[key]:
            var result := find_intersections(node, nodes, groups, key)
            nodes = result.nodes
            groups = result.groups
    for key in groups.keys():
        var outlines := []
        for node in groups[key]:
            outlines.append(get_outline(node))
        var combined = outlines[0]
        for outline in outlines.slice(1):
            combined = Geometry2D.merge_polygons(combined, outline)[0]
        _region.navpoly.add_outline(combined)
        _region.navpoly.make_polygons_from_outlines()
    for node in nodes:
        _region.navpoly.add_outline(get_outline(node))
        _region.navpoly.make_polygons_from_outlines()
  1. 1.

    We check the comparable node list to create the initial groups of intersecting nodes.

     
  2. 2.

    We follow this up by checking each intersecting group to make sure we’ve added all the nodes that overlap in the group. If we skipped this step, we could miss intersecting nodes due to the ordering of the initial comparable nodes array.

     
  3. 3.

    Once we have the final intersecting groups, we combine all their polygons into a single polygon per group.

     
  4. 4.

    These we add to the navpoly, along with a quick pass through all the non-intersecting polygons.

     

All this code combines to create a solution to the problem of overlapping outlines in a navpoly mesh. The resulting mesh means our player character will navigate around the obstacles:

A screenshot of the experiment window, which has an opened square shaped tile map with three sprite characters cow, skeleton, and chicken.

Combining polygons before adding them to the navpoly

This allows us to create obstacles dynamically and avoids the need to manually position NavigationRegion2D nodes. A handy trick, to be sure.

Summary

Navigation is one of those things that is easy to learn and difficult to master. Once you step outside of the simplest use case, things can and often do go awry.

Fortunately, we’ve come up with a solid solution to the problem of populating maps with obstacles. This will be super useful for the next game we make.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset