Thursday, July 14, 2016

Ian Millington "Artificial intelligence for games"

The basic insight, that this book gave me is that AI is not a rocket science. Actually, Ian Millington says that AI is a handful of algorithms, which when combined performs a smart and interesting behaviour. Algorithms are generally simple and often has an O(n^2) complexity. The general value of this book, however, is that it gives you a good understanding of how AI should work in your game and how to build flexible, optimised and convenient architecture of your AI engine. I guess, it is not necessary to learn all these algorithms, that are in the book (however you definitely need to know, which algorithm solves which problem). If you plan to work with AI it is worth to get acquainted with this book. Here I will write general things that I think it is worth to keep in mind, without a detailed description of algorithms (when needed it can be found on the Internet).

I guess this will be last technical post which is so long. For future technical readings, I will write a short resume for each chapter. There will be more posts, but they will be shorter and more informative.

There are three key moments in AI engine:
  1. Movement
  2. Decision making
  3. Strategy
Movement and Decision-making are a single character behaviour algorithms, while Strategy is a group behaviour algorithm.

There are plenty of movement algorithms. In the most general way, we can divide it to Kinematic and Steering algorithms. Kinematic algorithms take static data (like current position and orientation and target position and orientation) and perform a stationary movement, without acceleration. Steering algorithms perform more complex behaviour with changing of acceleration and with using prediction methods to obtain a smarter movement method. The common interface for this set of algorithms is Steering, that contains all the kinematic data (like position, orientation, velocity and angular velocity) and the accelerations for both linear and angular. Each frame the game calls method update(steering, maxSpeed, time) for class Kinematic for each object in the game and this method updates current position, velocity and orientation of the character. From the whole diversity of steering algorithms, I want to pay attention to collision and wall avoidance algorithms. The most simple solution here is to cast a cone for each character and check if something lays within this cone. But this approach can produce some mistakes, like two characters can actually avoid each other if they continue to go straight, but can be in each other cones as well. Or two characters can collide, but neither of them is inside the cone.  The better solution here is to check if the characters will collide if they continue to move with the same speed. For wall avoidance, the simplest solution is to cast a ray and check if it crosses the wall. However, the trickiest thing here is the angles. The better solution is to cast multiple rays, but you can get stuck in the acute corner, so you need to be accurate with this. However, more rays mean more processing time, so it is worth to find the optimal number of rays.

Every moving algorithm works only with one variable (like position/orientation, velocity/rotation or acceleration). Very often we need to combine different movement behaviours into one. There are plenty of ways to do it. The first approach is weighted blending. In this, you need to determine weights for each behaviour and then sum up it together. This method has a bad side like you will not actually get a collision avoidance if other behaviours affect the result. Another way to do this is to use some arbitration system, which will decide which behaviour to choose in given moment of time. You can blend this two solutions.

The next big topic in movement is coordinated movement. The simplest method here is fixed formation, where you assign each character to each slot in a formation and treat one slot as a leader. The more scalable way is to use emergent formations like to set for each character another character as a target. We can totally remove the leader of the formation, by assigning invisible leader in the centre of mass of the formation. For more complex behaviours we can use the whole formation as a character, so we can make formations from other formations. Another interesting feature here is slot roles. We can have each slot with appropriate role (like melee or ranged) and character with another role cannot take it. This approach has some problems like if you have some melee fighters left, but without any available melee slots. In this case, the solution is soft rules. Soft rules mean that each slot has a cost for each type of unit. The problem for AI is to place a unit in such a way to obtain a minimum cost.

There are some algorithms with tricky situations like 3d movement or motor control in the book, but I would not pay attention to it here.

Pathfinding is a huge topic in AI. There are some implementations of Dijkstra and A* in the book. In brief, these two algorithms are similar. They work with directed weighted graphs, and have two lists for nodes they have already visited and nodes they want to visit right now. The difference between these two algorithms is that Dijkstra uses the exact cost for estimation of overall path cost, however, A* uses heuristics for this purpose. There are some optimisations for A* in the book, to increase execution time or memory expenses, but these situations seem like very rare.

The main problem of pathfinding is the world representation because we need to turn the continuous world into the discrete graph. The simplest case here is to turn the world into tiles and use them as the nodes of the graph. The second way is to use Dirichlet domains. It requires the level designer to put some characteristic points into the level. The Dirichlet domain is the cone that cast from the character point down to the bottom of the level. The next way to divide the world is the point-of-view method. In this method, we choose inflexion points near the convex vertices and use it as nodes of the graph. To check if they have a connection we just check if one point is visible from another point by ray casting. The last method is polygonal meshes, where you use each floor polygon as a node.

For huge levels, with different available actions, you can use hierarchical pathfinding. It looks like formations of formations but for pathfinding. It looks like if you need to go from one city to another you have the cities graph on the top of your hierarchy. If you have found a path between cities, you go deeper and try to find the path from your home to the airport. After you found it you start to search for the path to your bus stop and so on. To check where to go in the lower level you need to specify the exit nodes from the level. On each step, you do not need to process all the graph, but only the part that you need to execute now.

It is not necessary to use distance as a cost for pathfinding graph and positions for nodes. There is a solution for continuous pathfinding in the book (where the graph is changing over time) which uses different objects for the nodes and the costs.

The next chapter of the book is about decision making. When AI needs to represent smart behaviour it should decide what it should do next. For this kind of situations, decision trees can be used. The decision tree is the tree with decisions in the leaves and conditions in the nodes. Every edge represents an answer for the node condition. Decision trees should be balanced, and there are couple  algorithms for balancing it in the book. Also, there is an algorithm for the dynamic generating of the decision tree, when AI gets in different situations. The next way to implement decision making is state machines. State machines can be hierarchical and include another state machine as a state. There are tricky moments in the handling of hierarchical state but they are very easy to solve in the exact situation. Decision trees and state machines could be combined to one structure.

States, however, can be not clear and so fuzzy logic comes out. Fuzzy logic supposes that you can be in plenty of states partially. Unlike solid logic, where you do use logic operators like AND and OR, in fuzzy logic, you replace them with min() and max() functions respectively.

In the Goal Oriented Behaviour, every character has its own set of goals and actions that lead to fulfilling some goal. Every action has a positive value for some action and may have a negative value for some another action. The character uses these values to chose the only right decision.

In a rule-based system, you have a database of knowledge and the set of rules. When you parse the database you check which rule should be triggered now.  The most popular algorithm for matching rules is Rete. It represents rules as an acyclic directed graph, where each node of the graph represents some patterns of the rule, that leads to concrete action.

For merging decisions of different decision-making systems, you can use Blackboard architectures. In this algorithm, every decision-making system watches the blackboard where different data is represented. If the decision-making system found something that it needs to change it asks for having a control of the blackboard. Then special arbiter choose which system will have a control in the next iteration gives the control and system make some changes on the blackboard. Then you start again.

The last part of the AI engine is Strategy and tactics. It responds for the group AI behaviour. One of the most common methods in tactical AI is waypoint tactics. The level designer adds the waypoints to the level, that represents, for example, safe location for the characters. We can have different types of waypoints for the same level and then combine it to the graph. We can add the actions that will look for an appropriate waypoint to the decision tree of the character and this will cause smart behaviour. The waypoints can be generating automatically. There are couple ways: you can watch a player's behaviour and detect some waypoints or we can pre-test every point in the game if it is a candidate to the waypoint.

For tactical representation to the level, we can use an influence maps. Briefly, the approach is about calculating military influence for each position in the map. Every military unit has it's own influence formula, that calculates an influence with some decreasing, depending on the distance. For more realistic distribution we can use some algorithms from graphics, like filters (e.g. blur) or cellular automata.

We can force our AI to learn from the situation. We can keep death counter and kill counter for each position in the game, that have some deaths or kills. AI can avoid positions with large death counter, and try to place itself with the position with large kill counter.

For the tactical pathfinding, each edge of the graph will have different weight, depending on the goal of the character. We can tweak heuristics for A* here, for example.

For the group behaviour. it is better to use hierarchical AI. The general AI will issue orders for the army, the commander AI will issue the orders for the group, etc. We can also use the tactical waypoints to represent specific group behaviour (like tactically effective positions for taking a room). Every member of the AI team needs to send a signal about what he going to do now, and others should coordinate their intentions with it.

The next chapter is about learning, about neuro-networks and other stuff. The basic thing that you need to remember here is that in most cases you do not need learning. If you are implementing it, it means that likely you are doing something wrong. Usually, learning is needed before production, to not involve a level designer or a tester for it. But basically it is hard to debug learning algorithms and it can cause some problems. But it can help you to build a decision tree, or make your AI learn from the player.

Next chapter is about board games. There are some set of games, where you can predict every case of play. You can create a graph of all the cases and estimate the best set of moves. For this purpose, you can use minimax algorithm (that will maximise your profit for your turn and minimise it for opponent's turn to predict the overall path of the game). You can also use a technique that called open books. It consists of pre-computed costs of a different set of moves in some database, so for chess, for example, you don't need to force your AI to think in the first few steps.

For the games where you cannot build a tree of the game (because it is very huge) you can generalise some information to the larger cases, and use minimax for not exact moves.

The next set of chapters is about useful techniques that you can apply in your AI engine. First of all is Level of detail technique, that is very common in graphics. The whole point is to use less detail when you don't need. Like, don't use pathfinding in the city that you don't see on the screen. Or you can use only general modelling of some features in the city, like economics or the crime level, but not how these things happened.

The next technique is about world representation and how to build an event system for you AI. There are couple approaches that you can use like broadcasting or register individual listeners, I guess it is quite clear for all. You can also have the event-based approach for sense management, and register listeners for each character. Then either event manager or the character can check all the limitations and decide can the character, for example, hear the sound or not.

You can also find the basic approach to building an AI for each game genre in the end of the book. I will not describe it here because I think it is quite clear what techniques you should use for your own game. There is a very good questionnaire in the book if you have some difficulties with it.

I definitely will use this book if I decide to implement AI in my game. It is a step by step guide for building an AI, so you can actually call it a handbook for every AI developer.




No comments:

Post a Comment