What are the most common AI systems implemented in Tower Defense Games

I'm currently in the middle of researching on the various types of AI techniques used in tower defense type games. If someone could be help me in understanding the different types of techniques and their associated advantages.

Using Google I already found several techniques.

• Random Map traversal
• Path finding e.g. Cost based Traversing Algorithms i.e. A*

I have already found a great answer to this type of question with the below link, but I feel that this answer is tailored to FPS. If anyone could add to this and make it specific to tower defense games then I would be truly great-full.

How is AI most commonly implemented in popular games?

Example of such games would be:

• Plant Vs Zombies - Not truly Intelligent, but there must be an AI system used right?
• Field Runners

Edit: After further research I found an interesting book that may be useful: http://www.amazon.com/dp/0123747317/?tag=stackoverfl08-20

• What is the point of this question? Is this just asking for a list of technologies? Why does it matter what is popular? How do you expect us to know how the AI is implemented in commercial, closed-source games, such as those you've listed? How can this question ever actually be "answered" in a definitive way? Voting -1 at the moment, since this appears to be attempting to lead an interminable discussion, rather than attempting to find a solution for an actual game development problem. – Trevor Powell Nov 19 '12 at 23:37
• The point of this question is to provide me and any other individuals with the basic fundamentals of various AI techniques used in different types of TD games. Of course I don't expect you to give a definitive guide on how they are implemented, matter of fact I did not even ask that. A Good description of different types of techniques will suffice. – BOWS Nov 20 '12 at 0:12
• I have also updated the question to only list/describe at max 5 different techniques this is to reduce it being "too open" – BOWS Nov 20 '12 at 0:22
• Limiting a number of responses (which, by the way, is not really possible since anyone can give an answer) is not meaningful, nor does it make a question less open ended. "Popular" is a good way to judge useful. It's sort of a list question, but I think the question is valid - what AI algorithms apply to tower defense games. And it's plausible that these algorithms could be discovered/known for closed-source games as well. Some games expose them in editor utilities, some might have a dev blog that talks about it or a Q&A with a developer, and so on. – Ricket Nov 21 '12 at 3:59
• @Ricket RE: "Popular" is a good way to judge useful. We clearly have very different life experiences. :) – Trevor Powell Nov 21 '12 at 4:13

A* will work, but for a Tower Defense game that has lots of enemies with the same goal and a relatively static geometry, it may actually be cheaper to just run Dijkstra's algorithm backwards from the goal, to find the shortest path tree from anywhere on the map to the goal, and cache the result until the geometry changes (i.e. a tower is built or destroyed).

Basically, this means that, for each grid point on the map, you store the direction that leads most directly to the goal from that point. Then you just have each enemy move in the direction given by the nearest (If there are n groups of enemies with different goals, or different terrain crossing abilities, you need to store up to n directions per node. Obviously, flying enemies don't normally need directions.)

Conveniently, if you save the distance from each point to the goal too, you can do incremental updates to the map when obstacles are added or removed: when an obstacle is added, you only need to update points in the branch of the tree cut off by the obstacle, whereas when an obstacle is removed, you only need to update any points from which the goal can now be reached more directly than before.

Alternatively, you can combine the caching with A*: for every enemy, run A* backwards from the goal to the enemy, but save the resulting tree and distances so that you can reuse it for other enemies (and for subsequent updates). This should quickly give you a fully cached shortest path tree of all the map areas that the enemies are actually passing through, while not wasting effort on dead ends that won't be visited anyway.

Both incremental updates and A* also let you efficiently test whether a tower would disconnect the map: with incremental updates, you just try the update and see if all enemy entrances can still be reached from the goal, while with A* you can just run a search from the goal to the entrance and see if it succeeds; if the obstacle does get built, you can then use the result as the starting point for your new pathfinding map.

It should even be possible to get the best of both worlds, by combining the cached A* idea with the incremental updates, although one would have to be careful about not leaving any stale cached directions where an enemy might try to use them for pathing. (Leaving stale directions in dead ends should be OK.) Basically, when an obstacle is added, you invalidate any cached directions leading through it, while if an obstacle is removed, you re-run A* from the obstacle to all enemies and possible entrance points and then merge the result with your previous cached paths. I'll have to think about that a little bit more, though...

• You could also use A* in combination with some sort of flocking. Never tried it myself but the idea is that 1 entity knows where to go and the others just follow. It could be cheaper. – Sidar Nov 19 '12 at 23:23

Well, I don't think plants vs zombies has much in the way of path finding. Just moves left. You could just generate a random number from 1 to 5 or however many lanes you have and stick the enemy there. Maybe with the constraint that it can't roll the same number twice. Or if it does re roll so you don't get too many in the same lane

If someone could be help me in understanding the different types of techniques and their associated advantages.

I want to answer that question by listing three techniques I would use if I were to implement a TD game:

1) Finite state machines or behavior trees for the little AI any agent would need. For something as simple as TD I'd probably use FSM. (

2) A* for path finding, with a cost of selecting paths that is already taken (for the AI, clustering is bad as it makes for an easier target) also I would try to select targets where I have 'gotten through' before

3) State planning / adversarial search / alphaBeta pruning for selecting the best agent to spawn next (optimize likelihood of player defeat) (the AI needs its own set of costs and cool-downs for this to work)

• #3 is only if you plan to not have specified lists of enemies that spawn. This would be most useful for AI opponents in a dueling TD like the recent "Tower Wars." – DampeS8N Nov 20 '12 at 13:24