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);
}
}
}
}
