A* Pathfinding Project

Navmesh on a spherical planet


Unfortunately, I don’t own the pro version yet.


Oh that’s what you meant, I misunderstood.
Can you post a screenshot of your complete inspector ? I can’t see the bottom of your Agent script, are you using the gravity ? Because you don’t want your agent to move according to the gravity.


there you go…


Did you use this code? https://pastebin.com/jsswyycg


yes. There wasn’t any Update function. So, I added that code to MovementUpdate function.


Why are you using a local variable for movementPlane? There should already be one in your AIBase class.

Aside from that, I have the same code as you for AIPath. Can you please paste your code from AIArbitrarySurface ?


pastebin is also using local variable for movementPlane.

public class AIArbitrarySurface : AIPath
	public LayerMask groundMask = -1;
	Vector3 interpolatedUp = Vector3.up;

	protected override IMovementPlane MovementPlaneFromNode (GraphNode node)
		var forward = Vector3.Cross (Vector3.right, interpolatedUp);

		return new GraphTransform (Matrix4x4.TRS (Vector3.zero, Quaternion.LookRotation (forward, interpolatedUp), Vector3.one));

	protected override void Update ()
		base.Update ();

		tr.position = RaycastPosition (tr.position);

	/** Find the world position of the ground below the character */
	Vector3 RaycastPosition (Vector3 position)
		RaycastHit hit;
		var normal = interpolatedUp;

		if (Physics.Raycast (position + tr.up * 0.5f, -tr.up, out hit, 2f, groundMask)) {
			normal = hit.normal;
			position = hit.point;

		// Use the node surface as the movement plane
		interpolatedUp = Vector3.Slerp (interpolatedUp, normal, 4 * Time.deltaTime);
		return position;


I checked and I have the exact same code as you, except for the “var movementPlane =” instead of just “movementPlane =” for me in MovementUpdate.
I tried to use it as a local variable and that’s what seems to be the problem, can you give it a try ?


thanks…it worked fine now.


Hi Aron, I’m also interested in this spherical pathfinding functionality!

I’m more than willing ot purchase the pro version, are these files from Raphael still something that could be shared? (Thank you Raphael for your generosity!)



@heckmouse, I can send you the files as well if you want.
It seems that this is more popular than I anticipated, so maybe I will merge it into the main package when I have the time.


Thanks Aron, I’ll let you know when I’ve purchased the pro version.


When I open example scene in the Spherical Navmesh beta it seems to be missing the meshes for the “cylinder” and “Mball.005” objects in scene 18. Should these be included or am I missing something? Thx! Either way I just used some other meshes to get it going. :smiley: Super excited to play with this and definitely highly interested. Kudos to Raphael_Ninpo for tackling this!!!

Unity has appeared to drop any kind of ongoing progress/support for their recent and unfinished nav changes. I’d been trying to get their new system to work on spherical terrain but it just seems to get more and more broken with editor changes. Super close and so so super frustrating.



Also, if there are additional files from @Raphael_Ninpo for the rvo avoidance I would greatly appreciate them being sent to me. :grin:
I’ve upgraded from version 3 to 4 of the Pro, happy to send my invoice# if needed. @aron_granberg


So, just wondering if you’ve made any further headway since August if you’ve tried tackling the RVO threading, obstacles, and getting it to work with RichAI and such? Thx again


Hi @Christougher, thank you for your interest in this thread !

Unfortunately I didn’t have time to improve the RVO on a spherical planet.
I modified a lot of code to adapt it to my project, so right now I won’t be able to provide a good example.
The RVO still has some flaws: currently, I’m using the system with 8 RVO quad trees around the planet, located on 8 of the 12 vertices of an icosahedron based planet (for my current configuration), so it works really well right on these vertices, but gets approximate far from these points, like on the middle of a face (http://bit.ly/2mzX9Qt).
It gets more precise with more quadtrees, but it also needs more computation, so you have to find a balance between accurracy and speed.

I intend to work on it again later, I’ll give you some news when I do so :slight_smile:




So in regards to performance there is a large chunk of garbage collection happening with the AIArbitrarySurface.CS script, I think from this line right here:

movementPlane = new GraphTransform(Matrix4x4.TRS(Vector3.zero, Quaternion.LookRotation(forward, interpolatedUp), Vector3.one));

Is there a way to maybe prevent calling for a new GraphTransform every frame as that generates lots of garbage?


Hey @Christougher, great work on your video ! (“genious modifications” oh, stop it you :blush:)
I didn’t have time to work on the optimization yet, but I’m glad you found some code to optimize.

A way I can think of to prevent calling for a new GraphTransform every frame would be to store them according to their position on the planet.
Depending of your planet base model, if it’s either an icopshere (http://bit.ly/2DDwMk1) or a different primitive sphere (http://bit.ly/2rbQWiu or http://bit.ly/2FG0fu6), maybe you can store the calculated GraphTransform for each vertex (or the center of each triangle, I don’t know what’s best), and then getting the closest GraphTransform at any given time (maybe the triangle would be the best option because you could raycast directly on the model and get the hit triangle).


Thx! Good thought and as the AI raycasts every frame to the surface anyway that might be the most performant way to go… But I was thinking maybe just updating the GraphTransform values every frame instead of trashing it and making a new one every frame for every AI.
Soooooo… quick question for @aron_granberg, would there be a problem with nixing the readonly property of the GraphTransform values? I made them writable and added this method to GraphTransform.cs

    public void UpdateGraphTransform(GraphTransform graphTransform,  Matrix4x4 matrix)
        this.matrix = matrix;
        graphTransform.inverseMatrix = matrix.inverse;
        graphTransform.identity = matrix.isIdentity;
        graphTransform.onlyTranslational = MatrixIsTranslational(matrix);
        graphTransform.up = matrix.MultiplyVector(Vector3.up).normalized;
        graphTransform.translation = matrix.MultiplyPoint3x4(Vector3.zero);
        graphTransform.i3translation = (Int3)translation;

        graphTransform.rotation = Quaternion.LookRotation(TransformVector(Vector3.forward), TransformVector(Vector3.up));
        graphTransform.inverseRotation = Quaternion.Inverse(rotation);

        graphTransform.isXY = rotation == Quaternion.Euler(-90, 0, 0);
        graphTransform.isXZ = rotation == Quaternion.Euler(0, 0, 0);

and thenadded
GraphTransform gTrans;

to AIArbitrary surface and changed

movementPlane = new GraphTransform(Matrix4x4.TRS(Vector3.zero, Quaternion.LookRotation(forward, interpolatedUp), Vector3.one));


gTrans.UpdateGraphTransform(gTrans, (Matrix4x4.TRS(Vector3.zero, Quaternion.LookRotation(forward, interpolatedUp), Vector3.one)));
movementPlane = gTrans;

Dropped a ton of garbage collection, like 7-13kb per frame for 30ish AIs. :grin: