Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question

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.

share|improve this answer
First I need to decide which one is the best for the target, even if I add weight to the obstacle , I need to calculate all possible path with A*. In other words, I don't want this violent way to do it, I hope to do A* on as little building as possible to find the best or more sub-optimal. About the destroying obstacle, if there are lots of soldiers on battle field, recaculate all will be a huge cost and not every soldier needed to recalculate. – user1208602 Mar 9 '13 at 12:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.