There are several buildings on the map with size n * n， and a lot of tiles of obstacles that can be destroyed. Suppose I put one soldier on (x,y) of the map, the soldier can reach a building by moving and destroying the obstacles. I need a way to figure out the best choice for the soldier and because there might be a lot of soldiers I hope this process can use as little computing resources as possible. I have come up with path finding and K-D tree finding the nearest neighbor, but neither fits well, since K-D tree works with no obstacles and path-finding needs to traverse a lot building. Besides, the destroying obstacles will affect those have made one path plan.
A* and other standard path finding algorithms let you assign costs for each move. You simply need to assign an appropriate cost to destroying an obstacle that represents how long it would take to destroy it.
When an obstacle is destroyed, you may want to recalculate paths for all moving units, as they may now have a more efficient way to reach their destination.