Game AI Training at Başkent University

The Computer Society committee and the Artificial Intelligence Study Group of the IEEE Başkent University Student Branch invited us to their AI Training Series. In a session of about ninety minutes, our founder Can Karabulut, a computer engineer, showed how AI algorithms work in games. Our computer engineer Batuhan Tatlısert gave an introduction to game coding. More than 70 students joined, and we put what we learned into practice by coding a game together.

Below we share what we covered that day, with examples from more than ten years in the software industry. We hope it is a good starting point for anyone who is new to game AI.

Finite state machines

An enemy that patrols, chases the player once it spots them and falls when its health runs out is moving between states. A finite state machine (FSM) is a model that defines how a character, an enemy or a menu moves between such states. Each state stands for one behaviour. Transitions decide when the entity moves from one state to another, for example after a trigger, when a timer runs out or when the player presses a key.

FSMs help game developers in three ways. Complex behaviour stays tidy because it is managed through clear states. Adding a new behaviour or changing an existing one becomes simple. Debugging gets easier too, since it is clear which transition changes each state.

Three ways to build one in Unity

The quickest start is to define the states in an enum and handle them in the update method of a C# script.

public enum EnemyState
{
    Idle,
    Patrol,
    Chase,
    Attack,
    Dead
}

For a more flexible and reusable structure, each state can be its own class (the State pattern). Every state class has EnterState, UpdateState and ExitState methods, and the character or AI class simply runs the current state.

Unity's Animator (Mecanim) is an FSM as well. Each animation clip is a state, and the transitions between them are set with bool, trigger, float and int parameters. For example, the character switches to the run animation when its speed is above zero. The Animator is great for animations. Keeping game logic such as AI in an FSM written in C# is usually the cleaner choice.

A boss character as an example

Think of a powerful boss character with five states. It waits until the player comes close (Idle). Then it starts its first attack patterns (PhaseOne). When its health drops below half, it moves on to new attacks and traps on the floor (PhaseTwo). When it takes a certain hit, it gets angry and attacks faster for a short time, then returns to the second phase (Rage). When its health reaches zero, the death animation plays (Dead). With an FSM, the attack and movement logic of each phase stays separate and easy to maintain.

Pathfinding algorithms

Finding the way from an enemy to the player is a graph problem. Points on the map are nodes and the routes between them are edges. In the training we compared five approaches.

BFS (breadth first search)

BFS explores a graph layer by layer. It first visits the neighbours of the start node, then their neighbours, until every node is reached, and it uses a queue to do so. When all edges have the same weight, BFS finds the shortest path, and it easily lists the nodes at a given distance. On deep graphs with many branches it can use a lot of memory, and when edge weights differ it cannot find the true shortest path.

DFS (depth first search)

DFS goes down one branch to its end, then backtracks and moves on to the branches it has not visited yet. It is written with a stack or with recursion. DFS does not guarantee the shortest path.

Dijkstra's algorithm

Dijkstra finds the shortest path on graphs whose edges have positive weights. It calculates the shortest distances from the start node to all other nodes with a priority queue. Unlike BFS, it also works when the weights differ. A positive weight means that crossing that edge has a cost or a distance. Dijkstra gives wrong results when there are negative weights, and the priority queue operations take more time as the search grows.

The A* algorithm

A* also looks for the shortest path, but it speeds up the search with a heuristic. For every node it works out f(n) = g(n) + h(n). Here g(n) is the real cost from the start to the node and h(n) is the estimated cost from the node to the goal. On grid maps the Manhattan distance, the sum of the horizontal and vertical differences, is a common choice for h(n). The straight line (Euclidean) distance works too. A good heuristic cuts unnecessary branching, so A* is faster than Dijkstra in most cases.

The greedy approach

A greedy algorithm makes the choice that looks best at each step. It is simple to write and fast to compute, and for some problems such as Huffman coding and the algorithms of Prim and Kruskal it reaches the best solution. It does not always find the best overall result, because the best local choices made step by step may not solve the whole problem in the best way.

Comparing them

Algorithm	Shortest path	Weights	Heuristic	Time complexity
BFS	Only with equal edge weights	No	No	O(V + E)
DFS	No	No	No	O(V + E)
Dijkstra	Yes	Positive	No	O((V + E) log V)
A*	Yes	Positive	Yes	O((V + E) log V), faster in practice with a good heuristic
Greedy	Depends on the problem	Varies	No	Varies

Here V is the number of nodes and E the number of edges.

Coding a game together

After the theory it was time to practise. Batuhan's introduction to game coding and the algorithms above came together in a game we wrote with the students. You can watch short moments from the session below.

Thank you

Many thanks to the IEEE Başkent University Student Branch, its Computer Society committee and its Artificial Intelligence Study Group for hosting us, and to every student who joined. If you have a question about game AI, you can always write to us.