A* Pathfinding Project

Partial pathfinding


#1

Okay so i have my road network graph that consist of point nodes.
And i also use grid graph for normal terrain. My agents move on grid normally and switch to road when player tells them to. It works great when road network is one interconnected blob. Problems start if i have road that is far away from others and thus is isolated(in road graph, i mean, agents can reach it ok by grid).

So what i need is to get as close as possible by road instead of reaching destination, hence the need forpartial path. Getting closest node is not an option because i’m either getting wrong point (if i search for a node on road) or i will ignore road if it try to find path on my grid graph, which is not desired behavior, too.
I tried to set calculatePartial = true; on ABPath before feeding it to seeker, still getting error paths instead of partial.
I know calculatePartial docs say its at work currently, but is there any alternatives?

Thanks.


#2

Is it important to you that the player decides if an agent should use the road or grid graph?

I do believe it’s possible to create connections between your grid graph and point nodes. So the AI agent can automatically take the road ( even for only a small portion of the route ) if it finds the cost to be lower than only using grid graphs.

I have never tried to set this up myself. But this is how the NodeLinks work.


#3

Yes, it is important for player to specify this.

Looked at docs, it seems the NodeLinks are intended for use with point graphs only since they need transforms (and thus gameobjects) to specify what to link, plus they also use point nodes internally in the code. So even if we disregard my grid graph for a second, my road graph has its own generator and only use point nodes internally, there is no gameobjects to which a can attach the links to begin with.

Well i guess i can try to code road <–> grid links myself, though having a way to simply calculate partial paths would be better. :roll_eyes:


#4

Hi

By default the pathfinding system will route to the closest node that the player can reach.
However there is a distance limit, it needs to be closer than A* Inspector -> Settings -> Max Nearest Node Distance. You can increase that value to increase the distance limit.

If you constrain the agent to use the point graph then then tell it to move to to some other part of the world it will find the closest point graph node that it can reach and pathfind to it.


#5

Okay, i will try that. Thank you.


#6

Finally had time to try what Aron had suggested, but i am either don’t understand how it works, or it actually doesn’t work.

Does my graph needs to be interconnected no matter what for partial pathfinding to work properly? What i mean by this is that when i have isolated roads, they are completely isolated and do not even have unwalkable links between them. So technically they are independent graphs except that they share single graph slot in A* inspector. Can this be a problem maybe?


#7

Hi

It does not need to be interconnected.

So what I’m suggesting is that

  1. If your agent is currently configured to traverse only the road graph
  2. And you request a path to somewhere far away
  3. And your A* inspector -> Settings -> Max Nearest Node Distance is set to a high enough value that the agent can reach a node which is within this distance of the destination.
  4. Then the path will be to the closest node on the road that it can reach.

#8

Well, what i actually observe is that paths fail and agent is not moving.

After enabling drawing of search tree in A* inspector as well as switching to wireframe camera in unity for thing to be a bit more evident to eye i guess i found why this might happen. When i order to move to “wrong” destination, search tree stuck showing as if i still used grid graph:

Yet when i order right one, i see this:

I use mix of AIPath destination setting(for regular orders, on grid) and seeker with its StartPath method for roads. Here is example of how i force agent to move on roads, btw:

Path roadTransit = ABPath.Construct(ClientTransform.position, (Vector3) marchInfoDestination.node.position);
roadTransit.nnConstraint = marchRules;
astarAgent.canSearch = false;
astarSeeker.StartPath(roadTransit, null, RoadsMask);

The interesting part is that if i set road asonly traversable graph in seeker instead of specifying graph masks in both NNConstraint of my path fed to Seeker.StartPath() as well as giving said to roadmask to start path method as well, it seems to actually calculate partial path. I guess while writing this post i sort of found the solution (lol), but why the approach of using Path+NNConstraint+Seeker.StartPath() is not working too?


#9

Hi

What is your marchRules class? You may want to create a PathNNConstraint instead of a pure NNConstraint, otherwise some features will be disabled.


#10

My marchRules field is pure NNConstraint
Okay, i will try to use PathNNConstraint instead


#11

PathNNConstraint is worked, indeed.

Thank you!