#22 Pathfinding and Package Timers


Welcome to the twenty-second devlog!

As I’ve been creating levels for the game these past few weeks, there’s been only one consistent roadblock: setting good TIMERS on the packages.

If you give players too much time, there’s no challenge and you can just do whatever you want (instead of cooperating and optimizing your strategy).

If you give players too little time, there will only be frustration. Packages run out of time JUST before they deliver it. In many cases, deliveries might simply be IMPOSSIBLE within the given time frame.

After weeks of experimentation and iteration, I can finally say I have the answer! (Well … an answer that seems good enough for now. We’ll see how my technique fares in levels that are much larger and more complex.)

 

The steps of delivery

For any package, no matter the circumstances, the delivery has two steps:

  • A player has to walk to the starting location of the package.
  • A player needs to move the package from there to its destination

Every timer should be at least long enough that these two steps can be accomplished.

To make this work, I actually implemented a pathfinding system. When a new delivery is created, this system finds the absolute shortest route for delivering the package. This follows the same two basic steps:

  • Loop through all the players. Find the path between the player and the package. Then pick the player that is most nearby.
  • Then, find the path between the package and its destination.

Add these two together, and voila, there’s your shortest path.

The thin black line in the video below shows the path between starting location and destination. (Around 0:40 there's finally a package going to the blue zone. Oh, how the game's probabilities always annoy me when I try to create videos for the devlogs.)


 

Converting to time

However, we don’t necessarily want to know the path itself. We want to know how long it would take to traverse the path.

Luckily, players have a somewhat fixed walking speed. I can simply do some quick tests to get …

  • The average speed when the player is moving freely
  • The average speed when the player is holding/pushing a package

(Why can’t you just use the same values as the player code? Because the player interacts with the physics environment. Due to friction, bounciness, slopes, hitting other players, etc. the player speed is on average lower than its maximum value.)

Once I have these values, I can get the time with: PATH LENGTH / WALKING SPEED.

 

Arr, there be problems

(I’ve used this heading before, I know. I just think it’s really applicable to developing games: there’s this great idea, a well-implemented algorithm … and then there’s always issues that pop up.)

For pathfinding, I use the AStar class built into Godot.

  • I loop through the terrain, which is a GridMap.
  • I connect each tile with its neighbours.
  • (If something is within jumping height, I connect it as well.)
  • In the end, I get a graph of nodes (the tiles) with connections (tiles the player can move between).
  • I ask AStar to find me the shortest path, which it does, and I’m done.

But … levels are made up of more components than just the GridMap. There’s trampolines, catapults, elevators, buttons, the list goes on!

To make matters worse: these components are usually ESSENTIAL for moving to a certain part of the level. Without using that trampoline, you just can’t get to certain packages or destinations.

Pathfinding doesn’t understand these, of course. The computer doesn’t know what a trampoline can do and how it helps players get to something that would otherwise be too high.

 

Navigation Helpers

So I created a NavigationHelper class. This class basically creates an “artificial” connection, outside of the GridMap system. I can place these anywhere I want within the level.

It has the following properties:

  • Starting Point (a node in the AStar graph)
  • End Point (a node in the AStar graph)
  • Bidirectional (true or false)
  • Weight (a number)


For example, say we have a trampoline. If I want to tell the computer what that trampoline can do, I set the properties like this:

  • Starting point = the trampoline location
  • End point = a higher terrain, which you can reach by jumping on the trampoline
  • Bidirectional = true, because you can go up AND you can go down of course.
  • Weight = this is tricky, I’ll explain it below.

As long as the starting point and end point are within the graph, it will create the right connection, and suddenly the computer knows that this trampoline connects certain parts of the level.

The weight essentially determines how hard it is to use this trampoline. By default, connections have a weight of 1 => there are no obstacles, so it always takes the same amount of time to move from one node to the next.

But a trampoline might be more difficult. Maybe you need a few tries to get the right jump. Maybe the trampoline can be moved, and you need to wait for a player to move it into position.

By setting the weight to a higher value, I tell the computer to count some extra seconds for this element of the route.

This is just a guess, as it depends hugely on the players, their positions, their cooperation, etc. I usually just play the level a few times, and check how many seconds it takes for me to use something. If the trampoline takes twice as long as simply walking, then I set the weight to 2. If an elevator takes 5 seconds to reach the top, I set the weight to 5.

 

Walkable Floors

Besides the interactive objects, there are also static objects that are NOT part of the terrain/GridMap.

For example, in some of the levels there’s some scaffolding that sits on top of the terrain. In later levels, there might be buildings, stone walls you can walk on, etc.

As you might expect, I also need to tell the computer to view these objects as part of the level map.

To do so, I add a group to all these objects, which is called “WalkableFloors”. At the start of the level, my navigation script finds all these objects, and adds them to the graph as if they were part of the GridMap.

 

Obstacles

In a similar vein, not all cells in a terrain should be connected. If there’s a fence somewhere, I don’t want to allow a connection between the cells on either side.

As such, every obstacle is put into a group “BlockableObjects”. At the start of the level, the algorithm loops through all these objects, and finds the cells on either side. Then it adds these cells to a list of “forbidden connections”. This is the actual code for that part. (Yes yes yes, it could be shorter and more optimized and all. I just wanted to show some actual code, instead of only talking about things at a high level.)

    for obj in get_tree().get_nodes_in_group("BlockableFences"):
        var t = obj.global_transform.origin
        
        var my_cell = gridmap.world_to_map(t)
        var my_cell_vector = gridmap.map_to_world(my_cell.x, my_cell.y, my_cell.z)
        var neighbour_to_forbid = Vector3.ZERO
        var margin = 0.5 # used to bypass imprecisions in fence placement
        
        # if the fence is on the LEFT side
        if t.x < my_cell_vector.x-margin:
            neighbour_to_forbid = Vector3(-1, 0, 0)
        
        # else if the fence is on the RIGHT side
        elif t.x > my_cell_vector.x+margin:
            neighbour_to_forbid = Vector3(1, 0, 0)
        
        # else if the fence is on the BACK side
        elif t.z < my_cell_vector.z-margin:
            neighbour_to_forbid = Vector3(0, 0, -1)
        
        # else if the fence is on the FRONT side
        elif t.z > my_cell_vector.z+margin:
            neighbour_to_forbid = Vector3(0, 0, 1)
        
        # if there IS a fence that should forbid something
        if neighbour_to_forbid != Vector3.ZERO:
            # make this connection forbidden
            # (by adding it to the list)
            forbidden_connections.append([my_cell, my_cell+neighbour_to_forbid])

A bit later in the code, at the place where it establishes all connections, it just checks if the connection that’s currently being considered is in the list or not.


 

 

Helping players

There’s this quote in the land of game dev:

“Don’t punish players for making mistakes, reward them for doing things right”

It’s just very frustrating to see packages disappear just before you can deliver them. It’s very overwhelming if you have three packages and they are ALL running out of time.

As such, I want to be lenient. Once I’ve calculated the absolute shortest route, I add a buffer to it. Currently, the buffer is 10 seconds, which seems to be a good balance. But I can change this buffer dynamically, if needed, so that’s no problem.

Additionally, there’s the overtime mechanic which will probably be introduced around level 3 or 4.

Overtime = “Whenever a package runs out of time, there’s a 50% chance it goes into overtime. You get another 10-20 seconds to deliver the package, a second chance”

During my tests, I’ve found this to be a very nice mechanic. It adds tension when a timer runs out … and excitement when you’re lucky and it goes into overtime! It’s something players were really happy with, even if it made some deliveries much easier in retrospect.

And lastly, there’s the difficulty mechanic, which will probably be introduced around level 8 or something.  Packages have a difficulty rating, which is set manually. If a package is more difficult, it gets more time (timer is multiplied by difficulty factor), but also yields a greater reward (reward is also multiplied by the difficulty factor).

I haven’t been able to test this mechanic in-depth yet, but I expect it to work quite nicely, and give players a reason to try the harder deliveries in a level.

 

Conclusion

There are certain disadvantages to the whole system I outlined in this article:

  • All elements (interactive, walkable floors, …) need to fit into the GridMap system. If any of these objects has the wrong scale, or a wrong origin position, there’s a good chance that the calculations will fail. It might think a floor is at position (0,0,1), while it’s actually at (0,0,2), and that small change can cause the pathfinding to fail completely.
  • For each level, there are a few things I need to set manually. (The NavigationHelpers, for example.)
  • It calculates routes during the game, which means they can’t get too large, otherwise the game will freeze for a small moment whenever a new delivery is created.
  • Guessing the “weight” of these interactive objects can be tough. In some rare cases, it will be wildly inaccurate, and there’s not much I can do about that. (If a trampoline just happens to be in the correct position already, players will be able to use it much quicker, which means the corresponding delivery gets slightly easier to complete.)

But in my opinion, the advantages are much more important:

  • I don’t need to set distances between zones, or timers for deliveries, manually. At all. This makes level creation very efficient and very flexible.
  • It adapts to a changing play state and keeps it challenging at all times.
    • For example, in one of my playtests the players would just stay near one of the package machines. They were like “screw the blue packages, we’re only doing the red ones”. But because the navigation calculates the timer based on the closest player, the timers for the red packages became VERY short, and for the blue packages they became longer. This forced the players to keep moving around! Suddenly the blue packages seemed very easy and inviting, while the red ones didn’t allow any mistakes.
  • If I want, it can even become dynamic.
    • For example, maybe I create a level where, when you cross the minute mark, a bridge suddenly collapses! This would change the routes between zones significantly. Using this system, it will automatically adapt the timers once I’ve removed the bridge from the graph.

 

Well well well, this was a very long and abstract devlog. But I really wanted to write it, as this solved one of the main issues I was having with the game. Now that timers work flawlessly, playing a level already starts to feel like it should in the final product.

Next time there will be some more videos and pictures again, I promise!

Get Package Party

Download NowName your own price

Leave a comment

Log in with itch.io to leave a comment.