LineCast wrong behavior (navmesh)


#1

Hi,

I’m trying to implement the movement of the character with dpad controller, similar to moving from Unity by using NavmeshAgent.Move method (https://docs.unity3d.com/ScriptReference/AI.NavMeshAgent.Move.html).
In Unity, the agent will be shifted by offset argument if there is no way out of the walkable area, or it get the first hit in the unwalkable area and slide along if this possible.

In Astar i couldn’t find anything suitable way for implement this because all methods i found using unity physics and CharacterController (which does not work specifically with navmesh), but found the LineCast method that could help with determining hit points beyond the walkable zone.
But there was a problem with this method:

You can see a built navmesh with a circle cut out. The green vertical line shows the current position of my “character”, the red lines its tracks.
And also we can see that the character enters into an obstacle, ignoring cuts (LineCast return false).

Using LineCast in movement code:

private Vector3 SimpleMove (Vector3 start, Vector3 offset)
{
	Vector3 target = start + offset;
	Vector3 result = target;
	GraphHitInfo info;
	// Check if there is a way out of the walkable area
	if (_navMeshGraph.Linecast (start, target, _navMeshGraph.GetNearest (start, NNConstraint.None) .node, out info))
	{
		// ...
		// Determine the point where will the character appear after a collision with an obstacle and slide
		return newPosition;
	}
	return result;
}

On straight lines that are parallel to the coordinate axes, this doesn’t happen. How can i solve this problem?

(using Unity 2017.1.1p4, A* Pathfinding Project Pro 4.0.11)

Edit:
I try this code:

bool result1 = _navMeshGraph.Linecast(start, end, _navMeshGraph.GetNearest(start, NNConstraint.None).node, out info1);
bool result2 = _navMeshGraph.Linecast(info1.point, end, _navMeshGraph.GetNearest(info.point, NNConstraint.None).node, out info2);

where result1 return true (there is obstacle between start and end points), result2 return false
and i think this is wrong too.


where red line is line from start to end, and green vertical line is info1.point


#2

Hi

Linecasts on navmesh-based graphs have worked well in almost all cases, there have unfortunately been edge cases when the start is right on the border of the navmesh (and in some other rare cases).
Good news is that I have rewritten the linecast methods to be both faster and more accurate now (mainly it only uses integer math instead of floating point math because floating point math is very tricky), but that code hasn’t made it to the release version yet.
There is a beta version with it however. If you go to the https://www.arongranberg.com/astar/download page and click the ‘Show Older Versions’ button you will see a 4.1.7 version on the spherical_beta branch (it’s not a regular beta, but it will work for this purpose). I think the linecast methods in that version should be a lot more stable.
There is one single case where I know it fails. This happens sometimes if the closest point on the navmesh when rounded to integer coordinates turns out to be outside the navmesh. I have fixed this in my dev version, however the updated code has not been uploaded yet.

There is also an included example script that does pretty much the same thing as you are trying to achieve. It is called NavmeshClamp and can be found in the ExampleScripts folder.

A much simpler solution for you can be to just move the character to the closest point on the navmesh after the move.

transform.position = AstarPath.active.GetNearest(transform.position).position;

However this has the risk of the object being able to penetrate thin walls.


#3

Thanks for reply. Beta version with NavmeshClamp really suits for my needs and i try use it, but it’s worth noting that in some cases on sharp angles before the obstacle the character starts to shake a little, but not much noticeably.


#4

Hi!

Quick question regarding the fixes and rewrite:
I noticed that the Linecast runs quite often into infinite loops (maybe due to precision errors?).
This will cause the distance in the out struct to blow up.

Does this still happen?

I currently manually inserted a check if the length of the linecast is smaller then the hit distance - which is not really a perfect solution.

Cheers
Jannes


#5

@Puppeteer
That shouldn’t happen anymore with the fixes.


#6

Is that on a slight slope?
The beta version is slightly incorrect when it maps the Vector3 position to a point on the closest node. This may result in some slight jittering on slopes.


#7

Not only slope. If character stay in sharp corner and try to move in obstacles direction i can see shake too.


#8

Hi

Do you think you could share a video of this happening?


#9
  1. sharp corner https://gyazo.com/1984dbdbdb5d29172143b3cfc8f7d7f9
  2. sharp corner with axis aligned side https://gyazo.com/57b6ae29221f05c3c65c4b8b81a3be62

#10

Ah. It seems there was some old code in the NavmeshClamp script that was used in an effort to work around the earlier problems with the linecast code.

Simply remove this line in the NavmeshClamp.cs script:

ohit = ohit + Vector3.ClampMagnitude((Vector3)hit.node.position-ohit, 0.008f);