i am currently working on an rts style game and have implemented basic A*, it works out the path from start to end. however i am trying to figure out the how to get the closest path if a path fails to be found (e.g if the player clicks on an obsticle or clicks and unreachable location), just like games like c&c/warcraft do. so if a location is unreachable the unit moves to the closest place available to the unit, how can i get a* to find the closest path if the actual path fails? thanks

Perhaps you can start a "small search" over near places of clicked obstacle. If you find an "available place", just start a new pathfinding :)

unreasonable?

A simple hack that I've used in the past (with varying degrees of success) is to draw a straight line from the start to the end point. Then, choose a point on that line that is close to the end but not at it, and try to path again. Repeat until you find something that works. You can also try slightly perturbing the test points so that they aren't on the line, but only close to it; that sometimes catches quirky cases but can cause its own issues if the variation is too large (like objects travelling totally useless routes).

That's just one thing that I'm aware of - pathfinding is not an area that I've really kept up with over the years. There's more than likely a better solution than this.

When you do the initial search and find it's not reachable, you could keep the search tree/map/whatever, and then start from the clicked location and search until you find a spot on the map marked as found (damn, I really suck at explaining)..

I would need some sort of image to explain what I mean..

...............000......0.BA.....000.........

You start at a and try to find B, 0 is blocked.. You try each . and mark them as visited, and you update them with best way to them, and you have scores and stuff on each of them after a search. After the search, all of the .'s will contain a distance and a score or something like that depending on your implentation. After that, you start from B and check tile by tile (perhaps in a circular way) untill you find a tile marked as 'visited'. That one is deemed to be one of the closest ones. If you want, you could finish the search with that radious and select the tile with the best score as a target, and then move there.

Do you understand me?

Instead of searching for the shortest path to the target, you could create an utility function for finding the shortest nearest path. You then have two dimensions to take into account: bird's distance left to the target, and distance moved from the source. During search, a record would be kept for the best path so far (according to the new utility function). A problem with this approach is that you may end up searching the entire space (just like you would for a failure during the normal approach), although you wouldn't have to search it several times.

Suggestion: [edit]this is about the original A* approach[/edit]

* Maintain in your nodes a parent pointer (to extract the path from any node).
* Keep track of which generated node has the shortest straightline distance to goal (probably your heuristic?).

When you detect that no path to exactly that location exists (search space exhausted?), take that "closest to" node and generate the path using the parent pointers.

You could use a more sophisticated method to determine what the closest-so-far is; perhaps moving an additional 30% to reduce the end distance-to-goal by 5% is not worth it in your mind.

hmm that sounds like a good way to do it, will have to try that, its just strange that theres no standard way to do this, i would have thought that this was a common problem.

What you're asking for is for A* to return a sub-optimal partial path when no path to the goal exists. It isn't designed for this, hence any means of handling this situation is necessarily ad hoc (and why you won't find a standard solution... because they typically depend on the domain).

First up, you clearly don't want your pathfinder to be searching the entire domain for a path when the goal is in a region that is inaccessible from the region containing the starting node. Hence, an obvious optimisation for your pathfinder (and not just relevant to this problem) is to provide it with an estimate of the cost of the optimal path before it begins searching and to have it stop searching when the path cost of the best path found so far is some factor times this initial estimate. A good guess at the path cost is the heuristic cost of the start node. How much more than the heuristic the optimal path will cost will depend on how accurate your heuristic is! You'll need to choose the factor based on the distribution of path costs in your domain. If you reach this limit before a path is found, then simply return "no path found" (or "computation too expensive").

In this situation, one can treat the goal as inaccessible from the starting location. In which case, pop the best node off the open list and treat this as the destination for the unit. While the unit is moving to that location, you might be able to spend some cycles searching for a path from that location to the previous goal. If once again you hit the computational limit, then you should accept that the goal is inaccessible for that unit and set its behaviour accordingly.

Cheers,

Timkin

Quote: Original post by Timkin
What you're asking for is for A* to return a sub-optimal partial path when no path to the goal exists. It isn't designed for this, hence any means of handling this situation is necessarily ad hoc

Your comment assumes the A* evaluation function has been set up to return a shortest path. A* is more general than that, and it is perfectly plausible to create an evaluation function that includes a "path smoothly curving" (or whatever) criterion in the evaluation function. Easier said than done to come up with, yes, but perfectly doable nevertheless.

I was originally considering this approach on smaller maps - say, 200x200. However, if your map is big enough (maybe 1000x1000), A* may take too long for use in real-time. Particularly if multiple searches would be run when multiple units are selected.

If A* is used, it would be best to have a way to determine if the goal is reachable or not. However, I have some misgivings about the behavior of using c*h(S) as a cutoff for f.

As for the approximate solution - popping off the best node in the open list won't necessarily give it to you, as it could very well be in the closed list (especially in the case of searching too far). That's why I suggested maintaining the "best so far" separately.

An alternative to A* could be path marking. This method is sub-optimal but could give a pretty good path. Your graph (the map) would be homomorphically abstracted - that is, you would group tiles into clusters, with each cluster retaining the connections to other clusters that its tiles have. Put another way,

If there is a tile 'a' in cluster 'A', and 'a' has an edge to tile 'b' in cluster 'B', then 'A' has an edge to 'B'.

A search is then conducted in the abstracted space (the graph of clusters). The result is a sequence of subgoals leading to the goal (eg: From Start, get to cluster#7. From cluster#7 get to cluster#12. etc)

Again, for approximation, the "closest cluster" could be used.