Open Release
pathengine-formations

Inside PathEngine’s Collapsible Formations (Exclusive Video) and Latest Release

Alex J. Champandard on May 29, 2009

The game AI & navigation middleware industry is moving very fast these days; even we're struggling to keep up! Today, PathEngine released its latest SDK and here at AiGameDev.com we've been sinking our teeth into it to check out the latest developments. In this article, you'll find a behind the scenes description of what's inside the release and how the features are implemented. On top of that, you can find the demo binary and the source code for samples within the "testbed" release available from their download page.

The key features of this release, discussed in this page, are the collapsible formations (including a video), support for both automatically generating navigation meshes based on BSP-geometry processing or voxelization (with a comparison), and finally support for run-time off mesh connections to allow agents to jump between arbitrary points in the world.

NOTE: Thanks to Thomas Young for giving us access to a pre-release build of the latest SDK, and for letting us post some exclusive details about the technology. PathEngine is a sponsor of AiGameDev.com.

Collapsible Formations

This release of PathEngine comes with an advanced sample that shows how formations can be handled. This behavior is not built into the library at the low-level so you can change the way the formations behave via game code. As it is now, each sub-formation always collapses to go through narrow gaps and doesn't considers taking detours to gain some more clearance. As Thomas Young points out, in some situations this would look more natural.

A recording of the demo is available as a video just below. (Click here to view it.) You can also find the majority of the source code for this sample (excluding the library code) in the testbed release available on the PathEngine site.

Audio & Video Screencast



NOTE: The video above is in 720p High Definition. Click on maximize to watch it full screen.

Technical Details

The default behavior in this demo is designed to have a very low update cost per individual agent, a minimal number of long distance pathfinding requests, using pathfinding based on the size of a single agent, and allowing the group to adapt to obstructions. Here's how it works in practice:

  1. A path is planned according to the size of the maximum size of an individual unit in the formation, rather than the formation size.

  2. The corridor around the path is used to calculate the ideal formation width, and positions available.

  3. Sub-formations are created based on the distance between entities, so occasionally groups split up to move around obstacles.

  4. Only one long distance pathfinding request is used per sub-formation, which reduces the cost of searching for paths.

  5. While following the path, there's a piece of code responsible for organising movement orders within sub-formations using local queries only.

Thomas Young points out another few interesting details about this demo:

“Local, short distance pathfinding requests are currently used to move to start positions, but in most cases these are not actually required, and will early out on a line collision test direct to goal.

This is a good example, I guess, of the extreme usefulness of a paired pathfinding/collision setup, and it should be straightforward to apply this kind of approach to any situation where paired collision and pathfinding queries are available! ”

Voxel & BSP Processing

Voxel-based approaches to processing polygon soup have been gaining traction lately. However, compared to solutions based on processing polygonal geometry, the decision of which to use is not so clearcut. PathEngine's latest release includes both, so I took a few comparison screenshots to visualize the differences in practice.

In the followings images, you'll see the following from left to right:

  • Blue — The original input geometry with polygon outlines.

  • Grey — Walkable surface extracted with voxel processing.

  • Green — Same walkable area extracted using BSP processing.

Here are the screenshots. (Click to enlarge.)

Screenshot 1: A fence example, showing the aliasing introduced by voxel solutions compared to perfect geometric processing.

Screenshot 2: Example scene with few differences. The voxel floor on the bridge is not as accurate.

I asked Thomas Young (developer of PathEngine) about the distinction between the two. Generally speaking, where do polygon-based approaches shine over voxel based approaches, and how would you decide which to use? Here's what he replied:

“The main point here is that BSP 3D processing has no aliasing. With voxel based approaches, if you have something like a doorway, the actual mesh width at this doorway can vary by a factor on the order of the voxel size being used, and so this is then something that needs to be taken into account if you want to guarantee passability for pathfinding agents — either by reducing the agent shape used for pathfinding, or by modelling all your doorways a certain amount larger than the actual physical agent size!

And then, apart from issues at obstruction boundaries, the BSP 3D processing also provides a much more exact ground representation. Being able to quickly get hold of Z values for agent rendering position is nice, but is something that can potentially be handled by other engine components if required. More importantly, perhaps, is the ability to convert things like content position markers to pathfinding configuration space, absolutely robustly. when you have large numbers of positions to work with, and don't want these to sometimes be assigned to the wrong piece of pathfinding ground then the quality of ground representation can become an important issue.

(Remember that with PathEngine we don't search directly through the ground meshes polys, so while representing ground mesh surfaces more exactly does mean larger ground mesh size, this does not then directly affect pathfinding performance.)

On the other hand, the extra precision comes at a cost, and having really fast processing times, without needing to do stuff like simplifying geometry or marking stuff up as solid objects, can just be that much more convenient. The great thing is that both content processing methods operate on exactly the same source data representation, and spit out exactly the same run-time mesh format, and so it is possible to switch between approaches without making any changes either to the input content data, or to run-time pathfinding code.”

If you have a commercial project, you can request an evaluation for the content processing system on their site by filling in a simple form.

Runtime Off-Mesh Connections

In practice, games with complex navigation will often need runtime changes to the underlying navigation graph. For instance, jumping down from or onto a moving platform can only be done when the platform is accessible from the nearby ledge.

PathEngine already supports these kinds of free form connections, but they were extended for this release:

“This feature is based on essentially the same idea as the off-mesh connections in previous releases, but with the difference that connections can now be completely specified at run-time if desired.”

In practice, this was achieved with three new API functions in the iCollisionContext. For more information see these following articles:

Summary

If you're interested in these demos and the sample code, you can download and access the SDK in the public testbed release available from the PathEngine download page. This also gives you access to most of the collapsible formations source, as well as a binary for you to experiment with.

Congratulations to the PathEngine team on this latest release!

Discussion 0 Comments

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!