Welcome to the Wolfire Blog! This is where we keep everyone up to date on our progress on Overgrowth and other new stuff. Be sure to subscribe to get the latest news! Also, be sure to check out the forums for even more up to date news - or get on IRC for up to the second updates.

Pathfinding with Detour

Add Comment! By David Rosen on May 27th, 2010

A few days ago I posted that we've added automatic navigation meshes using Recast, and now I'd like to show some navigation paths using its companion library, Detour. These libraries come with some really nice-looking debug visualization utilities, so I thought I would show them off here. Here are a few quick pathfinding tests to see how Detour handles some common trouble spots:

Detour navigation paths

Those look pretty accurate to me! It may look like the corners are cut so closely that the character would bump into a wall, but this is not the case; the navigation meshes are already taking the character's collision radius into account. Now let's see how it handles longer paths:

Detour navigation paths

It seems to work well on paths of any length, but sometimes shows a slight preference for going through tile corners. The navigation mesh is divided into tiles so that Recast only has to voxellize a small part of the scene at a time, and the tile connections may be biasing the navigation heuristics a little -- this should be pretty quick to sort out.

The next step is to get some AI characters to run along these paths, and see how it goes. There is a lot of interesting work to do to combine pathfinding with actual combat strategy and teamwork, and these libraries will help us get to that a lot sooner.