Unity Nav Mesh : find nearest position on a circle

Question

Imagine that an archer needs to be at least 3m away to be able to shoot his target, but he cannot be further away than 10m. So he must find a valid location inside this radius (in 3d of course).

So, what I need is a method that returns me the nearest (reachable) point on my nav mesh with a clear line of sight that is inside the radius.

I was thinking about always using the cirlce edge as an starting point for my calculations. Since this should always be the closest point. But this does not work in this example:

Since there is no direct line of sight at the cirle edge I cannot take it as an starting point.

I was also thinking about just picking random points (like 5000), checking if they have line of sight and checking the distance to the archer. But this is of course a horrible solution.

How can I find this magical point?

(I don't need a script but an idea :D)

Edit: It is not required to have a valid path to the target. If e.g. a river is in the way the archer wont be able to pathfind to his target. But he can still shoot over the river. Meaning he can find a valid spot.

Talesman

What's the use case of such algorithm ? You want to spawn enemies at this position ? How many positions would you need per frame ? Is this a 2D plane or there's elevations such floors, hills ? – Crayton

Interesting question. Where you wanna go in this case? i.postimg.cc/7hTL2qyN/Archer-Another-Case.png – Thomson

@Notaprivilegeduser this is a normal unity nav mesh -> 3D space with elevation. There are gonna be about 5-10 Enemies with a few different targets. – Talesman

@FakeFish it should take the shorter route. (lengthA vs lengthB) the shorter path will be selected. It should be A in this example – Talesman

@GoldenDremora docs.unity3d.com/Manual/nav-AreasAndCosts.html#Area%20Types this should probably resolve river-related aspect of the problem. Is it true? – Thomson

Answer 1

NavMesh.SamplePosition will return you the closes point on the navmesh with in a radius (your minimal attack distance).

1. Get path to the closest point to the target (if reachable is the target itself)

(1b. If that doesn't work you could always sample n closest points in a circle around the target)

2. Along this path (within the attack range): Raycast every step to check visibility

Irita

Answer 2

Set the destination of the player's navmesh to the center of the sphere.

The following actions are performed every frame:
Raycast from the center of the sphere to the current position of the player. If it directly hits the player without any obstacle between them, the player has reached the nearest position with a clear target.

Socrates

This wouldn't work because it is possible to have an obstacle, which leaves the LoS intact. E.g. the archer is standing at the edge of a cliff and his target is on the other side of the cliff. He wouldn't even be albe to pathfind to him but since he can shoot from this position its a valid one. – Talesman

I didn't quite get it, can you add a rough image of this example? – Socrates

I have edited my post. There is an new picture now – Talesman

Right, I understood where I have gone wrong – Socrates

Answer 3

Not familiar with navmesh but I what I would try:

1. Get the Plane P:

Easy as you got the normal direction and a point.

2. Get all the points to the side of the plane of interest. Lookint at the enemy in this case plane's method GetSide. Thats just a dot product, so cannot be cheaper.

3. Then you can filter out the points that do not have a valid target shoot due to an obstacle with some raycasts.

4. From those, finally choose the one that is closest to the enemy (AI) position, taking the min Vector3.sqrMagnitude. This is the lowest squared length of the distance, its much cheaper that the distance itself because square roots are not efficient, so when need biggest or shortest distance to use the sqrMagnitude is good practice. Instead of the straight distance, of you have the path distance to the point, that would be the one to look for :)

5. Guess that if no point is found that meets this requirements the you'd need to check the rest of the points of the mesh.

Carbazole

How do you plan on getting all the points? Like in an array? – Socrates

not familiar with nav mesh. Just dropping the idea. An array would be the best – Carbazole

Do you have any idea about the length of this array? I dont think this works incase if the area is too large – Socrates

Answer 4

You could maybe use your "horrible solution" in an Monte-Carlo approach:

• every frame (if target cannot be shot from the current position):
  1. sample just e.g. 10 random points around the target (instead of 5000)
  2. cast a ray from each point to the target
  3. for all points that did hit: perform pathfinding from the archer to them
  4. if one point is a nearer than the "target point last frame" make this point the "target point last frame" and navigate there

This may introduce a jitter but should yield an acceptable result after just a few frames.

To improve this, you could use a heuristic to bias sampling the random points. Like "first check in quarter of circle pointing towards archer".

Avocet

Answer 5

1. Create a ghost target at the same place as your original target. Let's suppose, our ghost is invisible for human player and can move infinitely fast. Ghosts can do that!
2. As ghosts can fly, ask your ghost to fly towards your archer. A river shouldn't be a problem. To distinguish different types of obstacles (walls, water) area costs should be helpful
3. Get a path built by navigation and pathfinding AI (should be accessible immediately after the start of the ghost's movement)
4. Split the path into linear segments.
5. Start moving the ghost across the path towards the archer (point by point), while the ghost and the target can see each other, and the distance between them is less than firing range.
6. As soon as any of the conditions from (6) is false, you already know the segment, the fire point is on. Well, previous point could be a decent fire point already, but imagine that there are no obstacles at all. In this case our path is a straight line segment which beginning coincides with the target position. Obviously we need to be more precise. By the way, let's call the segment - fire segment
7. Finally to find the fire point within the fire segment we could use bisection with tolerance ε = one_archer's_step. We should keep checking the same things we did in (5) for each bisectional point

Thomson