Recast Navigation conversion to C#

Hi guys,

I've been working on a conversion of Mikko's recast navigation. I've started over from scratch at least 3 times with countless hours trying to debug small issues. Anyway, I finally have everything working up to the point of the detailed mesh generation and thought I'd stop by to show off.

I'm working on Creating the detour nav mesh from the detailed mesh still following Mikko code. It is up to date with his latest release in his google code site

Here are the first 5 images showing the creation of the height field, up to part of the compact field.
The next post will include the contours, poly mesh, and detail mesh.

UPDATE: Today I was able to finish the export/import of binary data and feed it into the Detour Crowd system and get AI movement across the small test world. I've created a small video to show how to work with the system.

And another one showing integration with the Photon Framework I've built.

For an overview of the work that goes into the creation of these nav meshes, go here: http://critterai.org/nmgen_study

 

Here are the other 5 steps







As I said, I am now in the process of creating the nav mesh and then converting detour over to C# so that you can use this with Unity Basic.

 

Pretty cool. I can see this being useful for server side code or anyone who doesn't have Unity Pro. Are you planning on selling this? Or is it something you are doing for yourself?

-Dane

 

I am really not sure yet. My original idea was to covert his code so that I could build a world in Unity, generate and export a nav mesh and use that navmesh in a server for MMO or FPS games. Unity NavMesh is only good for use in Unity and I wanted something that could be exported, loaded on a server, such as one running photon, and have AI that can pathfind a little more accurately than in other games.

I wasn't real sure there would be much of a market for this, but if there is I'd consider writing some editor scripts to make it easier to use than the current hard-coded way it is now.

 

Nice work. I've always been thinking about porting Recast/Detour to C#.
Keep us updated!

 

Yesterday I spent the entire day converting the last of the code, 3.3k lines in one day is not something I want to do ever again.

The code builds and runs without throwing an exception. I am now looking into debugging it, by placing start and end objects and attempting to calculate a path and then drawing the debug for it. Hopefully I'll have pictures of that up today.

 

Well it has been another couple days and I'm glad to say that I now have recast finding a path between 2 capsules as demonstrated in the image. The next steps are to start making editor plugins so the parameters can be modified and to allow easier recalculating of paths.

 

This is some really nice work man. Keep it up. I'll definitely keep watching this thread as your progress!

 

Beautiful! This is exactly what my project needs for similar reasons.

I'd gladly kick in $50 and would be happy to beta test

 

I've gone ahead and written down some things I want for my own setup based on how "difficult" it can be to work with the raw recast data. I have a friend helping me with the editor by doing initial editor work that I will modify later.

I am looking at creating a Recast Editor window which will layout the initial parameters for generating the nav mesh, like the right side of the recast demo. From there I am looking at creating an object that will contain the NavMesh data as recast likes it. A Unity Mesh per navmesh piece will be created that will also allow the modification of the area type and flags for Detour. I will also be creating the NavMesh Query as a config so that, hopefully, i can create any number of flags and areas as well as costs and feed those into Detour.

I also still need to create a seeker so that once the path is determined, it can follow the path mainly for debugging purposes.

I'll be posting updates as I tag these things as they are necessary even for me to work more fluidly with recast.

 

A Minor update. I've been extremely busy but I have been able to get a couple things up and running.

I have created an editor that has a list of tags to choose from in order to build the nav mesh. This will make it easier to integrate with the client and only use say a "Navigation Mesh" tag.




When you hit build, it creates an object RecastNavMesh which contains the Recast PolyMesh, DetailPolyMesh, and the NavMesh. The next step from here is to allow people to see each NavMeshNode as a mesh in the scene. As you have seen I already have the ability to query the NavMesh, but I still need to generate the smooth path. Beyond that I have a few ideas for off-mesh connections and Convex Areas that will allow the change of area flags and then set up the ability to change costs in the query.

At some point I will also be adding the ability to serialize this data so that it can be placed on a server for pathfinding.

 

If you find you get bogged down and cant complete everything you want, please consider bringing others into the project.
I'd be happy to knock a few bullet points off in return for being able to use this myself.

if you are going to serialize then Id request you either serialize the data in a language neutral format, or you make the serialization format pluggable. Myself, i use a Java based tech on the back end.

 

The holidays have certainly caught up with me. I'm still working finish up the couple pieces I have in progress to get a good base.

I was actually looking at using XML Serialization or something similar specifically for people who aren't using Photon/C# as their back end. The problem for Java on the back end, is that you would need to convert the nav mesh code from C# to Java to do the path finding. Thankfully it uses arrays rather than C# specific objects which keeps the actual amount of conversion to a minimum.

 

If I have mesh data, I can write my own pathfinding over it, thanks!
(I've actually already done that once for NWN Walk Meshes. They are a bit simpler, beign 2D, but it shouldn't be that much harder.)

 

I've made some more progress today. It isn't as clean as I would like but it is getting closer. Now you can build the nav mesh from the editor which creates an object, the RecastNavMesh. I have started an inspector for the navmesh which will initialize the nav mesh based on the data provided and then I've also added a button to show the geometry. It is still rough around the edges, for instance I haven't made it use the same RecastNavMesh object yet, but things are progressing again.

I am curious to ask those of you who want to use the export of the navmesh data, what format you might think to see when it is exported. I'll be working on that in the very near future, in and around my other projects.

 

Another bit of progress, this time in the bug tracking department. I converted the code to draw the smooth path and found a few bugs/typos in the code that I had to correct first. Now it appears to be working and I have provided a few screenshots.

First: not much going on here, i created an inspector GUI for the recastNavMesh so that you can generate the geometry. As before it doesn't reuse the same mesh, but it puts the nav mesh object as the parent so you can quickly delete it:



Second I have the debug values to show the smooth path and the Bounding Volumes that comprise each polygon to make sure that the actor is within the correct polygon. I did this because i was having an issue with the wrong polygon being selected when the actor was near the edge of 2 or more polygons.




Now that I know I'm getting the correct path and that I can get the smooth path, i can begin working on the editor some more to export the nav mesh. After that I'm looking forward to working on realtime updates for the Actor.

 

For those of you wondering about the speed of this system compared to Recast written in C/C++:

Code (csharp):

1. Original       | Conversion
2. 300-400ms      | 2500-3500ms  - Mesh Generation
3. ?ms            | 00:00:00.0320019 (stopwatch elapsed) - 17 node path find and smoothing

So the pathfinding is actually pretty quick - rougly 0.0140410 seconds are spent finding the smooth path, so if you don't need the smooth path it cuts the time roughly in half but should allow for a great number of AI to get a path to a location without causing much strain on the system. If it scaled linearly, you could potentially run 30 agents before it takes more than 1 second for all agents to get a path. Hopefully a behavior tree associated with the agents would limit the number of agents needing to calculate new paths very often. It's possible we could further refine how often to build a new path by first checking if they are still inside the same polygon as they move.

 

This is coming along nicely! The extra build time doesn't seem like a big issue and the speed of the pathfinding is really quick . I can't wait to see this stuff in action, keep up the great work! Very interesting project.

-Dane

 

Hey CJR!

Glad to see this coming along. And Im still serious about being willing to pay something for this as long as it comes with either source or documentation so I can grab the data for other uses!

 

Awesome!

Cool that you have managed to translate such a large part of it.
Does it handle tiled navmeshes as well?

I am currently diving into the recast c++ code again to translate the tiled navmesh logic for the A* Pathfinding Project. I have also translated a large part of recast to C#, but it is not that structured and a few things are missing.

PS: For performance, one thing I found very time consuming in my C# translation was large memory block copies, the solution to that I have found is to use the Buffer.BlockCopy method, it improved performance a lot http://msdn.microsoft.com/en-us/library/system.buffer.blockcopy.aspx

 

I have been sidetracked the last few weeks. I was working with the Unity Editor and Inspector to get some better options with integrating with Unity. I can output the data of the nav mesh at this point. It was more a matter of testing the mesh within unity without having to rebuild the data when the program loads. Let me see if i can get something a little further along on this.

I'd like to upload it to the Asset Store and it will come with full source and not some locked, obfuscated .dll.

I just looked through what I have and while I do not have the TileMesh sample code converted, it wouldn't take much to convert it as I already have all the rest of the code set up to build the tiles. At first it would be pretty crude as it would build everything all at once, then later it could have editor/inspector controls to handle only building certain tiles.

 

OK, after working on the export all day today, I was able to get an Export working. I have 2 buttons now, one to export the XML version using XMLSerializer and a second that uses the BinaryFormatter to produce a binary version. Reloading from either is fairly simple. I created a proxy object to hold just the NavMeshParams and saved the NavMeshBuilder pieces from each tile. This is all the data necessary to rebuild a NavMesh from scratch using the Init and AddTile functions in NavMesh.

The XML file is 441KB and the BinaryFormatter file is 80KB.

The function to recreate a NavMesh from this proxy object is roughly 10 lines not including the Deserialize and setup which is another 5 or so lines of code.

 

Updated the main Page as I now have Crowd working and I can send an actor across the map to an end point.

 

Looking forward to testing this out.
Keep up the good work.

Are you aware of http://www.critterai.org/cainav/home ?

 

CritterAI was the inspiration behind making a complete rewrite in C#. The reason I wanted a complete rewrite in C# is because I didn't want to be forced into upgrading to Unity3D Pro just to use a native plugin. Another reason is that now I can use it in my Server code without having to use a bunch of wrappers and trying to cast things to C/C++ objects, it just works.

 

Awesome. Makes sense.
Any idea when/if you will allow others to test it out?

 

So I made some more changes, and while there are still things I want to work on, its "good to go" for now. Some of the things I changed:

Actors no longer require a link to the NavMeshQuery - they look for an object that has one as a component.
NavMeshQuery now has a debug feature where you can take 2 objects and generate a path between them.
Cleaned up the folder structure so it all resides in RecastUnity folder and breaks down from there.
Created an Editor for the Actor so parameters can be configured.
Made sure the XML version works as well as the Binary version.

A few things I want to go further with:

OffMeshConnections do not work yet, the code is in the Recast section, but there is no correlation into the Unity Editor.
Tiled Mesh creation isn't converted yet as it is a sample in Recast.
Region definition isn't in yet, so everything comes up as ground, I want to add a way to handle multiple types like water, mud, sand, etc.
General ease of use fixes, such as maybe merging the NavMesh and NavMeshQuery objects into a single entity.

Again, this is designed to be a utility within Unity3D to export for Photon to use without needing a headless Unity3D "master client"

 

This sounds very promising, keep up the good work.

 

Awesome!
Nice to hear your progress

 

Good work! Keep it up!

 

As some of you know, I've been working on MMO Tutorials with Photon. Yesterday, I had a strong desire to work on some AI code again. A couple friends said I should show a demo of the Recast code working on a Photon Server for pathfinding. So yesterday and this morning I worked on a Simple Server and added only the barest of code necessary to add recast, send the position updates of a single actor to a unity3d client and allow the client to send a message to reset the position so it would follow the path again.

It all works pretty well. I've found a minor bug that I need to fix that doesn't remove all the geometry during one of the later phases, but I made a quick video to show the results. Not terribly impressive, as I don't have a real terrain in yet, but it does the job well enough.

 

I've been cleaning up the code so it flows better and fits more within Unity3d. Nothing really major recently as my attention has been on other things. I removed the original BinaryFormatter and switched to JSon.NET and so now you can use XML, JSon, and Binary JSon. I added in some debugging by allowing you to select 2 objects in the NavMeshQuery and it will draw a gizmo showing the path the starting object would take.

As an aside, I've been toying with the idea of converting Bullet Physics as well to provide a physics collision engine on the server but allow the geometry to be created in Unity. The idea still isn't finalized, but it is something I consider in order to build a collection of MMO Utilities and to turn Unity3d into an Editor for an MMO project.

 

Is there a version available for others to start working with yet?

 

I also had the idea of porting recast, but seems like you got to it before me.

I hope there will be a version out soon, without the fancy features. I like the networking and all, but what I really want to try out is the Recast mesh generation in the editor and the path-finding client. Debugging in Unity3d is a plus as well.

 

Its been a couple months since I last posted. My asset has been up on the store: https://www.assetstore.unity3d.com/#/content/7041

Yesterday I made some modifications to better support WebPlayer builds and today I looked into some optimizations. On my machine that I have been testing with, I've been able to get the NavMesh generation down from 2500-3500ms to 1000-1200ms for the nav_test mesh. While this is still around 4-5x slower than the C++ implementation, it is a significant improvement over the old system.

I am also partway through the process of making the tiled version available. Right now I am working on separating out the tiles. Then I will be working on the UI portion to allow regeneration of specific tiles. This along with the speed increased will allow for regeneration of large meshes for games that wish to deform terrain and regenerate nav mesh data.

I am likely going to push a patch up that includes the WebPlayer fixes as well as the Speed Optimizations.

 

Aweseom CJR, gonna go look for it now!

 

This seems like it could save a fair amount of work. If I understand correctly, all the source code is provided with purchase? Hopefully I haven't missed anything obvious, but what sort of license is this provided under? If this isn't mentioned on the Asset Store page, it might be a good idea to add that information.

It seems like this might also work for games that use procedurally generated content and/or randomized levels. Based on your understanding of the code, does this seem like a realistic expectation in your opinion?

 

DO you have any approx ETA for when tiling support will be added?

Thx

 

yunit - I'll get back to you on the license and get that added to the Asset Store.

Currently the code is built with the idea of the level data being static, due to the amount of time it takes to generate nav meshes for large levels. It could be done for procedurally generated content and randomized levels, but be aware that the generation time for large levels can be lengthy. For instance a unity3d plane which is 10x10 units, scaled 100x1x100 (so roughly 1k x 1k units in size) took about 5 minutes to generate a 13 x 13 tiled nav mesh.

Gaski - I have tiles working, I had to create a progress bar for the example above where i used a 1k x 1k unit flat plane so it didn't appear that the editor is just hung and doing nothing. I need to build an object to hold all of the tiles and then allow the export to occur on the list of tiles because right now you can export each tile individually which isn't very helpful/useful. I would like to say it'll be ready next week to give me time to clean up how it works currently and to make the NavMesh object which will hold each tile.

 

Here are some screenshots from where I was working with the tiled voxels as well as after I added the progress bar for tiling support.

 

Pushed up 1.0.6 to be reviewed on the Asset Store.

Changes include:
1.0.6 - Updated Recast Source Package
1.0.5 - Tile Support
Initial Tile support added.
Fixed an issue when rebuilding that cause the Mesh to no longer be toggled on/off
Initial creation of NavMesh adds the vertexMat material
Fixed the Editor window crashing when selecting a tag with no geometry data
Added a progress bar for tile generation for visual feedback when building a mesh
NavMesh exports all tiles.

 

So I just pushed 1.0.7 up to the Asset Store for review. In this version I've added in the support for off-mesh connections. Furthermore, there was a bug that made the NavMeshQuery completely unusable when crossing across tiles. With that fixed and off-mesh connections being supported, the tool is coming along nicely. I am in talks with the author of the conversion of Json.NET to help support those who want to work with iOS as there are issues with the original version. My next focus for 1.0.8 is temporary obstacles.

 

Hi,

I am in the process of making an RTS game and I am looking into different methods of implementing pathfinding. I was wondering if this system would suit an RTS?

Will it handle numerous agents trying to navigate to the same area well?
Can it dynamic obstacles like other units that may be blocking a certain route?

 

Sorry for the delay in getting back to you.

Currently there is no temporary obstacle support, it is something I am working on.

The Crowd system works and keeps entities from running into each other and is already in, so It will attempt to navigate around other objects that might be blocking a specific path. It isn't as robust as say, Supreme Commander's swarm code. Otherwise it should be great for an RTS.

Just know that this is a pathfinding system, you tell an actor to move to a destination and it moves there. You still have to write the AI behind it to tell what to target, attack, where to build, etc. I apologize if you already know this, but many people think it should do all those things, when in reality its purpose is to get from point a to point b. it is a small part of the overall AI that you write yourself.

 

CJR, Can I use your recast code without Unity in a C# server environment?

 

Yes, the conversion is done in straight C#, I just added some additional functionality in Unity to ease creation and I would suggest you look at how I handle setting up the mesh and building the nav data. The only thing I don't have is any way to visualize the nav mesh outside of Unity.

 

Nice work on this. Thank you for undertaking it! Is there an ETA on 1.0.8? We're trying to make a moving maze game and temporary obstacle capability is just what we're looking for.

Thanks again!

 

Hi,CJR.the navmesh exported is a .obj file??

 

Does the exported binary file compatible with the original C++ version?

 

Hi did you manage to work out how to include the area flags and changing costs? Do you have any tips on how to get this setup if you dont have any plans on updating the release?
Thanks in advance!