Loading presentation...

Present Remotely

Send the link below via email or IM


Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.


Mathematics in Angry Birds

No description

Christine Oh

on 3 December 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Mathematics in Angry Birds

Introduction Tasks in Video Game Development Designer
Level Designer
Sound Engineer
Tester Vectors Have a length and direction but no absolute position
Simplify many of the common tasks needed in writing a physics engine
Eliminate having to solve separate dimensions separately; coordinates represent fields
Basic operations: dot/vector product, scale, magnitude, normalization
ex) Dot product on Java: Newton's 2nd Law of Motion Velocity and Position Rigid Bodies Rotation Collision Detection Separating Axis Theorem Collision Response Win with Calculus Rate of Change F=MA
Force acts on object, object accelerates in direction of force
Force is the change of momentum in respect to the change in time
Momentum: P= MV
F=K x dP/dt
K=1 so F=dP/dt and use substitution:
F=m(dv/dt) + v(dm/dt)
Dv/dt= a because acceleration is derivative of velocity
F=m(dv/dt) and (dv/dt=a)
F=MA rigid body- non-deformable shape with mass, position, orientation, velocity and angular velocity
majority of objects found in everyday life
i.e: teapot, a shelf
Forces can also act on a non-static body.
Ex) ball is dropped from a height, gravity constantly accelerating it towards the ground.
Momentum= body's mass x velocity
two moving bodies collide, combined momentum is unchanged, although it will have been partially transferred from one to the other.velocities before and after the collision are related
instantaneous force is applied relative to the mass and velocity of the colliding objects
conservation of momentum Angry Birds is a video game franchise created by Finnish computer game developer Rovio Entertainment
First game was first released for Apple's iOS in December 2009
Over 12 million copies of the game have been purchased from Apple's App Store
Versions for other touchscreen-based smartphones, including the Android, Symbian and Windows Phone operating systems
Expanded to video game consoles and for PCs Reaction Without Rotation When two hard objects collide, the total momentum of the two objects doesn’t change
Coefficient of restitution models the elasticity of the collision
Coefficient of restitution of two colliding objects is a fractional value that describes the ratio of speeds after and before an impact, taken along the line of the impact
When COR = 1, then object collides elastically, while objects with COR < 1 collide inelastically Reaction with Rotation Have to count for the fact that two objects will bounce off of each other.
Point of the collision will determine the reaction mostly
n real life, we do not know if the objects will overlap the way they can in a computer simulation so people manually backtrack and correct their positions so they are touching but not overlapping
When the objects do collide and overlap, we want to know the “penetration depth” of one object into another
Goal is to find the point where it is involved in the collision
Using the information about the depth of the collision, generate a very large force acting on the 2 objects, or, use an impulse response by modifying the objects’ velocities. Collision Detection in the Physics Engine Collision Detection is probably the most complicated aspect of physics engine
Generally is an expensive operation and requires a lot of effort because a game might include hundreds of objects reacting to each other
The way the object collides could be affected by its ability to rotate while moving
As shapes become more complicated or object rotates as it moves, its collision detection unit becomes much trickier and harder
To deal with concave (harder) shapes, the engine breaks it up into bunch of convex (easier) shapes
If the object is a very fast moving object such as bullets, it’s possible that they’ll “hop” over their target and avoid collision detection altogether. This fix is called continuous collision detection Collision Detection
General Procedure Split the world up into sections via a grid or a quadtree (Or octree in 3D)
If two objects are in the same section of the grid, then use a simple collision routine to see if the objects are colliding. (AABB testing is popular for this scenario)
If you think the objects are colliding, use a more thorough algorithm to see if the objects are indeed colliding
If the object collides, find out how the object would react Testings AABB (Axis Aligned Bounding Box)- Use of Bounding volume of colliding objects to detect whether object has collided or not.
Bounding volume is easier to find than the actual volume because it’s a simpler geometry. When the volumes of different objects collide, then we can conclude that object has collided with another
GJK is commonly used for 3D collision detection.Gilbert-Johnson-Kerrthi distance algorithm is a method used to determine the minimum distance between the two convex sets. It uses the frames of the new one and the old one to detect the collision by looking at the object’s convergence. This algorithm’s stability, speed, and small storage make it popular for collision detection unit, greatly contributing to video games making.
Separating axis theorem is used for 2D collision detection. Looks from many different angles to see whether the gaps between the two objects collide or not. If the gap is closed when viewed from right angle, the object has collided with another. Position, Velocity, and Acceleration are related in calculus
Velocity is the derivative of position, acceleration is the derivative of velocity
Position is the integral of velocity, velocity is the integral of acceleration
Knowing one of the three will allow the programmer to get the other two, simply by deriving or integratinga(t)=v’(t)=s”(t) Euler’s method is used with specific step sizes to get the position, velocity, and/or acceleration at each frame
Video games usually run at 30-60 frames per second, so one frame every .0333-.0167 seconds
velocity=acceleration*time step
position=velocity*time step
The time step would be .0333-.0167 seconds depending on frame rate In Angry Birds, the slingshot provides the values for the initial vertical and horizontal velocities
Acceleration due to gravity is factored into the vertical velocity, as gravity eventually causes it to become negative
Horizontal velocity is constant (acceleration is zero)
Knowing velocity, position can be calculated at each frame by Euler’s method
The game indicates certain points of position with puffs of smoke, which is a visible representation of Euler’s method
Knowing position allows the game to show where the bird is at each frame, and can thus show the path of the bird and determine where the bird lands Rotation also deals with position, velocity, and acceleration, however instead it works with rotation angle, angular velocity, and angular acceleration
Newton’s Second Law of Motion is also applied in rotation
Force (F)=Torque (T)-force with the tendency to rotate an object
Mass (m)=moment of inertia (J)-tendency to resist change in motion
moment of inertia in rotation is also related to the distribution of mass in relation to the distance from the center, which can be modeled with triple integration
acceleration is unchanged
Thus, T=Ja
The relation between rotation angle, angular velocity, and angular acceleration can be used with derivatives/integrals and Euler’s method to determine how much an object rotates (the angle), how fast it rotates (velocity), and how fast its rotation velocity changes (acceleration)
Euler’s method is used in programming to find each of these values and display them on the screen In Angry Birds, rotation is used when a bird hits a block
The acceleration, velocity, and mass of the bird determine the force the bird applies on the block
This force and the distance from the center of mass determine the Torque (T) applied to the block
The block’s mass determines its moment of inertia (J)
With T and J, angular acceleration can be found since a=T/J
Then Euler’s method can be used to find the angular velocity and rotation angle of the block at each frame
Thus, the rotation of the block can be displayed accurately and realistically on the screen Separating Axis Theorem is used to write an algorithm for collision detection between two objects.
It only works with convex polygons
The basic theory is, if you can draw a line between two objects, without touching either, then the two objects are not colliding
When coding, projections, or shadows, of the objects are looked at. If there is no overlap of those projections onto the same axis, there is no collision As soon as a single overlap is found, the program can determine there is a collision and exit out of the algorithm
However, in order to be sure that there is no collision, a certain amount of axes must be tested with no overlap on any
The axes that must be tested are the normals of the edges of each polygon
In Angry Birds, Separating Axis Theorem is used to detect when a bird, pig, or block have collided and the game can then respond appropriately Works Cited http://sites.davidson.edu/mathmovement/algebra-of-angry-birds/
http://www.codezealot.org/archives/55 The yellow angry bird follows a parabolic trajectory path until you click, at which point the bird will accelerate quickly, following the tangent line of the graph. You want to hit the black dot on the building. Parabolic Equation Plot points on graphing calculator
Go to Stat-->Calc
Select Quad Reg and enter L1, L2
Should get:
y=-0.06x^2+2.38x Chipmunk Physics 2 types of physics engines: BOX2D and Chipmunk Physics
Chipmunk physics: 2D rigid body physics library
Chipmunk physics code
CpSpace- the physics world simulation container
CpBody- uses concepts of a body that has mass and a moment of inertia to determine how each body will react/ behave on forces
CpShape- uses concepts of shapes that are attached to the bodies to manage collision detection and body interaction
CpConstraint- concepts of constraints that are attached to the bodies to constrain how the bodies can move in relative to each other
CpFloat: double
CpVect: 2D Vector used to define the boundaries of a shape
CpCollisiontype: categorizes things that can collide with other things
Full transcript