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?

15

Sorry for the delayed response here. Been busy.
I think it’s probably possible to run multiple requests manually, but it might get pretty intense on the performance as my game has pretty fast moving targets, so paths need to be recalculated relatively often.

The “target” isn’t as big of a problem as the start though. Maybe I can just use a heuristic to find a single node thats heading in “the general direction” of the target, then pathfind from there with a normal ABPath set using the custom destination code?

16

Let me try and get a better understanding of your needs- I think I’m trying to give advice on something I’m not fully understanding. When you say the start, what exactly are you envisioning? I’m assuming this is like, when you pull out on a street and you could go right, but left is faster because…squares and where it is in the block and what not lol

But when I think about that, when you do the pathfinding, wouldn’t it already find the best route, since you manually have connections that are one-way? Sorry for making you explain all this!

17

No no its all good. I understand it’s a little hard to wrap your head around the problem without a visual. So I drew something out.

Let’s say we’ve got us (green square) and our target (red star), and two lanes of traffic going opposite directions (orange circles are nodes, arrows are their connection)

Normally, any/all of our pathfinding processes will find the nearest node, then start searching there, which would launch us to the right regardless. We would probably end up going around the whole block to get to the red star.

image
image1268×297 3.55 KB

Ideally, if we could “start” from a few initial nearby nodes, there’s a good chance that one of those nearby nodes would be on the other side of the street, allowing us to pathfind straight to the red star directly… but this requires that we ignore the closest node in favour of a node with a better future heuristic… hence the need to search multiple start nodes.

image
image1085×268 3.42 KB

So lets say we solved that problem and are starting our search at a few initial nearby nodes so that it quickly finds the heuristic that heads in the right direction. There’s still another problem. Lets now imagine the target is on the same side of the road as us. We’ve determined the nearest node to the target is also right underneath it. Now we start pathfinding towards it, but instead we shoot right past it since none of the nodes on the opposite side of the road are the target node.

image
image1155×212 4.62 KB

Hence the need for a “distance” termination of sorts. In my case, I don’t need to be exact, as the vehicles do an intercept without using pathfinding once they’re near enough. In this above case, the intercept would take over as it passed the target, but what if the pathfinding deemed another route entirely to be quicker because this one overshoots?

I hope this helps illustrate the problem. I currently have “turnaround” connections that connect opposite lanes with a high cost, but it still causes vehicles to lose critical time going the opposite way first for a bit, stopping, turning around, and then going back, where it would be just better to head in the right direction immediately.

1 Like
18

My hero, legit :sob:

Hmmm yeah this is a fun one… but I am the undisputed king of taking wonky problems and finding wonkier solutions! So when I kinda think about this issue, I think about how we drive in the real world; we sort out things in a larger sense then give our solutions more resolution and detail afterwords. What if we apply the same logic here?

Maybe we have a recast graph- a notably lightweight one. We find our way to the destination using this macro-scale map, then use the path it finds to help shape our path for our more detailed path? We somehow, depending on how you want to set it up, get the general direction from one part of the recast path to the next and see which direction on the road best corresponds to that, follow our point graph path to the point, and if the destination is on the opposite side of the street… well we learned that during our recast graph’s plotting so we maybe just create temporary one-way connections to “turn in” to the destination, then remove them afterwords?

That is, absolutely, a roundabout (and could be costly) solution but I can’t think of any built-in tools for this specific situation. Does that work well for your project?

1 Like
19

You know, before implementing this A* project, I was actually doing something similar to that to optimize my own A* implementation. I thought, what is a road network if not just intersections linked by roads? I made each intersection a node, with a list of connected intersections (weighted by distance of course), and I navigated that first, then used the path output from that to reign in the nodes that my more detailed A* path traversed. If I go back to an initial check like that, I should be able to derive which side of the road the start and end are, and then choose the closest node that conforms to the correct side of the road maybe?

I’m also thinking about the assumptions I can make here and how they may help narrow down my needs. As far as I can think, the only vehicles that need to explicitly pathfind to a target will also not be following the laws of traffic. They are racers, or police, or whatever. Maybe I don’t even need to use the detailed node network for their pathing at all, and just use the larger network, and offset them to the right side a bit to try and flow with traffic. The rest of traffic doesn’t use pathfinding at all, they just pick nodes randomly as they go…

Regardless, I have a few options to try out from here, and I thank you both for helping me look into this!

1 Like