Jump to content
  • Advertisement
Sign in to follow this  
KaiserJohan

a* early exit on impossible set?

This topic is 918 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

Using the A* search alghorithm is there anything you can do to detect if goal is unreachable?

Otherwise the alghorithm ends up traversing the entire graph, which is unfortunate on really large sets sad.png

 

If not is there any variant of A* or similiar alghorithm that can do this while still finding the shortest path?

 

For example:

s = start
f = goal
passable = 1, impassable = 0

1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 0 0 0 1 1
1 1 0 f 0 1 1
1 1 0 0 0 1 1
1 1 1 1 1 1 1
1 1 1 s 1 1 1
Edited by KaiserJohan

Share this post


Link to post
Share on other sites
Advertisement
Just two tips. First limit the nodes you visit,abort if you do not find a solution with the given number of nodes. Second, start your search from the goal node (reverse search), with the assumption, that a goal is more often blocked then the entity, the algorithm will stop more often and earlier.

Share this post


Link to post
Share on other sites

Just two tips. First limit the nodes you visit,abort if you do not find a solution with the given number of nodes. Second, start your search from the goal node (reverse search), with the assumption, that a goal is more often blocked then the entity, the algorithm will stop more often and earlier.

 

The input sets are not known which makes making assumpions really diffcult. It could be that in some cases it's the start node that is blocked, and then the reverse will happen. Or that the graph has a worst-case layout and all nodes have to be explored sad.png

Share this post


Link to post
Share on other sites
For my game aborting after X tries is enough, but if you want to use a bulletproof system, you should look into build waypoint islands. That is, every waypoint or tile get an island id. You start with processing the whole map once and whenever the topology changed (eg. connecting two islands), then before starting A* check if both waypoints (start and end) are on the same island. If you have lot of dynamic connections between islands (small houses with doors etc.), you could build an island graph (island A is reachable from island B etc.) and apply A* first on this island graph before going in detail.

Share this post


Link to post
Share on other sites

 

Just two tips. First limit the nodes you visit,abort if you do not find a solution with the given number of nodes. Second, start your search from the goal node (reverse search), with the assumption, that a goal is more often blocked then the entity, the algorithm will stop more often and earlier.

 

The input sets are not known which makes making assumpions really diffcult. It could be that in some cases it's the start node that is blocked, and then the reverse will happen. Or that the graph has a worst-case layout and all nodes have to be explored sad.png

 

IF there is a chance of a worst-case layout (i.e. Possible route but it is the longest possible), there is not much to do to optimize beyond A*. You cannot limit searches to a number of nodes.
If it's simply the case the start or end nodes could be blocked, depending on your problem set specifics, you could check at each end if the node is quickly blocked. This may or may not save time depending on what your expected graphs are to be.
We could really be more helpful if we knew the specifics of your problem though.

Share this post


Link to post
Share on other sites

Yeah, depending on the game/usage/whatever, you could keep a list of all nodes that can reach a destination (basic floodfill), and then check if the start is within that list.  If your graph constantly changes, that's probably not so great.  (though perhaps not too bad, if you just do a floodfill again from the tiles that changed.)

Edited by ferrous

Share this post


Link to post
Share on other sites

If you have many agents, or a big map, pathfinding will become the biggest performance bottleneck in your game. You need many algorithm optimizations to bring it under control. If your map is dynamic, you need even more.

Firstly, you will need a high level representation of the map, here is a screenshot of mine:

tjMwC.jpg

 

The high level representation can be used for high-level pathfinding, path existence checks and distance estimation.

Edited by captain_crunch

Share this post


Link to post
Share on other sites

Thanks for input.

I was largely able to bring performance to acceptable levels by switching up data structures and allocation abit.

Share this post


Link to post
Share on other sites

Yeah, depending on the game/usage/whatever, you could keep a list of all nodes that can reach a destination (basic floodfill), and then check if the start is within that list. If your graph constantly changes, that's probably not so great. (though perhaps not too bad, if you just do a floodfill again from the tiles that changed.)

If you're going to do floodfill, you might as well keep track of the distance in case you're not doing a worst case search.

Obviously, that's equivalent to Dijkstra algorithm.

@OP:
Sorry for the self-promotion, but if you want to speed up A*, you may want to switch to JPS search instead (needs uniform grid costs, reduces the number of open/closed set operations by an order of magnitude)
http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/jump-point-search-fast-a-pathfinding-for-uniform-cost-grids-r4220 Edited by Alberth

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!