Jump to content
  • Advertisement
Sign in to follow this  
jhoward

A-Star pathfinding - searching for an impossible path

This topic is 3722 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've just finished implementing an A-Star algorithm to search a grid-based graph for a path from A to B. It all works quite efficiently when a valid path can be found. However, everything grinds to a halt if a path cannot be found. The algorithm continues to search every single node on the map in vain as it tries to find a path. There are two possible solutions I have thought of: a) Limit the number of nodes that can be explored (not ideal as a complex but valid path would be flagged as impossible) b) Stop searching if the nodes being searched continue to decrease in f value (still not great as you might have to move away from the goal first to avoid an obstacle) What are the recommendations on this matter? I have read a number of articles but nothing has touched on the subject.

Share this post


Link to post
Share on other sites
Advertisement
I assume that you keep a history of visited nodes, so that your A* algorithm does end on a finite graph, whether there's a path or not.

Otherwise, I don't believe there's a really smart solution to be found without giving more information to your pathfinding algorithm. If I were making a game and it would be slowing down each time the player asks for an impossible path, and impossible paths were common, I would do some preprocessing and split the graph in partitions, so that I can check for unreachable areas before even starting to look for a path.

Other types of preprocessing might also help when often pathfinding on the same graph. A* doesn't reuse information, it assumes you got a graph and only need to find a path once, so you could try to find a way to recycle information from one pathfinding session to the next.

Otherwise, I would put a max-limit on the value of the heuristic while searching and only consider nodes that are in the "vicinity" of the goal.

Or otherwise, some complicated multithreaded solution. If the game's realtime, let the character follow the most promising path, and update it while the pathfinding does its work. Or maybe just put some max processing time: if path not found in less than 5 seconds, give up.

I guess the best solution would depend on the type of context the pathfinding must do its work in.

Share this post


Link to post
Share on other sites
Quote:
Original post by jhoward
a) Limit the number of nodes that can be explored (not ideal as a complex but valid path would be flagged as impossible)

Assuming this is for realtime pathfinding then surely, whether a complex valid path exists or not, you don't want your program to grind to a halt because it's processing many, many nodes?
I'd just place a limit on the number of nodes to expand to a sensible point and make that tradeoff between performance and quality.

Share this post


Link to post
Share on other sites
I've been thinking about path finding recently as well, here's another few possibilities:

1) Search from both ends. The idea is that if a path is impossible, it's usually because some small subset of the world is inaccessible (possibly temporarily -- e.g. a locked room). The idea is that at least one of the sides will hopefully exhaust all their nodes quickly if there is no path.

However, this can double worst case scenarios (e.g. trying to pathfind from one side of an impassable river to another, the second side may have been nearly exhausted by the time you finished searching the first one, whereas you'd only need to exhaust one side otherwise)

2) Use higher level nodes. You can programatically construct them by a limited-area floodfill of the grid. By reducing the total number of nodes that need to be searched (by making them bigger), you reduce worst case costs. You could stick to grid-based A* for finding the actual path once you've verified a path exists, if you want.

3) Spread pathfinding costs out over multiple frames.

Share this post


Link to post
Share on other sites
i solved this problem by simply limiting the nodes searched. You have to pick a good number for your map size, but something like this might work:

if ( nodes_searched > total_nodes / 8 ) { stop }

Note that any time you put an artificial limit on it, you risk not getting a potentially valid, though difficult solution. Rarely does this happen however.

Other than that, you might also try to determine ahead of time if the map in general has isolated areas and simply get rid of them so that they do not present issues during gameplay. This assumes you have somewhat static terrain.

Share this post


Link to post
Share on other sites
In my pathfinder I've put a bool on each node telling if it's enabled or not.
If start or finish-position is disabled - don't search for a path!

Works like a charm, life is wonderful and so on... :)
My pathfinding runs in it's own thread, which is what I recommend since the user won't ever notice any slowdowns no matter how many agents you have roaming around...


Edit -

Just realized there could be problems with this approach if a door-node gets disabled, but you could assign each nodes into zones.
That way, if the keynode of the same zone as the start or finish position is disabled, quit early! :)

Share this post


Link to post
Share on other sites
Instead of a bool saying if a location is reachable or not, you might find an integer is better. You preprocess the map to split it into regions - all nodes store a region number, and all nodes in the same region are reachable from each other. For the example with the river nodes on one side could be marked as region 1 and the other marked as region 2. It's then just a simple check of 'do the regions match' before you do a full search.

You can also handle unlocking doors with that method by changing the values on one side of the door to match those on the other when the door is unlocked. For example if you built a bridge you just change all the 2s to 1s.

Handling the door getting locked again (or bridge being destroyed in our example) isn't quite so easy, but even if you do it with a full search of the map it's the same cost as a single failed path find.

If need be instead of modifying the region values in nodes directly you could create a single high level path node for each region which you use to keep track of region connectivity - you search that high level map first if the regions don't match.

Share this post


Link to post
Share on other sites
Adam, I like your solution. The only thing I would recommend rather than changing the integer value would be to have some sort of hash like structure to link the areas together. Such that when door is unlocked you link 1 and 2 together, and when door is locked again unlink them.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!