Reading: 'Artificial Intelligence for Games', and AI planning

As I have now implemented the inventory system into my game, following my previous post The Inventory System, I have put time into researching AI development for games. At this point, I have never tackled AI to a high level standard, with most consisting of AI repeating an action, or homing in on a player character. To learn more, and hopefully find a starting point, I read Artificial Intelligence for Games (2009, Millington, I & Funge, J). Below are the notes I have taken from my reading:

Artificial Intelligence for Games

Millington, I & Funge, J

1.2 Model of Game AI

The AI Model provided within the book.

Model splits AI tasks into three groups; Decision Making, Movement, and Strategy.

Decision Making & Movement contain algorithms working on a per-character basis.

Strategy operates on a whole team.

Board games (Chess, Risk) only require Strategy level.

Platform games (Jak and Daxter, Oddworld) only require Decision Making and Movement level.

1.2.1 Movement

If a character is attacking in melee, they will home in on the player, only activating the attack animation at a certain range.

Movement can be more complex; e.g. Splinter Cell, if the player is seen by a guard, they may attempt to locate the closest wall-mounted alarm, which can involve navigation over long distance.

1.2.2 Decision Making

“Involves a character working out what to do next.”

Will typically have a range of behaviours to choose from, decision making system need to work out the most appropriate behaviour at the given time.

Zelda games; farm animals stand still, move a small distance if bumped into.

Half-Life 2; enemy AI attempt multiple strategies to reach the player.

1.2.3 Strategy

Most action-based 3D games use only Decision Making and Movement.

“Strategy refers to an overall approach used by a group of characters.” In context of the book.

Will often still require characters to have their own Decision Making and Movement, with Decision Making being influenced by the group Strategy.

1.2.4 Infrastructure

To build an AI, a whole set of additional infrastructure is required.

Movement requests must be turned into action in the game.

AI requires game information to make sensible decisions, sometimes called “perception”; “working out what information the character knows”.

“World Interfacing is often a large proportion of the work done by an AI programmer”, and often the majority of AI debugging.

AI systems need to be managed to use the correct processor time and memory.

1.2.5 Agent-Based AI

Focused on “producing autonomous characters that take in information from the game data, determine what actions to take based on the information, and carry out those actions.”

Can be seen as a bottom-up design:

• ·         Work out how each character will behave, and the AI required to support it
• ·         Overall behaviour of the game is a function of how character behaviours work together
• ·         Decision Making and Movement make up the AI for an in-game agent

Non-Agent-Based AI act oppositely, from top to bottom. E.g. Pedestrians and traffic in Grand Theft Auto 3. Traffic and pedestrian flow is calculated via the time of day and the region of the city, and is only turned into singular cars and pedestrians when in view of the player.

“A good AI developer will mix and match any reliable techniques that get the job done, regardless of approach”.

1.3 Algorithms, Data Structures, and Representations

1.3.1 Algorithms

They are step-by-step processes, generating a solution to problems faced by AI.

Data structures hold data that allow the algorithm to quickly manipulate it and reach a result.

Data structures must often be tuned for one specific algorithm.

Set of elements must be understood to implement and refine an algorithm:

·         The problem that the algorithm tries to solve

·         A general description of how the solution works, including diagrams where needed

·         Pseudo-code presentation of the algorithm

·         An indication of the data structures required to support the algorithm, including pseudo-code where required

·         Particular implementation nodes

·         Analysis of algorithms performance: Execution speed, memory footprint, scalability

·         Weaknesses in approach

5.2 Decision Trees

“Fast, easily implemented, and simple to understand.”

Simplest technique discussed in book, with the potential to become quite sophisticated.

Very modular and easy to create.

5.2.1 The Problem

Using a set of knowledge, corresponding actions must be generated from a set of possible actions.

Mapping between input and output can become complex.

Same action may be used for multiple inputs, but a change in one input value can turn that action from sensible to stupid.

Require a method capable of easily grouping lots of input together under one action, while allowing the significant input values to control the output.

5.2.2 The Algorithm

Decision tree is made up of connecting points, starting at a “root” decision, with ongoing options being chosen thereafter.

Example of a decision tree

Choices are made based on the characters knowledge, often referring directly to the global game state, rather than a personal representation.

Algorithm continues along the tree until there are no more decisions to consider. An action is attached to each leaf. Once a leaf is reached, the relating action will be carried out.

Tree decisions will often be simple, with only two responses.

NOTE: Even just at this point, I feel a lot more confident pushing into the AI, structuring a tree in my mind that will be put onto paper. Though I have seen tree diagrams and flowcharts used in many ways previously, it never occurred to me that it could be implemented into AI Decision Making.

Common for object-oriented engines to allow the tree to access methods of instances.

To AND two decisions, they are placed in series in the tree; “I A AND B, then carry out Action 1, otherwise carry out action 2.”

To OR two decisions, they are placed in the opposite series in the tree; “If A OR B, then carry out Action 1, otherwise carry out action 2.”

An AND and OR tree

As decisions are built into the tree, the amount considered will be much smaller than the amount within the tree.

Can be built in stages; simple tree can be initially implemented, with additional decisions added on as needed.

Can be given more than two options to choose from;

Guard in a military facility, decisions based on current alert status; green, yellow, red, or black. Using binary decisions, the alert value must be checked three times. Using multiple branching, the value can be checked once for the decision.

Implementation of multiple branches are not as easily optimised as binary. Majority will always be binary.

Following on from this reading, I felt like I had a much clearer understanding of how to tackle my AI, and went about creating a simple decision tree for my AI:

Using this tree as a basis, I have gone on to pseudo-code the process:


While I believe there may be further tweaking required once implementing the code, the process of creating the decision tree, and writing some basic pseudo-code for the process, has greatly helped my learning process, and eased many concerns I had towards AI.

Tomorrow I shall begin implementation of the code, and hopefully have a level of working AI before the week is out.

Bibliography

Millington, I & Funge, J (2009). Artificial Intelligence for Games. 2nd ed. Burlington, MA: Morgan Kaufmann. p8-12, 295-300.