Game AI technologies for online games
KGC2007

Youichiro Miyake
y.m.4160@gmail.com
2007/11/9

Contact Information
Youichiro Miyake• Mail：y.m.4160@gmail.com• Twitter: @miyayou• Blog：http://blogai.igda.jp• LinkedIn: http://www.linkedin.com/in/miyayou• Facebook： http://www.facebook.com/youichiro.miyake

AI Demo④movie

concentrated attack

All autonomous agents think and act by themselves

Game AI technologies for online games
Historical Reviews of Game AI technologies and the future

Youichiro Miyake
y.m.4160@gmail.com
2007/11/9

Address of thanks
I feel honored the invitation to this famous conference.
This is my second visit to Korea.
For the master’s degree,
I studied physics with three Korean students of Soul University.
Now I’m working with two Korean programmers in Tokyo, Japan,
and everyday I have lunch with a Korean friend.
All Korean friends are kind, polite, and wise !
Youichiro Miyake
On Monday ~ Friday, I’m working in Sibuya, Tokyo, JapanOn Saturday~Sunday, I’m playing in Akihabara and so on…

Contents(Chapter.1)(Chapter.2)(Chapter.3)

Game AI Overview
Game AI Technologies
SummaryChapter 1.
Game AI Overview

History of technologies for developing digital gameFC

SFC

SS, PS

PS2,GC,Xbox

1999 DC

Hardware2005

Xbox360, PS3, Wii
2007

（次世代）
次世代）

時間軸

TV game3D
period of growth
period of maturity
Beginning

NetworkAI
Physics

Game AI technologies will grow in this game age (2005~), andit will mature in the next age.

Game design & AI technologies
Game design with AI technologies

Game design
without AI

AI technologies expand the possibilities of game design!

Perspective of game AI
When you stand on fundamental game AI technologies,
You can see further more…

Evolution and learning
Heuristic Finite State Machine
Multiagent
Planning
World representation
Knowledge representation

Game AI Seminars in Japan
Many developers in Japan
gather in the seminars
Intenational Game Developer
Association Japan!
5th

Neural Net & GA

4th
3rd

HFSM
multiagent

2nd

Planning

1sr Knowledge representation

In our company(once a week/～９０times)

FromSoftware

IGDA Game AI seminars(once a two month/6 series)

How? Two categories in game AI
Game ＡＩ

Character AI
AI in game system

For control of NPC

For control of game system

Agent architecture
C4 architecture

Level control
Auto-generation of terrain

Knowledge representation
Planning
FSM

Difficult to be unified

Genetic algorithm

Recent flow of game AI technologies
PS2,GC,XboxXbox360, PS3, Wii

2005

DC

Time

（次世代）
次世代）

2000
C4 architecture(MIT Media Lab.)

2002

2004

Halo
(Bungie Studio)

Halo2(Bungie Studio)

2001
Killzone(Guerrilla)

2005

2006

F.E.A.R.
(Monolith Production)

Chromehounds(FromSoftware)Recent flow of game AI technologies
PS2,GC,XboxXbox360, PS3, Wii

2005

DC

（Next gen.）
）

Time

2000
Agent architecture
C4 architecture(MIT Media Lab.)

2002

Event analysis
Halo(Bungie Studio)

2004 FSM
Heuristic(FiniteState Machine)
Halo2(Bungie Studio)

2005
Goal
oriented
F.E.A.R.
ActionPlanning(Monolith Production)

2006
Hierarchical planning
Chromehounds(FromSoftware)

2001
World representation
Killzone(Guerrilla)

Game AI techniques are developed on the basis of previous works !

Recent flow of game AI technologies
PS2,GC,XboxXbox360, PS3, Wii

2005

DC

①2000
Agent architecture
C4 architecture(MIT Media Lab.)③ 2002④ 2004

Event analysis
Halo(Bungie Studio)(Bungie Studio)

Time

Heuristic FSM(FiniteState Machine)
Halo2

⑤

② 2001（Next gen.）
）

2005
Goal
oriented
F.E.A.R.
ActionPlanning(Monolith Production)⑥

Multiagent
2006 system
Hierarchical planning
Chromehounds(FromSoftware)World representation
Killzone(Guerrilla)

New game AI techniques are developed on the basis of previous works !

What you can do to develop more intelligent
game AI for game designers and programmers① Research② Study

Research papers published
in GDC and scientificjournals !
(in these time you can get
most papers on internet.)

On the basis of thesetechnologies explained in papers,
develop techniques for gameAI !

③ Implement

For a game you aredeveloping, apply thesetechnologies!
Think new game design
With new AI techniques !
Think how to implementwith programming laguage
you use !

In this lecture, game AI technologies are explained along these three steps !

For learning…
For explaining all these technologies, I need 2.5 x 6 = 15 hours.
(In IGDA seminars in Japan, I had 15 hours lecture… )But today I have only 1 hours,
I must speak as rapidly as I can for introducing all topics…
You should understand how to learn game AI techniques,
rather than what I explained exactly !

Chapter 2.
Game AI technologies

Contents
1.
2.
3.
4.
5.
6.

Agent architecture C4 Architecture (MIT Media Lab.)
Knowledge representation Killzone (Guerilla)
Event analysis Halo (Bungie Studio)
Heuristic FSM Halo2 (Bungie Studio)
Goal-oriented Action Planning F.E.A.R. (Monolith)
Multiagent system Chromehounds (FromSoftware)Recent flow of game AI technologies
PS2,GC,XboxXbox360, PS3, Wii

2005

DC

①2000
Agent architecture
C4 architecture(MIT Media Lab.)

2002

Event analysis
Halo(Bungie Studio)（Next gen.））Time

2004 FSM
Heuristic(FiniteState Machine)
Halo2(Bungie Studio)

2005
Goal
oriented
F.E.A.R.
ActionPlanning(Monolith Production)

2006
Hierarchical planning
Chromehounds(FromSoftware)

2001
World representation
Killzone(Guerrilla)

New game AI techniques are developed on the basis of previous works !

Character AI

1.

Agent architectureThree Steps① Research② Study

Research papers published
in GDC and scientificjournals !
(in these time you can get
most papers on internet.)

On the basis of thesetechnologies explained in papers,
develop techniques for gameAI !

③ Implement

For a game you aredeveloping, apply thesetechnologies!
Think new game design
With new AI techniques !
Think how to implementwith programming laguage
you use !

In this lecture, game AI technologies are explained along these three steps !

① Research References for C4 Architecture(1) MIT Media Lab Synthetic Characters Group,
http://characters.media.mit.edu/(2) R. Burke, D. Isla, M. Downie, Y. Ivanov, B. Blumberg,(GDC2001), “CreatureSmarts: The Art and Architecture of a Virtual
Brain”,http://characters.media.mit.edu/Papers/gdc01.pdf(3) D. Isla, R. Burke, M. Downie, B. Blumberg (2001)., “A Layered
Brain Architecture for Synthetic Creatures”,
http://characters.media.mit.edu/Papers/ijcai01.pdf(4) D. Isla, B. Blumberg (2002), “Object Persistence for Synthetic
Characters”,http://characters.media.mit.edu/Papers/objectPersistence.pdf(5) Movies of Duncan,http://web.media.mit.edu/~bruce/whatsnew.html(6) Object Persistence for Synthetic Characters. D. Isla, B. Blumberg. In
the Proceedings of the First International Joint Conference on
Autonomous Agents and Multiagent Systems,
AAMAS2002.,http://characters.media.mit.edu/Papers/objectPersistence.pdf
Figures on following pages are from these references.

Three Steps① Research② Study

Research papers published
in GDC and scientificjournals !
(in these time you can get
most papers on internet.)

On the basis of thesetechnologies explained in papers,
develop techniques for gameAI !

③ Implement

For a game you aredeveloping, apply thesetechnologies!
Think new game design
With new AI techniques !
Think how to implementwith programming laguage
you use !

In this lecture, game AI technologies are explained along these three steps !

② Study

What is Agent ?

Three conditions for “agent”① Sensor to get information of environment② Decision-making to decide its will
③ Effecter to action in the world！

SensorDecision-making

Effect on the world

Agent of gameGame world

Sense
the game world around himself

Effect on the game world
through his body

Flow of information
between an agent and a game world
Information
flow
NPC

Sense
the game world around himself

Effect on the game world
through his bodyGame world

Agent architecture

time

NPC’s intelligence

From a view of NPC

Cognition
Process

Decisionmaking

behaviorgeneration
processmodeling

MemoryStatusSensorEffectersense

actionKnowledge representation
World representation(data extracted and abstracted from game world)

Body

Game World
interactiontimeAgent architecture

time

NPC’s intelligence

From a view of NPC

Cognition
Process

Decisionmaking

behaviorgeneration
processmodeling

MemoryStatusSensorEffectersense

actionKnowledge representation
World representation(data extracted and abstracted from game world)

Body

Game World
interactiontimeAgent architecture
From a view of NPC

Cognition
Process

time

NPC’s intelligence
behaviorDecisiongeneration
Technology
makingprocess（implemented in each module）

modeling

MemoryStatusSensorEffectersense

actionKnowledge representation
World representation(data extracted and abstracted from game world)effect

Body

Game World
interactiontimeThree Steps① Research② Study

Research papers published
in GDC and scientificjournals !
(in these time you can get
most papers on internet.)

On the basis of thesetechnologies explained in papers,
develop techniques for gameAI !

③ Implement

For a game you aredeveloping, apply thesetechnologies!
Think new game design
With new AI techniques !
Think how to implementwith programming laguage
you use !

In this lecture, game AI technologies are explained along these three steps !

③ Implement

C4 Architecture (2001)
AI for virtual creature

MIT Media Lab.
Synthetic Characters Group
論文：
論文：

D. Isla, R. Burke, M. Downie, B. Blumberg (2001).,“A Layered Brain Architecture for Synthetic Creatures”,
http://characters.media.mit.edu/Papers/ijcai01.pdf（One of the most important papar for game AI ）Real AI of virtual dog who lives in virtual world was developed,
and this architecture was applied to F.E.A.R.

C4 Architecture
Real AI for virtual creature in virtual world（Example）“Duncan”“Duncan” have intelligence and memories anda player can teach him through his voice.

MIT Media Lab. C4 Architecture
Time

NPC’s intelligence
Cognitive
tree

PercepMemoryObjects

SensorMotorsystemActionSelection

Working Memory

Blackboard
MotionWorld Representation
Body

Game world
InteractionTimePercept Tree and Working Memory

MemoryExtract & Classify(time-continuous)

Information extracted and classified through percept tree
is stored in Working Memory sequentially.

What do memories enable ?
＝ Prediction & surprise

Following an object!

Even if an object becomes behind a wall,
he can follow its orbit by using his memories!
But if an ball is disappeared against his prediction ,Duncan becomes surprised !

MIT Media Lab. C4 Architecture
Time

NPC’s intelligence Percept tree
Cognitive
Action
memories
認識
tree モーション Selection
アクションとMotor
systen

対象の選択タプル
ツリー

PercepMemoryObjects

SensorBlackboard

Working Memory

Motion① Prediction & Surprise② Human-like Mistake
World Representation③ Learning④ Proper perception
Game world
Interaction

Time

Body

Recent flow of game AI technologies
PS2,GC,XboxXbox360, PS3, Wii

2005

DC

①2000
Agent architecture
C4 architecture(MIT Media Lab.)

2002

Event driven
Halo(Bungie Studio)② 2001（Next gen.））Time

2004 FSM
Heuristic(FiniteState Machine)
Halo2(Bungie Studio)

2005
Goal
oriented
F.E.A.R.
ActionPlanning(Monolith Production)

2006
Hierarchical planning
Chromehounds(FromSoftware)World representation
Killzone(Guerrilla)

New game AI techniques are developed on the basis of previous works !

Store & Extract
Store

World information

Extract

PercepMemoryObjects

Working Memory

New information

Contents
1.
2.
3.
4.
5.
6.

Agent architecture C4 Architecture (MIT Media Lab.)
Knowledge representation Killzone (Guerilla)
Event analysis Halo (Bungie Studio)
Heuristic FSM Halo2 (Bungie Studio)
Goal-oriented Action Planning F.E.A.R. (Monolith)
Multiagent system Chromehounds (FromSoftware)

Character AI

2.

Knowledge representation

① Research

Killzone 内容： FPS
 開発元：Guerrilla Publisher: SCEE （Europe）、SEGA (Japan）
 Hardware: PS2
 出版年： 2004-2005 (Million seller) Online （not for Japanese version）

References for Killzone[1] William van der Sterren (2001),"Terrain Reasoning for 3D Action Games",
http://www.cgf-ai.com/docs/gdc2001_paper.pdf[2] William van der Sterren (2001) ,"Terrain Reasoning for 3D Action
Games(GDC2001 PPT)", http://www.cgf-ai.com/docs/gdc2001_slides.pdf[3] Remco Straatman, Arjen Beij, William van der Sterren (2005) ,"Killzone's
AI : Dynamic Procedural Combat Tactics", http://www.cgfai.com/docs/straatman_remco_killzone_ai.pdf[4] Arjen Beij, William van der Sterren (2005),"Killzone's AI : Dynamic
Procedural Combat Tactics (GDC2005)", http://www.cgfai.com/docs/killzone_ai_gdc2005_slides.pdf[5] Damian Isla (2005), "Dude, where’s my Warthog? From Pathfinding to General
Spatial Competence", http://www.aiide.org/aiide2005/talks/isla.ppt

Figures on following pages are from these references.

② Study

Killzone NPC

Strategic movement in a large map

In battle fieldMax７ｖｓ７
ｖｓ７(one of 7 is player)

My team

Human（Strong）Human

AI Ememies

Agent architecture
time

NPC’s intelligence

Effecter

SensorKnowledge representation
World representation

Body

Game World
interactiontimeKnowledge representation！

Game world

Knowledge
Representation（data）？

It should be prepared by a developer

World representation
Knowledge representation of global informationof the game world？

！

Data for AI

(Example) Waypoint data？

I can find away !

Terrain polygon data

Waypoint data

(Example) Waypoint data
point coordinate + intensity of lighting？

I can find alight way !

Terrain polygon data

Waypoint data +Intensity of lighting

(Example) Waypoint data
point coordinate + intensity of lighting+ LOS(line of sight) from east？

Enemies come from east !
I can find a dark way which cannot
be seen from east !

14

8

3

5

6

3

3

Terrain polygon data

Waypoint data
+ Intensity of lighting+ LOS(line of sight) from east③ Implement
Killzone: Look-up table for waypoint visibility

LOS(line of sight) with a quick calculation

How to use world representation ①

Tactical position picking

Step1 selected nearby waypoint, annotated with proximity

Step2 Annotations for positions with a line-of-fire to primary threat

40 … LOF only to crouched stance
20 … LOF both to standing and crouched stanceStep3 Annotations for positions with cover from the secondary threatsStep4 Annotations for positions inside the preferred fighting range

Step5 Adding up Step1~4 annotations yields the best attack position

Dynamic tactical position picking

Killzone
time

DynamicＮＰＣの知能部分
tactical position picking

センサー
世界表現
Look-uptable forwaypoint visibility
Knowledge
representation
ゲーム世界
World representation

エフェクター①tactical position picking②tactical path finding③supprresion fire
Body

Game World
interaction

timeRecent flow of game AI technologies
PS2,GC,XboxXbox360, PS3, Wii

2005

DC

①2000
Agent architecture
C4 architecture(MIT Media Lab.)③ 2002

Event analysis
Halo(Bungie Studio)② 2001（Next gen.））Time

2004 FSM
Heuristic(FiniteState Machine)
Halo2(Bungie Studio)

2005
Goal
oriented
F.E.A.R.
ActionPlanning(Monolith Production)

2006
Hierarchical planning
Chromehounds(FromSoftware)World representation
Killzone(Guerrilla)

New game AI techniques are developed on the basis of previous works !

Contents
1.
2.
3.
4.
5.
6.

Agent architecture C4 Architecture (MIT Media Lab.)
Knowledge representation Killzone (Guerilla)
Event analysis Halo (Bungie Studio)
Heuristic FSM Halo2 (Bungie Studio)
Goal-oriented Action Planning F.E.A.R. (Monolith)
Multiagent system Chromehounds (FromSoftware)① Research

Reference for Halo & Halo2

 Damian Isla (2005), “Dude, where’s my Warthog? From
Pathfinding to General Spatial Competence”,
http://www.aiide.org/aiide2005/talks/isla.ppt
http://nikon.bungie.org/misc/aiide_2005_pathfinding/index.html

 Damian Isla (2005), Handling Complexity in the Halo 2
AI, Game Developer's Conference Proceedings.,
http://www.gamasutra.com/gdc2005/features/20050311/isla_01.shtml

 Jaime Griesemer(2002),The Illusion of Intelligence: The
Integration of AI and Level Design in Halo,
http://halo.bungie.org/misc/gdc.2002.haloai/talk.html

 Robert Valdes(2004), “In the Mind of the Enemy
The Artificial Intelligence of Halo2”,
http://www.stuffo.com/halo2-ai.htm (現在はclosed)

Figures on following pages are from these references.

Halo (2002)







Game：SF/FPS
Developer： BUNGIE Studio
Publisher: Microsoft
Hardware: Xbox, Windows, Mac
Publishing year： 2002

Halo NPC Architecure
Event“Enemy found!”“Friend dead”“I was shot!”“Player shot !”Sensor

NPC’s intelligence
Situation
Analysis

Decisionmaking

Body
Interaction

Time

MotionControl

Emotion（only for dramaturgy）
Working Memory

Knowledge representation/
World representationGame world

Time

MotionHalo AI decision-making

ＦＳＭ

Event

Simple logic for selecting an action
for each character from a situation.

Level designers’ work
Event

DecisionMaking
ＦＳＭ
Each behavior has a trigger to cause.
An event causes some numbers of behaviors

Halo NPC Architecure
Event“Enemy found!”“Friend dead”“I was shot!”“Player shot !”

NPC’s intelligence

Situation analysis
Situation logic
DecisionDecision-making
AnalysismakingEmotionSensorInteraction

Time

MotionControl

Emotion（only for dramaturgy）
Working Memory①Knowledge
Responserepresentation/
to an event② Properreaction of each character
World representation③ Emotion & Dialogues
Game world

Time

Body

MotionRecent flow of game AI technologies
PS2,GC,XboxXbox360, PS3, Wii

2005

DC

①2000
Agent architecture
C4 architecture(MIT Media Lab.)③ 2002④ 2004

Event driven
Halo(Bungie Studio)(Bungie Studio)② 2001（Next gen.））

Time

Heuristic FSM(FiniteState Machine)
Halo2

2005
Goal
oriented
F.E.A.R.
ActionPlanning(Monolith Production)

2006
Hierarchical planning
Chromehounds(FromSoftware)World representation
Killzone(Guerrilla)

New game AI techniques are developed on the basis of previous works !

Contents
1.
2.
3.
4.
5.
6.

Agent architecture C4 Architecture (MIT Media Lab.)
Knowledge representation Killzone (Guerilla)
Event analysis Halo (Bungie Studio)
Heuristic FSM Halo2 (Bungie Studio)
Goal-oriented Action Planning F.E.A.R. (Monolith)
Multiagent system Chromehounds (FromSoftware)Halo2 (2004)







Game：SF/FPS
Developer： BUNGIE Studio
Publisher: Microsoft
Hardware: Xbox, Windows, Mac
Publishing year： 2004

Halo2 NPC Architecure
Event“Enemy found!”“Friend dead”“I was shot!”“Player shot !”Sensor

NPC’s intelligence
Situation
Analysis

Decision- DAG Motion
making HFSM Control

Emotion（only for dramaturgy）
Working Memory

Knowledge representation/
World representationGame world

Body
Interaction

Time

Time

MotionDecision-making by HFSM（Hierarchical FSM）
ＤＡＧ (Directed acyclic graph) = behavior tree
Retreat

Flee

Cover
Self-preservation
Guard

Grenade
Vehicle strafe
ChargeRoot

Melee
Vehicle fightEngageIdle

0th layer

1st layer

Fight

Presearch

Search

Uncover

Guard

Investigate

Guard

2nd layer

3rd layer

How to use HFSM
Order & Style
Define conditions
for area transition

Behavior lists that NPC can execute

Area

Position
Zone

Halo2 NPC Architecure
Event“Enemy found!”“Friend dead”“I was shot!”“Player shot !”NPC’s intelligence
Situation
AnalysisTime HFSMDAG Motion
Decisionmaking ＨＦＳＭ Control
ゲーム世界

Sensor

Emotion（only for dramaturgy）
Working Memory

Knowledge 3-layered
Worldrepresentation/
representation

World representationGame world
ゲーム世界

Time

Motion① for each character② for each situation③ for each area
Body (=HFSM)
unified method
Interaction(-> Scalable AI)

Recent flow of game AI technologies
PS2,GC,XboxXbox360, PS3, Wii

2005

DC

①2000
Agent architecture
C4 architecture(MIT Media Lab.)③ 2002④ 2004

Event analysis
Halo(Bungie Studio)(Bungie Studio)

Time

Heuristic FSM(FiniteState Machine)
Halo2

⑤

② 2001（Next gen.）
）

2005
Goal
oriented
F.E.A.R.
ActionPlanning(Monolith Production)

2006
Hierarchical planning
Chromehounds(FromSoftware)World representation
Killzone(Guerrilla)

New game AI techniques are developed on the basis of previous works !

Contents
1.
2.
3.
4.
5.
6.

Agent architecture C4 Architecture (MIT Media Lab.)
Knowledge representation Killzone (Guerilla)
Event analysis Halo (Bungie Studio)
Heuristic FSM Halo2 (Bungie Studio)
Goal-oriented Action Planning F.E.A.R. (Monolith)
Multiagent system Chromehounds (FromSoftware)

Goal-Oriented Planning

What is Goal-Oriented Planning ?

What is “goal-orietned” ？
AI who can find his purpose from its environment !

For video games, developer must prepare some goals for AI,
And AI select suitable one of themFind a purpose!

goal

Action for its goal!

Environment

Goal-oriented agent in video games（１） Developer must prepare some goals for AI in development.
Decision() making（２） AI select one of them, and act for its goal.
Goal-oriented

I select one
goal,and achieve
it!

Goals
AttackplayerEnvironment

Protect
friendselect!

extract!
ProtectbaseWhat is planning ?
Initial State

Action1 Action2 Action3 Action4

Fundamental Concept：

Initial State

Goal

Goal

PlannerGoal oriented planning Agent
Goals × Planning
How?

What ?
＝

an agent who decides what he should do andhow he should do it.
Goals
Planning

AttackplayerProtect
friendProtectbase

環境Planning has two methods
１．chaining
Planner chains actions
automatically.

F.E.A.R(Monolith Soft)

２．HierarchicalA big goal calls some goals,
and its goal calls smaller goals…

ChromeHoundsContents
1.
2.
3.
4.
5.
6.

Agent architecture C4 Architecture (MIT Media Lab.)
Knowledge representation Killzone (Guerilla)
Event analysis Halo (Bungie Studio)
Heuristic FSM Halo2 (Bungie Studio)
Goal-oriented Action Planning F.E.A.R. (Monolith)
Multiagent system Chromehounds (FromSoftware)

Goal-Oriented PlanningF.E.A.R (2004)

Game：Horror FPS
Developer：Monolith Production
Publisher: SIERRA
Hardware: Windows, PS3
Publishing year： 2004

References for F.E.A.R.
 Orkin, J. (2006), 3 States & a Plan: The AI of F.E.A.R.,
Game Developer's Conference Proceedings.
 Jeff Orkin, Applying Goal-Oriented Action Planning toGames, AI Game Programming Wisdom 2, Charles
River Media., 217-228, (2003)
 Mat Buckland, “Programming Game AI by Example”,
Chapter 9, WORDWARE publishing Jeff Orkin’ HP http://web.media.mit.edu/~jorkin/
Figures on following pages are from these references.

F.E.A.R NPC AI architecture
NPC’s intelligence
Cognitive
Process

SensorGoal-oriented
Action Planning

SymbolCommon representationof all knowledge

Motiongeneration

Blackboard
MotionWorking Memory

Knowledge representation/
World representation
Body

Game world
Interaction

Time

Time

Chaining

Representation form of behavior
for planning by chainingP r e c o n d it io n

B e h a v io r

E f fe c t

Precondition = necessary condition for executing the behavior
Effect= effect caused by the behavior

Planning system for F.E.A.R.
Simple representation of agent’s world
20 symbols for representing agent’s world
SymbolkSymbol_AtNodekSymbol_
WeaponArmedkSymbol_TargetIs
AimingAtMe

kSymbol_AtNodeTypekSymbol_
WeaponLoaded

kSymbol_
RidingVehicle

Agent-centric representation

kSymbol_Target
IsSuppressed

kSymbol_
UsingObject

kSymbol_
TargetIsDead

Planning system for F.E.A.R.
Chaining based on symbol representation
Planning
NoCondition

Draw weapon
kSymbol_
WeaponArmedkSymbol_
WeaponArmed

Chaining

Load weapon
kSymbol_
WeaponLoaded

kSymbol_
WeaponLoaded

AttackPlannerkSymbol_
TargetIsDead

Chaining
GOAL
kSymbol_
TargetIsDead

Recent flow of game AI technologies
PS2,GC,XboxXbox360, PS3, Wii

2005

DC

①2000
Agent architecture
C4 architecture(MIT Media Lab.)③ 2002④ 2004

Event driven
Halo(Bungie Studio)(Bungie Studio)① Research② 2001（Next gen.））

Time

Heuristic FSM(FiniteState Machine)
Halo2② Study⑤ 2005

Goal oriented
F.E.A.R.
ActionPlanning(Monolith Production)③⑥Implement
Multiagent
2006 system
Hierarchical planning
Chromehounds(FromSoftware)World representation
Killzone(Guerrilla)

New game AI techniques are developed on the basis of previous works !

Contents
1.
2.
3.
4.
5.
6.

Agent architecture C4 Architecture (MIT Media Lab.)
Knowledge representation Killzone (Guerilla)
Event analysis Halo (Bungie Studio)
Heuristic FSM Halo2 (Bungie Studio)
Goal-oriented Action Planning F.E.A.R. (Monolith)
Multiagent system Chromehounds (FromSoftware)References for this chapter(1)AOGC2007(Asia Online Game Conference) (invited lecture),
Youichiro Miyake, "The future of online games with game AI technology"(Material) http://www.bba.or.jp/AOGC2007/pdf/miyake_PPT.pdf
http://www.bba.or.jp/AOGC2007/pdf/miyake.pdf(online article) http://www.rbbtoday.com/news/20070226/38939.html(2) CEDEC 2007(invited lecture),
Youichiro Miyake, "How to make game AI on Agent architeture"(CEDEC2007) http://cedec.cesa.or.jp/contents/r22.html(Material) http://www.geocities.jp/mnagaku2000/igda/cedec07r22t07pre.zip(3) CEDEC 2006,
Youichiro Miyake, "Perspective of game AI from the making of ChromeHounds"(CEDEC2006)(To R41) http://cedec.cesa.or.jp/2006/rs04.html(Material) http://www.geocities.co.jp/mnagaku2000/igda/cedec2006r41.html(Online article)http://www.famitsu.com/game/news/2006/09/01/103,1157106762,59438,0,0.htm(4) IGDA Japan chapter, Game AI seminars No.3,
Youichiro Miyake, "Multiagent system for game AI"(IGDAJ)
http://www.igda.jp/modules/eguide/event.php?eid=41(online article) http://www.rbbtoday.com/news/20070513/41655.html
http://codezine.jp/a/article/aid/1344.aspx

Chromehounds

Game： robot action online-game
Developer： FromSoftware
Publisher: SEGA
Hardware: Xbox360
Publishing year： 2006
In a large map、two player teams fight each other in 15min. in 3D online world,and player team can also fight with AI team.

Mission of Chromehounds AI TeamAI Team must fight against player team on the equal condition

AttackPlayer Team（Max 6）

ＡＩ Team（Max 6）

The abilities needed for NPC① Sense the situation around himself② Decide his action corresponding his
situation③ Move and attack(1) autonomous agent
Individual(2) Multiagent system
Team

For building an autonomous agent① goal-oriented hierarchical planning system
in agent architecture×② real-time path planning(makes NPC move between any two points on a map )= autonomous agent

① goal-oriented hierarchicalplanning system
in agent architecture

AI architecture of ChromeHounds NPC
Time

NPC’s intelligence
Selecting an goal
By Evaluation Function

Cognition＋
Hierarchical
Goal-Oriented Planning
Reactive mode

SensorBehavior-making
Process

Working memory

MotionWorld Representation
Body

Game World
interactionTimeHierarchical goal-oriented planning

A goal is a combination of small goals
Goal

Goal

Goal

Goal

Hierarchical goal-oriented planning

A small goal is a combination of smaller goals
Goal

Goal

Goal

Goal

Goal

Goal

Goal

Goal

Goal

In Chromehounds(Xbox360)
real-time Hierarchical Goal-Oriented Planning

HierarchicalFind the
tower
Go to
the tower

Conquer
The tower
Conquer
the tower

Find path tothe tower

shootMove along
the pathwalk

Wait 10seconds

stop

NPC

Strategy

Tactics

Behavior Command

Demo movie for real-time Hierarchical
Goal-Oriented Planning

Players or AI control
this type of machinefrom this view point.

Demo movie

Demo movie for real-time Hierarchical
Goal-Oriented Planning
NPC’s Goal-oriented planning

Strategic goal
tactics goal
behavior goal

Demo movie

Hierarchical goal structures for NPC in
Chromehounds
Strategic goals
AttackEnemy

Conquer Protect
The tower Friend

Protect
Base

AttackEnemies’ Base

RescuePatrolFriendScout

Tactics goals
Follow
Path

Close

Go to apoint

AttackgatherRun
about

EscapeBehavior goals
Move
Betweentwo point

Stop & Go

Stop

Command goals
Walk

Shot

Stop

Go
back

Go
Go to theforward side of enemy

Programming skills

Class Goal

Programming for goal-oriented（Design Pattern: Composite structure）
Instance

Class GoalClass Goal

Condition for clear

Condition for clear＋
Activate()
Process()
Terminate()＋
Activate()
Process()
Terminate()

Activate … initial setting
Process …

behavior in active

Terminate … process for finish this goal
（Function are written by script language）

Condition for clear＋
Activate()
Process()
Terminate()
Class Goal
Condition for clear＋
Activate()
Process()
Terminate()
Instance

Decision making for Hierarchical goal structures
Agent must select one adequate goal topresent situation.

Decision making system
Select by evaluating goals

Strategic goals
AttackEnemy

Conquer Protect
The tower Friend

Protect
Base

AttackEnemies’ Base

RescuePatrolFriendScout

Tactics goals
Follow
Path

Close

Go to apoint

AttackgatherRun
about

EscapeBehavior goals
Move
Betweentwo point

Stop & Go

Stop

Command goals
Walk

Shot

Stop

Go
back

Go
Go to theforward side of enemy

Evaluation value for strategic goals
that changes to a situation in game
Decision making = select one goal
Select best high-score goal

AttackEnemy

Conquer Protect
The tower Friend

Protect
Base

AttackEnemies’ Base

Strategic goals

RescuePatrolFriendScout

AI architecture of Chromehounds NPC
Time

NPC’s intelligence
Selecting an goal
By Evaluation Function

 Hierarchical＋Goal-oriented planning

Cognition

Hierarchical
Goal-Oriented Planning

反射モード
反射モード

Behavior-making
Process

ゲーム世界
SensorWorking memory

Motion① NPC decides one goal by himself
World②
NPCRepresentation
makes plans to accomplish the goal NPC he selected.
Body

Game World
interactionTime② Real-time path planning system(makes NPC move between any two points on a map )Data structure for path planning（１） Waypoint
many points should be put on a map（２） Navigation mesh
Mesh data can include information of surface of terrain

What is Navigation Mesh ?
NPC can move over 凸-polygons which a whole 2D map is covered with.
B

Steps（１） Divide a map into triangles which do not include obstructions(indeveloping a game).
（２） Find a path to a goal point from a start point (in game).
（３） Move along a path.

Navigation mesh for Chromehounds(1) 30000 – 80000 meshes(2) 80 maps
(3) All meshes are auto-generated from collision models of stages.
(4) Information of terrain’s surfaces (snow, sand, water, edge, nearedge) can be implemented in mesh data.

80 maps of terrains such as mountains、cities, and lakes can be
represented as a unique navigation mesh data format.

Navigation mesh information of surfaces are implemented（１） Sand and water reduces NPC’s speed.
These surface information are implemented in Navigation mesh data.
Finding not a shortest path but a minimum-time path
NPC can move while considering surface of terrain.
（２） When any object is destructed, navigation mesh data is updated.

NPC can move corresponding a change of its environment.

Debug_Path02.avi

Demo movie

Contents
1. Game AI overview
2. Game AI technologies in Chrome Hounds(1) Autonomous agent① goal-oriented hierarchical planning system in agent architecture② real-time path planning system(2) Multiagent system

3. Developing Character AI based on agent architecture

For building an autonomous agent① goal-oriented hierarchical planning system
in agent architecture×② real-time path planning
autonomous agent

For building a strong NPC team
Cooperation and teamwork are needed !

multiagent system

Multiagent system in Chrome HoundsFive techniques for cooperation of goal-oriented planning agents
To help each other①Protect ②Rescue
Cooperation by strategic goal
To judge the situation③④
Circumstantial Concentrated
attackjudgement

Cooperation by algorithm
Teamwork to win

There are 3 categories and 5 techniques.

⑤TeamAI
Cooperation by TeamAIMultiagent technology ① Protect
A strong agent follows a weak agent to protect him.

Strategic goal “Protect friend” is prepared A weak agent or one who cannot move fast
are protected by a strong agent.
 An agent who protect a friend attack
enemies around it.

NPC’s Goal-oriented planning① ProtectProtect Friend
Attack enemies aroundhis friend .

CH_protectII
guardian
Agent who can move only slowly…

Demo movie

① Protect

CH_protectII

Demo movie

Multiagent technology ② Rescue
One agent come to the agent who are attacked and fight with him.
Strategic goal “Rescue friend” is preparedPPPA agent who have little stamina could be
rescued But because player could attract agents byattacking an agent, an agent who have too little
stamina are not rescued.

P② Rescue

CH_ResaueFriend

Demo movie

Multiagent technology ③ circumstantial judgment
A group of agents judge whether their war potential is higher or lower
than enemies.If it is lower, they escape, and if not, they fight.
P P
P

Escape !

P

P P

all war potential ＞ １．４ ｘ all war potential

P P
P

Attack！
！

All war potential < １．４ ｘ all war potential

A whole map of Chromehounds

Don’t fight with much stronger enemies,Fight with equal or weaker enemies !

③ circumstantial judgment

By circumstantial judgment, they come back to the base,and join their friend.

Demo movie

Multiagent technology ④ concentrated attack
Concentrate fire to one of enemies
Concentrate fires to one enemies that has lowest war potential.

P
P
P

Concentrate fires to one enemies that has lowest war potential,
And destroy enemies step by step.

④ concentrated attack

Demo movie

Multiagent technology ⑤ TeamAITeamAI control agents by goal
Agents share a common goal！

TeamAI！
Base！

TeamAI cast goals to agents

What is TeamAI ?
TeamAI has team strategies, and decide one of themcorresponding to the situation in game by evaluating them.

TeamAI= decision making system for team

DestoryAllememiesProtect
My
Base

ConquerAll
TowersDestroy
Enemies’baseWhat is TeamAI ?
TeamAI has team strategies, and decide one of themcorresponding to the situation in game by evaluating them.
TeamAI= decision making system for team

DestoryAllememiesProtect
My
Base

ConquerAll
TowersDestroy
Enemies’base

AttackEnemies’ Base

AttackEnemies’ Base

AttackEnemies’ BaseOne team strategy is
consist from some strategic
goals to agents.

What is TeamAI ?
TeamAI has team strategies, and decide one of themcorresponding to the situation in game by evaluating them.
TeamAI= decision making system for team

DestoryAllememiesProtect
My
Base

ConquerAll
TowersAttackEnemies’ Base

AttackEnemies’ Base

Destroy
Enemies’base

AttackEnemies’ Base
AttackEnemies’ Base

Agent 1

AttackEnemies’ Base

Agent 2
Planning

AttackEnemies’ Base

Agent 3

One team strategy is
consist from some strategic
goals to agents.

What is TeamAI ?
TeamAI has team strategies, and decide one of themcorresponding to the situation in game by evaluating them.
TeamAI= decision making system for team

DestoryAllememiesProtect
My
Base

ConquerAll
TowersDestroy
Enemies’base

AttackEnemies’ Base

AttackEnemies’ Base

AttackEnemies’ Base
AttackEnemies’ Base

Agent 1

AttackEnemies’ Base

Agent 2
Planning

AttackEnemies’ Base

Agent 3

Team strategy is acombination of goals.
One team strategy is
consist from some strategic
goals to agents.

What is TeamAI ?
TeamAI has team strategies, and decide one of themcorresponding to the situation in game by evaluating them.
TeamAI= decision making system for teamProtect
Base
Protect
Base

DestoryAllememiesProtect
My
Base

ConquerAll
TowersDestroy
Enemies’baseProtect
Base
AttackEnemies’ Base

Protect
Base

Agent 1

Protect
Base

Protect
Base

Agent 2Agent 3

Planning

AttackEnemies’ Base

Agent 4

Team strategy is acombination of goals.

One team strategy is
consist from some strategic
goals to agents.

When a goal is given from team AI,
how does NPC decide his goal ?
TeamAI= decision making system for team

DestoryAllememiesProtect
My
Base

ConquerAll
TowersDestroy
Enemies’
baseTeam’s rationality

AttackEnemies’ BaseCOM 2

Conquer
TowersNow executing…

Individual’s rationality

When a goal is given from team AI,
how does NPC decide his goal ?
NPC select a goal which get higher score between two goals.
TeamAI= decision making system for team

DestoryAllememiesProtect
My
Base

ConquerAll
TowersDestroy
Enemies’base

AttackEnemies’ Base

COM 2

Evaluation value : 64

×Conquer
TowersNow executing…

Evaluation value : 53

When a goal is given from team AI,
how does NPC decide his goal ?
NPC select a goal which marks higher score between two goals.
TeamAI= decision making system for team

DestoryAllememiesProtect
My
Base

ConquerAll
TowersDestroy
Enemies’base×AttackEnemies’ Base

COM 2

Evaluation value : 76
Conquer
TowersNow executing…

Evaluation value : 88

How
team
AI
interfere
individualAI
In the first part, individual NPC’s decision should be dominant、In the last part, team AI’s decision should be dominant.
Final evaluation value of team AI’s goal = Goal evaluation value ｘ comp_team
Final evaluation value of NPC’S goal = Goal evaluation value ｘ comp_idv
COM dominant

1.2
1.0

COM、
、Team
Competitive

Team dominant

comp_idv

Control game’s flow by team AI !
0.0

comp_team

the first partthe middle part（0~5 min.,or before a robot
is destroyed））（the first part + 5min.））the last part（the middle part +5min.））Evaluation values of Team Strategies(Sorry, this is Japanese)⑤ TeamAI⑤ TeamAI
NPC’s Goal-oriented planningThis agent is executing the goal “Protect” he has chosen.

Demo movie

⑤ TeamAI⑤ TeamAIA goal from a team strategy has interrupted agent’s goal.

Demo movie

Chapter 3.
SummarySummary for this lecture(1) In these time, developer can search many papers on
internet.
In these 5 years !
(2) From those documents, developers can study muchknowledge and many techniques.
But most techniques are explained for the game the author developed !

(3) To apply game AI techniques to your game, you shoudand you can arrange and apply them for your gamedesign.

For opening the next generation game…
PS2,GC,XboxXbox360, PS3, Wii（Next gen.）
）

DC

Time

2005

2000
C4
architecture
Agentarchitecture(MIT Media Lab.)

2002
Event analysis
Halo(Bungie Studio)

2004
Heuristic FSM
Halo2(Bungie Studio)

2005
2001
World representation
Killzone

Goal oriented
Action Planning
F.E.A.R.
(Monolith Production)

2006
Hierarchical planning
Chromehounds(FromSoftware)

New
KoreanGame(Guerrilla)

I hope new Korean games open the future of digital gamefor the future of digital games in the world !

Thank you very much for your attention !

Photo from http://www.cyberleaf.com/

Any question and idea
Today: In the front of ROOM 304(Speaker’s room) 17:30-17:45 : or(as a member of IGDA Japan: yoichi-m@pk9.so-net.ne.jp )y.m.4160@gmail.com
http://www.igda.jp