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

Question

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:

• Radiant Defense
• 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

Answer 1

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...

Answer 2

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

Answer 3

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)