Transcript ppt

Math / Physics 101
GAM 376
Robin Burke
Winter 2008
Homework #1
Use my code not Buckland’s web site
 Visual Studio Express


see DL’s comments (col site)
Discussion site

any course-related topic
Begin math / physics 101

If you’ve taken GAM 350
or any other kind of physics
 mostly review

Vectors
 Coordinate spaces
 Kinematics

Why physics?
What does physics have to do with
AI?
 Game characters

must react to the world and its physics
 must make predictions about what will
happen next
 must take actions that depend on the
world’s physical properties

Why physics?
This is the most fundamental form of
“avoiding stupidity”
 Game characters

should act as though they understand
the physical world of the game
 will often be blind to other aspects of
the game

Vector

A multi-dimensional quantity


We will deal mostly with 2-D vectors


represented by a tuple of numbers
<2, 5>
3-D vectors are more mathematically
complex
but not fundamentally different
 for AI purposes

Vectors

can represent positions


can also represent velocities


<1,1> is a position 1 unit north and 1
unit east of the origin
<3,-4> is a speed of 5 units in a
northwesterly direction
other quantities

orientation, acceleration, angle, etc.
Vector operations




Magnitude
 v = <x1, y1>
 | v | = magnitude(v) = sqrt(x12+y12)
 the length of the vector
Adding
 <x1, y1> + <x2, y2> = <x1+x2, y1+y2>
Scalar multiplication
 <x1, y1> * z = <x1*z, y1*z>
 changes only the length
Normalization
 v / |v|
 makes a vector of length 1
 does not change the orientation of the vector
More vector operations

dot product

<x1, y1> ● <x2, y2> =
• x1 * x2 + y1 *y2




scalar quantity
related to the angle between vectors
cos (angle) = u ● v / | u | | v |
Note


if u and v are normalized (length = 1)
then u ● v is the cosine of the angle between
them
Example

we have two agents: a, b
 each has a vector position
 and a normalized vector orientation
• the direction they are facing





turn to face an enemy
 agent: Pa, Oa
 enemy: Pb, Ob
vector from agent to enemy
 Pba = Pb-Pa
 normalize it
compute dot product
 norm(Pba) ● Oa
compute inverse cosine
this is the angle to turn
Turn to face
cos-1(Oa • norm(Pb-Pa))
Pa
Pb-Pa
Pb
What if I want to run away?
Normal vectors

A normal vector is orthogonal to
another vector


in 2 dimensions = 90 degrees
n●v=0
Coordinate transformations


We will always want to move back and forth between
coordinate systems
 objects each have their own local coordinate systems
 related to each other in "world space"
Example
 NPC
• a character is at a particular position, facing a particular
direction
• he defines a coordinate system

Door
• the door has its own coordinate system
• in that system, the handle is in a particular spot

To make the character reach for the handle
• we have to make the two coordinate systems interact
Transformations

We know




Set of transformations



where the handle is in door space
where the agent's hand is in agent space
what is the vector in agent space
transform handle location L0 to world space
Lw
transform handle location to agent space La
Each transformation


is a translation (changing the origin)
and a rotation changing the orientation
Affine transformations

Usually coordinate transformations are
done through matrix multiplications


we multiply a vector by a matrix and get
another vector out
The curious thing is


that to do this we have to use vectors and
matrices one size larger than our current
number of dimensions
you will see <x, y, 1> as the representation
of 2-D vector and <x,y,z,1> for 3-D
Matrix math
2-D dimensional array
 Matrix multiplication

FxG
 dot product of

 a11 a12
a
 21 a22
a31 a32
• rows of F
• columns of G

corrolary
• multiplication only works
• if cols of F = rows of G
a13 
a23 
a33 
Matrix math

Can also multiply a vector times a
matrix


vxM
Result
a new vector
 each entry

• a dot product of v with a different row of M

length of v
• must equal number of cols in M
Example



rotation around the origin by angle θ
matrix cos( )  sin(  ) 0
 sin(  )

 0
0
1
multiply by current vector


cos( )
0
<1, 1> becomes <1, 1, 1>
answer



x = cos(θ) – sin (θ) + 0
y = sin(θ) + cos(θ) + 0
z=1
x' = x cos(θ) – y sin(θ)
 y' = x sin(θ) + y cos(θ)

(2.12, 0.70)
(1, 2)
θ = -π / 4
Translation
Achieved by adding values at the
ends of the top two rows
 This rotates and translates by (3, -4)

cos( )  sin(  ) 3 
 sin(  ) cos( )  4


 0
0
1 
Efficiency



Mathematical operations are expensive
 especially trigonometric ones (inverse cosine)
 also square root
 multiplication and division, too
Normalization is particularly expensive
 square root, squaring and division
We want to consider ways to make our calculations
faster
 especially if we are doing them a lot
Squared space

We can do calculations in "squared
space"


never have to do square roots
Example

test whether one vector is longer than
another
• sqrt(X12+Y12) > sqrt(X22+Y22)
• X12+Y12 > X22+Y22
• both will give the same result
Exercise
Kinematics

the physics of motion

we worry about this a lot in computer
games
• moving through space, collisions, etc.

our NPCs have to understand this too
in order to avoid stupidity
Basic kinematics

position



a vector in space
(point position)
for a large object we use a convenient point
• classically the center of mass

velocity

the change of position over time
• expressed as a vector

pt+1 = pt + vΔt


if we define the time interval Δt to be 1
we avoid a multiplication
Basic kinematics II

Acceleration

change in velocity over time
• also expressed as a vector
vt+1 = vt + a Δt
 Pair of difference equations

Numerical methods


We want to run a simulation that shows what happens
But now we have a problem



Example
 deceleration to stop





there is a lag of 1 time step before acceleration impacts
position
not physically accurate
t = 0, d = 0, v = 10, a = 0
t = 1, d = 10, v = 10, a = -5
t = 2, d = 20, v = 5, a = -5
t = 3, d = 25, v = 0, a = 0
Correct distance traveled



Δd = v0 Δt + ½ a Δt 2
Δd = 10
d = 20
We can improve our
simulation


finer time step (expensive)
improved estimation methods


Example





for example instead of using vt, we can use the average of
vt and vt+1
t=0, d=0, v=10, a =0
t=1, d=10, v=10, a = -5
t=2, d=17.5, v=5, a=-5
t=3, d=20, v=0, a=0
better




we slow down in the first time step
correct final answer
but only works if acceleration is constant
take GAM 350 for better ways
Another derivation
velocity
v(t+1)
v(t)
time
What does this have to do
with AI?

Imagine a NPC



he has to decide how hard to throw a
grenade
that judgment has to be based on an
estimate of the item’s trajectory
When NPC take physical actions



we have to know what the parameters of
those actions should be
very often physics calculations are required
not as detailed as the calculations needed to
run the game
Approximation in Prediction




NPC will frequently need to predict the future
 where will the player be by the time my rocket gets
there?
Assumptions
 current velocity stays constant
 we know the speed of the rocket
Correct way
 vector algebra
 lots of square roots and trig functions
Typical approximation
 use the current distance
 won't change that much if the rocket is fast
Accuracy?

Accuracy may be overrated


for NPC enemies
We want an enjoyable playing experience

no warning sniper attack is realistic
• but no fun


a game has to give the player a chance
Built-in inaccuracy



many games have enemies deliberately miss on
the first couple of shots
others build random inaccuracy into all
calculations
others use weak assumptions about physics
• simplify the calculations
• and give a degree of inaccuracy
Force

Netwon's law


In other words


F = m*a
acceleration is a function of force and
mass
Force is also a vector quantity
a force acting along a vector
 imparts a velocity along that vector

Example

When a bat hits a ball

we will want to determine the force
imparted to the ball
• we could simulate this with the mass of
the bat and its speed
• more likely, we would just have a built-in
value

direction of the force
• we need to know the angle of the bat
when it strikes the ball
More complex motions

To handle rotation


we also have to worry about torque
and angular momentum
For example

if a rocket hits the back of a car
• it will spin
• if it hits the center, it will not
Torque

Force applied around the center of
mass of an object
torque gives rise to angular
acceleration (spin)
t=dF=Iα

d = moment arm
For our purposes

We will ignore rotational motion

deal only with forces acting on points
• typical simplification for AI
Thursday

Finite state machines