16
\$\begingroup\$

I'm making a Tower Defense and I need a good pathing algorithm for it.

I have thought about Dijkstra but I need one that can be dynamic; it must be able to update itself when one edge is removed or added without a full recalculation.

I'm coding in C# if it helps.

\$\endgroup\$

9 Answers 9

7
\$\begingroup\$

You'll generally want to use A*, unless there's something importantly different you're looking for.

\$\endgroup\$
11
  • \$\begingroup\$ If I'm not that familiar with A*, how would I address dynamically changing environments? Re-calculate at every frame? At collisions? \$\endgroup\$
    – Justin L.
    Jul 22, 2010 at 1:57
  • 1
    \$\begingroup\$ Generally you would re-path each frame in a simple game like this. The map grid will likely be very small and the number of agents in the hundreds at most. If it ended up being a huge performance problem somehow you could optimize it later by not rebuilding the tree except when needed. \$\endgroup\$
    – coderanger
    Jul 22, 2010 at 2:32
  • 6
    \$\begingroup\$ If it is sluggish, my recommendations: don't calculate the path for every mob. Likely, theyre all taking the same path. I only recalc on new tower placement, and the tower is in current path. Even then, Only do a re-calc for monsters at points in the path before the block square, not for mobs that are past it and therefore don't care. And then, to make the pathfinding shorter, you could limit it to find the way to square after the blocked square, since you already know the path from there. \$\endgroup\$ Jul 22, 2010 at 8:33
  • 4
    \$\begingroup\$ Actually, "mob" is industry (and MMO/MUD player) lingo for "mobile object". \$\endgroup\$
    – user744
    Jul 23, 2010 at 18:41
  • 3
    \$\begingroup\$ Regardless, it is long-standing, dating back to MUD1, and standard enough to have appeared in many publications. en.wikipedia.org/wiki/Mob_%28computer_gaming%29 \$\endgroup\$
    – user744
    Jul 25, 2010 at 18:57
19
\$\begingroup\$

I needed to solve a similar problem: pathfinding on a large maze-like grid with constantly changing "costs" and barriers.

The thing is, in tower defense game the number of entities that need to have the path solved for them is usually much larger than the number of nodes in the graph. A* is not the most appropriate algorithm for handling this, because you'll need to solve it anew each time something is changed. Well it is appropriate if you need to find only one path, but in my case I needed to be able to handle entities which can appear in different locations and each has its own path.

The Floyd-Warshall algorithm is far more appropriate, though for my case I wrote a custom algorithm that whenever a node changes, it re-calculates the cost to that node from all its neighbors, and then if the neighbors have been changed it is invoked recursively on them.

So in the beginning of the game, I just fire up this algorithm on all my "goal" nodes. Then, whenever a single node changes (for example, becomes un-passable), I just fire it up on that node and the change is propagated to all the nodes that will be affected, and then stopped. So no need for global recalculation, and the algorithm is completely independent from the number of entities that will require pathfinding.

My algorithm was basically something like (pseudo-code):

update_node method in Node class:
    $old <- $my_score
    find $neighbor node among all neighbors such that
        $neighbor.score + distance_to($neighbor) is minimal
    $my_score <- $neighbor.score + distance_to($neighbor)
    $next_node <- $neighbor
    if ($my_score != $old)
        for each $neighbor
            $neighbor.update_node()

With the initial score depending on whether the node is a target or some kind of barrier.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Also would be easy to dynamically spread this over frames as the CPU load changes. \$\endgroup\$
    – tenpn
    Jul 22, 2010 at 7:57
  • \$\begingroup\$ +1 for A* not being the right algorithm to use. \$\endgroup\$
    – Ricket
    Aug 18, 2010 at 14:20
5
\$\begingroup\$

The route algorithm I used on my TD was backwards from normal A* pathing due to the number of entities I had in the game. Instead of routing from the goal to the bad guys, I routed from the goal to every empty square on the board.

This doesn't take very long, you just keep iterating the board until you've found your "costs", and it provides good feedback for blocked routes (if you're doing those). Using Floyd's algorithm is fast and cache friendly compared to A* as it's not doing data dependent lookups, it's just loading in and operating on data in streams.

Start with your board set to infinite cost, then set the goal square to cost zero, then iterate over the board checking to see if a neighbouring cell costs less than the current cost plus the travel cost. The travel cost is where you put your heuristic (in my case, the cost of travelling diagonally was infinite, but the cost of travelling through a tower was high, so they were allowed to eat through towers, but didn't unless they had no choice)

Once you've got your costs grid, you can quickly build a "flow" grid from that by testing the steepest gradient of cost on the cells. This works really well for massive amounts of bad guys because none of them ever have to path find, they just follow the virtual signposts.

Another benefit is that this way you only have to run this task every time you adjust the obstructions (or in my game, when a creep eats through one of your towers). Not every time a creep/mob enters the field (which with thousands of mobs and tens per second would have been quite a headache).

\$\endgroup\$
4
\$\begingroup\$

Pathfinding is fast, and on something the size of a normal tower defense game, you'll have no trouble running a full A* or Dijkstra pass whenever something changes. We're talking well under a millisecond for a full refresh. Any kind of adaptive pathfinding ends up horrifyingly complicated. Just do it the simple way, unless you're making the world's largest tower defense grid.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ It's worth noting that Tower Defense is popular on mobile phones, where pathfinding is not fast. Especially on slightly older devices, like the Sidekick, or Android 1.6 devices. \$\endgroup\$ Jul 22, 2010 at 8:37
  • 1
    \$\begingroup\$ Developers have been using pathfinding algorithms like A* and Dijkstra on far less powerful hardware for decades (think Game Boy). Any phone new enough to have a screen adequate for gaming shouldn't have a problem, provided of course that the implementation is reasonably efficient. There are some nifty optimizations discussed here: harablog.files.wordpress.com/2009/06/beyondastar.pdf \$\endgroup\$ Aug 20, 2010 at 15:33
  • \$\begingroup\$ +1. I came to the same conclusion when I was developing my own DTD clone. I tried updating the paths incrementally but the algorithm became too complex. After spending a day on it, I switched to a full recalc on each change. That worked, and with a few tweaks I was able to make it fast enough. \$\endgroup\$
    – finnw
    Feb 8, 2011 at 14:59
2
\$\begingroup\$

How does A* pathfinding work? might be a good place to start :-)

\$\endgroup\$
2
\$\begingroup\$

This may be overkill for your solution, but think of routing backwards instead of forwards.

In a TD game, the enemies are generally trying to get to a specific goal. Route backwards from that goal to the first enemy, then cache that path. On path generation for subsequent enemies, use the first path as a starting point, and so on. If you have multiple enemy entrace points, or multiple goals, have a range of pre-cached paths to start from.

\$\endgroup\$
1
\$\begingroup\$

Waypoint pathfinding would probably be the best for a td game, because generally based on the level the ai follows a direct path. Basically you set your nodes or waypoints then have the "ai" point towards the waypoiny and walk to it, once it gets close enough to that have it go to the next waypoint, face it and move towards it.

\$\endgroup\$
2
  • \$\begingroup\$ This only works for those TD games where you can only place turrets at the side of the path - not games that allow placement of towers anywhere on the board. \$\endgroup\$
    – Iain
    Jul 22, 2010 at 14:02
  • \$\begingroup\$ yeah initially the author didn't specify which type he wanted so I assumed non dynamic. \$\endgroup\$
    – Loktar
    Oct 6, 2010 at 18:13
1
\$\begingroup\$

Since someone asked, you address dynamically-changing environments by re-computing the path every time the player places or removes a tower, and you just store that path in memory in the mean time. The environment doesn't change on every frame.

Note that some TD games have a set path and don't allow you to place towers on it, so they solve pathfinding the easy way: by hardcoding a path and not letting you block it :)

\$\endgroup\$
1
\$\begingroup\$

A simple solution is to cheat.

Design the map beforehand to make sure that there is no dead ends. Then in each intersection, add a trigger that makes the character to choose a route (example: always turn left, always turn right, or random).

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Presumably he is talking about something like Desktop TD where the user is creating the map on the fly. Still for the "dumb" enemies that might be a nice solution so you can make enemies with better AI a bit of a difficulty boost. \$\endgroup\$
    – coderanger
    Jul 22, 2010 at 4:57

You must log in to answer this question.

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