## Navigating around concave 3d shape (efficient steering behavior)

Hello,

I am currently doing some AI-programming for a computer game and I would like to ask, If anyone has an opinion or preferably a (better) solution to my current problem. I have searched through various other forums and papers, but I could not find a solution that exactly fits my problem.

English is not my first language, so please bear with me and ask for clarification, if necessary.

The context of my problem is efficient steering behavior in 3 dimensions (think of spaceships and asteroids). Let’s imagine that I have a start point (my current position) and an end point (where I would like to go) and there is a 3d-voulme in between, it is comprised of triangles (clockwise defined), which are in turn comprised of 3d-points.

Now the question is: “What is the next point that I should go for, in order the quickly reach the desired end-point?”

Here are a few conditions that also have to be considered:
a.-the “Spaceship” is a point, it has no volume of its own
b.-the obstacle (asteroid) can have a concave shape
c.-the obstacle may be constantly moving or rotating therefore the calculation should be
efficient and fast, so it can be repeated in quick succession, however the shape of the obstacle is constant
d.-it is not necessary to include the movement-over-time of the obstacle in the calculation, the obstacle can be seen as static
e.-it is not necessary to calculate the entire path around the obstacle, only the next “waypoint”
f.-the next waypoint and the resulting path of the spaceship does not have to be perfect but only reasonably good
g.-it is possible that multiple obstacles collide and “phase” into each other, forming a bigger obstacles with two or more intersecting 3d-volumes

I experimented a lot with graph-based solutions, but (depending on node-density and -positioning) they are ether to slow or give ugly paths. Also they are a little bit overkill for my problem since I don’t need the entire path but only the next waypoint. The entire path would be useless anyway, since the obstacle may be moving.

My current solution looks like this:

I calculate all the edges of the obstacle that define the surface-area that can be seen from my start point (as if it were a light source). Then I calculate the point on each such edge that is closest to the direct line from start to finish (mostly it is one of the endpoints of the edge, but not always). Of those nearest points, I choose the one that has the smallest angel to the line from start to finish.

This works exceptionally well for convex obstacles and if condition g. is omitted.

However, how can I do this with concave shapes?

I imagine it could work with some form of 3d-line-clipping where I somehow calculate the silhouette of the obstacle as seen from my start-point. However, I cannot work with projection to a 2d-plane, since it might be possible, that the start-point is already inside the convex-hull of a concave obstacle. For example, the start-point might be in the center of a big donut-shaped obstacle.
I’m currently trying my luck with some form of 3d-silouett butt I think there should be a better and simpler solution.