Recast 1.2

One of my larger projects currently are Recast and Detour. They are both open source projects aiming to solve some path finding related problems. Recast is automatic navigation mesh generation toolkit and Detour is a runtime component which can be used to do some spatial queries and pathfinding on navmeshes. Basically you can throw any triangles mesh Recast and it will generate a mesh from that data which allows the AI to navigate in that environment using Detour.

By releasing Recast and Detour open source, I hope that people who usually do not have access to such technology can fullfill their crazy ideas as well as I hope the code can live up to high standards of other game developers and they could adopt it to be used in their games.

I just recently released Recast 1.2. In this version the new feature is to be able to build navigation meshes in tiles. That is, large worlds which would not otherwise fit into memory can be processed in smaller chunks.

The tiles allow other kinds of interesting things too. First the Recast algorithm performs way better when it is run on smaller set of data. The bottleneck of the algorithm is large open areas. They will create inaccuracies and take a lot of performance. Secondly if the tile size is reasonable, the resulting mesh will follow the contours of the underlying geometry much better.

The really interesting stuff will follow in the next version, Recast and Detour 1.3. I plan to use the tiled data structure at runtime too. Currently the tiles are stiched together after all the processing is done.

The tiled structure allows us to do streaming. That is, the user is able to remove and add tiles he wishes. It does not matter where the tiles come from, it can be from disk or you can create the tiles on the fly too! Recast is fast enough to build a 20 by 20 meter tiles in about 25-50ms (assuming indoor shooter level). I have not idea how well this will work in practice, but I'm really eager to find out!

There are other things the tiled structure allows too, for example it would be used for hierarchical pathfinding (HPA*) and certain queries, like finding nearest polygons, can be made faster too.