10
\$\begingroup\$

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?

\$\endgroup\$
2
  • 1
    \$\begingroup\$ wouldnt that be a collision detection within your walkable path ? \$\endgroup\$
    – Prix
    Commented Jul 24, 2010 at 6:05
  • \$\begingroup\$ 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) \$\endgroup\$
    – bummzack
    Commented Jul 24, 2010 at 10:43

1 Answer 1

Reset to default
22
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ would love to see a code example of this implementation, sound simple and robust \$\endgroup\$
    – DFectuoso
    Commented Jul 24, 2010 at 9:03
  • 3
    \$\begingroup\$ 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... \$\endgroup\$
    – bummzack
    Commented Jul 24, 2010 at 10:38
  • \$\begingroup\$ This is a great solution I wouldn't have thought of, thanks! \$\endgroup\$
    – jhocking
    Commented Apr 27, 2011 at 14:24
  • \$\begingroup\$ 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. \$\endgroup\$
    – Martin Sojka
    Commented Apr 27, 2011 at 14:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .