Find shortest end point

General
1

this is a grid graph, 0 is a unit, 5 is a unwalkable node, others are walkable.

  789
0 456
  123

when requesting a path from 0 to 5, since 5 is unwalkable, it will first find a nearest walkable node. which result maybe 1~9 randomly. maybe pick worst result 6.

Is there any way to ensure pick shortest path (4) as end point ?

2

seems could add a GetNearestAll function that return all nestest nodes that has same cost. then use a multi target path to find shortest one

3

Hi

That specific edge should already be taken care of. If the regular path sees that the end node is an unwalkable grid node, it will consider all adjacent ones to be valid destinations. At least if you use version 4.x. Is this not working for you?

4

I tried many times and find that if obsticle is more than one grid, problem still happens

lets assume that x and * is unwalkable node, s is seeker, others are walkable.

  ▲
 xxx
 x*x
 xxx
  ▼

  s

when start a path to center * node, it will always go to ▲, even there is a much closer node ▼

I made a simple reproduce project, run and click anywhere on terrain, sphere will move to clicked node.
when clicking center of cube obstacle, it will go top.

My project.zip.txt (38.9 KB)
(rename .zip.txt to .zip)

5

Hi

In your code you have

var target = (Vector3) AstarPath.active.GetNearest(eventData.pointerCurrentRaycast.worldPosition).node.position;
FindObjectOfType<AILerp>().destination = target;

That will make it first find the single closest node to the destination (which in this case turns out to be the wrong node) and then it assigns that as the destination. Skip the GetNearest step and I think it will work.

6

nope. GetNearest without secondary parameter is NNConstraintNone. it don’t care about walkable and will return the center unwalkable node.
I have tried log that value and ensure it’s correct (0.5,0,0.5)

7

Hi

What I can see in the project is that the obstacle is a 3x3 block of unwalkable nodes. Not a single unwalkable node.

image
image905×625 62.3 KB

There is a special case implemented when the obstacle is a 1x1 unwalkable node (like what you described), but it doesn’t work for larger obstacles (and often you wouldn’t want that either).

What you could do is a simple trick. Move the destination slightly closer to the agent’s current position. That will bias it so that it will more likely find the node which is on the closer side of the obstacle.