How can I implement pathfinding that avoids obstacles on a spherical planet?

Question

Hi everyone, I am trying to make the enemy go around the planet, towards the player (I am using Faux Gravity for the movement logic).

I tried using Unity's NavMesh tools, but because this is not a flat mesh, they didn't really get the job done;

How can I make my enemies go around the planet towards the enemy in a physics based way?

I thought about calculating the a direction from the enemy towards the player and then moving the player towards a vector perpendicular to the planet's surface (in this case transform.forward) like so:

This way I can correctly move enemies towards the player, but the AI doesn't have any notion of any possible obstacle it should avoid.

I am specifically looking for some sort of A* algorithm, that would work on a spherical surface, like the one of a planet.

Is there a better way to do this?

Answer 1

I am specifically looking for some sort of A* algorithm, that would work on a spherical surface

The name for an A* algorithm that can work on a spherical surface is: A*

You don't need to do anything special to make A* work on arbitrary spaces. That's already its jam. Anything you can represent as a graph of connected sites/regions will work just fine — whether those sites are on a grid, an irregular web, in 2D, 3D, 4D or more, even non-spacetime dimensions (see past notes on pathing through dimensions of bomb inventory / key debt), or yes, even on a sphere.

To make such a graph over the surface of the sphere, a popular method is to take the grid of a wireframe unit cube and project it onto the sphere, either by normalizing the position vectors, or "spherifying" them.

You could also take your current planet mesh and create a graph node for each face or vertex, and a graph edge for each mesh edge joining them. Just make sure you maintain connectivity wherever you cross a normal/UV seam.

I'd avoid a latitude-longitude based grid here, since the pinching at the poles makes the distribution of points very uneven. But if your topography lets you park the poles out of the way in non-pathable terrain like a mountain or ocean then it might be OK. ;)

Now that you have a graph of connected sites across the sphere, you can mark those occupied by obstacles as obstructed, then search the graph for an unobstructed route to your goal using the usual A*, or any of the variants of it you like.

Your heuristic function can still be Euclidean distance (ie. the length of the spherical cord joining two points), since all that's required of the heuristic is that it never overestimates the distance.

You could also use arc length as your heuristic: acos(dot(start, end)) (where start & end are unit vectors in the respective directions). This takes curvature into account so it's a tighter bound and might result in better prioritization. If you go this route, you should measure your graph edge lengths in arc distance too, to ensure they never take a shortcut smaller than the heuristic predicted.

Answer 2

There are many options but projecting vectors is a common and efficient way of constraining movement - possibly the most elegant way.

Another possible solution - have a dummy transform at the center of the sphere as a parent of the enemies, and rotate that dummy transform using unity's built in quaternion rotation functions. However this way seems less flexible to me, since it only works with a perfect circle and is less able to deal with obstacles. I think you're on the right track.