Pathfinding in a spherical world

Hi! I am trying to implement a simple pathfinding systeam (that would work with waypoints) to my game. The catch is that the world is spherical. I tried using Mid´s WayPointMaster, but it seems that getting the distance between the starting and end node doesnt work (since distance in the sphere doesnt work the same way as in planes).

I thought about building a graph with waypoints as nodes and try to find the shortest way, but cant find a way to do this.
Any ideas?

Ty for your time

 

A quite simple approach could be:
1. Calculate your distances with the haversine formula
2. Find your shortest path with the algorithm of your choice (Dijkstra, Bellman-Ford,..)

 

how would i get the latitude and longitud? This seems to be a solution to my problem

EDIT: I took a look at the haversine formula but im not sure how to use it :S. Can you help me plz?
Ty

 

You can specify latitude and longitude as two angles in the http://en.wikipedia.org/wiki/spherical coordinate system. On the Wikipedia page you'll find formulas to convert your Vector3 position into the necessary 2 angles and the radius.
Then store the two angles in a Vector2 and do the same with another waypoint. The snippet below will give you the distance between the two points (you have to set the radius variable also somewhere)

Code (csharp):

1.  
2. private static float haversineDist(Vector2 pos1, Vector2 pos2)
3.   {
4.     float dLat = Mathf.Deg2Rad * (pos2.x - pos1.x);
5.     float dLon = Mathf.Deg2Rad * (pos2.y - pos1.y);
6.  
7.     float a = Mathf.Sin(dLat / 2) * Mathf.Sin(dLat / 2) +
8.       Mathf.Cos(Mathf.Deg2Rad * (float)pos1.x) * Mathf.Cos(Mathf.Deg2Rad * (float)pos2.x) *
9.       Mathf.Sin(dLon / 2) * Mathf.Sin(dLon / 2);
10.     float c = 2 * Mathf.Asin(Mathf.Min(1, Mathf.Sqrt(a)));
11.     float d = radius * c;
12.  
13.     return d;
14.   }
15.  

 

Maybe is Very late, but you can use a native sphere in unity an get a nodes grid of size 20X20 from vertices, and use some generic pathfinding algorithm, by example I Use the A* algorithm and I Get my grid from the vertices of the mesh spherical.

 

Hello camilo3ds, can you show code or how you convert vertex to grid?

 

Just used NavMesh for navigation on spherical world with complex topology

It was quite tricky, so for now I have no power to record a tutorial, but be sure, I`ll do In any way, this all done with default unity tools, no plugins or third-party code. In short - I baked my planet 6 times, rotating different sides up. Then I manually added baked navmesh pieces, setting it`s rotation. And then connected it with off mesh links (sure, it must be more accurate for production).

 

hi. you can have here only one unit i guess. what about many fighting? i assume not this solution. I assume your sphere needs to rotate? not sure. how the units stay upwards? if i want them to stay upwards more precisely according to the gravity? i guess, i could create more sides? i will try.

 

Hi. It's just a usual NavMesh, so it can handle as many units as default one. One limitation - be aware about off-mesh links, it needs to be setup correctly, and you have to make a lot of them for many units.

In this solution, sphere rotation is possible, but very expensive, because it requires to re-load all the baked navmesh chunks. So, it's not the case.

Regarding staying upwards. It's just a basic implementation, for real game, you have to handle upward direction manually. For example, you can rotate each unit in correct direction inside LateUpdate message:

Code (CSharp):

1. void LateUpdate()
2. {
3. transform.up = transform.position; // this assumes your sphere center is in 0, 0, 0
4.  
5. // or
6. Transform sphereTransform; // assuming you have set this variable somewhere outside, and its a sphere center
7. transform.up = transform.position - sphereTransform.position;
8. }

This technique allows you to create as many sides as you want, and build, for example, toroidal world. Or you can create your world on an inner side of sphere.

 

This is just what I was searching for.

So it's possible. You're breaking your sphere into reasonable sections, rotating that section so it's at the "top" to calculate your mesh, rotating each mesh back into place, and then piecing them together. I'm assuming that flipping we're seeing is the jump from mesh to mesh.

And you're only doing it 6 times? Do you have the max slope at the highest setting?

I'd love to see more. Can I follow your progress somewhere?

 

Yeah, 6 times (like cube sides) is enough in my case. Max slope in this case would be 45 deg., but honestly I don't remember what exactly was set. I didn't moved this further, because it was just an experiment, so there is no progress exactly on this project - but you can subscribe my Games Garden youtube channel, I'll defenitely post any of my projects and experiments here.

 

In the manual pages, there is a link to some extra navMesh scripts. Why they're not automatically included, I don't know, but it's for doing just the same. Generating NavMeshes at different orientations, with a game object link to place and connect meshes. It's simple enough to run.