DevLog #15 – How to find the right path

Hello everyone!

After last week’s post on weather events, it’s time for another devlog! Let’s get back to our more technical series on level generation and talk about pathfinding.

Where should we go?

In project “Stasis”, the main gameplay loop consists of fighting against enemies. That’s why we need AI. We will probably make a more detailed post in the future to present how we implement enemy behaviors and attack patterns. For today, we consider the simple following problem: we have a monster somewhere and we want to move it towards the player.

To do that, we use Godot built-in A* class. As the documentation tells:

A* (A star) is a computer algorithm that is widely used in pathfinding and graph traversal, the process of plotting short paths among vertices (points), passing through a given set of edges (segments). It enjoys widespread use due to its performance and accuracy. Godot’s A* implementation uses points in three-dimensional space and Euclidean distances by default.

Godot AStar documentation

We use the built-in class to avoid wasting time doing it ourselves and because we trust them to have an efficient and reliable implementation. Let’s see how we set everything up.

Back to datamaps again. But also collision maps.

First, we have to remember how we generate levels. As we explained in this devlog, we create all environments from a datamap and a collision map. The datamap contains information about the textures to use, but also the height of every existing tile. The collision map is a dictionary where we keep track of tiles where we spawned objects like trees, monoliths, or doors. By default, we consider all tiles to be free, unless the collision map tells otherwise. If the collision map contains a tile, then we have two possible values:

• Obstructed. There is an object on the tile. Enemies should not try to move on it.
• Spacing. There is an object nearby. We recorded this value to avoid spawning objects too close to one another. However, this does not impact pathfinding, there is no issue with enemies moving on this tile.

At level creation, we forward the datamap and collision map to the scene in export fields, so that they get saved for later. When we do load the scene, we execute some code in the _ready() function to configure the A* algorithm.

Configuring Godot A*

First, we create a new object: astar = AStar.new().

Secondly, we loop over all existing tiles in our datamap and add them with astar.add_point(id, Vector3(i + 0.5, height, j + 0.5)). We add only tiles that are not obstructed, so we check the collision map before doing so.

The id is an integer we compute with a bijection from N² to N. This means every pair of coordinates maps to a single integer, and conversely every integer maps to a single pair of coordinates. If you search the internet, you will probably find formulas for such a bijection. In practice, we use another approach. We don’t need all N² because our room size never exceeds 100. So we simply use the following map: id = i * 100 + j. Similarly to matrix coordinates if you were implementing them with a single array. Our goal is to have a quick function to compute the corresponding id of any coordinates within this 100×100 matrix. We also register the position of the point : Vector3(i + 0.5, height, j + 0.5)). We add 0.5 to i and j to get the center of the tile. The height is the value contained in the datamap.

Thirdly, we add the connections with astar.connect_points(id1, id2, false). For every existing tile, we compute their id (id1) and look at their four neighbors: top, bottom, left and right. If the neighbor id (id2) exists in the A* data (astar.has_point(id2)), then we have to compare the heights. That’s why the third parameter is at false: connections are not bidirectional. Enemies can fall from any height, but we configured them to jump only 1 or 2 tiles. If the height difference implies to move up 3 tiles or more, we don’t add the connection, this is a forbidden move.

Using Godot A*

That’s it! Now, we can use the A* data in the enemy AI code to retrieve a path: path = astar.get_point_path(self_id, player_id). The result is empty if no path exists, and an array of points otherwise. We then setup the enemy velocity to move towards the third point of the path (we consider the first two points are too close to the entity and will cause messy movement). We however do have to care about two things here:

• Don’t forget to multiply y and z values by sqrt(2) because of the our configuration for pixel perfect rendering. The values we registered in the A* data were raw unscaled coordinates.
• If the enemy is moving towards a higher tile, we have to trigger a jump. Otherwise it will get stuck.

Closing tips

We presented the main points about how we use Goot A* pathfinding in our game. Let’s close this devlog with some tips and adjustments we made:

• In the astar.add_point method, there is a third optional parameter to specify the weight of the point. Initially, we added all points with the same weight but changed that later. Now, we give a higher weight to tiles on the edges. Unless it has no other choice, the A* algorithm thus tend to avoid these tiles. We like to have enemies stay away from the edges before they will wall into the void by accident less often. Also, it becomes a little harder for the player to push them into the void. Since we have a special bullet type with increased knockback, this is more interesting this way (more on bullet types here, although the knockback bullets are not mentioned there, this is brand-new information!).
• At first, when enemies were moving towards the player, we were computing a path at every physics frame. With multiples enemies and long paths, we noticed an impact on the frame rate. Now, we use the previous path and refresh the computation every 0.2 second. This means 12x less computation compared to a constant 60 fps. This is more than enough for enemies to react quickly to the player changing position, while getting improved performance.
• To compute a path, we first have to get the id of the corresponding tile. However, world positions are floating numbers. And we also have this sqrt(2) scale on two axes. The computation is thus not that accurate. In the middle of the land, it doesn’t matter. However, when entities are near edges, it can lead to situations where we don’t find an id although we should. That’s why we are a bit loose on the id computation. In practice, we look at all the neighboring tiles, and select the existing one with a height closest to the true entity altitude value.
• Debugging pathfinding can be very cumbersome. We have a flag to enable debug visuals. When activated, we spawn red transparent meshes at all coordinates returned by a path computation (and we delete them at the next one). As you can see on the sceenshot below, it helps to see what is going on.

The end of this devlog

Thanks for reading this far, we hope you liked this post. As always, feel free to ask questions in the comments! See you next time!