Recursive Best First Search for Pathfinding?
-
Just curious if RBFS can be used in pathfinding scenario such as a map with obstacles between location A and B? I am doing an experiment and the result shows that for some situations RBFS is able to find the path but for others it is not, even there are paths available.
-
Just curious if RBFS can be used in pathfinding scenario such as a map with obstacles between location A and B? I am doing an experiment and the result shows that for some situations RBFS is able to find the path but for others it is not, even there are paths available.
By definition, a path is not a path if there is an "obstacle" (that cannot be overcome). (Unless one considers / programs a "dead-end" as a "branch" / u-turn).
"(I) am amazed to see myself here rather than there ... now rather than then". ― Blaise Pascal
-
Just curious if RBFS can be used in pathfinding scenario such as a map with obstacles between location A and B? I am doing an experiment and the result shows that for some situations RBFS is able to find the path but for others it is not, even there are paths available.
It is a normal behaviour as RBFS is heuristic, so it discards some branches of the solution tree which may contain the solution. There are some heuristic algorithms, also for some graph problems, that find a solution which is not optimal but they at least find something close to the solution, which is satisfactory, whereas the other heuristic algorithms, when they miss the solution path, they will give you no results. For finding paths in graphs, heuristic algorithms should be used only if you do not have enough memory for a regular BFS. They usually provide no solution if they miss them. I am now writing solving diamond peg solitaire with BFS, which should be ready within a couple of days on my site informatyka-delphi.blogspot.com If I am lucky, the graph will have up to 15 GB, compressed graph 4GB, so I shall find the solution with BFS.