4
\$\begingroup\$

I know about several of path-finding algorithms that exist: depth-first search, Dijkstra's algorithm, A* etc.

Now I would like an algorithm that gives me the N paths with lowest cost. Can this be obtained by some simple modification of one of the above? Or is a different algorithm needed, and if so which?

\$\endgroup\$
  • 2
    \$\begingroup\$ Trivial version: Run A*. When it finds a path to the goal, note it as "shortest path #1". Then, tell the algorithm, "no, you didn't actually reach the goal" and continue where it left off. It will choose the next best candidate node in the open set and try to continue the path. Again when it reaches the goal, note that as path #2, and repeat. Of course, this will tend to give you very similar paths: "take the shortest path to the goal until the last two steps, then walk around it & enter from the side" - if that's not what you want then you need to define rigorously how the paths should differ \$\endgroup\$ – DMGregory Nov 20 '16 at 18:24
  • \$\begingroup\$ @DMGregory In this implementation redblobgames.com/pathfinding/a-star/… if you tell it it didn't reach the goal, it will not come up with the alternate path. Maybe you're thinking of a different implementation where that woud be possible...? \$\endgroup\$ – oneloop Nov 20 '16 at 19:50
  • \$\begingroup\$ In that version you'd remove the goal from the frontier, to effectively "undo" having reached it. You just need to watch out for your taken paths completely walling-off the goal so it can no longer be reached at all for subsequent attempts. For this reason, I don't actually recommend this approach: I just posed it to show "different" is a weak criterion and might not really describe the character of the paths you want. Consider sharing more details about why you need multiple paths. \$\endgroup\$ – DMGregory Nov 20 '16 at 20:17
  • \$\begingroup\$ @DMGregory what do you mean removing the "goal from the frontier"? In that algorithm the goal is never added to the frontier. Yes, I want many similar paths. It's a long story. I am limited in how many direction changes I can do to a unit (only one per turn) and so my plan is for each unit calculate many different but similar paths and select the order in which to change direction across units in a way which is efficient. Hard to explain without going into great detail. \$\endgroup\$ – oneloop Nov 20 '16 at 20:47
  • 1
    \$\begingroup\$ I didn't say never add it, I said once you reach the goal, remove it. But again, don't get hung up on this (frankly bad) solution. Edit your question to include more details of your problem so we can help you find a better solution. \$\endgroup\$ – DMGregory Nov 20 '16 at 23:00
3
\$\begingroup\$

Yes, you can modify these algorithms to find different shortest paths, with a few caveats.

First, there can be an exponential number of shortest paths. Consider a simple chessboard example, where you're trying to travel from the top-left corner to the bottom-right corner. Since a chessboard has 8x8 squares, you just need to travel to the right 7 times, and down 7 times, in any order. One way to find different paths is to use tie breakers that tend to produce different results. For example, you can try a tie breaker that always moves horizontally before vertically to produce one path, then one that does the opposite.

Then there's the question of how different you want the paths to be. Would you prefer paths that are as short as possible, even if they are virtually identical? Or would you rather look for paths that are as different as possible, at the cost of taking long detours?

Here's one example algorithm you can try: modifying A* so that it penalises nodes that have been used previously: http://jsfiddle.net/3huzrpyk/

enter image description here

This algorithm, based on this, simply looks for two paths. The second path (blue) uses a custom cost function (the g(x) part) that penalises nodes that are already used by the first path. The penalty can be customised - low values means it tries to maintain very short paths, high values (like the image) means it tries to avoid repeating nodes even if it must take a longer detour.

\$\endgroup\$
  • \$\begingroup\$ Ok thank you. Either forcing first step or putting higher cost on cells which are already contained in the other path does indeed provide new paths. I'm marking this as correct. \$\endgroup\$ – oneloop Nov 22 '16 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.