Finding multiple non-overlapping paths

Is there an ideal or suggested method for finding multiple non-overlapping paths in a GridGraph? Preferably in a deterministic fashion. Currently it seems to me like I’m going have to either set the pathfinder to singlethreaded only (since each path needs to calculate and then claim its path nodes in the grid completely before the next path can run) and occasionally manually push items to the front of the work queue, which will be bad for my others graphs in the scenario which don’t have this restriction and could safely use multiple threads; or devise a separate work queue just for requests on the specified graphs which, while it would allow me to use multiple threads, seems potentially over-complicated for the task at hand. Hoping that I’m missing something already built in that might help with this.

For some situational context: I am using gridgraphs to calculate paths for connections on a circuitboard-esque editing surface, so no two paths can intersect on any nodes, and the editor cannot determine placement of items in some situations unless it is verified that all connections to it can also find (unique) paths to the new location.

Thanks!

Hi

To solve that problem optimally is unfortunately a very hard problem (NP-Complete if you know that term).
It can be reduced to this problem: https://en.wikipedia.org/wiki/Multi-commodity_flow_problem
That can usually be solved very well using linear programming, e.g using the simplex algorithm. However those algorithms are well outside the scope of this package.

If you are just looking for an approximation that may or may not be optimal you should be able to use the ITraversalProvider to make sure that future paths do not use any of the same nodes as the paths that you have already calculated. The paths have to be calculated sequentially, otherwise there is no way to ensure that they do not use the same nodes. One could calculate them in parallel speculatively and fall back to sequential calculation if there are collisions, but I don’t think that would help much.

I wrote an example for this use case. Here’s some copy and paste from it (it is not included in the current documentation, it will be included in the next version): [UPDATE] this is now included in the docs on this page: https://arongranberg.com/astar/docs/circuitboardexamplecs.html

This example shows how to use the Pathfinding.ITraversalProvider interface to generate paths like on a circuit-board.The image below shows a test case when using the script to calculate 4 paths on a small grid. The visualization of the paths has been improved manually using an external photo-editing application.


The code has intentionally been left simple, so very little error checking and special case handling is done.

Note that finding paths on a circuit-board in an optimal way is a very hard problem (NP-Complete). For further information about that, see https://en.wikipedia.org/wiki/Multi-commodity_flow_problem

Attach this script to any GameObject and fill in the ‘items’ array with the start end endpoints of each path.

See Also Utilities for turn-based games, ITraversalProvider

using UnityEngine;
using System.Collections.Generic;
using Pathfinding;
public class CircuitBoardExample : MonoBehaviour {
    [System.Serializable]
    public class Item {
        public Transform start;
        public Transform end;
    }
    public Item[] items;
    class Blocker : ITraversalProvider {
        public HashSet<GraphNode> blockedNodes = new HashSet<GraphNode>();
        public bool CanTraverse (Path path, GraphNode node) {
            // Override the default logic of which nodes can be traversed
            return DefaultITraversalProvider.CanTraverse(path, node) && !blockedNodes.Contains(node);
        }
        public uint GetTraversalCost (Path path, GraphNode node) {
            // Use the default costs
            return DefaultITraversalProvider.GetTraversalCost(path, node);
        }
    }
    
    void Update () {
        var traversalProvider = new Blocker();
        for (int index = 0; index < items.Length; index++) {
            var item = items[index];
            // Create new path object
            ABPath path = ABPath.Construct(item.start.position, item.end.position);
            path.traversalProvider = traversalProvider;
            // Start calculating the path and put the path at the front of the queue
            AstarPath.StartPath(path, true);
            // Calculate the path immediately
            path.BlockUntilCalculated();
            // Make sure the remaining paths do not use the same nodes as this one
            foreach (var node in path.path) {
                traversalProvider.blockedNodes.Add(node);
            }
            // Draw the path in the scene view
            Color color = AstarMath.IntToColor(index, 0.5f);
            for (int i = 0; i < path.vectorPath.Count - 1; i++) {
                Debug.DrawLine(path.vectorPath[i], path.vectorPath[i+1], color);
            }
        }
    }
}

I had not considered this problem as isomorphic to MCF before; excellent observation! Thankfully I do not require an optimal solution to this, simply one that is at least somewhat performant, produces a relatively repeatable that makes sense to the user, and of course isn’t too terrible to maintain. ITraversalProvider is precisely the kind of thing I was looking for and I’m not sure how I never noticed it when looking through the code! I think it will be a huge improvement over my current implementation which relies heavily on registering graph updates for execution in between each individual path (to claim the nodes by disabling their walkability) and enforcing some order to ensure that any other paths outside of the ‘set’ don’t get computed until it is safe to do so.

I am still left with the downside of having to run single threaded, which is fine for the graph in question but less than ideal for the other graphs that do not have this requirement and could benefit from additional threads, but I think that’s an acceptable tradeoff that’s not worth finding a solution for at the moment.

Thank you for the very thorough response; incredibly helpful! And excellent product, by the way.

You do not have to use a single thread for all pathfinding code. The only constraint is that these paths are calculated in sequence, not in parallel. That is accomplished in the above code using the BlockUntilCalculated method call (but you don’t want to calculate everything in one frame you can use path.WaitForPath instead using a coroutine).

Followup question for you on this! While overriding the traversal provider did allow me to get most of the functionality I wanted, I still have a couple issues. Currently one of my last remaining annoyances is in relation to diagonal connections on the graph. Normally in an eight-way graph, I expect (and desire) that I should not be able to path from a node to its upper-right neighbor (offset 5, by the numbering you use in code) if offsets 1 and 2 are both already occupied. However, since I am using custom data to inform the traversal provider, I am not doing connection updates/recalculations as usual, so these paths wind up being valid and causing my “wires” to cross over each other.

So, I’ve been trying to figure out how best to add this logic to the traversal provider and haven’t had much luck. The CanTraverse method, as expected, accepts the argument for the node being traversed “to”, but I’m not seeing how to find the node being traversed “from” in the path argument. Without this, it seems impossible to reject diagonal connections. Am I missing the information somewhere, or maybe taking the wrong approach entirely? (I do have another solution involving doing the walkability/connection updates as usual, but there are other issues with that, so I’m still preferring this one for now)

Hi

Currently this is not possible using the ITraversalProvider interface.
You will have to modify the GridNode.cs class. Find this line:

 if (!path.CanTraverse(other)) continue;

immediately after that, add a new call to whatever method you want to use to validate the connection.
The current node is “this” and the node that we are moving to is “other”.

That seemed to do it; thanks! My walkability-based solution would have required changing some of the code to make maxNearestNodeDistance graph-specific anyhow, so I suppose having to changed things in the pathing classes is kind of unavoidable either way.

1 Like

If I am right, the solution proposed can - and to be exact - lead to no paths found when paths exist because it is dependent on the order the paths are used. In the example image, imagine on path should go from top to bottom and one path uses all cells of one row (even if not required)