Transcript Document

Artificial Intelligence
in
Game Development
Yingcai Xiao
Artificial Intelligence in Game Development
Non-player character (NPC) / non-person
character / non-playable character: any
game character that is not controlled by a
player, usually controlled by AI.
AI in games controls NPCs to simulate
intelligence behavior.
Examples
First AI games created in 1951.
NIM and Checker
Pac-Man (1980) added personalities to enemies.
https://www.youtube.com/watch?v=x4tqMv0CvTQ
Garry Kasparov defeated by IBM's Deep Blue computer in
1997
https://www.youtube.com/watch?v=_Y9hriLylIo
IBM Watson
Interaction
Interaction with Natural Language
Jeopardy
https://www.youtube.com/watch?v=WFR3lOm_xhE
API
http://www.ibm.com/smarterplanet/us/en/ibmwatson/?lnk=buwa
Cloud
http://www.ibm.com/smarterplanet/us/en/ibmwatson/watsoncloud.html
Examples
• Halo: Intelligent aliens will retreat after their
leader killed. (Jobs)
• Sims: smart objects that can go hungry, bored,
tired, ...
• TechnoSphere: an online digital environment
where users from around the globe could
create creatures and release them into.
• Black & White: belief-desire-intention, god
overseeing little people.
AI Algorithms
• LOS (line of sight): avoid of being shot.
• Graph Theory and Routing: maze games.
• BF/DF Searching Algorithms: board games.
• FSM (Finite State Machine): state of mined
games.
AI Algorithms
• Genetic Algorithms: evolutionary computing
based on adaptation and survival.
http://www.biomanbio.com/GamesandLabs/Genegames/genetics.html
http://www.biomanbio.com/GamesandLabs/Cellgames/CellExplorerAnimalCell.html
(Arrow keys to move, “s” to shoot an object for explanation.)
AI Algorithms
• Decision Trees: hierarchical graph to make
decisions based on conditions.
• Fuzzy Logic: make decisions based on vague
information.
AI Algorithms
• Cellular Automata: a grid of cells with each
cell value being updated constantly by its
neighbor’s values.
• Game of Life
• Stephen Wolfram
• Wolfram Alpha
AlphaGo
• AlphaGo: a game engine that plays the Go
game.
• Go: a Chinese board game of strategies.
19x19, 361!, 10761 (total number of
fundamental particles in the observable
universe:1085).
• The first computer program to beat a
professional Go player (4:1, March 8-15,
2016).
AlphaGo Algorithms
• Based on tree searches and neural networks
that can learn.
• Policy Network: only consider a few
promising positions (limit the breadth of the
search tree.)
• Value Network: only consider a few steps
deep (limit the depth of the search tree).
Flocking
Flocking
• Flocking: crowd behaviors.
• Starling murmuration:
https://www.youtube.com/watch?v=eakKfY5aHmY
• Reynolds, Craig W. (1987). "Flocks, herds and
schools: A distributed behavioral model.". ACM
SIGGRAPH Computer Graphics 21 (4). pp. 25–34.
• Batman Returns (1992): flocking bats and The Lion King
(1994): wildebeest stampede.
Flocking
• Craig Reynolds: http://www.red3d.com/cwr/
• Reynolds, Craig W. (1987). "Flocks, herds and schools:
A distributed behavioral model.". ACM SIGGRAPH
Computer Graphics 21 (4). pp. 25–34.
• Authored the OpenSteer library
• Won 1998 Academy Scientific and Technical Award
for pioneering contributions to 3D computer
animation for movies.
• Uses procedural models to simulate complex
natural phenomenon.
The Flocking Algorithm
• The algorithm
• Implementation in Unity3D
• Building a Unity package for reuse
• Building a flocking library in a game engine
The Flocking Algorithm
•
Craig Reynolds’ Boids:
artificial objects follow natural flocking behavior
•
Unity Implementation:
http://black-square.github.io/BirdFlock/
•
JavaScript implementation: http://gpolo.github.io/birdflocking/
•
OpenGL implementation: http://www.navgen.com/3d_boids/
The Flocking Algorithm
• Tutorial:
http://www.vergenet.net/~conrad/boids/pseudocode.html
• Unity Code Explanation:
http://wiki.unity3d.com/index.php?title=Flocking
The Flocking Algorithm
• Craig Reynolds’ Boids: artificial objects
flow natural flocking behavior.
• 3 Basic Rules:
cohesion - to move toward the center of
the mass of the flockmates
separation - to avoid flockmates
alignment – to steer towards the flock direction
Implementing Flocking
The Flocking Algorithm
• Craig Reynolds’ Boids: artificial objects flow natural
flocking behavior.
• 3 Basic Rules:
cohesion - to move toward the center of the mass of
the flockmates
separation - to avoid flockmates
alignment – to steer towards the flock direction
http://www.vergenet.net/~conrad/boids/pseudocode.html
EDP Game Development
Event Loop
Event
Mapping
&
Event
Dispatching
init_game();
while(!done) {
e = get_event()
Event
switch(e) {
case “p”:
change_game_parameters( );
break;
…
Event
Handler
default:
display_game_objects();
compute_next_frame();
}
}
EDP Game Development
Event Loop
Event
Mapping
&
Event
Dispatching
init_game();
while(!done) {
e = get_event()
Event
switch(e) {
case “p”:
change_game_parameters( );
break;
…
Event
Handler
default:
compute_next_frame();
display_game_objects();
}
}
EDP Game Development
Event Loop
Event
Mapping
&
Event
Dispatching
init_game();
create_boids();
while(!done) {
e = get_event()
Event
switch(e) {
case “p”:
change_game_parameters( );
break;
…
Event
Handler
default:
compute_CoM_AV();
compute_boid_velocity();
display_boids();
}
Flocking Code
C# code at http://wiki.unity3d.com/index.php?title=Flocking
(1) Create the flock at the BiodController::Start()
//all boids
(1) Update animation parameters in BiodController::Update ()
//all boids
(2) Control the animation in BoidFlocking::BoidSteering ()
//each boid
Flocking Code
(1) Create the flock at the Start()
• Flock Size
• Boids Array
• Position
• Direction
Flocking Code
(1) Create the flock at the Start()
• Bounding box
• Global and local transformation
• The Controller
Flocking Code
(2) Update animation parameters in Update ()
• Center of Mass
• Average Direction
• The Controller
Flocking Code
(3) Control the animation in BoidFlocking::BoidSteering ()
• This is the script for each boid.
• Separation is taking care of by rigidbody.
• Cohesion is to follow the CoM.
• Alignment is to follow the Average Direction
PA4 Coding / Flocking
http://www.cs.uakron.edu/~xiao/game/igd4.htm
The Theory / Rules:
cohesion - to move toward the center of the mass
of the flockmates
separation - to avoid flockmates
alignment – to steer towards the flock direction
PA4 Coding / Flocking
The Example:
Holistic Game Development with Unity By: Penny de Byl
http://proquest.safaribooksonline.com/book/programming/ga
me-programming/9780240819334
Section 5.6: a flock of seagulls flying against wind in small
groups.
http://proquest.safaribooksonline.com/book/programming/ga
me-programming/9780240819334/chapter-5-charactermechanics/ch5_6_006_9780240819341_web_ch05_html
Sorting and Searching
in
Game Development
Sorting & Searching
• S&S needed to develop AI games to find optimal
strategies, paths, in the game logic.
• The main challenge is the huge size of the search
tree. The number of branches in the search tree of a
19x19 Go board game is larger than the number of
atoms in the known universe.
• The key of success is to reduce the search space but
not the optimal solutions.
Sorting
• Sorting the search space can make searches faster.
• Sorting can be used to prioritize the search space.
• Weights can be added to reflect heuristic information.
Basic Sorting Algorithms
• Sorting Algorithm Animations
http://www.sorting-algorithms.com/
https://www.cs.usfca.edu/~galles/visualization/Comparis
onSort.html
• Wiki listing
https://en.wikipedia.org/wiki/Sorting_algorithm
Searching
• Basic searching
• Statistical searching
• Searching for globally optimal solutions
Basic Searching Algorithms
Code Listing
https://users.dcc.uchile.cl/~rbaeza/handbook/search_a.html
https://www.cs.auckland.ac.nz/~jmor159/PLDS210/niemann/s_man.htm
Comparisons
http://bigocheatsheet.com/
http://research.cs.queensu.ca/home/cisc121/2006s/webnotes/search.html
Example: weighted objects.
Statistical Searching Algorithms
https://en.wikipedia.org/wiki/Monte_Carlo_tree_search
AlphaGo Algorithms
• Based on tree searches and neural networks
that can learn.
• Policy Network: only consider a few
promising positions (limit the breadth of the
search tree.)
• Value Network: only consider a few steps
deep (limit the depth of the search tree).
Resources
http://AIGameDev.com
http://www.GameAI.com