A* Pathfinding Project

NavmeshCut produces incorrect cut on aligned mesh


#1

Hello Aron,

In my use case, NavmeshCut produces mesh with “loose” vertices when the cut is aligned with Raycast grid cells:

This is the graph before the cut:

After executing the cut I get following result:

As it’s apparent, the vertices with 1 are not really connected with vertices nr. 2, this unfortunately breaks my algorithm to calculate the outline of the cut. Is this a known issue :frowning: ?


#2

Hi

So if I am understanding you correctly, you would have wanted to have these additional splits? (see image)

The current output is the intended one. For pathfinding purposes nodes in adjacent tiles do not necessarily need to share vertices. Note that this is true even for the recast graph output (even though is almost all cases the vertices are shared).

For what reason do you need the outline of the cut?


#3

Yes, you understand correctly.

I need to calculate the outline, to be able to determine approach points from multiple angles to object represented by cut geometry. The cut is not walkable. I precompute this information after the cut happens.

Is there anything I can do to suggest the cut mechanism to try to preserve uniform geometry?


#4

But can’t you just use the original cut info from the NavmeshCut component for that?

Unfortunately not really. Except offsetting the cut slightly, but that also adds the risk of creating some extremely thin triangles which will be really bad for pathfinding.


#5

I suppose I can use my original mesh to do the calc. I thought the cut would be robust enough to allow me to do this on the mesh.

Also I don’t really agree it wont affect pathfinding, if the cuts ware walkable the pathfinding from nodes 1 to 2 will cause the path to go around the cross into another arm, because there is no connection between 1 and 2.

Oddly enough I noticed this happening only when I have some edges aligned perfectly with the mesh.


#6

There is special code for connecting nodes across tile borders even if they do not share vertices. If you enable the ‘Show Connections’ mode I think you will see that they are indeed connected.
There are some rare cases where it fails (mostly due to an annoying bug in a 3rd party library that I use), but in pretty much all cases it should work.


#7

Oh than I could probably use this code to get the neighbor nodes in my code as well? I was currently just using connections attribute of the node.

Where can I find this piece of code?


#8

Hmm… That connection should be included in that list.

The relevant code is in NavmeshBase.cs line in the ConnectTiles method though.


#9

Aron, indeed the connections are there, but my code did not anticipated that some neighbors wont have all triangles connected.

I guess I would have to modify the mechanism a little.

Thanks for your help!