Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm making a Tower Defense and I have basic pathfinding working, but I got a problem.

I want to make the path blockable, and when a block occurs the runners will attack the blocking towers.

So what I need is a way to find the shortest path that, more importantly, has the lowest number of towers in the way.

How do I do that?

share|improve this question
1  
wouldnt that be a collision detection within your walkable path ? –  Prix Jul 24 '10 at 6:05
    
Since the blocking towers are destructible, there is actually a path. Just the cost of moving through them is way higher than moving along an unobstructed path. (See answer from coderanger below) –  bummzack Jul 24 '10 at 10:43

1 Answer 1

up vote 19 down vote accepted

In your path scoring just make it so passing through a tower costs the same as going through some big number of tiles. In general it will try to get around them, but if there isn't such a path the output will still be going through the least number of obstacles. You can tune the penalty so that sometimes they will just go through instead of going all the way around the map if you want too.

share|improve this answer
    
would love to see a code example of this implementation, sound simple and robust –  DFectuoso Jul 24 '10 at 9:03
3  
The A* algorithm (en.wikipedia.org/wiki/A*_search_algorithm) works with path costs. Just increase the cost for segments that run through a tower. Your agents will then try to avoid the towers, or if it's "cheaper" to attack a tower, they will attack it. The idea of the A* algorithm is to minimize the cost, so you should be able to achieve what you want by simply tweaking the path costs... –  bummzack Jul 24 '10 at 10:38
    
This is a great solution I wouldn't have thought of, thanks! –  jhocking Apr 27 '11 at 14:24
    
Just a note: Giving the tower nodes a huge movement costs without also increasing the estimate used for the A* algorithm when the path is obviously blocked will mean that your agents will check every node on their part of the obstacle before deciding on a break-through point. Depending on the amount of nodes and agents, this might make the algorithm prohibitively slow. –  Martin Sojka Apr 27 '11 at 14:35

Your Answer

 
discard

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.