5

I conduct a path finding library. QuickGraph, open graph library, fits all my requirements but I have met one problem. I need the shortest path algorithms to skip edges which are impassable by the current moving agent. What I want is something like this:

Func<SEquatableEdge<VectorD3>, double> cityDistances = delegate(SEquatableEdge<VectorD3> edge)
{

    if(edge.IsPassableBy(agent))
        return edgeWeight; // Edge is passable, return its weight
    else
        return -1; // Edge is impassable, return -1, which means, that path finder should skip it

};

Func<VectorD3, double> heuristic = ...;

TryFunc<VectorD3, IEnumerable<SEquatableEdge<VectorD3>>> tryGetPath = graph2.ShortestPathsAStar(cityDistances, heuristic, sourceCity);

I could imagine solving this problem by creating a copy of graph and deleting the impassable edges, but it is unnecessary waste of computer's resources. Could one, please, hint me on how to solve this problem? Or is there no solution and I should update the source?

Aditya
  • 1,693
  • 19
  • 27
PanCotzky
  • 564
  • 2
  • 5
  • 12
  • 6
    A quick hack would be to make the impassible edges have a weight that is larger than the total weight of the real shortest path. The A* algorithm will always move paths containing your "impassible" edges to the end of the priority queue and will find the real shortest path. The disadvantage of this approach is that *if every path to the goal traverses an "impassible" edge then the hacked up algorithm will choose a path, rather than doing the correct thing and failing*. – Eric Lippert Jan 13 '13 at 17:11
  • 2
    @EricLippert A workaround around that workaround could be that you'd check the resultant path length, and if it's greater than your "impassable" edge weight, you'd expect it failed to find a path. – Luaan Nov 29 '13 at 13:08
  • If you want to specify a custom method distance retrieval method, aren't things like `DelegateIncidenceGraph` meant for doing what you need? – Superbest Feb 25 '14 at 21:15

1 Answers1

0

Given your weights are of double type, you should be able to use double.PositiveInfinity for the weight of an impassible edge.

As Eric Lippert says, the failure case of a high weight is a complete path, however any addition or subtraction from double.PositiveInfinity should still be infinity. The double type has an IsPositiveInfinity method to test.

So, try setting the impassible weight to infinity and test the final path length.

Iain Ballard
  • 4,433
  • 34
  • 39