Transcript CSCE 590E Spring 2007

CSCE 552 Spring 2011
Inverse Kinematics & AI
By Jijun Tang
Announcements

Second presentation: April 11th and 13th



In class
Each group 12 minutes
What to show:





Detailed designs of layers/modules/classes
Progress report with demo
3D/2D Models, graphics, etc
Schedules and milestones
Problems and planned changes
Frustum and Frustum Culling
Hemisphere Lighting
Normal Mapping Example
Specular Lighting
Environmental Map
Inverse Kinematics






FK & IK
Single Bone IK
Multi-Bone IK
Cyclic Coordinate Descent
Two-Bone IK
IK by Interpolation
FK & IK

Most animation is “forward kinematics”


But there are feedback mechanisms




Motion moves down skeletal hierarchy
Eyes track a fixed object while body
moves
Foot stays still on ground while walking
Hand picks up cup from table
This is “inverse kinematics”

Motion moves back up skeletal hierarchy
Example of Inverse
Kinematics
Single Bone IK

Orient a bone in given direction





Find desired aim vector
Find current aim vector
Find rotation from one to the other



Eyeballs
Cameras
Cross-product gives axis
Dot-product gives angle
Transform object by that rotation
Multi-Bone IK

One bone must get to a target position



Can move some or all of its parents
May be told which it should move first


Bone is called the “end effector”
Move elbow before moving shoulders
May be given joint constraints

Cannot bend elbow backwards
Cyclic Coordinate Descent




Simple type of multi-bone IK
Iterative: Can be slow
May not find best solution: May not
find any solution in complex cases
But it is simple and versatile: No
precalculation or preprocessing
needed
Procedures







Start at end effector
Go up skeleton to next joint
Move (usually rotate) joint to minimize
distance between end effector and target
Continue up skeleton one joint at a time
If at root bone, start at end effector again
Stop when end effector is “close enough”
Or hit iteration count limit
Properties


May take a lot of iterations
Especially when joints are nearly
straight and solution needs them bent



e.g. a walking leg bending to go up a step
50 iterations is not uncommon!
May not find the “right” answer

Knee can try to bend in strange directions
Two-Bone IK


Direct method, not iterative
Always finds correct solution


Allows simple constraints


Knees, elbows
Restricted to two rigid bones with a rotation
joint between them


If one exists
Knees, elbows!
Can be used in a cyclic coordinate descent
Two-Bone IK Constraints





Three joints must stay in user-specified
plane: e.g. knee may not move sideways
Reduces 3D problem to a 2D one
Both bones must remain original length
Therefore, middle joint is at intersection of
two circles
Pick nearest solution to current pose, or one
solution is disallowed: Knees or elbows
cannot bend backwards
Example
Disallowed
elbow
position
Shoulder
Wrist
Allowed
elbow
position
IK by Interpolation


Animator supplies multiple poses
Each pose has a reference direction




e.g. direction of aim of gun
Game has a direction to aim in
Blend poses together to achieve it
Source poses can be realistic


As long as interpolation makes sense
Result looks far better than algorithmic IK with
simple joint limits
Example


One has poses。 for look ahead, look
downward (60 ), look right, look down and
right
。
。
Now to aim 54 right and 15 downward,
thus 60% (54/90) on the horizontal scale,
25% (15/60) on the downward scale




Look ahead (1-0.25)(1-0.6)=0.3
Look downward 0.25(1-0.6)=0.1
Look right (1-0.25) 0.6=0.45
Look down and right (0.25)(0.6)=0.15
IK by Interpolation results

Result aim point is inexact



Blending two poses on complex
skeletons does not give linear blend
result
But may be good enough from the game
perspective
Can iterate towards correct aim
Attachments



e.g. character holding a gun
Gun is a separate mesh
Attachment is a bone in character’s skeleton




Represents root bone of gun
Animate character
Transform attachment bone to world space
Move gun mesh to that pos+orn
Attachments (2)


e.g. person is hanging off bridge
Attachment point is a bone in hand





As with the gun example
But here the person moves, not the bridge
Find delta from root bone to attachment
bone
Find world transform of grip point on bridge
Multiply by inverse of delta

Finds position of root to keep hand gripping
Artificial Intelligence:
Agents, Architecture, and Techniques
Artificial Intelligence



Intelligence embodied in a man-made
device
Human level AI still unobtainable
The difficulty is comprehension
Game Artificial Intelligence:
What is considered Game AI?

Is it any NPC (non-player character)
behavior?





A single “if” statement?
Scripted behavior?
Pathfinding?
Animation selection?
Automatically generated environment?
Possible Game AI
Definition
Inclusive view of game AI:
“Game AI is anything that contributes to the
perceived intelligence of an entity,
regardless of what’s under the hood.”
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
Specialization of
Game AI Developer

No one-size fits all solution to game AI


Strategy Games



Battlefield analysis
Long term planning and strategy
First-Person Shooter Games



Results in dramatic specialization
One-on-one tactical analysis
Intelligent movement at footstep level
Real-Time Strategy games the most
demanding, with as many as three full-time
AI game programmers
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
Players cannot
Complete terrain layout
Location and state of every game object
Location and state of player
But isn’t this cheating???
Sensing:
Enforcing Limitations


Human limitations?
Limitations such as





Not knowing about unexplored areas
Not seeing through walls
Not knowing location or state of player
Can only know about things seen,
heard, or told about
Must create a sensing model
Sensing:
Human Vision Model for Agents

Get a list of all objects or agents; for each:
1. Is it within the viewing distance of the agent?


How far can the agent see?
What does the code look like?
2. Is it within the viewing angle of the agent?


What is the agent’s viewing angle?
What does the code look like?
3. Is it unobscured by the environment?


Most expensive test, so it is purposely last
What does the code look like?
Sensing:
Vision Model


Isn’t vision more than just detecting the
existence of objects?
What about recognizing interesting
terrain features?


What would be interesting to an agent?
How to interpret it?
Sensing:
Human Hearing Model




Human can hear sounds
Human can recognize sounds and
knows what emits each sound
Human can sense volume and
indicates distance of sound
Human can sense pitch and location


Sounds muffled through walls have more
bass
Where sound is coming from
Sensing:
Modeling Hearing

How do you model hearing efficiently?


Do you model how sounds reflect off every
surface?
How should an agent know about sounds?
Sensing:
Modeling Hearing Efficiently

Event-based approach



When sound is emitted, it alerts
interested agents
Observer pattern
Use distance and zones to determine
how far sound can travel
Sensing:
Communication

Agents might talk amongst
themselves!



Guards might alert other guards
Agents witness player location and
spread the word
Model sensed knowledge through
communication

Event-driven when agents within vicinity
of each other
Sensing:
Reaction Times



Agents shouldn’t see, hear,
communicate instantaneously
Players notice!
Build in artificial reaction times



Vision: ¼ to ½ second
Hearing: ¼ to ½ second
Communication: > 2 seconds
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
Thinking:
Expert Knowledge

Many different systems





Encoding expert knowledge is appealing
because it’s relatively easy



Finite-state machines
Production systems
Decision trees
Logical inference
Can ask just the right questions
As simple as if-then statements
Problems with expert knowledge: not very
scalable
Finite-state machine (FSM)
Production systems



Consists primarily of a set of rules about
behavior
Productions consist of two parts: a sensory
precondition (or "IF" statement) and an
action (or "THEN")
A production system also contains a
database about current state and
knowledge, as well as a rule interpreter
Decision trees
Logical inference


Process of derive a conclusion solely
based on what one already knows
Prolog (programming in logic)
mortal(X) :- man(X).
man(socrates).
?- mortal(socrates).
Yes
Thinking:
Search

Employs search algorithm to find an
optimal or near-optimal solution




Branch-and-bound
Depth-first
Breadth-first
A* pathfinding common use of search

Kind of mixed
Depth and breadth-first
Thinking:
Machine Learning


If imparting expert knowledge and search
are both not reasonable/possible, then
machine learning might work
Examples:




Reinforcement learning
Neural networks
Decision tree learning
Not often used by game developers

Why?
Thinking:
Flip-Flopping Decisions



Must prevent flip-flopping of decisions
Reaction times might help keep it from
happening every frame
Must make a decision and stick with it


Until situation changes enough
Until enough time has passed
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
Acting:
Showing Intelligence




Adeptness and subtlety of actions impact
perceived level of intelligence
Enormous burden on asset generation
Agent can only express intelligence in terms
of vocabulary of actions
Current games have huge sets of
animations/assets

Must use scalable solutions to make selections
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
Learning


Remembering outcomes and
generalizing to future situations
Simplest approach: gather statistics



If 80% of time player attacks from left
Then expect this likely event
Adapts to player behavior
Remembering

Remember hard facts



Memories should fade



Observed states, objects, or players
Easy for computer
Helps keep memory requirements lower
Simulates poor, imprecise, selective human
memory
For example



Where was the player last seen?
What weapon did the player have?
Where did I last see a health pack?
Remembering
within the World


All memory doesn’t need to be stored
in the agent – can be stored in the
world
For example:




Agents get slaughtered in a certain area
Area might begin to “smell of death”
Agent’s path planning will avoid the area
Simulates group memory
Making Agents Stupid

Sometimes very easy to trounce player



Make agents faster, stronger, more accurate
Challenging but sense of cheating may
frustrate the player
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
People notices it
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
No one wants to fight a stupid enemy, trade-off
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
US Military Chain of
Command
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



Simulates flocking birds, schooling fish
Developed by Craig Reynolds: 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
Need a leader
Flocking/Formation
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
Mapping Example
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