Transcript Movement – Physics(ish) - Google Project Hosting

CS425 Lecture 9
Jan M. Allbeck
Slides based on those by Graham Morgan
Tonight

Simple physics
Simple collision detection
A bit of OpenGL by NeHe
[I stop by 8:30 (maybe 8:45)]
Group work time!

Next week: evaluations (they actually matter)




Movement – Physics

Objectives –




Realize a simple method for moving entities.
Understand the complexities associated to
introducing realistic physics into games.
Learn the basics of some mathematical techniques
for achieving movement.
Be able to make informed judgments on the
suitability of physics powered algorithms when
achieving animations.
Achieving movement


Irrespective of what you want to achieve,
mathematics will form some part of your
solution.
There are two approaches we may take:



Faking physics
Not faking physics (well, not in the same way
anway)
If we can model quite accurately the physics of
a gaming environment why should we fake it?


Answer 1: Computational steps required are large,
possibly resulting in game slow down (low frame
rates).
Answer 2: The mathematic ability of the
programmers tends to be limited.
Remember this stuff…..

Time


Speed


The rate of change of velocity
Force


The rate of change of position over time (has speed and direction)
Acceleration


An indication of travel
Velocity


The distance travelled given some time limit
Direction


A measured duration
Causes objects to accelerate (has direction as well as magnitude)
Mass

The weight of an object? (NO! weight depends on gravitational pull)

The quantity of matter
Newton’s Laws of Motion

What are they…..
Newton’s First Law of Motion

Every object in a state of uniform motion
tends to remain in that state of motion unless
an external force is applied to it.

This also indicates that if an object is at rest
(not moving) it will remain at rest.
Newton’s Second Law of Motion

A force is applied only to the concept we
commonly call acceleration.

An object's mass m, its acceleration a, and
the applied force F may be represented by the
simple formula:

F = ma
Newton’s 3rd Law of Motion

For every action there is an equal and
opposite reaction.


Yes, discussed many times in 1970s sci-fi shows.
If two objects bump into each other they will
react by moving apart.
Physics (don’t get confused)

Newtonian (THIS ONE FOR GAMES)


Classical


Newton’s space and time were absolute
Einstein's space-time could be “changed” by
matter
Quantum

Deterministic causality questioned and multiple
localities in single instance
Types of forces

There are a few, however, game developers
have to contend with:


Trying to be a little more clever, a game
developer may introduce the following:


Gravity, Applied, and Normal
Spring, Air Resistance, Friction and Tension
http://www.physicsclassroom.com/Class/newtlaws/
U2l2b.cfm
Example – Faking 2D movement
with acceleration

Variables and mathematics




Variable D identifies direction (taken from domain
of, say, 16 possible directions of movement).
Variable S identifies current speed (possibly
identifying number of pixels covered per frame
across screen).
Variable A identifies acceleration (a small number
that is added to S each frame).
The math is trivial and very quick to compute.
Example – Faking 2D movement
with acceleration
D=NW results in X=X+S and Y=Y+S.
D=NNW result in X=X+(S/2) and Y=Y+S
NNW
NW
Etc.






Repeat {
Draw
Update X & Y
Update S (using A)
Handle events (may result in changing of
D or A).
}
Example – Using physics to achieve
2D movement with acceleration

The derivative of the position vector is the velocity vector for a
point X, Y that represents a position of an entity.
 This tells us in which direction the entity is moving and at
what speed.
 Luckily, vector calculus is simply scalar calculus on each
element of the vector (i.e., the derivative of the X element
of the position is the X element of the velocity).
 STOP! - Remember, when differentiating a variable we find
the rate at which it is changing. You all remember gradients
of curves and then applying differentiation to quantities
changing with time?


You should answer yes to this.
Recap – for the curve y=f(x) the gradient function is called the
derivative of f(x) so that
f `(x) =
lim
f(x+h) - f(x)
h0
h
Example – Using physics to achieve
2D movement with acceleration

Denote the position vector with r, the
velocity vector with v.

A dotted r may also be used for v (this indicates
differentiated with respect to time).
dr
=v=r
dt
• Acceleration is the derivative of velocity.
– This also means it is the second derivative of
position.
d2r
dt2
=r=
dr
dt
=
dv
dt
=v=a
• Integrating the acceleration over time gives the velocity.
• Twice integrating the acceleration gives the position.
Complications


We have simply considered a point moving in a
straight line.
When we wish to have a curved line more
complicated mathematics is required.



Further complications arise when we introduce
other forces (such as modeling gravitational pull or
a push effect from an exploding entity or rotational
velocity).
The introduction of forces is a necessity as nothing
would move without them.
Writing algorithms that satisfy the physics
requirements of complex modern games is
extremely difficult.

The programmer should have good training in
mathematics and possibly be of an engineering
background (e.g., mechanical).
Physics engine


When developing the 3D graphical aspect of a
game we use tools. Even if it is just OpenGL,
we are helped.
The same can be said about game physics to a
certain extent.


Code libraries exist that ease the development of
games that require physics.
A drawback is that there is no one standard
API for using physics in games.


Software houses tend to develop their own propriety
development tools.
These tools tend not to provide good usage in a
heterogeneous environment.
Physics Engines




Havok
Open Dynamics Engine (ODE)
PhysX
Bullet
Why use physics engines?



They improve realism.
Faking physics does not provide a realistic environment.
 Take our velocity/acceleration example. How easy will
it be to ensure that items act in a realistic manner?
 For example, what type of algorithm could you
develop that shows items of different mass realistically
bouncing off each other?
There is no doubt that the presence of physics increases
the realism aspects of a game. However, is real physics
what you want?
 Car racing games tend not to be realistic. Driving at
200 mph round bends is simply not possible (and
would result in far more damage than you actually
witness).
 You can change the values fed into a physics engine to
create “unrealistic” environments.
When to use physics


Due to the computational demands of reproducing
accurate environments using real physics, it may not be
practical to use “heavyweight” physics algorithms all the
time.
 Consider a game that provides a nice animation
sequence of a clock face to enhance realism. The clock
face plays no part in the game play.
 Is it worth spending valuable computational time
determining the exact position of the hands every
frame so the clock tells the PC time?
Sometimes flat (not even 3D) bitmap based animation
sequences will suffice.
 The player may not even notice the difference.
NeHe Basic Physics
http://nehe.gamedev.net/data/lessons/lesson.asp?
lesson=39
NeHe Particles
http://nehe.gamedev.net/data/lessons/lesson.asp?
lesson=19
NeHe Rope Physics Demo
http://nehe.gamedev.net/data/lessons/lesson.asp?
lesson=40
Cars – an example of using
physics

Objectives


Understand what calculations are required to
produce realistic car animation.
Apply such calculations to aid in car animation.
A car

Cars have attributes such as wheels, an
engine and a shell.
The world of the car

Cars exist in an environment that exerts
forces.
Resistance

A car driving down a road experiences
two (main) types of resistance.

Aerodynamic drag, rolling resistance.
Rtotal  Rair  Rrolling
• Once this resistance has been
determined it is possible to identify the
amount of power a car must have to
“move”.
Aerodynamic drag
Mass density of
air
Projected frontal area of
car normal to direction of
V
Rair  (1 / 2)V S pCd
2
Speed of car
Drag coefficient
0.29 – 0.4: sports cars
0.6 – 0.9: trucks and
tractors
Rolling resistance

Tires rolling on a road experience rolling
resistance. This is not friction and has a lot to do
with tire deformation. Missing out a lot of
complications, we can use the following formula.
Rrolling  Cr
Coefficient of rolling resistance
Tire manufacturers usually
provide this.
Cars ~ 0.015, trucks ~ 0.006 –
0.01
Weight of car
(assuming four
identical tires)
Power



Power is the measure of the amount of
work done by a force, or torque, over time.
Mechanical work done by a force is equal to
the force times the distance an object
moves under the action of that force.
Power is usually expressed, for cars, in
units of horsepower.


1 horsepower = 550 ft-lbs/s
So we need to determine power of the
engine and what force such power actually
delivers to the wheel.

What speed do we end up with?
Horsepower

Calculating horsepower to overcome
total resistance at a given speed (we are
working in feet and lbs here).
P  ( RtotalV ) / 550
horsepower
Total resistance
corresponding to
car’s speed (V)
Engine output



The previous equation simply identified the required
power to be delivered to the drive wheel to reach
speed V.
Engine power required will be higher (e.g., mechanical
loss).
Power is actually delivered to tire in the form of torque.
Fw  Tw / r
Force delivered by
tire to the road to
push car along
Torque on the tire
Radius of tire
Stopping

Stopping distance relates to the braking
system and how hard the driver breaks.



If a car skids then the stopping distance
relates to the frictional force between the
tyres and the road.
If travelling uphill the stopping distance
will be shorter.


In simple terms, the harder the brakes are
applied the shorter the stopping distance.
Gravity plays a role.
If travelling downhill the stopping distance
will be greater.
Calculating skidding distance
Initial speed of
the car
d s  v /[ 2 g (  cos   sin  )]
2
Acceleration due
to gravity
Coefficient of
friction between
tires and road.
Usually around
0.4
Inclination of
the road
More calculations required?


In this example we have applied only very
basic calculations.
In a real driving game a lot more parameters
play a role.


For example, suspension, variable engine power,
road surface.
However, just applying what we have seen
here will provide a dramatic increase in
realism.
Collision Detection

Objectives –



Understand what is meant by the term collision
detection.
Understand the limitations of collision techniques.
Realize methods for gaining greater levels of
collision detection when dealing with irregular
shaped objects.
What is collision detection?




Entities occupy, partially or fully, the same location at the
same time.
We term the above scenario a collision.
Collision leads to event(s) in most cases –
 Bullet hitting a box of grenades causing the event of
explosion and possibly other events (e.g., reduction of life
force for players stood near the grenades at time of
explosion).
However, this is not the full story –
 Ideally we should foresee collision as immanent and time
our event to occur at a deterministic point in time (true
collision).
 Q: How is this achieved while still maintaining performance?
 A: With great difficulty when performance permits.
Text represented world (Easy)





We move into a new location, each location is textually
represented via description.
Entities in the same location are simply considered
“collided”.
Once collision has occurred then other actions may be
achieved (i.e., interact with other entities present in the
location – e.g., chat).
Text based adventure games (e.g., classic games such
as The Hobbit on the ZX architectures) may present
some descriptive pictures.
Round based games (e.g., Civilization – military units in
the same space fight).
Graphically represented world

Check to see if the edges of your entity cross the edges of
another entity
 If they do then cause collision event.

Slightly complicated when we don’t really want to show
intersection (e.g., foot going through wall):
 Bounding box (or sphere) introduced:
 Check for collision with vectors of bounding box (or sphere).

Cheating in 2D:
 In quite a static environment, check to see if pixels of an
entity change color – draw background last. This approach
popular with 80’s 2D arcade style games as resolution was
low. Color was often used to identify items (good or bad).
A problem with frame rate and
collision


An entity moves around the screen at a given
speed. This speed may be increasing, decreasing
(accelerating or decelerating) or may be static.
If the speed of an entity is such that the distance
moved on screen is sufficiently large per frame
rate, then simply identifying if vertices cross is not
an appropriate solution.

They may never cross!
Entity
Solid wall
Frame 1
Frame 2
Considering time in collision
detection

Assume entities E1 and E2 are displayed in
different positions at the following frame
times t1, t2 (giving the illusion of motion).
E1
E2
t1
E2
E1
t1
• We know they collided, but as far as the display is concerned
no collision has occurred. (they have passed through each
other).
• We need to introduce the notion of time into our
equations to aid collision detection.
Possible solutions – Projecting bounding
box.

Produce bounding box around an entity at
current frame and next frame position (look
ahead) and check collisions using this new
shape.
• For this method to work we are actually carrying out twice as
much detection as required. This is very time consuming and
will possibly reduce performance (even slower frame rate).
Possible solutions – Using time in our
equations



Use a recursive algorithm to check for
intersection at lower time intervals (even
though these will not be displayed on screen).
Carry out our calculations in 4D (including
time). This is complicated physics and
computationally draining of valuable CPU
time.
In real-time games (such as first person
shooters) these types of calculations are just
too intensive.
Using a sphere

We surround our entity with a large enough
sphere to ensure that collisions (in the most
part) are detected.
• When projected into consecutive
frames, the spheres should overlap.
• This ensures we cover the whole
(well nearly whole) scope of the
possible collision.
• We check if the distance between the two centres of the
spheres is less than the sum of the radii.
• However, while the calculations are simple, the results can look
poor on screen (collision events may occur when the user
actually views no collision).
More precise detection

When entities are an irregular shape, a
number of spheres may be used.
• In this diagram we use three spheres for greater
accuracy.
• Geometry in games may be better suited to
bounding boxes (not circles).
• To ease calculations, bounding boxes are
commonly axis aligned (irrelevant of entity
transformations they are still aligned to X, Y and
Z coordinates in 3D) These are commonly called
AABBs (Axis Aligned Bounding Boxes).
Recursive testing of bounding boxes

We can build up a recursive hierarchy of bounding
boxes to determine quite accurate collision
detection.
• Here we use a sphere to test for course grain intersection.
• If we detect intersection of the sphere, we test the two sub
bounding boxes.
• The lower bounding box is further reduced to two more
bounding boxes to detect collision of the cylinders.
Tree structure used to model collision
detection
B
A
A
D
B
C
E

C
D
E
A recursive algorithm can be used to parse the tree structure
for detecting collisions.

If a collision is detected and leaf nodes are not null then traverse the leaf
nodes.

If a collision is detected and the leaf nodes are null then collision has
occurred at the current node in the structure.

If no collision is detected at all nodes where leaf nodes are null then no
collision has occurred (in our diagram B, D or E must record collision).
Speed over accuracy



The approach which offers most speed would be to have
AABBs of a size fixed at entity initialization time.
 That is, irrelevant of entity transformation the
associated AABB does not change in size or shape.
This is cumbersome for entities shaped like cylinders.
 Plenty of “free space” will exist around the cylinder.
For more realistic collision detection the bounding box
may fit closely to the entity and rotate along with
associated entity.
 This requires the bounding box to be recomputed
every time an entity is rotated.
NeHe Collision example
http://nehe.gamedev.net/data/lessons/lesson.asp?
lesson=30