Transcript CSCE 590E Spring 2007 - Computer Science & Engineering

CSCE 590E Spring 2007
AI/Audio
By Jijun Tang
Announcements

April 30th: demos



Final Demo: May 8th, 5:30pm, Amoco Hall



Show progress/difficulties
Risk analysis
No extension is possible
Make sure you equipment works on site
High school outreach


Anyone can contact their high school admin to
arrange direct talks to students
Of course, in SC only
Homework



Page 591 question 1
5 points, due on Monday
Hardcopy should be turned in before
the class
Artificial Intelligence



Intelligence embodied in a man-made
device
Human level AI still unobtainable
The difficulty is comprehension
Goals of an
AI Game Programmer
Different than academic or defense industry
1. AI must be intelligent, yet purposely flawed
2. AI must have no unintended weaknesses
3. AI must perform within the constraints
4. AI must be configurable by game designers
or players
5. AI must not keep the game from shipping
Game Agents

May act as an




Opponent
Ally
Neutral character
Continually loops through the
Sense-Think-Act cycle

Optional learning or remembering step
Sense-Think-Act Cycle:
Sensing

Agent can have access to perfect
information of the game world


Game World Information




May be expensive/difficult to tease out
useful info
Complete terrain layout
Location and state of every game object
Location and state of player
But isn’t this cheating???
Sense-Think-Act Cycle:
Thinking



Sensed information gathered
Must process sensed information
Two primary methods


Process using pre-coded expert
knowledge
Use search to find an optimal solution
Sense-Think-Act Cycle:
Acting



Sensing and thinking steps invisible to
player
Acting is how player witnesses intelligence
Numerous agent actions, for example:






Change locations
Pick up object
Play animation
Play sound effect
Converse with player
Fire weapon
Extra Step in Cycle:
Learning and Remembering


Optional 4th step
Not necessary in many games


Agents don’t live long enough
Game design might not desire it
Making Agents Stupid

Sometimes very easy to trounce player


Make agents faster, stronger, more accurate
Sometimes necessary to dumb down
agents, for example:




Make shooting less accurate
Make longer reaction times
Engage player only one at a time
Change locations to make self more vulnerable
Agent Cheating

Players don’t like agent cheating


Sometimes necessary




When agent given unfair advantage in speed,
strength, or knowledge
For highest difficultly levels
For CPU computation reasons
For development time reasons
Don’t let the player catch you cheating!

Consider letting the player know upfront
Common Game AI Techniques








A* Pathfinding
Command Hierarchy
Dead Reckoning
Emergent Behavior
Flocking
Formations
Influence Mapping
…
A* Pathfinding



Directed search algorithm used for finding
an optimal path through the game world
Used knowledge about the destination to
direct the search
A* is regarded as the best



Guaranteed to find a path if one exists
Will find the optimal path
Very efficient and fast
Command Hierarchy

Strategy for dealing with decisions at
different levels


From the general down to the foot soldier
Modeled after military hierarchies


General directs high-level strategy
Foot soldier concentrates on combat
Dead Reckoning




Method for predicting object’s future position
based on current position, velocity and
acceleration
Works well since movement is generally
close to a straight line over short time
periods
Can also give guidance to how far object
could have moved
Example: shooting game to estimate the
leading distance
Emergent Behavior


Behavior that wasn’t explicitly
programmed
Emerges from the interaction of
simpler behaviors or rules


Rules: seek food, avoid walls
Can result in unanticipated individual or
group behavior
Flocking

Example of emergent behavior


Developed by Craig Reynolds


Simulates flocking birds, schooling fish
1987 SIGGRAPH paper
Three classic rules
1. Separation – avoid local flockmates
2. Alignment – steer toward average
heading
3. Cohesion – steer toward average position
Formations

Group movement technique



Mimics military formations
Similar to flocking, but actually distinct
Each unit guided toward formation
position

Flocking doesn’t dictate goal positions
Influence Mapping



Method for viewing/abstracting distribution
of power within game world
Typically 2D grid superimposed on land
Unit influence is summed into each grid cell


Unit influences neighboring cells with falloff
Facilitates decisions




Can identify the “front” of the battle
Can identify unguarded areas
Plan attacks
Sim-city: influence of police around the city
Level-of-Detail AI



Optimization technique like graphical LOD
Only perform AI computations if player will
notice
For example


Only compute detailed paths for visible agents
Off-screen agents don’t think as often
Manager Task Assignment

Manager organizes cooperation between
agents




Manager may be invisible in game
Avoids complicated negotiation and
communication between agents
Manager identifies important tasks and
assigns them to agents
For example, a coach in an AI football team
Terrain Analysis


Analyzes world terrain to identify
strategic locations
Identify





Resources
Choke points
Ambush points
Sniper points
Cover points
Trigger System


Highly specialized scripting system
Uses if/then rules




If condition, then response
Simple for designers/players to
understand and create
More robust than general scripting
Tool development simpler than general
scripting
Promising AI Techniques


Show potential for future
Generally not used for games





May not be well known
May be hard to understand
May have limited use
May require too much development time
May require too many resources
Bayesian Networks


Performs humanlike reasoning when
faced with uncertainty
Potential for modeling what an AI
should know about the player


Alternative to cheating
RTS Example

AI can infer existence or nonexistence of
player build units
Blackboard Architecture

Complex problem is posted on a
shared communication space




Agents propose solutions
Solutions scored and selected
Continues until problem is solved
Alternatively, use concept to facilitate
communication and cooperation
Decision Tree Learning


Constructs a decision tree based on
observed measurements from game
world
Best known game use: Black & White


Creature would learn and form “opinions”
Learned what to eat in the world based
on feedback from the player and world
Filtered Randomness


Filters randomness so that it appears
random to players over short term
Removes undesirable events



Like coin coming up heads 8 times in a row
Statistical randomness is largely preserved
without gross peculiarities
Example:

In an FPS, opponents should randomly spawn
from different locations (and never spawn from
the same location more than 2 times in a row).
Genetic Algorithms




Technique for search and optimization that
uses evolutionary principles
Good at finding a solution in complex or
poorly understood search spaces
Typically done offline before game ships
Example:

Game may have many settings for the AI, but
interaction between settings makes it hard to
find an optimal combination
N-Gram Statistical Prediction



Technique to predict next value in a
sequence
In the sequence 18181810181, it
would predict 8 as being the next value
Example

In street fighting game, player just did
Low Kick followed by Low Punch

Predict their next move and expect it
Neural Networks


Complex non-linear functions that relate one
or more inputs to an output
Must be trained with numerous examples


Training is computationally expensive making
them unsuited for in-game learning
Training can take place before game ships

Once fixed, extremely cheap to compute
Planning



Planning is a search to find a series of
actions that change the current world state
into a desired world state
Increasingly desirable as game worlds
become more rich and complex
Requires



Good planning algorithm
Good world representation
Appropriate set of actions
Player Modeling

Build a profile of the player’s behavior



Continuously refine during gameplay
Accumulate statistics and events
Player model then used to adapt the AI


Make the game easier: player is not good at
handling some weapons, then avoid
Make the game harder: player is not good at
handling some weapons, exploit this weakness
Production (Expert) Systems

Formal rule-based system




Database of rules
Database of facts
Inference engine to decide which rules trigger –
resolves conflicts between rules
Example


Soar used experiment with Quake 2 bots
Upwards of 800 rules for competent opponent
Reputation System



Models player’s reputation within the game
world
Agents learn new facts by watching player
or from gossip from other agents
Based on what an agent knows



Might be friendly toward player
Might be hostile toward player
Affords new gameplay opportunities

“Play nice OR make sure there are no witnesses”
Smart Terrain



Put intelligence into inanimate objects
Agent asks object how to use it: how to
open the door, how to set clock, etc
Agents can use objects for which they
weren’t originally programmed for


Allows for expansion packs or user created
objects, like in The Sims
Enlightened by Affordance Theory

Objects by their very design afford a very
specific type of interaction
Speech Recognition



Players can speak into microphone to
control some aspect of gameplay
Limited recognition means only simple
commands possible
Problems with different accents,
different genders, different ages (child
vs adult)
Text-to-Speech



Turns ordinary text into synthesized speech
Cheaper than hiring voice actors
Quality of speech is still a problem




Not particularly natural sounding
Intonation problems
Algorithms not good at “voice acting”: the mouth
needs to be animated based on the text
Large disc capacities make recording human
voices not that big a problem

No need to resort to worse sounding solution
Artificial Intelligence: Pathfinding
Introduction




Almost every game requires
pathfinding
Agents must be able to find their way
around the game world
Pathfinding is not a trivial problem
The fastest and most efficient
pathfinding techniques tend to
consume a great deal of resources
Representing
the Search Space


Agents need to know where they can move
Search space should represent either



Search space typically doesn’t represent:


Clear routes that can be traversed
Or the entire walkable surface
Small obstacles or moving objects
Most common search space representations:



Grids
Waypoint graphs
Navigation meshes
Grids

2D grids – intuitive world
representation


Each cell is flagged


Works well for many games including
some 3D games such as Warcraft III
Passable or impassable
Each object in the world can occupy
one or more cells
Characteristics of Grids



Fast look-up
Easy access to neighboring cells
Complete representation of the level
Waypoint Graph


A waypoint graph specifies lines/routes that
are “safe” for traversing
Each line (or link) connects exactly two
waypoints
Characteristics
of Waypoint Graphs



Waypoint node can be connected to
any number of other waypoint nodes
Waypoint graph can easily represent
arbitrary 3D levels
Can incorporate auxiliary information


Such as ladders and jump pads
Radius of the path
Navigation Meshes


Combination of grids and waypoint graphs
Every node of a navigation mesh represents
a convex polygon (or area)


Advantage of convex polygon


As opposed to a single position in a waypoint
node
Any two points inside can be connected without
crossing an edge of the polygon
Navigation mesh can be thought of as a
walkable surface
Navigation Meshes (continued)
Characteristics of
Navigation Meshes



Complete representation of the level
Ties pathfinding and collision detection
together
Can easily be used for 2D and 3D games
Searching for a Path


A path is a list of cells, points, or nodes that
an agent must traverse
A pathfinding algorithm finds a path


From a start position to a goal position
The following pathfinding algorithms can be
used on



Grids
Waypoint graphs
Navigation meshes
Criteria for Evaluating
Pathfinding Algorithms


Quality of final path
Resource consumption during search


CPU and memory
Whether it is a complete algorithm

A complete algorithm guarantees to find
a path if one exists
Random Trace

Simple algorithm



Agent moves towards goal
If goal reached, then done
If obstacle


Trace around the obstacle clockwise or
counter-clockwise (pick randomly) until free
path towards goal
Repeat procedure until goal reached
Random Trace (continued)

How will Random Trace do on the
following maps?
Random Trace Characteristics



Not a complete algorithm
Found paths are unlikely to be optimal
Consumes very little memory
Understanding A*

To understand A*


First understand Breadth-First, Best-First,
and Dijkstra algorithms
These algorithms use nodes to
represent candidate paths
Understanding A*
class PlannerNode
{
public:
PlannerNode *m_pParent;
int
m_cellX, m_cellY;
...
};

The m_pParent member is used to chain nodes
sequentially together to represent a path
Understanding A*

All of the following algorithms use two lists




Open list keeps track of promising nodes
When a node is examined from open list


The open list
The closed list
Taken off open list and checked to see whether it
has reached the goal
If it has not reached the goal


Used to create additional nodes
Then placed on the closed list
Overall Structure of the
Algorithms
1. Create start point node – push onto open list
2. While open list is not empty
A. Pop node from open list (call it currentNode)
B. If currentNode corresponds to goal, break from
step 2
C. Create new nodes (successors nodes) for cells
around currentNode and push them onto open list
D. Put currentNode onto closed list
Breadth-First

Finds a path from the start to the goal by
examining the search space ply-by-ply
Breadth-First Characteristics

Exhaustive search



Consumes substantial amount of CPU
and memory
Guarantees to find paths that have
fewest number of nodes in them


Systematic, but not clever
Not necessarily the shortest distance!
Complete algorithm
Best-First



Uses problem specific knowledge to
speed up the search process
Head straight for the goal
Computes the distance of every node
to the goal

Uses the distance (or heuristic cost) as a
priority value to determine the next node
that should be brought out of the open list
Best-First (continued)
Best-First (continued)

Situation where Best-First finds a suboptimal path
Best-First Characteristics



Heuristic search
Uses fewer resources than BreadthFirst
Tends to find good paths


No guarantee to find most optimal path
Complete algorithm
Dijkstra

Disregards distance to goal



Keeps track of the cost of every path
No guessing
Computes accumulated cost paid to
reach a node from the start

Uses the cost (called the given cost) as a
priority value to determine the next node
that should be brought out of the open list
Dijkstra Characteristics




Exhaustive search
At least as resource intensive as
Breadth-First
Always finds the most optimal path
Complete algorithm
A*

Uses both heuristic cost and given cost to
order the open list

Final Cost = Given Cost + (Heuristic Cost * Heuristic Weight)
A* (continued)

Avoids Best-First trap!
A* Characteristics




Heuristic search
On average, uses fewer resources than
Dijkstra and Breadth-First
Admissible heuristic guarantees it will find
the most optimal path
Complete algorithm
Summary

Two key aspects of pathfinding:


Representing the search space
Searching for a path
Audio Programming
Audio Programming
Audio in games is more important than
ever before
Programming Basic Audio

Most gaming hardware has similar
capabilities (on similar platforms)


Mostly programming interfaces differ
Learning fundamental concepts of
audio programming is important
API Choices

DirectSound (part of DirectX API)


OpenAL



Newer API
Available on multiple platforms
Proprietary APIs


Only available on Windows platforms
Typically available on consoles
3rd Party Licensable APIs

Can offer broad cross-platform solutions
Analog Sound Wave
Basic Audio Terminology and
Physics

Amplitude


Frequency


The perception of frequency
Tuning


Measurement of the interval between wave cycles,
typically measured in Hertz
Pitch


Measurement of a sound wave’s pressure
Musical distribution of frequencies over keys
Decibel

Measures sound amplitude
Digital Representation of a
Sound Wave
Digital Representation
of a Sound Wave

Most common technique known as sampling





Sampling involves measuring the amplitude of
the analog wave file at discrete intervals
The frequency of sampling is known as sampling
rate
Each sample is typically stored in a value ranging
from 4 to 24 bits in size
The size of the sample value in bits is known as
the ‘bit depth’
Music CDs have a sample rate and bit depth of
44.1 kHz (samples/sec) and 16 bits (sample size)
Quantization Error in Sampling
Bit Depth and Signal Noise

Bit depth of sample data affects signal noise



Signal to noise ratio = number of available bits /
1
For example, 8-bit samples have a 256:1 SNR
(~48 dB), and 16-bit samples have a 65,536:1
SNR (~96 dB)
Decibel ratio is calculated using 10 x log10 (ratio)
or 8.685890 x log e (ratio)
Sampling Frequency and
Frequency Reproduction


Sampling frequency affects range and
quality of high-frequency reproduction
Nyquist Limit


Frequencies up to one-half the sampling
rate can be reproduced
Audio quality degrades as frequency
approaches this limit
Sampling Errors vs. Sampling
Frequency
Modern Audio Hardware

Samples are piped into sound
“channels”



Often a hardware pipeline from this point
Various operations, such as volume,
pan, and pitch may be applied
3D sounds may apply HRTF
algorithms and/or mix the sound into
final output buffers.
Sound Playback Techniques

Two basic playback methods:
1. Play sample entirely from memory buffer
2. Stream data in real-time from storage
medium


Streaming is more memory efficient for very
large audio files, such as music tracks,
dialogue, etc
Streaming systems use either a circular
buffer with read-write pointers, or a doublebuffering algorithm
Playback
Sample Playback and
Manipulation

Three basic operations you should know

Panning is the attenuation of left and right
channels of a mixed sound



Results in spatial positioning within the aural stereo
field
Pitch allows the adjustment of a sample’s
playback frequency in real-time
Volume control typically attenuates the volume
of a sound

Amplification is generally never supported
Compressed Audio Format

Compressed audio formats allow sound and
music to be stored more compactly

Bit reduction codecs generally are lightweight


ADPCM compression is implemented in hardware on
all the major current video game console systems
Psycho-acoustic codecs often have better
compression


Discard sounds our ears would not typically be able to
hear
Require substantially more computational horsepower
to decode
MP3, Ogg Vorbis,
Licensing & Patent Issues

The MP3 format is patented


Ogg Vorbis is similar to MP3 in many ways


Any commercial game is subject to licensing
terms as determined by Fraunhofer & Thompson
Multimedia, the holders of the patents
Open source and patent-free (royalty-free)
Be aware of patent and license restrictions
when using 3rd party software
3D Audio

Two sets of data required when
working in world coordinates:

Listener Data


Composed of world position and orientation
(virtual microphone in the world)
Source Data

Composed of sound position, orientation,
velocity, etc (virtual sound source in the
world)
Listener/Source
Environmental Effects


Environmental effects nearly always
implemented in hardware
Sound transmission is categorized in
three ways



Direct transmission
Early reflections (echo)
Late reflections (reverberation)
Sound Transmission
Categories
Environmental
Effects Standards

EAX 2.0 and beyond



EAX 2.0 developed by Creative Labs and
released as an open standard
EAX 3.0 and 4.0 remain proprietary
Creative Labs standards
I3DL2

Open standard developed by IA-SIG,
similar to EAX 2.0 in functionality
Programming Music Systems

Two common music systems

MIDI-based systems


(Musical Instrument Digital Interface)
Digital audio streaming systems

(CD audio, MP3 playback, etc)
Advantages and
Disadvantages of MIDI




Actual music data size is negligible
Easy to control, alter, and even
generate in real-time
High quality music is more difficult to
compose and program
Only effective if you can guarantee
playback of a common instrument set
Example
Other MIDI-based
technologies to be aware of

DLS (DownLoadable Sound) Format


A standardized format for instrument
definition files
iXMF (Interactive eXtensible Music
Format)

New proposed standard for a container
format for interactive music
Advantages / Disadvantages
of Digital Audio Streams




Superb musical reproduction is
guaranteed
Allows composers to work with any
compositional techniques
Some potential interactivity is
sacrificed for expediency and musical
quality
Generally high storage requirements
A Conceptual Interactive
Music Playback System



Divide music into small two to eightbar chunks that we’ll call segments.
A network of transitions from segment
to segment (including loops and
branches) is called a theme.
Playing music is now as simple as
choosing a theme to play. The
transition map tracks the details.
Advanced Audio Programming





3D Audio Environmental Effects
Integration
Audio Scripting and Engine Integration
Lip-sync Technology
Advanced Voice Playback
Voice Recognition
3D Audio Environmental
Effects Integration

Environmental effects should be driven
by a room’s shape and material
composition.


Can determining the optimal effect
settings be done automatically?
This may be important as game worlds
become larger and more complex
3D Audio Environmental
Effects Integration (cont)

Sound occlusion and damping is a
particularly difficult problem to solve



This is essentially a pathfinding problem
for audio.
Doors can dynamically affect a sound’s
properties
Very few titles have even attempted a
robust, general-purpose, and automated
solution to these problems.
Room Acoustics
Dynamic Occlusion
Audio Scripting and Engine
Integration




Very little audio programming should
be done by general game
programmers
Game Engine should offer robust
support for audio triggers and scripts
Engine should deal with audio scripts,
not “sound files”
Why is this so important?
Audio Scripting

Many situations require much more
information than can be embedded in
a linear audio file




Sound Variation
Sound Repetition
Complex Sound Looping
Background Ambience
Lip-sync Technology

Lip-sync technology is a blending of audio
and visual techniques to create realisticlooking speech by in-game actors.



Simple techniques such as waveform amplitude
measurement has worked previously, but…
In future titles, it will be considered inadequate.
Much work can still be done in this field.
Advanced Voice Playback



Real-time spoken feedback is especially
important in sports titles (simulated
announcers)
Game are reaching the limits of what current
techniques (canned, prerecorded phrases
combined in series) can provide.
Again, this is an opportunity for future
groundbreaking audio work.
Voice Recognition



Spoken commands are much easier to
deliver in certain situations.
A great example of this? Squad-based
tactical shooters.
Current generation systems are still
very error prone. A great opportunity
for breakout audio technology.