Meshes of navigation

Update 8/23/2011: the source/executable for the navigation mesh .obj exporter is here. Import a mesh, set up the parameters (only simple mode is supported right now), and have it generate the mesh. It should output a .obj file in the directory where it was executed.

The AI system has finally received a massive and desperately needed update: support for navigation meshes. That means the bots shouldn’t get stuck running into walls all the time, or running back and forth between waypoints like machines. I think this was probably the biggest weakness of the game up until now; the AI is still something of a problem, but it’s much better.

I stumbled across an incredible open source project called Recast, which is an extremely reliable automatic navigation mesh generator. It rasterizes your polygon soup into a giant voxel, finds the edges, discards non-traversable nodes (based on customizable parameters), and simplifies the resulting geometry. Try the demo, it’s amazing.

Since it’s open source, I was able to modify the Recast demo to export a .obj file containing the generated navigation mesh, which is then imported into Blender, and then exported to Panda3D’s .egg model format, from which I can extract vertex data in the game. I may write some utilities to simplify this process, but for now it does just fine, and beats the heck out of creating the nav meshes manually. I’ll probably release the modified Recast demo too, since it was a bit of a pain to get working.

Anyway, here’s a visualization of the whole process, from generation in Recast, to converting and simplification in Blender, to practical application in the game. The last screenshot shows a visualization of the pathfinding data in-game. I’ll cover the details of the pathfinding implementation later, but right now I need to sleep.


Christ follower and indie game developer. Running, music, programming, games, art.

Posted in A3P, Coding
9 comments on “Meshes of navigation
  1. jacob schieck says:

    hey you wouldn’t still have your source for the obj exporter for the recast demo would you? i’m trying to do the same thing

  2. et1337 says:

    Yeah, I do. Here it is:

    Basically just import a mesh, set up the correct parameters (simple method only is supported at the moment), and have it generate the navigation mesh. It will output a .obj file in the folder where it was executed.

    Let me know if you have any issues or questions.

  3. Christoffer Schedin says:

    Hey! The recast obj-exporter is exactly what i’m trying to accomplish, but the link seems to be broken.
    I’ve tried writing my own, but it seems like some edges are shared by more than two triangles, which leads me to believe that somewhere 0-area triangles are finding its way into my exported mesh.
    Your link seems to be broken, could you please upload it again, so I can have a look at your code?

  4. Christoffer Schedin says:

    Thank you very much! You’ve been a great help :)

  5. aralox says:

    Thank you so much for this! <3


  6. Sterling101 says:

    You my friend have just saved me about 5 days work – I don’t know if I can thank you enough!!
    I was either going to have to build my navmesh by hand which for an entire town would have taken ages or sat and pulled recast apart to do the same as you’ve done.
    Thank google your blog is still alive and kicking!!

    • et1337 says:

      Glad I could help! If you’d like, you can thank me by following/liking/sharing/tweeting/favoriting/whatever my blog. :)

  7. nixt says:

    Thanks for this!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Evan Todd. Christ follower and indie game developer. Running, music, programming, games, art.