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.
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?
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.
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.
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.
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.
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!
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.
