Transcript Course Introduction

Artificial Intelligence
in Games
(GATE-561)
Dr.Çağatay ÜNDEĞER
Instructor
Middle East Technical University, GameTechnologies
Bilkent University, Computer Engineering
&
General Manager
SimBT Inc.
e-mail : [email protected]
GATE-561
Game Technologies Program – Middle East Technical University – Fall 2009
1
Outline
•
•
•
•
•
GATE-561
Objective and Scope of the Course
Course Outline
Course Requirements
Assessment Method
References
2
Course Objective
• Theoretical basics of artificial intelligence (AI)
• Practical application to behavior modeling in
game development.
GATE-561
3
Course Scope
• Part 1:
– Introduction to game components, AI and role of AI in games
• Part 2:
– Frequently used AI architectures, which can be used for
designing AI engines in games;
• Part 3:
– Basic decision taking, search and path planning techniques
towards detailed reasoning of a game entity.
• Part 4:
– Group behavior which makes an individual entity take
decision considering a group of entity in coordination and
cooperation.
• Part 5:
– High and low level script programming issues, which is very
commonly used in games.
GATE-561
4
Course Outline
• Introduction to Common Game Components
– Environment
– Scenario
– Perception
– Behaviour
– Physics
– Body Movement and Animation
– Visual Effects
– Sound Effects
GATE-561
5
Course Outline
• Introduction To Artificial Intelligence (AI)
– Description of AI
– History of AI
– AI Techniques
GATE-561
6
Course Outline
• AI Architectures
– Sense-Reason-Act Loop
– Knowledge Representation
• Finite-State Machines
• Hierarchical Finite-State-Machines
• Production Systems
• Semantic Networks
– Time Management
GATE-561
7
Course Outline
• Decision Taking
– Neural Networks
– Decision Trees
– Game Trees
– Fuzzy Logic
– Prolog
GATE-561
8
Course Outline
•
GATE-561
Search and Path Planning
– Environment Modeling
– Off-line Search Techniques
• Basic Search Techniques
– Depth First Search
– Breadth First Search
– A* and Its Derivations
• Common Search Techniques
– Hill-Climbing
– Simulated Annealing
– Random Trees
– Probabilistic Roadmaps
– Genetic Algorithms
• Hierarchical Planning Techniques
• Path Smoothing Techniques
– On-line Search Techniques
• RTA*
• MTS
• MTES
– Incremental Search Techniques
• D*
• D*Lite
9
Course Outline
• Group Behaviors
– Formations
– Flocking
– Multi-Agent Pursuit
GATE-561
10
Course Outline
• Script Programming
– Low Level Scripts
– High Level Scripts
GATE-561
11
Course Outline
• Paper/Assignment Presentations
• Project Presentations
GATE-561
12
Course Requirements
• Develop a small-scale AI project individually.
• 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).
GATE-561
13
Assessment Method
• A project will be developed including:
– Project Documents (Final Report, Source Code, Executables)
– Project Presentation and Demonstration
• Assignments:
– Implementation Assignments
– Paper Reading/Presentation Assignments
GATE-561
30%
20%
25%
25%
14
Project Topics
•
War Craft like strategy game with attack and defense behavior of two
opposing forces.
–
Number of students: preferably 2
–
Environment: A war craft like grid world environment with
obstacles.
–
User control: Locate defense forces and define their initial
defense mission by orders. Locate attack forces and define their
initial attack mission by orders.
–
Automated entities: Both defense and attack forces
–
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).
–
Visualisation: Looking environment from the top view.
GATE-561
15
Project Topics
•
Hide and escape behavior of a group of tanks against a helicopter attack.
–
Number of students: 1-2
–
Environment: A grid world environment with obstacles and mountains preventing line of sight.
–
User Controlled Entities: A simple helicopter with a formulized sensor range (depending on the
target velocity) and limited with field of view.
–
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.
–
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:
•
If no helicopter is seen, go through the path.
•
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:
•
Slow down or stop in order to prevent detection
•
Hide and stop behind a mountain area
•
Determine a new path to target location near to original path far from the helicopter area
and continue movement
•
If helicopter is near and going directly towards you
•
Split the group and escape randomly far from the helicopter until you feel safe.
•
If helicopter is invisible again, resume mission and go to target point.
–
Visualisation: Looking terrain from the top view and just see the tanks detected by the sensors.
GATE-561
16
Project Topics
•
Follow and help behavior:
–
Number of students: preferably 2
–
Environment: polygonal (triangulated) navigation areas with
holes/gaps.
–
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.
–
Automated entities: A 3d helper character. If 2 students are in the
project, there will be some attack forces/aliens.
–
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.
–
Visualisation: 3d environment
GATE-561
17
Project Topics
•
Dog fight:
– Number of students: 1
– Environment: : A grid world environment with
mountains.
– User Controlled Entities: One of the aircrafts may be
controlled by the user.
– Automated entities: A group of opposing aircrafts
– 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.
– Visualisation: may be a 3D view
GATE-561
18
Project Topics
•
Traffic simulation:
– Number of students: 1-2
– 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.
– User Controlled Entities: None or one car may be
controlled by the user
– Automated entities: Traffic/cars in the environment.
– Behavior: Traffic will be fully automated with cars
located around randomly.
– Visualisation: Top view
GATE-561
19
Project Topics
•
Two body (soldier) defense supported forward movement:
–
Number of students: 1-2
–
Environment: A grid world environment with obstacles
–
User Controlled Entities: None
–
Automated entities: One of more two soldier groups attacking a
defended area with opposing forces.
–
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.
–
Visualisation: Top view
GATE-561
20
Project Topics
•
Firing with bombs and missiles against a moving
target:
– Number of students: 1
– Environment: An environment with some
obstacles
– User Controlled Entities: Escaping entity is
controlled by the user.
– Automated entities: Attacking entity
– 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.
– Visualisation: May possibly be top view
GATE-561
21
Project Topics
•
A backgammon like game (or something similar):
– Number of students: 1
– User Controlled Entities: One side
– Automated entities: The other side
– 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).
GATE-561
22
Project Topics
•
Intelligent sensing while moving:
–
Number of students: 1
–
Environment: A grid or polygonal based city like environment with
obstacles preventing line of sight
–
User Controlled Entities: None or moving entity may be controlled by the
user
–
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)
–
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:
•
Kill anyone around
•
Look around to maximize vision
•
Look at sides while passing an obstacle corner to maximize vision
•
Look behind in order to detect someone pop up behind
•
Look at the direction that a sound (firing) is coming
•
Look at more dangerous ones with higher priority (but don’t forget
the others)
•
Track moving entities to keep seeing it
–
Visualisation: Top view
GATE-561
23
Project Topics
–
GATE-561
Bird behavior:
• Number of students: 1
• Environment: A grid or polygonal base
environment with mountains and trees
• User Controlled Entities: A man
• Automated entities: Birds
• Behavior: Birds are flying around randomly
or within a flock. Sometimes they stay on
top of a tree. If the man is closer to them,
they escape, avoid and go somewhere or
fly to another tree.
• Visualisation: Any
24
Project Topics
•
A generic AI engine:
– Number of students: 1-2
GATE-561
25
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,
Charles River Media, 2000
• [3] “Artificial Intelligence: A Modern Approach”,
Stuart Russel and Peter Norvig, Prentice Hall, 1995
• [4] “Machine Learning”, Tom M. Mitchell, 1997
GATE-561
26