Don't have a complete solution yet, but I am aproaching it along these lines.
For each available direction from the origin, find all "optimal" (not necessarily shortest, as in the green route above). This can be done by choosing the next direction at each square based on d(ns) and d(ew) (distance in each orthogonal direction from current location to destination square). This will start you with four paths at most to start with.
For each interim location along the paths found, choose an available direction NOT PREVIOUSLY ATTEMPTED and solve the same problem from the new starting point.
This would require a data structure that links each PARTIAL PATH to successful paths, which would define what directions to take in the decision above from the terminal square.
The number of partial paths along successful paths would be large, yet finite. The number of successful partial paths from the interim square could only be 3*number of partial paths to that square (since the direction entered from could not be a possible choice, leaving the other three directions.)
Some unanswered questions in my mind are how many or what percent of obstructed cells are there? What is the largest grid you foresee?
Now to code...
Need help with pathfinding
-
djsfantasi
- Posts: 87
- Joined: May 21, 2010 17:38
- Location: Massachusetts, USA
- Contact:
Mind if I ask 'why' you want to find all possible paths between two points?
Even if the two points are right next to each other, there will be MANY paths depending on the grid size.
I don't see the usefulness of finding all paths unless to compare each path for some OTHER variable not being accounted for in the path finding routine to find the desired path (for instance, if a certain type of square (terrain) is more desirable to go through than other 'normal' squares then after determining all possible paths you go through and weight each one with how many times they go over the valuable square.... but again, why? If you are going to further compare paths as to some sort of desirability, then just build in that desirability to a 'shortest path' routine and it will find it.
You could, I suppose, switch things around and change a shortest path routine to finding the LONGEST path, which WILL iterate through every possible path.... just need to save each path each time it discards it.
maybe not... gotta think about that a bit first...
oh well, why do you want this routine again?
Even if the two points are right next to each other, there will be MANY paths depending on the grid size.
I don't see the usefulness of finding all paths unless to compare each path for some OTHER variable not being accounted for in the path finding routine to find the desired path (for instance, if a certain type of square (terrain) is more desirable to go through than other 'normal' squares then after determining all possible paths you go through and weight each one with how many times they go over the valuable square.... but again, why? If you are going to further compare paths as to some sort of desirability, then just build in that desirability to a 'shortest path' routine and it will find it.
You could, I suppose, switch things around and change a shortest path routine to finding the LONGEST path, which WILL iterate through every possible path.... just need to save each path each time it discards it.
maybe not... gotta think about that a bit first...
oh well, why do you want this routine again?