Hi, I’m currently working on a Tower Defense game on a spherical planet, and I’d like to use a NavMesh graph to handle the pathfinding, agents movement, collision, etc., and it seems to be the most powerful for accurate movements and pathfinding.
Probably write a new class extending NavMeshGraph because I need the scanning method to set all the triangles of the model to be walkable (and not only have the ones on the top half on the model: http://imgur.com/a/6gsgJ)
Also write a new class extending from RichAI because I need my agents to stay oriented according to the planet (always have their feet on the ground so they can walk around the planet), so maybe not using the gravity system or update it frequently so the gravity is always oriented towards the center of the planet.
What do you think about these ideas ? Do you think it’s possible to do what I’m thinking about ?
I just removed these lines from NavmeshBase.cs, line 885:
// Make sure the triangle is clockwise in graph space (it may not be in world space since the graphs can be rotated)
if (!VectorMath.IsClockwiseXZ(node.GetVertexInGraphSpace(0), node.GetVertexInGraphSpace(1), node.GetVertexInGraphSpace(2))) {
int tmp = node.v0;
node.v0 = node.v2;
node.v2 = tmp;
}
What do you think about this modification?
I’ll now try to write a class extending from RichAI to update the agent orientation or gravity according to where it is on the sphere.
I did some experiments with pathfinding on a curved surface recently: https://youtu.be/xMp-vnOR2yk
Basically what is required is the change that you made to NavmeshBase and something to set the correct orientation of the AI. I started with the AIPath script instead of the RichAI script because the RichAI script does a lot of complicated stuff behind the scenes that currently relies on there being a fixed ‘up’ direction in the world.
Here is my script:
using UnityEngine;
namespace Pathfinding.Examples {
using Pathfinding.Util;
/** Example AI for Example scene 18.
* This AI aligns itself to whatever node it is standing on (navmesh graphs only)
* which makes it possible to use it for things like spherical worlds.
*/
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;
}
}
}
Since you know it is a sphere you may want to change it to always orient itself using the normal of an ideal sphere, not the normal of the ground surface as that surface will not be completely smooth (you can see some small side effects of this in the video above).
Thank you for your answer, I’m glad I was on the right track with the change on the NavmeshBase script!
What you’re doing in the video is basically what I needed, so that’s perfect!
Is the version of Astar you’re using already available? I updated to 4.1.1 but I can’t find the MovementPlaneFromNode method.
Also, I was modifying some scripts (like RichAI or MovementUtilities) to try to adapt them from the 2D Y-up movement/funnel system because I think the RichAI is great and the Funnel simplification helps improve the movement a lot, so I’ll let you know if I manage to modify it the way I want.
Can you please tell me on which version of your project this code should be used ? I can’t seem to find the exact same chunks of code as in your pastebin, either on 4.0.10 or 4.1.1.
I’m eager to see this system working!
Nevermind, I actually found where to put the code approximately in AIPath.cs.
It’s working now, and it’s really great! You did an amazing job by making this possible, thanks a lot!
Is it possible to use RVO controllers though? I tried to add some but it doesn’t seem to be working properly because of the XY or XZ planes.
I made some changes to the RVOController script (I added a method to get the movement plane according to the current position on the planet like you did in yourAIArbitrarySurface script) but there must be more to change than just what I did (agents “slide” on the sides of the planet, probably because the RVO algorithms work on a plane).
It won’t be that easy to get RVO working though. RVO works in a plane. What would work would be to create a virtual plane for each agent and then calculate the neighbouring agents’ positions in that plane before doing the movement calculations. Unfortunately it would require some work to get to that point.
Maybe you could try experimenting with simpler avoidance behaviors like for example boids?
Yeah, I was starting to realize it would be harder than I thought to modify the RVO…
But I think it would be a better idea to use a “local” RVO system instead of using Boids.
I actually already made a pathfinding system and an AI on a sphere for the game I’m working on, and I encountered several problems.
Here’s the gameplay trailer, in which you can see some units moving:
To do the pathfinding system, I used an icosphere and a Dijkstra algorithm to link all the vertices together (no rocket science compared to navmeshes and such).
The AI was quite basic: it followed the path point by point (I actually rotated the agent around the center of the planet since it’s a sphere instead of translating it), and I used a basic avoidance system that consisted in doing a SphereCast forward, and only steering left or right to dodge an obstacle or another agent (which led to agents stuck in walls or between other agents, so clearly not the perfect solution).
Also, I bought the Behaviour Designer Movement Pack because there are a lot of interesting components, and I thought I could avoid using the RVO controller thanks to some behaviours, but it turns out that they kind of relies on it too…
So that’s why I think it would be a better approach on the issue to use a local plane for all the avoidance.
It could work to have, like you said, a plane for each agent (with the agent up vector as the normal of the plane), and project the positions of the surrounding agents/obstacles only this plane.
Do you have any advice or idea about how I could do that? Where could I implement this system? Which scripts to extend or modify?
Thanks again for your advice and your time.
Looking at your trailer (nice one btw) I am not sure if RVO-style local avoidance is what you want. You have a lot of vehicles and RVO really isn’t that well suited to vehicles as the algorithm relies on agents being able to move in any direction at any time. It often looks odd if vehicles start to move sideways.
What you could try is to use a combination of your previous movement behavior together with some pathfinding influence. When your units stop they could add a penalty (say +10000) to the ground below them (just a few nodes around the character. When they start to move again (before they request a path again) you can remove that penalty. This should cause other agents to try to find paths around the existing units, but if necessary they will fall back to trying to move through them. You will have to very careful that you remove the penalty from the same nodes that you added the penalty to though, otherwise you will end up with residual penalty on the map where units have forgotten to remove their penalty or even some cases where too much penalty has been removed.
This type of pathfinding will likely not be perfect either. You will have to complement it with some other kind of basic movement behavior like the one you already had to get nice movement.
That’s true that it may be weird to see vehicles move sideways, but we intent to partially change that so it might actually not be that bit of a problem.
The idea of the penalty is good, but the grid we’re using might be too bit to work accurately, and we might end with agents not going through a small path because of that, and we want our units to stay on the main route we send them on, not go around the planet to find another path.
Anyway, I have some great news: I managed to get your RVO algorithms to works on a spherical planet!
I basically copied severals scripts of yours and changed them to work in any plane, not either XZ or XY.
I had to create a quadtree by agent though, each quadtree being oriented according to the up vector of each agent (basically).
I’m actually pretty surprised it works so well, I’ve been starting from scratch a few times before managing to make it work, and it worked on the first try after I finished refactoring and correcting some script errors.
It currently only works with a SimpleRVOAI type of script, I intend to make it work with AIPath and maybe even RichAI if everything goes well.
It also currently only works on the main thread because of some utility classes I made for all the 2D to 3D transformations, and only the main thread can execute some specific code I wrote, so I’ll have to figure this out eventually.
I can give you my code if you want, I think you’d be way faster than me if you want to keep on working on that part
Since it is a very niche requirement for RVO on a sphere, I don’t think I will integrate it into the main package (it would probably lead to more complex and slightly slower code in the common case). But if you want to post the code here (or upload it to github perhaps) so that others who have the same issue can look at it, then by all means do it
Just make sure you don’t upload all the RVO files (I doubt you have made changes to all of them) as the RVO system is only included in the pro version, not the free version.
I think the RVO can actually work on more complex shapes than sphere, because it’s based on the agent normal, so I believe it could actually work on your “peanut”-shaped mesh.
I actually modified most of the RVO files (and planning to modify some more, like the RVO obstacles), and I didn’t post any code because it was not included in the free version, as you told.
Maybe I can email you the files so you can decide if you want to post some of them, or even if they’re worth using for yourself.
I’m looking for a solution to path finding on a spherical world as well which brought me here. I haven’t purchased the plugin yet although I would be happy to purchase the pro version assuming it could be used in this way. Thanks for sharing your progress with the modifications Raphael, that’s very cool of you. Assuming I purchase the pro version, is there a way I can get the modifications so I can hit the ground running?
Hey I don’t want to be too impatient here but I just wanted to bump this in case it got lost over the weekend. I was hoping to get started on this as soon as I can.
