Question on Path Finding Implementations

Unity Engine
1

Hello everyone, I’m new to AI path finding in general and had a question on which (if any) of the following approaches might be best for my situation:

My Situation:
I’ve got some NPC boats that know where the player’s boat is located. I would like to have the NPC boat(s) move to the player’s position plus/minus an offset amount (essentially the NPC boat’s “ideal engagement range” (a min/max distance the ship prefers if at all possible).

What I’ve got right now:
I’m giving the NPC boat(s) the players position, then using Unity’s Nav Mesh system to actually find a path to that position. I’d like to keep the Nav Mesh system for the course plotting, and just worry about how the initial point of interest is determined if possible.

My ideas:

  1. Parent - Child Node System:

-When the point is determined, go through all of the highest level parents to check for min/max distance and line of sight, take all possible matches then go into children and make more checks (and so on for each level of child).

-I can see it working but it just seems like a lot of unnecessary checking, and it requires lots of high level parents to make sure that good locations are not passed on because the parent does not have LOS on the target.

  1. Get Local Nodes:
    -When the point is chosen, check for all Nodes in an area and choose between those.

-Simple, but possible issues with getComponent having to get lots of scripts in an area depending on density of Nodes.

  1. Nodes with Trigger Boxes:
    -Similar to 2, but here, when Nodes detect collision, they send their script to the colliding object, which would then send that as a array/list to the script that handles choosing a position.

-Similar possible drawback to 2.

  1. Raycasting:
  • When the point is chosen, make a raycast from that point in some direction, checking that the end point of the raycast is greater than the min distance. If it is, then choose a point from the min/max distance along the ray and make that the new adjusted target. If there is no good point, rotate a certain amount and try again until a good point is found.

-Would avoid Nodes all together, would need additional logic to make sure the raycast does not put locations too close to other geometry (nodes could avoid this by checking the area around them when created and removing themselves if that are too close to something).

Any ideas are appreciated, thank you for reading.

2

Have you considered playing around with this?

3

@ Okomikeruko:

I have thought of that, however as my picture shows (hopefully), I am worried about a situation where the NPC is blocked by terrain, but is inside of its ideal range preventing it from moving. And, even if it does move, it will hit its minimum range before it gets around the obstacle and just sit there doing nothing until the player moves. Using more logic would force the NPC to move to a more valid position (at least it should).

1859934--119338--example.png
1859934--119338--example.png1024×1024 61.8 KB

4

1860389--119365--blap.png
1860389--119365--blap.png800×600 5.84 KB

Try to raycast / linecast from your ai to your player. Use the hit information to determine the size of the obstacle and place a few nodes around the object. Raycast / linecast from the nodes to the player, if they can see the player, move to those nodes and then to the player. It’ll be a little game of…

Can the ai see the player? No
Node A can see the player!
Can the ai see Node A? No
Node B can see node A!
Can the ai see Node A? Yes
move the ai to Node B
move the ai to Node A
move the ai to the player

1 Like
5

What we do is plan a path to the position and continually check for line of sight and being within attack distance as the agent is moving to its destination. We only stop moving when both of those things is true. Trying to “guess” a destination based on a radius is incredibly unreliable (as you’ve discovered :slight_smile: )

1 Like
6

@ Tomnnn:

-Certainly a valid solution. I’ll keep it in mind if I end up using Nodes in some capacity.

@ KelsoMRK:

-Yeah, no arguments from me. At this point, I’m using the “raycast from the player’s location” method using a number of checks to ensure the position is safe, then doing more/less what you are doing to determine if the NPC moves to the spot and should stop / get a new point / etc.

In my case, I’ve got NPC boats (most of which need different logical checks based on their fighting style)…probably going to just end up compromising and finding logic that mostly works for all the ship types…