Search multiple closest nodes to start (and end)

General
1
  • A* version: 5.3.3
  • Unity version: 6000.0.32f1

Hey hey, I’m using a custom graph that uses Point nodes. I just needed to manually decide connected nodes for lanes in my road system. The issue I’ve run into though, is the path generated can be extremely different depending on which node is designated as “closest” to the start and end point. For example…

There are lane change connections, but in intersections some lanes can only go certain directions.

image
image1265×545 51.9 KB

If the start position and end position line up on the same side of the street, I can get a nice quick route.

image
image1268×536 59.7 KB

But if the start (or end) happens to be on the other side of the street, all hell breaks loose.

image
image1278×679 76 KB

Which can get even worse if I allow a high cost turnaround connection between opposite lanes.

image
image1070×475 56.9 KB

Ok so my question is: Is it possible to have the start point connect to a few nearby nodes within range, and start searching through those, instead of the “SINGLE” closest node. (And likewise with the end point)

EDIT:

Ok, part of the problem was my distance calc not reaching the full * 1000 it needed for the heuristic, but my original question about multiple or “fuzzy” start and end regions still stands.

2

Interesting situation :thinking:
Can you show the point graph itself? Or the nodes rather?

3

I’ll have to post a picture of the gizmos for the underlying node graph that the astar graph is generated from once I’m off work, but in the meantime, it’s pretty straight forward.

Each lane on the road is just a string of one-way nodes with multiple branches in intersections. There is also connections to adjacent lanes that are higher cost so that cars can change lanes to get into a lane that turns where they need, and a very high cost connection to the other direction’s lanes so that a car can turn around with a U-turn if absolutely needed.

The u-turn connections can help a lot, but still produce undesirable results if the start point’s closest node is in a lane going away from the goal.

4

image
image1160×688 84.2 KB

The nodes are yellow spheres. Main connections are yellow lines and they follow the road, right side drive.
Orange lines are lane-change connections.
Red lines are “U-Turn” connections.

5

I get this now! The visualization helped a lot, thanks! But yes, there is.

So it looks like what you’ll want to do is use NavGraph.GetNodes to get all the nearby nodes or just NavGraph.GetNearest for the next closest node (depends on how you want it to work really). From there you can use GraphNode.Connect to link them as you wish. IIRC, you’ll also have to use AstarPath.UpdateGraphs within AddWorkItem to actually have it “save” the graph:

6

Hi

The MultiTargetPath can be used to search from a list of given nodes to a single target, or from a single start point to multiple targets. It cannot search from multiple start points to multiple targets, though.

However, you’ll need to find the relevant start nodes yourself.

7

This should work! Is there a way to maybe just terminate the pathing once its within range of the end position instead of trying to path to a specific end node?

8

See PathEndingCondition - A* Pathfinding Project

1 Like
9

Perfect. Y’all are fantastic! :smile:

10

@aron_granberg

Hey again, just finally got around to trying to implement this and…
Pathfinding error: Multi target paths cannot use custom ending conditions

Looks like I can’t both use multiple start locations with a “ranged” end position.

I also noticed that when using the Multi target paths with multiple start points, it flips the direction, and traverses my nodes backwards (wrong side of the road) because it actually starts at the destination.

Any idea what I can do to achieve the same effect?

11

Mind posting your code for me to review/try? Trying to test it on my end but I’m certainly doing something wrong :thinking:

12

Sure thing, this is essentially all it is:

private void RequestNewPath()
{
    if (!target || !target.PossessedObject) return;

    if (_path != null && _path.PipelineState != PathState.Returned)
        return;

    _nearbyNodes.Clear();
    AstarPath.active.data.GetNodes(FillClosestNodes);
    
    _path = MultiTargetPath.Construct(_nearbyNodes.ToArray(), TargetPosition, null, OnPathCalculated);
    var endingCondition = new NearbyEndingCondition(_path);
    endingCondition.distanceToReach = _interceptDistance * 0.5f;
    _path.endingCondition = endingCondition;
    
    AstarPath.StartPath(_path);
    
    _cachedTargetPosition = TargetPosition;
}

private void FillClosestNodes(GraphNode thisNode)
{
    if (thisNode == null) return;
    if (((Vector3)thisNode.position - Position).sqrMagnitude < NEARBY_NODE_DISTANCE * NEARBY_NODE_DISTANCE)
    {
        _nearbyNodes.Add((Vector3)thisNode.position);
    }
}
13

Ah, yeah I got the same note about MultiTargetPath not being able to use ending condition. I was confused because the documentation shows it being available under the class, but now I see that MultiTargetPath derives from ABPath.

Now, I’m thinking maybe you can use MultiTargetPath to find the path there, then set an ABPath to that node and use the ending condition that way? I’m not sure if that’d be “hacky” or not though…

14

Right. I forgot about that.
Yes, that’s unfortunately not possible due to how the MultiTargetPath works. It might be possible to change the code to support it, but it would only work for some use cases, and it would be a non-trivial change.

Is it possible for you to run one path request for each potential target node?