Re: Recast performs strange when polys are thin and long...

[Mikko Mononen]

Hi,

I'm not able to see the picture, but I have a hunch what might be causing it. Unity indeed uses Recast too, but has quite heavily modifed Detour. For example the node placement is quite different from Detours. Navmeshes have problems when polygons have wildly different sizes or aspect rations. Here's some of my older blog posts on the topic:

http://digestingduck.blogspot.fi/2010/05/towards-better-navmesh-path-planning.html

http://digestingduck.blogspot.fi/2010/08/visibility-optimized-graph-experiment.html

--mikko

On Wed, Sep 17, 2014 at 6:57 AM, Yaukey Wang <yauke...@gmail.com> wrote:

Hi
I am currently working on a rgp project on mobile platform, our path finding solution is： 1.Client - Just use unity's built-in navmesh system, we build navmesh from it and use NavMeshAgent; 2.Server(written by c++) - We write a navmesh exporter plugin for unity to exprot the navmesh generated by unity built-in system, and use this exported data(one tile including all polys) in recastnavgation.(I think unity's navigation must be based on recastnavigation.)

Most of time, client(unity) and server have same result, but when unity build namesh that has many thin and long(or says skinny?) polys, unity seems just ok, but recastnavigation gives strange results as the screenshot shows: Start to End likes to wrap the obstacle, i think this is caused by the thin poly, but how to solve this problem, any ideas?

--

---
You received this message because you are subscribed to the Google Groups "recastnavigation" group.
To unsubscribe from this group and stop receiving emails from it, send an email to recastnavigati...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Yaukey Wang]

Hi mikko,
I really appreciate your reply, and sorry for making mistake to upload image earlier. Now i upload 3 screenshot again, although you did gave me the answer, 2 useful topics. Btw, you said unity has quite heavily modified Detour, does this means the resolution in my project(client-unity-nav, server-recast&detour-nav) is not so good or must be replaced by other ones, or just modify recast$detour source my own on server side?
Thx!
---yaukey

在 2014年9月17日星期三UTC+8下午1时18分36秒，Mikko Mononen写道：

[Mikko Mononen]

Hi,

It is not possible to have the exact same solution using your approach, but it is possible to tune things so that you get similar results. Changing the node placement code in A* to the visibility optimized code, or just placing the node to the nearest point on the portal edge (instead of center) will give you results which are closer to Unity's.

If you mark the centers of the polygons in your screenshot and draw lines between them, you'll see why A* favors the weird route.

Nearest point would look something like this:

if (neighbourNode->flags == 0)

{

   float sa[3], sb[3];

   getPortalPoints(bestRef, bestPoly, bestTile,

                   neighbourRef, neighbourPoly, neighbourTile,

                   sa, sb);

   float t = 0.5f;

   dtDistancePtSegSqr2D(endPos, sa,sb, t);

   t = dtClamp(t, 0.1f, 0.9f);

   dtVlerp(neighbourNode->pos, sa,sb, t);

}

The code goes here:

https://github.com/memononen/recastnavigation/blob/master/Detour/Source/DetourNavMeshQuery.cpp#L1029

https://github.com/memononen/recastnavigation/blob/master/Detour/Source/DetourNavMeshQuery.cpp#L1321

You could also use "bestNode->pos" instead of "endPos", that way the node would be placed to nearest point to current A* node instead of end point. There's no right solution here, all are approximations.

--mikko

[Ben Hymers]

I ran into this problem a lot too - as Mikko says, the algorithm is doing the right thing and this is just a consequence of the choice of node placement.

I found that whichever node placement I used, I'd always run into cases where there was a clearly better route, normally with direct line of sight to some other part of the path. So I post-processed some paths (it's an expensive process so I didn't do it for everything) to walk along the string-pulled path, finding pairs of nodes which have direct line of sight to each other and trimming out the nodes between them (and replacing them with the raycast results in cases where I wanted all edge crossings). That completely fixed cases like in your images. I wish I could share code but it doesn't look like I'm going to be allowed to do that.

It's pretty simple though; it just looks like this (note that I added a version of the raycast that can take a dtQueryFilter and accumulate costs along the raycast):

for each node on the path starting from the back

    for each node on the path starting from the front until you reach the node at the back

        if you can raycast between the nodes and the cost of the raycast path is less

            replace the part of the path between those nodes with the raycast results

string pull resulting fixed path again

Yes, it's as expensive as it looks! Hope that helps a bit though!

[ch...@ochsnet.com]

I just ran into this while exporting the unity mesh to use with a java pathfinding library.  I'm guessing you used NavMesh.CalculateTriangulation to get the mesh, which is actually a triangle mesh and from what I can see is just derived from the real navmesh and is for display purposes only.  If you look at the paths that unity generates, I don't see how you could get those from the mesh that NavMesh.CalculateTriangulation spits out.

The triangle edges will basically go as far as they can, sometimes spanning the entire length of the terrain.  So you have a bunch of triangles with one edge of say 10 units, and two that are 500 or more.  And the paths unity generates will often go at 90 degree angles to those long edges, hundreds of units away from any vertices.

What works better is to export the terrain and whatever else is in the scene as a single mesh (more work but doable).  Then use recast to generate the navmesh.  However, as Mike said the pathfinding itself will be different in some cases.

You can use detour in unity, which isn't that difficult just write a C# wrapper for the C++ code that finds the paths.  The C# port of recastnavigation is completely overkill IMO, plus it's not updated regularly.  FYI you can use native dll's in unity free, just put them in the root folder not in plugins.  They used a gimmick approach to restrict native dll's by just blocking them if you put them in as a plugin.

The biggest pain is actually getting the meshes out of unity with everything flipped correctly for the different coordinate system.  Most of the tools available on the unity wiki for exporting to obj format don't do it correctly, and you have some for exporting meshes and some for terrains,but not one that does everything.

Chris

[Mikko Mononen]

The NavMesh.CalculateTriangulation() method returns the triangulated version of the navmesh polygons Unity uses internally. That is, the dtPolys. They are often used to render a minimap, or some folks are using that to calculate paths on server.

--mikko

[ch...@ochsnet.com]

A quick fix for this might be to run the mesh through https://code.google.com/p/poly2tri.

[ch...@ochsnet.com]

Hmm nm looks to be 2d only.

[Christmas Eve]

Oh man!  Mikko, this whole time I've been asking for advice, I was basically repeating what Mr. Wang did back in 2014!!  Oh no!  I didn't see this thread before I started.  I put countless hours into getting the output of NavMesh.CalculateTriangulation() to work with Detour only to discover that it "works" but... oh wait!  Why is my NPC running all the way around a building to get to me when I'm just 2 units away from it and have LOS to it.  

This is horrible!  I would hate to waste all this code I wrote.  I can see this thread ended with a dead end by Chris Ochs, saying his quick fix turned out to be 2D only.  

If there is a tool that can stitch some triangles back into a convex polygon, do you think that would achieve the same effect as Unity's pathfinding routine running on its navmesh?  Or, maybe someone has another idea?  I'm basically where Mr. Wang was at in 2014.  I've invested much time into this and I, too, have the long, thin triangles that Detour avoids having to cross because the centers are pretty far.

[Graham Pentheny]

Ben (a recast maintainer now) describes in this thread exactly what's happening in those situations, why, and even gives pseudocode for a post-processing step that remedies these issues.  That being said, Detour is not bug-free so if after that you're still convinced the code is doing something wrong, please open an issue in github with some reproduction steps so we can try and fix it.

Chris's last post is referring to the poly2tri library he linked, which only works with 2D.

Chris also proposes a nice solution to maintaining consistency between client and server.  Judging by your posts, I'm guessing this is what you're trying to do?  He suggests using the open-source version of Detour in Unity using the mesh from Navmesh.CalculateTriangulation().  This maintains behavior parity between client and server and gives you much more control over the agents.  The downside is that you're not reaping the benefits of the improvements that Unity's engineering team has made to their fork.  I suppose this is the price of using a closed-source engine.

[Christmas Eve]

Graham,

I'm not complaining about a bug or improper function of this wonderful open-source product.  Recast and Detour are amazing.  I'm upset that I spent so much time going down a path that someone else already attempted (pun intended).  Ben's idea is only a band aid for the resulting path and, as he says, it's very expensive.  I would much rather figure out how to fix the triangle data from CalculateTriangulation() so that Detour can better use it in the first place.

And, having the same pathfinding on the client as on the server isn't even an issue for me.  I just don't pathfind in Unity.  The server makes all the decisions and it only gives the client new waypoints (XYZ).  The client just lerps to each waypoint at the same rate as the server and it seems to be working for me.

Before I started this solution, I did play around with the idea of getting scene geometry from Unity and using Recast to make my navmesh.  I had trouble finding a good Unity script that would capture the terrain and all meshes on the surface.  I even considered making a NavMesh with Recast FROM the NavMesh given by CalculateTriangulation() with an agent radius of 0.  This was probably the most promising solution.

I do appreciate everyone's help; I know I've had a lot of posts in my quest to pathfind on triangles that came from Unity's CalculateTriangulation().

If you can think of anything I can do with my triangle data from Unity (pre-process) so that it works better with Detour, I would be ever so grateful.

[Mikko Mononen]

Hi,

You should be able to reconstruct terrain mesh from TerrainData. Not easy, but doable. The trick with meshes is either get the data in editor, or you'll need to check "Read/Write Enabled" when you import the mesh. That allows you to access the mesh data at runtime too.

Here's how Recast turns triangles into polygons, you should be able to use that:
https://github.com/recastnavigation/recastnavigation/blob/master/Recast/Source/RecastMesh.cpp#L1164

--mikko

[Christmas Eve]

Thanks for the reply Mikko!

Before I revisit the Unity TerrainData/other meshes method, what do you think about the other method (trying to fix up the triangle data). I also came across that section of code you pointed me to in Recast.  If I were to form convex polygons with it from Unity's navmesh triangles, do you think I might get the intended effect I'm seeking? (solving what this thread is about).

I thought about giving it a go.  It wouldn't be a simple copy and paste and dropping in my verts/polys, I can see there's more going on in that function that would require some work.  Before I do it, I just wanted to make sure there's even a possibility that I'm heading in the right direction with this.

I know Chris Ochs mentioned something about Unity's long and thin triangles spanning the entire terrain, but that's not happening to me.  They do not span a larger/longer area than the tile they came from.  So, maybe I'm on the right track?

[Christmas Eve]

I just made another attempt at the other solution we discussed.  While I was waiting for an answer on the triangle-combining method, I decided to revisit my Recast code.

I made a C# script that exports an entire Unity scene, excluding trees.  They should be easy though.  I plan to just insert octagonal cylinders wherever a tree exists on the terrain.

I'm extremely burnt out from the months of working toward a good pathfinding solution though.  I'm a bit lost in the recast code.  Does anything exist out there already that can take a list of verts/inds/areas and run a tiled Recast on it?  And I mean besides the RecastDemo.  The demo displays the scene and navmesh, which takes more processor time.  I just want a "bake" routine that does the conversion to a navmesh.  I did export my scene data to an .obj format and load it into the demo, though.  The scene looked okay but the frame rate was about 3 seconds per frame (0.3 FPS) and clicking "Build" was prohibitively slow.  I finally killed the process.

[Graham Pentheny]

The demo project is just a simple SDL renderer and obj file loader that interact with the API's that recast provides.  Making a "headless" version is fairly straightforward.  You should be able to look at what it's actually doing in Sample_TileMesh::buildAllTiles() and replicate it. Note, that in the demos, it saves a lot of intermediary data so that debug visualizations can be drawn. Where you won't be needing that, you don't need to keep that data around. In the example, these places are where it's checking !m_keepInterResults and freeing some buffers.

[Graham Pentheny]

Chunky meshes are auto-generated by InputGeom::loadMesh - you shouldn't need to mess with them directly.  They're an intermediate format that helps determine which triangles are within a tile.

I'll admit the process overall is pretty granular.  API granularity allows you as a user to highly customize and control Recast's behavior, however at the cost of requiring multiple steps to perform simple high-level tasks.  We're definitely aware of this as a barrier to entry, and are considering ways of remedying it, though for now we've always aired on the side of giving the users as much control and flexibility as possible.  For now, you're best off trying to use/copy the samples in RecastDemo.

On Tue, Feb 23, 2016 at 1:07 PM 'Christmas Eve' via recastnavigation <recastna...@googlegroups.com> wrote:

Thanks for the info Graham.  I did look at the source a couple times.  I think I stopped looking when I couldn't figure out what a chunky mesh is.  I'm supplying an entire 10000x10000 wu scene that is not divided into tiles.  I assume Recast does that for me.  I'm not sure what to supply Recast when it references chunkyMesh->maxTrisPerChunk, etc.  This is referenced per tile rather than a global list of all scene geometry.  Obviously the demo must be doing it somewhere and I'm not seeing it.

[Christmas Eve]

Hi Graham!

Aww sorry about that.  I didn't know you could still read deleted posts.  I answered my own question after I posted it so I deleted it as not to bother you with it.  I ended up picking apart the demo and creating a completely headless navmesh builder.  So, between this new C++ code I wrote and the C# code to export Unity scenes, I have a complete solution for building navmesh's from Unity for use outside of Unity.

There are just two small things remaining.  On my largest level, it seems to have only created tiles for roughly half of the scene.  I'm not sure why it stopped.  I'm baking the level with larger and fewer tiles right now to see if it helps.

The other question I have is,  my levels have different areas (like a water surface vs ground, etc).  I used to set the polyareas and polyflags to what I wanted in my other version that bypassed Recast and used navmesh triangle data from Unity.  I can see where it sets flags from areas (m_pmesh->areas).  But where did it get these areas from?  I didn't provide them to Recast.  I do have a list (per triangle of input geometry) of what the flags should be but I'm not supplying them yet.  Is there a particular point in the process where it's best for me to set these flags?

In other news, I plan to make the navmesh building process multithreaded to speed it up :) I'm going to try to have it use all CPU cores (by processing 4 tiles at once).  It doesn't look like the Recast code needs the results of one tile before starting the next...

 

[Christmas Eve]

My build for a larger tile size (256) and a slightly larger agent radius seems to have worked on my large world!  I got all the tiles. I'm still trying to figure out this areas/flags thing.  I need to be able to set some to swim (2) but when they're still triangles.  

[Christmas Eve]

It seems to me that rcCreateChunkyTriMesh() needs to split up areas from my full-scene areas[] array as it's splitting up triangles into chunks.  Then, these chunkyAreas need to be integrated into the build process.  I'm hesitant to carry out an idea because I feel like I must be overseeing something.  After all, areas and flags are built into Recast/Detour so I must be missing something.

[Christmas Eve]

I'm pulling my hair out here trying to figure this out.  There is a global list of tris and also tris per tile and also lists of tris per chunk!  I can't figure out how to track which area goes with which original triangle so that I can properly set the flag for the scene geom triangle it came from!  I'm overwhelmed!  I feel like restoring all the Recast code to normal and then running a post process and setting flags based on vertex positions.

[Ben Hymers]

Is rcMarkConvexPolyArea what you're looking for? The general idea is to mark spans in cells within the compact heightfield with the area type, and this is then used by later stages to e.g. put poly edges between regions, where without the area markup there wouldn't have been an edge. rcMarkConvexPolyArea does this for a convex poly region in space.

You shouldn't need to batch up your areas by tile location as rcMarkConvexPolyArea checks against the tile bounds already, though it's possible that you could speed up setting of areas by only calling it on tiles that the poly can possibly overlap.

As for multithreading - yes, you should be able to parallelise! The RecastDemo doesn't do this for simplicity, but it's totally possible.

[Christmas Eve]

Thank you Ben!  I made huge progress since yesterday.  Not only was I able to get areas working but, today I sped up the build process tremendously by making it multithreaded.

An FYI for everyone out there: it takes a lot more than using separate contexts per thread to make a multi-threaded build thread safe.  Basically all of the class properties, m_?????, need to be instantiated again for each thread.

So my solution uses a queue of 4 threads and takes 399% CPU time... nicceeee! :)

I now have a complete solution for pathfinding outside of Unity, thanks to the Recast/Detour team! 

Thanks for all of your guidance Mikko, Graham and Ben!

[Ben Hymers]

You're welcome! I'm glad it's working for you!

Yes, there's a lot to do to make RecastDemo thread safe. I think perhaps it's something we should look at doing at some point, perhaps in another sample? Or as an option to the existing tile sample. Mikko was talking a while ago about exposing threading options in the API but that's something that's very hard to wrap. Implementing it in RecastDemo as an example would be much easier!