A* Plugin: Find all possible paths

[dennisschumann]

Hello,

the A* Plugin provides a method to find one (the direct?) path between two nodes. In my example there are several equal paths:

A to B to C and A to D to C. Meant are the paths from A to C.

Is there a way that the plugin return both paths since they are equal to their path langth?

Best regards!

[Yomguithereal]

@A---- I'll let you answer.

[A----]

No, in the current state of the implementation it does not, and most implementations of any pathfinding algorithm.

But you can modify either this A* implementation ( https://github.com/A----/sigma-pathfinding-astar ) or create your own.

You may end up with loads of solutions, which may not be that interesting though. If I understand correctly, you either have some kind of grid-based layout, or changed the pathLength function to always return 1 (which is more or less the same).

Taking a 5-by-5 matrix of nodes, there are tons of solutions that have the same Manhattan distance between (1,1) and (5,5).

[dennisschumann]

Thank you for your response. This means, that the plugin shows only the first solution. If there are equal solutions, it ignores the others, right? Best regards!

[A----]

Yes.

Taking a look at the source, it would not be that difficult to push some (but not all) solutions in an array. Check this here: https://github.com/A----/sigma-pathfinding-astar/blob/master/sigma.pathfinding.astar.js#L104

But you'd have to take a closer look if you want solutions like A → B → D → E and A→ C → D → E because, from what I remember, this algorithm only keep one path for each intermediary node.

[dennisschumann]

Thanks!