A* Pathfinding Project

Navmesh on a spherical planet


Oh and by the way, I added a fix in my code, I don’t know if it was before or after submitting my files, but regarding the RVO quad trees, you’ll want to ignore the RVO agents and obstacles that are on the other side of the planet by using a Vector3.Dot, which will prevent your agents from trying to avoid things on the other side of your planet, and also reduce the amount of computation needed.


Nice, I’ve tested it on mobile and the rvo 3d is killing performance. I still haven’t been able to wrap my head around how the multiple quad trees work exactly. Any chance you could share a tid bit of code and where it might go for the vector3.Dot? I was actually thinking that maybe an octree would work well to limit checks between only nearby agents. That could be well outside of my skill range just yet , as I just barely learned what an octree was last week lol. Don’t have a coding background either.


Hello I’m really very interested is this too, could you send the files to me?


@Christougher the Vector3.Dot goes in RVOAgents3D.cs, around line 839:

// Ignore the edge if the agent should not collide with it
if (vertex.ignore || (vertex.layer & collidesWith) == 0 || Vector3.Dot(position3D - planetPosition, vertex.position - planetPosition) < 0) {…}

For how the quad trees work, here’s an ugly drawing I tried to do:

You can see the 2 tangent planes with their normal, well these planes represent the quad trees, and each black arrow is an agent projected onto these planes, so each quad tree will work like Aron coded them to work, doing the RVO computation and all, but each will do it according to it’s normal, and each agent will get information from the closest quadtree, which has the more reliable RVO results.

At some point in development, I had one quadtree by agent, so each agent could have the most reliable RVO information, but I reduced the number of quadtrees because it had an exponential complexity the more agents you had.
I still think about this solution, because it could work with light optimized code, but I’ll keep that in mind for later.


Thx again! the line you added to RVOAgent3D looks like it would only affect the obstacles and not agents. Is there a similar line or fix you added to GenerateNeighbourAgentVOs ? I’m definitely getting agents affected by other agents when they are far away from each other… and it seems more pronounced to be when they are far sides of the planet. I can’t seem to find anywhere that a distance check or planet side check would prevent the 3d agents from avoiding each other.


Heh, it seems like you’re right!
I took a look and indeed, this code is called in the “GenerateObstacleVOs”, but I didn’t add it in “GenerateNeighbourAgentVOs”.
I can’t test it right now but it should be quite the same code, using a Vector3.Dot with the current agent position and the “other” agent position.


Sooo, I think the problem is something else…

first off I changed your code snippit a bit as I’m not using ‘planetPosition’ and made it more normalized (and more optimized??)

if (vertex.ignore || (vertex.layer & collidesWith) == 0 || Vector3.Dot(position3D / position3D.magnitude, vertex.position / position3D.magnitude) < 0.85)

so now it limits it to obstacles which are much closer as opposed to just on the same hemisphere.

and I added something similar to GenerateNeighbourAgentVOs which ultimately I think is completely unnecessary after all…

            float tempfloat = Vector3.Dot((position3D - Vector3.zero) / position3D.magnitude, (other.position3D - Vector3.zero) / position3D.magnitude);
            if (tempfloat < 0.9)

With the debug.Log running it was apparent that GenerateNeighbourAgentVOs wasn’t even being called if they were on opposite sides or just not very close. This clearly gets taken care of before the neighbor.Count gets figured out. So this doesn’t seem to be the culprit as to what could be causing the wonky movement. If I have two or more agents right next to each other they work great, I see only minimal artifact in their movements. If the same two agents are far away from each other they have some pretty pronounced jitters in their movement… strange.

EDIT… Never mind… the culprit was I had threading turned on the RVOController3D. If threading is turned off everything works pretty smooth. Oops. Do you use threading on it at all? Thx


I do actually, I have one worker thread for the RVO Simulator 3D, and I set the Astar Path Pathfinding Settings Thread Count to “Automatic Low Load” (which uses 4 threads on my computer).


Yeah, I had actually played around with it a bit more and saw one thread on the RVO controller gave it a moderate speed boost whereas anything more cause some game breaking jittery movement. Curious-er and curious-er.


Hi all, I’m a little late to the party but thanks to everyone I was able to get the AI to follow an arbitrary path on a sphere! The only problem now is that the character snaps to the surface as it moves. I know that the solution involves having the character’s up vector match the surface normal of the planet’s sphere collider but I’m not sure how/where to do that. How have you all managed to get such smooth movement over the surface?


@aron_granberg That example scene showcasing curved/spherical world, is that only on the pro version?
Can’t find it at least! Thanks.
Edit: Ah, I see, it’s all using nav mesh which is a pro feature, and the spherical beta is also pro only.


Hi there,

I recently purchased the pro version of AstarPathfindingProject. I am very interested in path finding on the surface of a spherical object. I was wondering if the functionality for having an AI move on a spherical surface has been added to the project yet? Or if there is an example scene that is in the main build?
I have been following this thread, but it seems like the changes to the AIPath would now be different considering the code changes that have occurred since then. Is there an updated version of this spherical movement available?

I appreciate any help! Thanks.

Pathfinding on a Spherical Surface

I actually did update the code to work with the 4.1.11 beta. Not sure if there are any breaking changes with the official 4.1.12 release. I’ll see if I can get it to Aron to share when I get some time.


Thanks so much! That would be fantastic. If anyone could share, that would be very helpful.


I’ve updated the movement scripts to work with 4.14 Beta and sent it to Aron. As it includes Pro only code with the RVO avoidance please contact him to share it. Enjoy! There is an example scene and an icosphere mesh you can use.

Of note with the code. The GraphTransform.cs script has been modified and included to improve performance with the RVO3D stuff. I’ve also not attempted to update the RVO code as it was above my head, so it is the same as it was when @Raphael_Ninpo Rafael_Ninpo made it months ago.


That’s fantastic! Having RVO with the spherical movement will be such a boon. I will contact Aron regarding this. Thanks for the help! I’ll post back with results :slight_smile:


Also, this works on the 4.12 official release as well as the 4.14 beta…


Oops I just realized this doesn’t include the modifications to bake the spherical navmesh correctly. (You’ll notice that it is blue on top and green on the bottom at runtime) and it definitely affects pathfinding… I’ll see if @aron_granberg can help me figure out what else needs updated from 4.1.7 beta to current…


Ahhh gotcha. Is that not the “Recalculate Normals” setting?


There’s something more I think. If you notice when baked in editor without recalculate normals it is all blue but at runtime the navmesh will change back to blue and green… two separate navmeshe surfaces… almost like it rescans it with recalculate normals selected…