Game ProgrammingAI

Nick Prühs, Christian Oeing

Objectives

• To understand the importance of AI in games

• To learn about different approaches to game AI architectures

• To take a closer look at behavior trees in particular

2 / 90

Why AI?

• Enemies

• Allies

• Challanges

• Vivid game world

• Toy

3 / 22

Early Example: Pac Man

“This is the heart of the game. I wanted each ghostly enemy to have a

specific character and its own particular movements, so they weren’t all

just chasing after Pac Man in single file, which would have been

tiresome and flat.”

- Toru Iwatani, Pac-Man creator

4 / 22

Early Example: Pac Man

5 / 22

http://gameinternals.com/post/2072558330/understanding-pac-man-ghost-behavior

Left 4 Dead

6 / 22

http://www.valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf

Naive Approach: Hard-Coded Rules

• If-Then-Else

• Hard-coded

• Fast to implement

• Access to whole data model

• No fixed structure

7 / 22

Finite State Machine

• Splitting AI into different states

• Arbitrary number of states

• Well-defined state transitions

8 / 22

Hierarchical FSM

9 / 22

• Hierarchical Structure

• Allows transitions at same level, only

• Drastically reduces the total number

of transitions

Planner

• Goal-oriented

• Specific AI not defined by developer

10 / 22

Utility-based

• Action-based, similar to planner

• No goal, thus no action chains

11 / 22

Neural Networks

• Improving AI through training data

• No way of modifying the AI after training

• Further reinforces the disadvantages of action-based architectures

• Rarely applied in games

• Exceptions:

▪ Creatures

▪ Supreme Commander 2

12 / 22

Behaviour Trees: History

• Became popular in 2005 with Halo 2

• Successfully implemented in

▪ Halo 2 + 3

▪ Spore

▪ Swords & Soldiers

▪ GTA: Chinatown Wars

▪ The Bourne Conspiracy

▪ SWAT 4

▪ Bioshock

▪ Dark Sector

▪ … and more

13 / 22

Behaviour Trees: What‘s new?

• Similar to Finite State Machines

• Split decision logic from actual actions

14 / 22

Behaviour Tree Structure

• Directed tree

▪ Single root node

▪ Inner nodes = decision logic

▪ Leafs = Actions

15 / 12

Behaviour Tree Ticks

• Tick starts at root node

• Current node executes its logic

• Node state is reported back to parent node:

▪ Success

▪ Running

▪ Failure

16 / 12

Behaviour Tree Tick Example

17 / 12

Prioritized Structure

• Children are executed left-to-right

18 / 12

Modular Structure

• Adding new nodes possible everywhere

19 / 12

Parametrized Structure

• Node defines parameters and their types

• Parameters definie actual execution

• Increases reusability

• Example: Move to position

20 / 12

Data Exchange

• Achieved thorugh a blackboard

• Dynamically defines parameters of other nodes

• Nodes remain independent of each other

• Simple implementation, e.g. Dictionary or Hashtable

21 / 12

Node: Selector

• Arbitrary number of children

• Only one child node active at the same time

• Selects first child that doesn‘t return Failure

22 / 12

Node: Sequence

• Arbitrary number of children

• Only one child node active at the same time

• Selects children one after another until one returns Failure

23 / 12

Combining Sequences and Selectors

24 / 12

Node: Decorator

• Single child

25 / 12

Blackboard

• AI memory

• Exchanges data between nodes

26 / 12

Blackboard

• Keys need to be unique

• May cause conflicts

27 / 12

Picklock

• Easiest way to enter building: Open door!

28 / 12

Picklock

• Not always that easy

29 / 12

Picklock

• Generic way of entering a building through any kind of entrance

30 / 12

Picklock

• There are many ways to get in

31 / 12

Crafting

• Using ingredients to create new items

• Ingredients need to be available

• What to do, if missing any ingredients?

• Ingredients might be crafted as well

32 / 12

Crafting

33 / 12

More Examples

• Combat: Fighting, healing, running, taking cover

• Survival: Running, guarding, fighting, eating

• Strategy: Training workers, building structures, training fighters

• Dialogues: Conditional answers, linked answers

34 / 12

Data Driven

• Structure allows building a generic visual editor

• Usable by game designers as well

• Can be used in multiple projects

35 / 12

Available Tools

• Unity3D

▪ Behave 2 (Angry Ant)

▪ Behavior Designer (Opsive)

• Unreal Engine

▪ Built-in

• Cry Engine

▪ Built-in

36 / 12

Custom Tools

• Define data structure

▪ e.g. XML, easy to read and edit

38 / 12

<BehaviorTree Name="CraftItem"><Sequence>

<Action Type="HasRecipe" List="Ingredients" /><Decorator Type="Iteration" List="Ingredients" Iterator="Ingredient" >

<Sequence><Selector>

<Action Type="TakeItemFromInventory" ItemRef="Ingredient" StoreIn="IngredientItem" /><Action Type="SearchItem" ItemRef="Ingredient" Distance="50" StoreIn="IngredientItem" /><BehaviorTreeRef Name="CraftItem" ItemRef="Ingredient" StoreIn="IngredientItem" /><Action Type="SearchItem" ItemRef="Ingredient" Distance="500" StoreIn="IngredientItem" />

</Selector><Action Type="PutItemInList" ItemRef="IngredientItem" List="IngredientItems" />

</Sequence></Decorator><Action Type="MixIngredients" List="IngredientItems" />

</Sequence></BehaviorTree>

Custom Tools

• Generic approach

• How to make game-specific actions available to generic editor?

▪ Use editor to add actions

▪ Export from game and import in editor

▪ Generic actions

▪ Import from DLL using reflection

39 / 12

Behaviour Tree Summary

• Generic structure leads to many applications

▪ Reuse of decision logic and game-specific actions

▪ Common editor for multiple projects

▪ Learn once, apply again and again

• Strictly follows rules

▪ No dynamic AI, such as when using Planner

40 / 12

Conclusion

• Many different architectures

▪ (Hierarchical) Finite State Machines

▪ Planner

▪ Utility-based

▪ Neural Network

▪ Behavior Trees

• Choice depends on actual game

• Each architecture is better than no architecture!

41 / 22

References

• Heiko Klinge. Warum KI in Spielen stagniert. http://www.tecchannel.de/webtechnik/entwicklung/1744817/warum_kuenstliche_intelligenz_ki_in_spielen_stagniert/

• Chad Birch. Pac Man AI. http://gameinternals.com/post/2072558330/understanding-pac-man-ghost-behavior

• Don Hodges. Pac Man AI Bug. http://donhodges.com/pacman_pinky_explanation.htm

• Alex Champandard. Top AI Games. http://aigamedev.com/open/highlights/top-ai-games/

• Mike Robbins. Neural Network in Supreme Commander 2. http://twvideo01.ubm-us.net/o1/vault/gdc2012/slides/Summit_AI/Robbins_Michael_Off%20the%20Beaten.pdf

• Mike Booth. The AI systems of Left 4 Dead. http://www.valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf

• Damian Isla. Handling Complexity in the Halo 2 AI. http://www.gamasutra.com/view/feature/130663/gdc_2005_proceeding_handling_.php

• Alex Champandard. Behavior Trees: Three Ways of Cultivating AI. http://www.gdcvault.com/play/1012744/Behavior-Trees-Three-Ways-of

References

• Chris Simpson. Behavior Trees for AI.

http://www.gamasutra.com/blogs/ChrisSimpson/20140717/221339/Behavior_trees_for_AI_How_t

hey_work.php

• Cry Engine. Coordinating Agents with Behavior Trees.

http://docs.cryengine.com/display/SDKDOC4/Coordinating+Agents+with+Behavior+Trees

• Chris Hecker. My Liner Notes for Spore.

http://chrishecker.com/My_Liner_Notes_for_Spore#Behavior_Tree_AI

• Joost "Oogst" van Dongen. AI in Swords & Soldiers. http://joostdevblog.blogspot.de/2010/12/ai-in-

swords-soldiers-part-1.html

• Unreal Engine. Behavior Trees.

https://docs.unrealengine.com/latest/INT/Engine/AI/BehaviorTrees/index.html

• Cry Engine. Modular Behavior Tree.

http://docs.cryengine.com/display/SDKDOC4/Modular+Behavior+Tree

Thank you!

http://www.npruehs.de

https://github.com/npruehs

@npruehs

nick.pruehs@daedalic.com

5 Minute Review Session

• Name a few applications of AI in general!

• How do finite state machines work?

• How do hierarchical state machines improve on that?

• What other AI architectures do you know?

• What’s the basic structure of a behavior tree?

• How do sequences and selectors work?

• What’s a decorator node?

• How do nodes exchange data?