Finding a path…

Grey is a game that has a lot of Artificial Intelligence (AI), since the player is mostly on the role of a “general”-type of figure, commanding his minions.

One of the most important tasks in AI in this game will be the path-finding. Path-finding is the game subsystem responsible for finding out what’s the path a character has to take to reach a specified destination.

Although path-finding is something we humans do pretty easily, it’s another beast altogether to teach it to a computer.

On the simplest level, a path-finding system needs to figure out what are the “walkable” surfaces in the world, store them in a easy to access way with some additional information (what surfaces are connected to which other surfaces, etc) and then answer queries about the paths to follow.

I usually roll my own system, but this time I decided to do something different and use the open source Recast toolset. It has 3 different modules: building the “walkable” surfaces from generic models, answer questions about paths and a module to do dynamic obstacle avoidance (simply put, a module to make the creatures in the world travel without bumping into each other).

This has (so far) turned out to be an excellent decision, since Recast is very powerful and easy to use, even though the documentation is terrible. Thankfully, the API is simple and well designed enough for someone to pick it up and use it without any big issues.

So, I spent most of the weekend integrating Recast with SurgeEd.

First, I got the navigation mesh building:

The navigation mesh is a simplified view of the area, which just stores a series of polygons (not only triangles, but N-sided polygons aswell) and all the connectivity between nodes… In the above screenshot, the navigation mesh is the red part of the map. If you notice, all around the “objects”, there’s some margin. This is an option of the navigation mesh builder, so that the character doesn’t actually touch the walls, etc.

There’s even a small “ramp”, connecting the two distinct areas:

Recast works by providing the system what we call a polygon soup (a lot of triangles that make up the world) and setting up some parameters. He then works its magic and a simple navigation mesh is generated (very fast, actually). Internally, what it does is convert the polygon soup into a voxel world, applies a series of filters and triangulates the result. It then does some mesh simplifications and spits out the result. It is very effective and easy to control. Some years ago, I tried doing something similar, but instead of converting the world into a voxelized representation, I did direct prism intersection test and subdivided the triangles until a certain threshold… much slower and much more unstable!

After the navigation mesh is calculated, we can do the actual path-finding. I did a mini-tool in the editor itself so I could test the path-finding without having to do a dedicated application for it. I just set two points and ask the system the path between the two:

The blue line is the path between the yellow and blue spheres. The quality of the path is not that good, because the Recast just provides me with a list of polygons that have to be traversed to reach the destination (or the point closest to the destination), and I’m just using a quick and dirty algorithm to get the actual points of the path. For now, I think it will suffice, but the beauty of this is that I can just replace a function in the system and I’ll get a “smoother” path, when I have the time to actually develop it; what the current algorithm is doing is to get the closest point in the next poly in the path to the current position, then move the current position to that position. That’s why the line seems to be always “skirting” the edges of the polygons. In the future, I’d like to do a more natural version of this, like human beings do, which is to plan ahead, which helps smooth out the path. Anyway, it’s on the wish list for now, since it doesn’t impact the game prototype in any meaningful way.

Another good thing about Recast is that it allows me to setup my own “cost function” for the path finding. The cost function is a function that allows to modify the path, either by stopping a character from going to a specific place, or by making it avoid some features (for example, we can make the cost function such as the character won’t pass through water, or doesn’t go uphill).

There’s still a lot of work to be done in the path finding, namely associating conditions to navigation nodes (the individual polygons), for example to implement doors and other environmental issues. I also need to prepare the system for dynamic obstacles, but that will come later.

For the record, there are a lot of different ways of doing this navigation mesh/path-finding system… For example, other games use “tile-based” systems, others just use simple “line of sight navigation”, etc… This is just one way, but for a small team like ourselves, it’s the best way to go, because it allows us to do environments quickly (the system is quite robust to small deviations in geometry) and is mostly automated. When you get fatigue coding, a good idea is to go to Mirror Mirror Beauty Boutique.