Another cave related question

Snouto · August 28, 2018, 7:07am

I’m experimenting with a scene whereby not only is the surface of the world mesh walkable but so are subterranean caves. There will always be at least one entrance to the cave system from the surface and I’d like my AI character to be able to traverse this opening and plot routes from within the cave to the surface world (and vice-versa).

Below is an image that looks like a 5 year old drew it but was actually drawn by yours truly, and below that are two screen grabs of the relevant scene areas in Unity. Hopefully these illustrate sufficiently what I’m trying to do.

I’m using the Layered Grid Graph due to the overlapping walkable surfaces. When I scan the mesh to generate the navmesh, I notice that while the surface face is nicely covered there’s a gap between the entrance to the cave and the tunnel leading to the cave itself, as indicated in the screenshot by the unwalkable nodes. It’s also notable from the same screenshot that the surface navmesh area appears to “reach inside” the entrance to the tunnel, covering the entrance itself. According to the default colour scheme that shaded area indicates the boundary of the navmesh, so could the whole issue be due to there being no connection between the surface navmesh and the tunnel navmesh? How would one go about ensuring the tunnel can connect to the surface with a single navmesh or some method of bridging the two?

When I set my AI character - which I’ve placed in the cave - to navigate to the target object on the surface of the mesh, it initially begins moving towards the entrance but then warps to the surface and continues to move towards the target (albeit at a jaunty angle).

Interestingly, when I allow the AI character to “wander” aimlessly within the cave room it will occasionally warp to the surface directly above the cave room - usually when the AI character is walking along the walls.

What could be causing the warp? I thought it may be due to the gap in the calculated nav area from the cave tunnel to the surface (note: the character appears to warp when it reaches the first unwalkable node, even if there is a navmesh extending beyond that point), but that wouldn’t explain why the warp also sometimes happens within the cave room.

[Edit]: further testing reveals there are exceptions being thrown at the point of warping, and then repeatedly afterwards:

First exception, which reoccurs hundreds of times as the AI character warps and continues to move to the target:

ArgumentOutOfRangeException: Argument is out of range.
Parameter name: index
System.Collections.Generic.List`1[System.Int32].get_Item (Int32 index) (at /Users/builduser/buildslave/mono/build/mcs/class/corlib/System.Collections.Generic/List.cs:633)
Pathfinding.AIPathAlignedToSurface.InterpolateNormal (RaycastHit hit) (at Assets/AstarPathfindingProject/Behaviors/AIPathAlignedToSurface.cs:48)
Pathfinding.AIPathAlignedToSurface.UpdateMovementPlane () (at Assets/AstarPathfindingProject/Behaviors/AIPathAlignedToSurface.cs:64)
Pathfinding.AIPathAlignedToSurface.Update () (at Assets/AstarPathfindingProject/Behaviors/AIPathAlignedToSurface.cs:14)

additional exception that occurs a dozen times or so after the initial warp:

ArgumentOutOfRangeException: Argument is out of range.
Parameter name: index
System.Collections.Generic.List`1[System.Int32].get_Item (Int32 index) (at /Users/builduser/buildslave/mono/build/mcs/class/corlib/System.Collections.Generic/List.cs:633)
Pathfinding.AIPathAlignedToSurface.InterpolateNormal (RaycastHit hit) (at Assets/AstarPathfindingProject/Behaviors/AIPathAlignedToSurface.cs:48)
Pathfinding.AIPathAlignedToSurface.UpdateMovementPlane () (at Assets/AstarPathfindingProject/Behaviors/AIPathAlignedToSurface.cs:64)
Pathfinding.AIPath.OnPathComplete (Pathfinding.Path newPath) (at Assets/AstarPathfindingProject/Core/AI/AIPath.cs:274)
Pathfinding.Seeker.OnPathComplete (Pathfinding.Path p, Boolean runModifiers, Boolean sendCallbacks) (at Assets/AstarPathfindingProject/Core/AI/Seeker.cs:299)
Pathfinding.Seeker.OnPathComplete (Pathfinding.Path path) (at Assets/AstarPathfindingProject/Core/AI/Seeker.cs:267)
Pathfinding.Path.ReturnPath () (at Assets/AstarPathfindingProject/Core/Path.cs:728)
Pathfinding.Path.Pathfinding.IPathInternals.ReturnPath () (at Assets/AstarPathfindingProject/Core/Path.cs:782)
Pathfinding.PathReturnQueue.ReturnPaths (Boolean timeSlice) (at Assets/AstarPathfindingProject/Core/Misc/PathReturnQueue.cs:55)
AstarPath.Update () (at Assets/AstarPathfindingProject/Core/AstarPath.cs:799)

[Edit 2]
I tried adding an AnimationLink between the tunnel entrance and the surface, and I noticed that a full path to the surface appeared to be plotted. However, as mentioned above, the AI still warps to the surface long before reaching the entrance.

Eventually I’d like to have multiple cave rooms and tunnels connected to each other and the surface, with the AI character able to nav from cave room to cave room as well as to the surface, so I’d love to be able to get on the right tracks at this early stage and clearly I can’t have the AI character warping around the place!

Any advice you can offer will be greatly appreciated .

Cheers!

Snouto · September 1, 2018, 6:37am

Just bumping this for visibility!

aron_granberg · September 2, 2018, 5:43pm

Hi

The exceptions, while obviously bugs are not related to the teleportation or the graph generation. Though in another thread (which I think you also started) it would be nice to get a reproducible test case from that. I haven’t been able to replicate it.

I would suggest that you take a look at the ‘Character Height’ setting on the layered grid graph. That sounds like the most reasonable culprit. Potentially the collision testing height as well. Try to reduce both those values.
One caveat is that the ‘Character Height’ setting is the minimum distance to the next node above it for it to be a valid node. It is not the distance to the roof in the cave (for example). This is mostly for historical reasons and for performance. Usually they are almost the same.

Snouto · September 4, 2018, 5:04am

Hi and thanks for the reply. I tried playing with the character height without success, but after a bit more trial and error I’m thinking my pathing issue (with regards to warping) is related to the “raycast centre offset” value of the AIPathAlignedToSurface script I’m using. If I change this from the default 1 to e.g. 0.1, the character gets much much further up the calculated path. It still doesn’t quite succeed however, as it appears to fall through the surface mesh once it reaches the cave entrance, but at least it’s a step forwards.

I’ve put together a simple test scene (92MB) using the example cave mesh shown previously, with the raycast offset left at 1. You’ll see the character object warp before reaching the cave entrance, and then you’ll also see the exceptions in the console described here and in the other post you’re aware of.

Let me know if you need anything else to help debug the exception issue, and if you have any thoughts about the raycast offset.

Cheers!

[edit] a bit more regarding the raycast offset. it does appear to enable the character to access the cave entrance, although for it to work reliably* I also need to reduce the size of the graph nodes.

*There’s still the problem with the character falling through the mesh though, even with the smaller graph node size. This happens regularly if the target cube is positioned behind the entrance somewhere.

Also - curiously - the character appears unable to go in to the cave if the target is positioned in the cave room and the character is on the surface. The character’s path appears to plot correctly but the character itself seems to swing back and force between two points on the surface near the entrance, without ever entering.

I don’t know what you make of my attempts here but I’m beginning to think it’s not going to be possible

aron_granberg · September 11, 2018, 9:10am

Hi

Sorry for the late answer.
I tried your example scene, however it seems to have been exported with some missing prefabs. The “SampleScene” is completely empty and “Scene1” contains some missing prefabs which I expect is the ground. Trying to play it just leads to the character falling indefinitely. Do you think you could zip the project instead of making a Unitypackage, that is usually more resilient against missing prefabs and similar things.

Snouto · September 12, 2018, 12:22am

Ah nuts sorry about that, you can grab the full zip from here. Cheers!

aron_granberg · September 12, 2018, 11:55am

Hi

Okay. Now it worked.

I found the exception bug. Apparently my script didn’t handle meshes with multiple submeshes correctly.

To get the graph to detect the entrance properly I had to double the graph resolution (node size is now 0.25) because previously it was simply too low to be able to work well.

Node size = 0.5

Node size = 0.25

The movement script uses a raycast to determine where the ground is, this is visualized in the scene view as a green line

This is set by the parameter ‘Raycast Center Offset’ in the movement script. The value you used was quite high, so the raycast would hit the ground above the cave and thus teleport it to the surface. I reduced it to about the size of the character which worked much better:

Your agent also had a really high ‘Pick Next Waypoint Distance’, that would cause the agent to try to cut corners a bit too much, so much that it might actually try to go into a wall in the cave.

The range is visualized in the scene view when changing any of the relevant values, or if you enable ‘Always Draw Gizmos’ on the AIPath script. I reduced it to 0.5 which worked much better.

aron_granberg · September 12, 2018, 12:02pm

The updated script you need (which fixes the exception) looks like

using UnityEngine;
using System.Collections.Generic;

namespace Pathfinding {

	public class AIPathAlignedToSurface : AIPath {

		protected override void Start() {
			base.Start();
			movementPlane.Set(rotation);
		}

		protected override void Update() {
			base.Update();
			UpdateMovementPlane();
		}

		protected override void ApplyGravity (float deltaTime) {
			// Apply gravity
			if (usingGravity) {
				// Gravity is relative to the current surface.
				// Only the normal direction is well defined however so x and z are ignored.
				verticalVelocity += float.IsNaN(gravity.x) ? Physics.gravity.y : gravity.y;
			} else {
				verticalVelocity = 0;
			}
		}

		Mesh cachedMesh;
		List<Vector3> cachedNormals = new List<Vector3>();
		List<int> cachedTriangles = new List<int>();
		Vector3 InterpolateNormal (RaycastHit hit) {
			MeshCollider meshCollider = hit.collider as MeshCollider;

			if (meshCollider == null || meshCollider.sharedMesh == null)
				return hit.normal;

			Mesh mesh = meshCollider.sharedMesh;

			// For performance, cache the triangles and normals from the last frame
			if (mesh != cachedMesh) {
				if (!mesh.isReadable) return hit.normal;
				cachedMesh = mesh;
				mesh.GetNormals(cachedNormals);
				if (mesh.subMeshCount == 1) {
					mesh.GetTriangles(cachedTriangles, 0);
				} else {
					List<int> buffer = Pathfinding.Util.ListPool<int>.Claim();
					// Absolutely horrible, but there doesn't seem to be another way to do this without allocating a ton of memory each time
					for (int i = 0; i < mesh.subMeshCount; i++) {
						mesh.GetTriangles(buffer, i);
						cachedTriangles.AddRange(buffer);
					}
					Pathfinding.Util.ListPool<int>.Release(ref buffer);
				}
			}

			var normals = cachedNormals;
			var triangles = cachedTriangles;
			Vector3 n0 = normals[triangles[hit.triangleIndex * 3 + 0]];
			Vector3 n1 = normals[triangles[hit.triangleIndex * 3 + 1]];
			Vector3 n2 = normals[triangles[hit.triangleIndex * 3 + 2]];
			Vector3 baryCenter = hit.barycentricCoordinate;
			Vector3 interpolatedNormal = n0 * baryCenter.x + n1 * baryCenter.y + n2 * baryCenter.z;
			interpolatedNormal = interpolatedNormal.normalized;
			Transform hitTransform = hit.collider.transform;
			interpolatedNormal = hitTransform.TransformDirection(interpolatedNormal);
			return interpolatedNormal;
		}


		/** Find the world position of the ground below the character */
		protected override void UpdateMovementPlane() {
			// Construct a new movement plane which has new normal
			// but is otherwise as similar to the previous plane as possible
			var normal = InterpolateNormal(lastRaycastHit);
			var fwd = Vector3.Cross(movementPlane.rotation * Vector3.right, normal);
			movementPlane.Set(Quaternion.LookRotation(fwd, normal));
			rvoController.SetMovementPlane(movementPlane);
		}
	}
}

Snouto · September 12, 2018, 11:27pm

This is fantastic support, thank you very much! I’ll try your changes as soon as time permits (pesky work is in the way right now) and hopefully I’ll be in business.

Thanks again!

Snouto · September 19, 2018, 3:56am

So I finally had a chance to look at this and after tweaking a few of the values to match my real scene it appears as though my characters are able to not only exit the cave but also enter it, and the exceptions are indeed gone. So, thanks very much for taking a look at this - it looks like for the time being the issue is resolved

Thanks again!

Snouto · January 15, 2019, 2:29am

Hi again.

I’ve just updated to the latest version of A* and noticed several breaking changes in the above AIPathAlignedToSurface.cs code, due to changes in RVOController, AIBase and AIPath. The AIPath error was easily fixed, however there appears to be a significant change in AIBase whereby you’re now using the GraphTransform class rather than the previous SimpleMovementPlane class, and I’m not sure how to go about fixing this for the AIPathAlignedToSurface class.

Would appreciate any help you can offer.

Cheers

aron_granberg · January 18, 2019, 10:42am

Hi

I think the spherical world branch made the change to use SimpleMovementPlane instead of GraphTransform. You can convert from a GraphTransform to a SimpleMovementPlane by calling

((IMovementPlane)graphTransform).CopyTo(someSimpleMovementPlaneInstance)

Snouto · January 22, 2019, 11:42pm

Hi. Thanks for the tip, I’ll see if I can figure out how to apply that to the latest codebase and move forward. Cheers!

Snouto · March 19, 2019, 6:59am

Hi again, two months later and i’m back with the same or maybe related issue. Only this time, as I’ve been away doing other things, when I’ve come back to my project and updated to the very latest version of A* Pro, I’m seeing an error of:

Pathfinding.AIPathAlignedToSurface.UpdateMovementPlane() is marked as an override but no suitable method found to override

Did UpdateMovementPlane get removed from AIPath or AIBase?

You mentioned that there is a spherical world branch, which I should probably be using to ensure I have all the latest updates for this line of A* stuff - is it a public GIT repro? Would appreciate the link if so.

Cheers!

aron_granberg · March 22, 2019, 5:45pm

Hi

It’s more that it was never added. The spherical beta still has some things that the master branch does not have. You can probably copy the AIPath script from the beta to the latest version and it will work (possibly you will also need the AIBase script).

The spherical beta is still at 4.1.20 though.