2
$\begingroup$

I am making a game in Unity3d and I need a pathfinding algorithm that can guide enemies towards the player on a 3d surface. The problem is that the 3d surface can take any shape, so it can be a 3d sphere, cube, torus and many more shapes.

I tried using A* but for that formula I need the distance between the two points, and since the object is curved I cannot get that so easily. I found that you can use the Haversine formula if its a sphere, but that won't work on a torus or a random 3d shape.

I want this kind of result except with every kind of object: https://www.youtube.com/watch?v=hvunNq7yVcU

Is there a way/algorithm that I can use to get that result? I know there is somthing called nav mesh but I need to program it myself. Also I cannot find how nav mesh approaches this dilemma. I am going to use the triangles of my object as nodes.

So my question boils down to:

Does anyone know a algorithm for pathfinding that works on any 3d surface?

Thanks in advance.

Improve this question
$\endgroup$
2
  • $\begingroup$ I'm not sure what you're looking for. You already know that A* works on any 3D surface but you don't know how to calculate distance. Are you looking for a pathfinding algorithm or a way to calculate distances? You can just use the straight-line distance between the two points (ignoring the surfac) as your metric in A*. $\endgroup$
    – David Richerby
    Feb 24, 2016 at 16:42
  • $\begingroup$ Also, if the triangles of your object are the nodes, you can just calculate distances locally: make a weighted graph whose vertices are the triangles and that has an edge between two adjacent triangles, with the weight of the edge being the distance between the centres. Then use any search algorithm on that weighted graph. $\endgroup$
    – David Richerby
    Feb 24, 2016 at 16:45

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.