How to reduce the cost of search based on previous BFS?
You have two very different situations in the next search condition. If the graph is set up to represent a grid, then the obstacles are simply removed edges to the vertex where the obstacle is, by moving obstacles you have changed the graph, so any new problem is a search on a new graph and the old results are meaningless. For any two verticies, to see if the new obstacles block the old path is easy, however to see if replacing the edges from the old graph will shorten the path requires you to redo path finding. So in the case of the obstacles changing any algorithm would involve much more work then just redoing the BFS, which is quite simple. As for a changed user position you could sacrifice initial cost and search for all other searches upfront, depending on how many times you want to call the algorithm this may or may not pay off, this case is very situation dependent.