search

jrialland / python-astar

Simple implementation of the a-star algorithm in Python 🌟
BSD 3-Clause "New" or "Revised" License
217 stars 64 forks source link

Performance drop on unreachable tile #1

Closed thorhunter1 closed 5 years ago

thorhunter1 commented 5 years ago

I notice a performance bottleneck when trying to reach unreachable node. Any suggestions of how to mitigate it?

jrialland commented 5 years ago

Hard to say : The algorithm is design to check every possible node until it runs out of candidate. Depending on your problem you may find another way to determine if there is a solution or not. For example you can s see if you can eliminate some nodes, or have a 'rough' representation with less nodes that can be used to test wether there is a solution or not, before running the real search.

thorhunter1 commented 5 years ago

The answer to my problem would be bidirectional search (unreachable area is often much smaller than the rest of grid). Is it possible for this implementation to support it?

jrialland commented 5 years ago

Have you tried to use AStar(goal, start, reversePath=True) instead of AStart(start, goal) ? It might solve your particular problem

eyaler commented 5 years ago

i am also looking for a cheaper way to ensure reachability before running Astar. if there is high risk of unreachability, would it make sense to run BFS/DFS before trying Astar?