ARTIFICIAL INTELLIGENCE IN COMPUTER GAMES
(GATE-561)
Game Technologies Program, Department of Modeling and
Simulation
Informatics Institute
Middle East Technical University
Fall 2009
Dr.Çağatay
ÜNDEĞER
Instructor
Middle East Technical University, GameTechnologies
Bilkent University, Computer Engineering
&
General Manager
SimBT Inc.
Room : II-206
e-mail : cagatay@undeger.com
web-site : www.cs.bilkent.edu.tr/~cagatay
1.
Objective & Scope
The course presents
the theoretical basics of artificial intelligence (AI) and their practical
application to behavior modeling in game development.
After a brief introduction
to game aspects, AI and role of AI in games, the first part of the lecture will
introduce frequently used AI architectures, which can be used for designing AI
engines in games; and the second part will cover basic decision taking, search
and planning techniques towards detailed reasoning of a game entity. Next part
will deal with group behavior which makes an individual entity take decisions
considering a group of entity in coordination and cooperation. Finally, the
last part will cover high and low level script programming issues, which is
very commonly used in games.
In the course,
students will be given term papers to be read, which will be summarized and
presented in the class. Additionally, there will be survey, design and/or
implementation assignments to be presented/demonstrated in the class. Finally,
the students will develop and present individual projects related with entity
behavior modeling in games.
1.
Course Outline
•
Introduction to Course
• Introduction to Common Game Components
– Environment
– Scenario
– Perception
– Behaviour
– Physics
– Body Movement and Animation
– Visual Effects
– Sound Effects
•
Introduction To Artificial Intelligence (AI)
–
Description of AI
– History of AI
– Behavior and Agent Types
– Properties of Environments
– Problem Solving Strategies
–
Common Search Strategies
•
Common AI Architectures
– Entities, Attributes and Relations
–
Tasks, Actions, States and Events
–
Finite-State Machines
–
Hierarchical Finite-State-Machines
–
A Sample AI Architecture
•
Reactive Behavior Modeling
–
Introduction to Reactive Behaviors
–
Fuzzy Logic
–
Neural Networks
–
Decision Trees
–
Instance-Based Learning
•
Deliberative Behavior Modeling
–
Introduction to Deliberative
Behaviors
–
Game Trees
–
Production Systems
–
Path Planning
1. Environment Modeling
1. Grid-Based Models
2. Polygonal Models
2. Off-line Path Planning
1. Uninformed Search
1. Breadth First Search
2. Depth First Search
3. Iterative Deepening
Search
4. Bidirectional Search
5. Dijkstra’s Algorithm
2. Informed (Heuristic)
Search
1. A*
2. A* Derivations
3. Incremental Search
1. D*
2. D*Lite
4. Random Search
1. Hill-Climbing
2. Simulated Annealing
3. Random Trees
4. Probabilistic Roadmaps
5. Genetic Algorithms
5. Hierarchical Planning
Techniques
6. Path Smoothing
Techniques
3. On-line (Real-time)
Path Planning
1. RTA*
2. MTS
3. MTES
•
Group Behaviors
–
Formations
–
Flocking
–
Multi-Agent Pursuit
•
Script Programming
–
Low Level Scripts
–
High Level Scripts
•
Knowledge Representation
–
Semantic Networks
–
Frames
•
Time Management
–
Discrete Time Management
–
Continuous Time Management
–
Discrete Event Simulations
•
Paper/Assignment Presentations
•
Project Presentations
2.
Course Requirements
The students are expected to develop a
small-scale AI project individually or with a group of two. The project topics
will be selected from a list of topics provided by the instructor (additional
topics can be proposed). Implementation will be done in C++ preferably with
Visual Studio (V6.0 or .NET) or Borland C++ Builder (V6.0 or 2009).
3.
Assessment Method
A project
will be developed including:
Project
Documents (Final Report, Source Code, Executables) 30%
Project
Presentation and Demonstration 20%
Assignments:
Implementation Assignments 25%
Paper Reading/Presentation Assignments 25%
4.
List of Project Topics
a.
War Craft like strategy game with attack and defense behavior of two
opposing forces.
i.
Number of students: preferably 2
ii.
Environment: A war craft like grid world environment with obstacles.
iii.
User control: Locate defense forces and define their initial defense
mission by orders. Locate attack forces and define their initial attack mission
by orders.
iv.
Automated entities: Both defense and attack forces
v.
Behavior: Defense forces defend a region (a small town etc.) and try to
prevent attack forces to enter their region autonomously. Attack forces try to
kill defense forces and get protected area autonomously. User should not need
to order the entities all the time. Entities should have enough intelligence to
decide and navigate appropriately. For instance if attack is from north, most
of them should go to north, and little should stay south (but not all).
vi.
Visualisation: Looking environment from the top view.
b.
Hide and escape behavior of a group of tanks against a helicopter
attack.
i.
Number of students: 1-2
ii.
Environment: A grid world environment with obstacles and mountains
preventing line of sight.
iii.
User Controlled Entities: A simple helicopter with a formulized sensor
range (depending on the target velocity) and limited with field of view.
iv.
Automated entities: One or more tanks having a predefined scenario
(navigation corridor/path). Tanks have larger fixed sensor ranges and they know
that helicopters have lower range, but does not know exact the range value.
They just have an estimate.
v.
Behavior: A group of tanks moving through the navigation corridor/paths
that are predefined in the scenario, but they can deviate from their path if
they see a helicopter. Possible deviations are as follows:
1. If no helicopter is
seen, go through the path.
2. If a helicopter is
seen that is far and/or not going directly towards you, estimate that it
hasn’t seen you and perform a hide behavior which may be:
1. Slow down or stop in
order to prevent detection
2. Hide and stop behind a
mountain area
3. Determine a new path
to target location near to original path far from the helicopter area and
continue movement
3. If helicopter is near
and going directly towards you
1. Split the group and
escape randomly far from the helicopter until you feel safe.
4. If helicopter is
invisible again, resume mission and go to target point.
vi.
Visualisation: Looking terrain from the top view and just see the tanks
detected by the sensors.
c.
Follow and help behavior:
i.
Number of students: preferably 2
ii.
Environment: polygonal (triangulated) navigation areas with holes/gaps.
iii.
User Controlled Entities: A 3d main character controlled by the user which
can move freely in neighboring areas and jump between the areas having gaps in
between.
iv.
Automated entities: A 3d helper character. If 2 students are in the
project, there will be some attack forces/aliens.
v.
Behavior: A 3d helper character following the main character in the
environment. If 2 students are in the project, helper character will be
defending the main character against the attacks with guns (sword and/or
pistol, etc.). Some entities will be attacking entities against main and helper
characters.
vi.
Visualisation: 3d environment
d.
Dog fight:
i.
Number of students: 1
ii.
Environment: : A grid world environment with mountains.
iii.
User Controlled Entities: One of the aircrafts may be controlled by the
user.
iv.
Automated entities: A group of opposing aircrafts
v.
Behavior: Two groups of aircrafts are given a mission path that are
intersecting each other. When they come close two each other they will attack
each other until one group is terminated and later on the winning group will
continue on its predefined path. One of the aircrafts may be controlled by the
user.
vi.
Visualisation: may be a 3D view
e.
Traffic simulation:
i.
Number of students: 1-2
ii.
Environment: a connected graph with intersections and roads having one
or two way directions/lanes and one or multiple lanes within one direction. The
number of lanes may be changing on a single road in different regions.
iii.
User Controlled Entities: None or one car may be controlled by the user
iv.
Automated entities: Traffic/cars in the environment.
v.
Behavior: Traffic will be fully automated with cars located around
randomly.
vi.
Visualisation: Top view
f.
Two body (soldier) defense supported forward movement:
i.
Number of students: 1-2
ii.
Environment: A grid world
environment with obstacles
iii.
User Controlled Entities: None
iv.
Automated entities: One of more two soldier groups attacking a defended
area with opposing forces.
v.
Behavior: Defense forces will be still and firing the arrack forces. If
they are under fire, they fire less frequently and less correctly, but if they are
not under fire, they fire more frequently and more correctly. Attack forces are
in two body groups (in each group there are two soldiers). They are moving
forward on their path (a corridor with a predefined with). But movement of each
soldier is one by one. One will be hiding behind and obstacle and protecting
the other; and the other will be moving forward (may be firing meanwhile).
After the moving one hides behind an obstacle, the roles of soldiers are
exchanged.
vi.
Visualisation: Top view
g.
Firing with bombs and missiles against a moving target:
i.
Number of students: 1
ii.
Environment: An environment with some obstacles
iii.
User Controlled Entities: Escaping entity is controlled by the user.
iv.
Automated entities: Attacking entity
v.
Behavior: Attacking entity will follow and try to kill the other moving
entity. Attacking entity should estimate the firing direction against an
unknown estimated escape movement.
vi.
Visualisation: May possibly be top view
h.
A backgammon like game (or something similar):
i.
Number of students: 1
ii.
User Controlled Entities: One side
iii.
Automated entities: The other side
iv.
Behavior: The other side will play autonomously, but backgammon rules
will be significantly differentiated (no ready source code should be used so
the game should be something unknown).
i.
Intelligent sensing while moving:
i.
Number of students: 1
ii.
Environment: A grid or polygonal based city like environment with
obstacles preventing line of sight
iii.
User Controlled Entities: None or moving entity may be controlled by the
user
iv.
Automated entities: A moving entity and some entities in the city firing
the moving one with some random delays (they will be fixed or moving with a
predefined scenario)
v.
Behavior: Moving entity will move on a predefined fixed navigation path
and if see someone, it will shoot. Meanwhile moving it should maximize its
perception in order not to be killed. Therefore it should:
1. Kill anyone around
2. Look around to
maximize vision
3. Look at sides while
passing an obstacle corner to maximize vision
4. Look behind in order
to detect someone pop up behind
5. Look at the direction
that a sound (firing) is coming
6. Look at more dangerous
ones with higher priority (but don’t forget the others)
7. Track moving entities
to keep seeing it
vi.
Visualisation: Top view
j.
Bird behavior:
i.
Number of students: 1
ii.
Environment: A grid or polygonal base environment with mountains and
trees
iii.
User Controlled Entities: A man
iv.
Automated entities: Birds
v.
Behavior: Birds are flying around randomly or within a flock. Sometimes
they stay on top of a tree. If man is closer to them, they escape, avoid and go
somewhere or fly to another tree.
vi.
Visualisation: Any
k.
A generic AI engine:
i.
Number of students: 1-2
5.
References
[1] “Artificial Intelligence and Soft
Computing: Behavioral and Cognitive Modeling of the Human Brain”, Amit Konar, CRC Press, 2000
[2] “Game Programming Gems”, Mark DeLoura,
[3] “Artificial Intelligence: A Modern
Approach”, Stuart Russel and Peter Norvig,
Prentice Hall, 1995
[4] “Machine Learning”, Tom M.
Mitchell, 1997
6.
Course Materials
2) Introduction to Game Components
5) Reactive Behavior Modeling: FuzzyLogic
6) Reactive Behavior Modeling: Neural Networks
7) Reactive Behavior Modeling: Decision Trees
8) Deliberative Behavior Modeling: Introduction to Path Planning
9) Deliberative Behavior Modeling: Off-line Path Planning
10) Deliberative Behavior Modeling: On-line Path Planning