Hey there,
What would be the best strategy to find several (let’s say 3) different paths for the same origin / end node couple?
I aim to find the shortest (if possible), another one which would be longer, and a final one even longer.
Thanks.
Hi
In general this is a harder problem known as k-shortest paths, the algorithms for that are not implemented in this library.
You can try to add penalties to some random nodes along the way and then recalculate the path, which works reasonably well. This is what the AlternativePath modifier does.
Great, I’ll look at Alternative Path modifier then. Thanks!
Do you know if it’s possible to ask to find a path by its length? Like “try to find a path from A to B composed, at least, of N nodes”?
Hi
That problem is unfortunately NP-Complete (i.e for non-trivial graphs it will take a HUGE amount of time to find those paths).
See https://en.wikipedia.org/wiki/Hamiltonian_path
Hmm ok 
What is a “non-trivial” graph for you?
No idea really. But if you look at that wikipedia page, there is a graph on the right side, that is on the smaller side of the non-trivial graphs. Even with cutting edge approaches, graphs with as few as 40-50 nodes can take seconds or minutes to solve (or a fraction of a second, it really depends on how the graph looks).
Well… I see.
What do you think of using a strategy like :
- Get the shortest path.
- take a node at the middle of the path and use it as a center.
- from this center take a node randomely in the graph using a radius equals to the “length” of the shortest path.
- ask to find a path from origin to this random node, and a path from this random node to the end point.
PS: I plan to find paths on a city map.
Hi
I would instead suggest.
- Get the shortest path
- Pick a random node on the path and increase the penalty of that node by some large value (say 100000 or 1000000).
- Goto 1.
You can use AstarPath.WaitForPath to force a path to be calculated immediately.
I’m working on a city map… and I’m afraid taking just one point of the path to change its cost might just create a small “bump” around it and not a different itinerary.
(Example of the map I’m working with - my first try with A*Pathfinding by the way, the results are really impressive - I’m jealous of what you have achieved here 
-)
[EDIT: the map is not weighted correctly yet, that explains the strange shape of the path]
You could instead apply a penalty to ALL nodes in the path (though maybe a slightly lower penalty this time). That might work better.
I’m going to try that today. Thanks.
This is what I have so far.
(the graph is not weighted correctly, please don’t mind the weird paths)
1 Like
Looks good! 
Small update.
1 Like