Navigate over Navmesh gaps with Waypoint routes

[reecpjParticipant]

Hi,

I’m trying to get a character to move over uneven terrain (some small cliffs etc). There are gaps in the navmesh that I would like to make traversable. The character currently gets stuck sometimes when the navmesh is steep.

I thought (perhaps wrongly) that adding waypoint networks or routes would automatically allow additional paths to be considered than the navmesh connections. This doesn’t work for me, the character still doesn’t move past the gaps in the navmesh (despite multiple waypoint networks/ paths over the gaps, whose start and end positions are definitely on the navmesh).

The only ways I can think of to do this now are set up behaviour tree constraints to switch to a follow path when in range of a path (not ideal) or colliders the character can walk into that move the character independently of RAIN. Neither are ideal in my opinion. Thanks for any advice you have!

[CodersExpoParticipant]

Why are there gaps in the navigation mesh? Can you create multiple mesh graphs that overlap and solve this issue? Example, Create one reasonably large mesh and several small mesh connecting to another reasonably large mesh. They can overlap each other. Use navigation graph tags if you want to allow/restrict the ai from traversing certain mesh graphs.

[reecpjParticipant]

The gaps are due to “steep” terrain such as a 1 meter drop, or things like a platform not directly touching another platform. More navmeshes won’t help, but I thought waypoints defining where the ai could move over the gaps would. Maybe I was wrong.

[CodersExpoParticipant]

It’s my understanding the navigation mesh is required for the path finding to be done and thus use the RAIN workflow for moving to a point on the graph. If a “moveto” location is not on the graph it will fail. I think your solution to assign a location to “moveto” and take control of the character is all that can be done to get between these gaps. Maybe we can ask the big Kahuna. Jester? Thoughts?

[SigilKeymaster]

What CodersExpo says is correct. We do plan on supporting off mesh links, but it is just not there yet.

As it goes, if you are working with a single Navigation Mesh it is possible to add connections to the graph at runtime, allowing you to connect areas that normally weren’t connected.

This is pretty custom though, so it could break. It did work with my simple Navigation Mesh that I created, just have to create two empty game objects, assign this script to them and fill out their fields appropriately.

using UnityEngine;
using System.Collections;
using RAIN.Navigation.NavMesh;
using RAIN.Navigation.Graph;
public class Link : MonoBehaviour {
	[SerializeField]
	private NavMeshRig _ourNavMesh = null;
	[SerializeField]
	private Link _otherLink = null;
	private bool _connected = false;
	void Start()
	{
		if (_ourNavMesh == null || _otherLink == null)
		{
			Debug.LogWarning("Navigation mesh or other link is unassigned");
			return;
		}
		if (_connected)
			return;
		_connected = true;
		_otherLink._connected = true;
		int tNodeOne = _ourNavMesh.NavMesh.Graph.Quantize(gameObject.transform.position, 0);
		int tNodeTwo = _ourNavMesh.NavMesh.Graph.Quantize(_otherLink.gameObject.transform.position, 0);
		if (tNodeOne == -1 || tNodeTwo == -1)
		{
			Debug.LogWarning("Links not on navigation mesh");
			return;
		}
		NavMeshPoly tPolyOne = (NavMeshPoly)_ourNavMesh.NavMesh.Graph.GetNode(tNodeOne);
		NavMeshPoly tPolyTwo = (NavMeshPoly)_ourNavMesh.NavMesh.Graph.GetNode(tNodeTwo);
		NavMeshEdge tEdgeOne = GetClosestEdge(tPolyOne, tPolyTwo);
		NavMeshEdge tEdgeTwo = GetClosestEdge(tPolyTwo, tPolyOne);
		if (tEdgeOne == null || tEdgeTwo == null)
		{
			Debug.LogWarning("Couldn't find edge to connect");
			return;
		}
		float tConnectCost = (tEdgeOne.Center - tEdgeTwo.Center).magnitude;
		NavigationGraphEdge tOneWay = new NavigationGraphEdge(tEdgeOne.NodeIndex, tEdgeTwo.NodeIndex, tConnectCost);
		tEdgeOne.AddEdgeOut(tOneWay);
		tEdgeTwo.AddEdgeIn(tOneWay);
		NavigationGraphEdge tOtherWay = new NavigationGraphEdge(tEdgeTwo.NodeIndex, tEdgeOne.NodeIndex, tConnectCost);
		tEdgeTwo.AddEdgeOut(tOtherWay);
		tEdgeOne.AddEdgeIn(tOtherWay);
		Debug.Log ("Added connection from node " + tEdgeOne.NodeIndex + " to " + tEdgeTwo.NodeIndex);
	}
	void OnDrawGizmos()
	{
		Gizmos.matrix = Matrix4x4.identity;
		Gizmos.color = Color.white;
		Gizmos.DrawWireSphere(gameObject.transform.position, 0.5f);
		if (_ourNavMesh != null && _otherLink != null)
			Gizmos.DrawLine(gameObject.transform.position, _otherLink.gameObject.transform.position);
	}
	void OnValidate()
	{
		if (_otherLink != null)
		{
			_otherLink._otherLink = this;
			_otherLink._ourNavMesh = _ourNavMesh;
		}
	}
	NavMeshEdge GetClosestEdge(NavMeshPoly aNodeOne, NavMeshPoly aNodeTwo)
	{
		float tClosestDist = float.MaxValue;
		NavMeshEdge tClosestEdge = null;
		for (int i = 0; i < aNodeOne.EdgeCount; i++)
		{
			NavMeshEdge tEdge = (NavMeshEdge)_ourNavMesh.NavMesh.Graph.GetNode(aNodeOne.GetEdge(i));
			if (tEdge.PolyCount == 2)
				continue;
			float tDist = (tEdge.Center - aNodeTwo.Center).magnitude;
			if (tDist < tClosestDist)
			{
				tClosestDist = tDist;
				tClosestEdge = tEdge;
			}
		}
		return tClosestEdge;
	}
}

Think of it as a poor mans off mesh link.

[reecpjParticipant]

Wow, thanks, that could be useful! I was hoping that a waypoint route/ network would automatically provide additional options for the AI than the Navmesh graph.

I suppose the less-hacky way of doing it would be to have a separate behaviour constraint (seeing if the ai’s target point would make the ai follow a path that briefly goes off the navmesh) to take the ai off the navmesh and get it to patrol the closest waypoint route (one-way) that would take it closer to its target point on the navmesh. Would that be more advisable than directly editing the navmesh?

Thanks for the help, guys!

[CodersExpoParticipant]

I think it really depends on what works for you. You most certainly could move your character from point to point off the mesh but I think what Sigil is offering here is a way to dynamically maintain the ability link points on a graph. If you know ahead and have control over where the character needs to move, and there is no random chance or dynamic evaluations require, then I suspect your solution would be the easiest to implement and support. IMHO

• This reply was modified 2 years, 1 month ago by  CodersExpo.
• This reply was modified 2 years, 1 month ago by  CodersExpo.

[CodersExpoParticipant]

Here is a nice overview of Off Mesh linking https://docs.unity3d.com/Documentation/Components/class-OffMeshLink.html

[CodersExpoParticipant]

Sigil, I was able to create a link between two empty game objects with this code (thank you btw) on the same navigation mesh. If I create two separate navigation meshes and place a game object on each I don’t get a link. I get “Links not on navigation mesh”. I understand this because _ourNavMesh is not the same for both game objects. I was attempting to see if this would work similar to how I understand Unity’s off mesh linking.

So my question, does this script act as a sort of “bridge” to tie the gaps in a single mesh together. For example in Reecpj’s case, if the character stops because of a gap in rough terrain, you could add a game object with this script on both sides of the gap to prevent the character from stalling when running into these. Obviously, I would expect these to be large gaps that can’t be overcome by adjusting the navigation mesh cell size.

[CodersExpoParticipant]

OK, this is awesome! Sigil I answered my own question, thanks!

1. Create a terrain and build a small mound just large enough that the mesh cells don’t cover when generating the navigation mesh. Make sure it goes all the way across the terrain.
2. Create a navigation mesh for the terrain (my terrain is 50 length by 50 width not to big). Note the entire terrain is covered by the mesh EXCEPT the mound stretching across. This hill has no cell coverage and there is no way around. Effectively separating your character from the other half of this mesh graph.
3. As Sigil suggested, create two empty game objects. Place each on either side of the mound and make sure they are on the mesh.
4. Add this script Sigil wrote to each game object.
5. Select the first game object and drag your navigation rig component into the property field “Our Nav Mesh”. Drag the other gameobject into the property field “Other Link”. Check both game objects have a reference to the nav rig and each other.
6. Add a character to the scene on one side of the mound on the mesh. Add the RAIN AI component.
7. Create a waypoint route with one point on one side of the mound and another point on the other side. Select all and drop to surface.
8. Create a behavior tree and add the waypoint route node. Define the waypoint rig and variable.
9. Add a child move node and give it the waypoint routes move variable and speed.
10. Assign this BTAsset to your character.
11. Regenerate the navigation mesh and run the app.

Your character will walk off the mesh and to the other side because he now has a link. He will walk through the mound though so you have to…

1. Add a rigid body and freeze rotation X and Z
2. Add/adjust a capsule collider

Now he walks over the hill to get to the other side….sounds like a joke coming on

Now just for fun, remove the script from both game objects and run it again. Your character is stuck. Awesome help with this script Sigil!

[reecpjParticipant]

Brilliant, thanks for all the help! I’m so grateful for all your tutorials, I’d probably be stuck without them.

I tried adding a rigidbody to avoid walking “through” colliders but it seems to have no effect if kinematic, and if not kinematic the ai just falls straight through the ground (which has a correctly shaped collider and a kinematic rigidbody on it). What GameObject did you add the rigidbody to, and what settings did you use?

EDIT: Tried a kinematic rigidbody on the parent of the AIRig component, and that seems to work! Awesome

Thanks!

• This reply was modified 2 years, 1 month ago by  reecpj.

[Author]

Posts