Preparing this year’s version of my Introduction to the Unreal Development Kit, I got reminded of Epic having integrated Recast in February this year: Recast is an open-source library for automatic generation of navigation meshes. Although nav mesh generation has been part of the UDK for almost two years now, Epic finally decided to switch to Recast, gaining an almost ten times performance boost.
I highly recommend reading the corresponding CritterAI article in case you’re interested in that topic: Stephen Pratt explains the whole generation process from heightfield generation to region generation to contour generation to convex polygon generation. Many detailed explanations and elaborate illustrations make this article really worth reading. What are you waiting for?