# a* early exit on impossible set?

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

## 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

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 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.

##### 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

##### 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 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

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 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 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:

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

Edited by captain_crunch

##### 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 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

1. 1
2. 2
3. 3
Rutin
16
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633722
• Total Posts
3013549
×