Designing game AI
Pathfinding in Tower Defense game
Enemies’ movement is the main key in Tower Defense game since you can make your whole game with only enemies going towards their goal.
Since I already spoke about path finding in previous posts, I will just explain which techniques are usually used for pathfinding in Tower Defense game and how they are executed:
This method cannot be considered as pathfinding method, because monsters are only following a certain path. Enemies will just head towards the next waypoint until it has reached the end, since levels are usually statics (predefined), waypoints are alternatively be replaced by series of movements (turn right – go straight – turn left – go straight). The advantage of this technique is that code can be really light and so is the execution (no computing calculations). This method is perfect for statics maps.
If you have interactive maps you have to implement pathfinding algorithms (usually A* or Dijsktra). I will not explain in detail how Dijkstra and A* are working but if you want to read more about A* and Dijsktra you can read my previous post : About Pathfinding in AI
A* can easily find the best path for your monsters quickly.A* will not visit every tile of your map but only the most relevant ones (based on heuristics) and will end if the goal is found. This algorithm is perfect for your game if all monsters are spawning from the same point to the same end point for an interactive map (like obstacles which can be added by the player on the map).
Dijkstra will also find the best path but will visit more nodes than A*. However if you have a lot of enemies spawning from the different points but going to the same end point for an interactive map , it may be actually cheaper (since A* is needs more operations per node) to run this algorithm backwards.
A second alternative is to run A* backwards and modify the ending condition to find more than one end point.
a) With the game idea for the final assignment in mind, create a list of all the different types of AI that are needed to realise this. Consider what techniques you want to use for decision making, pathfinding etc. if required.
Since best pathfinding is the unique condition to realise a basic tower Defense, usually enemies AI in tower Defense are rather limited, however you can still make a lot of different monsters which will not behave the same (monsters that are speeding up enemies, healers…)
The following pictures will show you ideas that I have for my game :
1. Standard monster
This monster will be the most basic one. It will just find the shortest path from its starting point to the end and follow the path.
A* will be used for the pathfinding.
2. Half-Blind monster
This monster will not see obstacles until a certain moment but will still move from its starting point to the end point.
This monster’s path was inspired by the previous lab, for its path, it is just a small variation of A* where the algorithm will first prioritize the path straight to the goal before considering obstacles.
3. Flying monsters
This monster will fly from its starting point to the end point.
There are 2 possibilities for this monster, we can either move its straight to the direction from its spawn (no algorithm needed) or apply A* algorithm and add some obstacles in the sky like trees or high buildings, for this, a simple boolean can be added for flyable tiles.
We can also add enemies like birds which will avoid some tiles around a scarecrow or amphibians that will be able to swim faster in ponds/rivers, there are many variants that can be designed.
4. Turrets destroyers
This monster has more health than others, it will destroy your turrets.
For this enemy, I am thinking of adding 2 or 3 spawns in the map so that enemies will be able to randomly spawn from different points. This monster will try to break the closest turret using A*, I may add a group behaviour like if there are already 3 monsters trying to destroy one turret, the monster will attack another one.
5. The sneaky thief
This thief will try to steal your resources and will try to disassemble your turrets
For this enemy, the AI will be a little more complex. He will try to steal resource in your camp (especially money) when you won’t be next to it, otherwise he will focus on your best turrets (most valuable one or the one that has the best fire rate). He will also flee from you if he sees you. A* will be used for his movements and for his behaviour I’ll use Unity animator tool based on state machine model.
Depending on the player’s experience, I may not add all of the following AI or change behaviours of some monsters but among them, numbers 1 , 3, 4 and 5 are sure to be implemented in the game.
Once I will have basic enemies of a classical tower Defense, I may want to add survival elements. For example, the player will be able to hit some enemies, will need to eat/drink; also food can be dropped when monsters are killed and can be eaten or sold. Therefore I thought about some more AI which are the following :
Wolves will eat meat on the ground but attack you if you are too close to them.
Wolves will simply eat meat close to them, they will usually move in group and will approach and attack the player if he’s getting to close to them but also chase it. If the player is attacking a wolf next to another, the other one will also attack the player. Either A* can be used for its pathfinding, but also random wandering where wolf will just eat food within a certain range.
5. Little robot
This nice robot will help you to gather food dropped by dead monsters.
For this AI the problem is a bit complex. The first thing to think about is where the food will be dropped (can two pieces of meat be on the same tile or only one piece of meat per tile). If food is randomly dropped in the map, then we cannot use the map graph to perform algorithms but that’s not convenient for now because I have to create another graph. So considering that food can only be dropped in one node of the graph, I will have several pieces of food dispatched in several nodes. The problem is the following: the robot will leave the camp, gather each piece of food and then return to the camp. The second thing to think about is the knowledge of the robot, will he be aware of all pieces of food and its position in the world or not.
- Considering the robot doesn’t know the position of each piece of food :
The first approach is to predefine a tour and then apply A* on each piece of food within the range of the robot.
The robot will just follow the path and if there is food in the scanner range he will take it (by applying A*) or leave it (if there is no path).
However this approach is not good because it will not consider obstacles in the map, to solve that maybe the solution is to do a semi-random wander around the map or visit each walkable tiles on the map but that may not be the most optimal solution at all.
- Considering the robot does know the position of each piece of food :
This problem can be assimilated to the travel salesman problem (which is the following : A salesman has a list of cities he wants to visit and we wants to find the shortest tour that visits each cities only once (with one difference that is the robot can actually return to one tile that he has been). There is currently no exact solution for this problem in a fast way, the exact complexity for this algorithm is n!, but the Held–Karp algorithm solves the problem in time O( n^2*2n ).
To make the robot more realistic we can add a flying scanner that will scan all pieces of food before hand in the map.
The easiest way to solve this (using heuristic) is to choose the nearest neighbour using A* on each piece of food until all pieces have been collected. This is not the best optimization but this method is only 25% longer than the shortest path possible on average [see The Traveling Salesman Problem: A Case Study in Local Optimization].
On top of that algorithm, we can apply the 2-opt algorithm which consist of reconnecting edges in an (Hamiltonian) cycle if the new path is shorter. Nevertheless, the complexity is still high ( worst case is O(n^3) ).
From my point of view, it is not necessary to apply the 2 opt algorithm since the player will be able to gather food by himself (before he will be able to afford the robot) and if some nodes disappear, the robot will have to reapply the algorithm (which will consume a lot of time/memory).
The nearest neighbour method seems to be a good solution for this problem, to improve this we can also implement (on Unity) A* pathfinding on separated thread from the game code.
First what is knowledge representation for AI ?
Knowledge representation is the amount and type of data that the robot will have. Depending on this, the robot will be able to plan, remember and/or predict things. For example, we can simulate the sight of the AI by drawing a range around its head. Knowledge representation is especially useful to design emotions (confusion, surprise, fear…) and design a particular behaviour for each emotion it has.
Knowledge representation can be assimilated to memory storage where data (knowledge) will be stored; it can have several representations like (working memory, short term memory, long term memory or episodic memory) and the AI may be able to select the most important data over others (chasing one type of enemy in priority).
However, knowledge representation can be a disadvantage for the game since it will add more complexity, be inefficient or just not be relevant for the game.
In tower Defense, there are usually not much knowledge representation. Enemies will already be aware of the path they will take towards the goal (to keep the game interesting).
However, some of my enemies might have some knowledge : wolves will be sensitive to the player’s threat, the robot will have to be acknowledged of food position (flying scanner) before being able to build a path and the sneaky thief will be able to detect the player from a certain distance.
Dijkstra’s algorithm (wikipedia)
A* search algorithm (wikipedia)
Travelling salesman problem (wikipedia)
2-opt (local search algorithm wikipedia)
Paper by Mahsa Sadat Emami Taba (2009) Solving Traveling Salesman Problem With a Non complete Graph
Paper from Johnson, D. S.; McGeoch, L. A. (1997). The Traveling Salesman Problem: A Case Study in Local Optimization
Course by Martin Burtsche High speed 2 opt tsp solver
Book by Ray Barrera, Aung Sithu Kyaw, Clifford Peters,Thet Naing Swe Unity AI Game Programming (second edition)