2D Physics 101 - Pong
Recently a discussion on the SFML irc channel included a question about how to perform very simplistic collision detection in a game such as a clone of Pong or Breakout, where full blown physics simulations provided by libraries such as Box2D or Chipmunk were overkill, and the programmer themselves wanted to learn a bit about writing their own collision code. As I find this an interesting topic, and have implemented systems of my own on occasion, I decided I would share my take on the subject.
First I should note this is *very* simplistic. Pong and Breakout don't need an accurate physics simulation to be fun, so this post won't cover simulating force, mass, friction etc. The post assumes a single dynamic object (the ball) while all the rest of the objects are static and do not react to collisions. While the bat (or paddle) does move (because it is controlled by the player) it does not react to the impact of the ball, and is therefore considered static. The post will not consider any collision detection optimisations, and so will not scale well with a greater amount of objects. I will start with AABB (Axis Aligned Bounding Box) collisions as SFML provides some handy functions for these out of the box, before briefly touching on circle-circle collisions towards the end. When all is done hopefully I will have presented a diving board for developing a Pong or Breakout clone, as well as perhaps a good starting point for developing a more detailed physics simulation.
Basics of a Collision
To start let's break down what happens (or what we expect to happen) when the ball collides with a solid object. Firstly we need to detect if there's actually been a collision. Using SFML shape classes is handy here, as all SFML drawables have an AABB available via the the getGlobalBounds() function. This function returns an sf::FloatRect which itself has a function called intersects() that returns true if one rectangle intersects another. It also provides a useful feature allowing the overlapping areas to be returned as a new sf::FloatRect. It follows then, that all we need to do is test the AABB of the ball, obtained via getGlobalBounds(), against the global bounds of each of the static objects.
When a collision is found it needs to be handled, or resolved. Resolving a collision means that the ball is returned to a state where it is no longer colliding with a static object, and that its velocity is updated in an at least semi-realistic way. The first part of resolving a collision is to calculate the manifold. This contains, at the very least, a vector representing the collision normal, and a penetration value. The collision normal is a unit vector representing a direction from which the ball has collided with the solid object, perpendicular to the colliding face. As we are using AABBs there are only four faces, therefore only four directions which can be represented by the normal. This makes things easier to calculate further down the line. The penetration value is the amount by which the ball overlaps, or has penetrated, the solid object.
Once we have this information we can update the ball's position so that the two AABBs no longer overlap. This is simply done by moving the ball along the collision normal by the penetration amount. Secondly the ball's velocity needs to be updated so that it starts to move away from the solid object. We could just invert the ball's velocity, but this looks unnatural. Really the velocity should be reflected, much like light reflecting off of a surface. Our collision normal comes in handy again here, as we can use this to reflect the ball's velocity accurately.
Theory in Action
So how is this implemented? For this example we'll create a simple ball class which will handle everything outlined above. The solid objects will be a std::vector of sf::RectangleShapes, against each of which we can test the AABB of the ball. The ball class needs to be both drawable and transformable, so it inherits the sf::Drawable and sf::Transformable classes. It also implements the pure virtual draw() function of sf::Drawable, as outlined in the SFML tutorials. The ball needs to be updated once a frame with the elapsed time, so that it can be moved by a given velocity. The velocity is a combination of a normalised sf::Vector2f member variable which represents the current direction of the ball and a constant value, speed. Every update the ball is moved by m_velocity * m_speed * dt, where dt is the time elapsed since the last update. This on its own is enough to make the ball move at a constant speed and direction, and if you try this you'll notice the ball will continue in a straight line until it disappears off the screen.
Once the ball has moved we can then check each one of the static objects for a collision and then resolve it, using the method outlined above, if one is found. The ball class is constructed with a reference to the vector of solid objects, which is kept as a member of the class so we can easily read the shape data.
Earlier on I mentioned the sf::FloatRect::intersects() function, and the fact that it can be used to determine the overlapping area when two AABBs overlap, like so:
This overlap is useful in the manifold calculation because, depending on whether the width or height is greater, we can easily tell if the collision is happening in the X or Y axis. By subtracting the position of the static object from the ball's current position we also get a vector broadly representing the collision direction (remember we want to narrow this down to just one of the four AABB faces). Note that the origins of the static objects are set to their local centres, so that this works properly. These two values are then passed to the getManifold() function of the ball class.
From this the manifold calculation is pretty simple. If the width of the overlap is less that the height we are colliding in the X axis. If the x value of the broad collision normal is less than zero the ball is on the right of the static object, else it is on the left. The penetration is the width of the overlap. If the width is greater than the height of the overlap the calculation is the same, but performed on the Y axis instead. The calculated collision normal and penetration value can then all be packed neatly into an sf::Vector3f, where the z value is the penetration value, and then returned from the function.
The ball class's resolve() function takes the manifold and uses it to move the ball from its colliding position by moving it back along the normal by the penetration depth, and then reflects the ball's velocity about the collision normal. The reflection function can be seen in detail in the sample code.
Multiple Collision Types
This should be enough to have the ball bouncing merrily around the window. When looking at the code, however, you may have noticed that the manifold and resolve functions are separate when, strictly speaking, this needn't be so. On the other hand this post has only covered AABB collision - what if you want to collide circles together too? Well the theory behind that is basically the same, we just need a different method for calculating the manifold. In the second example I've added an alternate function for calculating the manifold of two circles. To detect if two circles are colliding, measure the distance between their centres. If it is smaller than the sum of the two circle's radii then we must have a collision. The penetration is the difference between the the summed radii and the current distance.
As a circle has no faces the collision normal is always a unit vector of the distance between the two centres. Plug these values into our manifold and the rest of the collision resolution remains the same.
Note that in the code I've used the lengths of the vectors squared - this is a square root optimisation which removes the unnecessary use of the square root function when comparing distances. The result of comparing squared distances will always be the same as comparing the root of the distances, and we only need to use the square root function when finding out the actual penetration if there is a collision. A third getManifold() function could also be created for AABB vs circle collisions quite easily from here - although I will leave that as an exercise for the reader.
Conclusion
That pretty much sums up what I wanted to cover in this post. As I stated earlier it is a very rudimentary look at the physics in games such as Pong or Breakout, and there are quite a few things which can be done if you want (and I encourage you to) to take this further. The method above does not take in to account if you wish to collide two dynamic objects together. At the very least the resolution of the penetration needs to be shared between the two colliding objects. This method does not account for the fact that in most cases you'll want to have at least some mass for your objects, so that when dynamic objects of different sizes collide they affect each other more realistically. The example code also won't scale very well - the small amount of static objects is fine as a demo, but in scenarios where many objects are involved I suggest some sort of spacial partitioning, such as a quad tree, to quickly cull any unnecessary testing in a broad phase pass. Below are a few links which I have found useful in the past, as well as links to the example source code.
Example 1
Example 2
Further reading:
Physics Engines for Dummies @ Wildbunny
Gamasutra pool hall physics
Writing your own physics engine
Wikipedia's quad tree entry
First I should note this is *very* simplistic. Pong and Breakout don't need an accurate physics simulation to be fun, so this post won't cover simulating force, mass, friction etc. The post assumes a single dynamic object (the ball) while all the rest of the objects are static and do not react to collisions. While the bat (or paddle) does move (because it is controlled by the player) it does not react to the impact of the ball, and is therefore considered static. The post will not consider any collision detection optimisations, and so will not scale well with a greater amount of objects. I will start with AABB (Axis Aligned Bounding Box) collisions as SFML provides some handy functions for these out of the box, before briefly touching on circle-circle collisions towards the end. When all is done hopefully I will have presented a diving board for developing a Pong or Breakout clone, as well as perhaps a good starting point for developing a more detailed physics simulation.
Basics of a Collision
To start let's break down what happens (or what we expect to happen) when the ball collides with a solid object. Firstly we need to detect if there's actually been a collision. Using SFML shape classes is handy here, as all SFML drawables have an AABB available via the the getGlobalBounds() function. This function returns an sf::FloatRect which itself has a function called intersects() that returns true if one rectangle intersects another. It also provides a useful feature allowing the overlapping areas to be returned as a new sf::FloatRect. It follows then, that all we need to do is test the AABB of the ball, obtained via getGlobalBounds(), against the global bounds of each of the static objects.
When a collision is found it needs to be handled, or resolved. Resolving a collision means that the ball is returned to a state where it is no longer colliding with a static object, and that its velocity is updated in an at least semi-realistic way. The first part of resolving a collision is to calculate the manifold. This contains, at the very least, a vector representing the collision normal, and a penetration value. The collision normal is a unit vector representing a direction from which the ball has collided with the solid object, perpendicular to the colliding face. As we are using AABBs there are only four faces, therefore only four directions which can be represented by the normal. This makes things easier to calculate further down the line. The penetration value is the amount by which the ball overlaps, or has penetrated, the solid object.
Once we have this information we can update the ball's position so that the two AABBs no longer overlap. This is simply done by moving the ball along the collision normal by the penetration amount. Secondly the ball's velocity needs to be updated so that it starts to move away from the solid object. We could just invert the ball's velocity, but this looks unnatural. Really the velocity should be reflected, much like light reflecting off of a surface. Our collision normal comes in handy again here, as we can use this to reflect the ball's velocity accurately.
Theory in Action
So how is this implemented? For this example we'll create a simple ball class which will handle everything outlined above. The solid objects will be a std::vector of sf::RectangleShapes, against each of which we can test the AABB of the ball. The ball class needs to be both drawable and transformable, so it inherits the sf::Drawable and sf::Transformable classes. It also implements the pure virtual draw() function of sf::Drawable, as outlined in the SFML tutorials. The ball needs to be updated once a frame with the elapsed time, so that it can be moved by a given velocity. The velocity is a combination of a normalised sf::Vector2f member variable which represents the current direction of the ball and a constant value, speed. Every update the ball is moved by m_velocity * m_speed * dt, where dt is the time elapsed since the last update. This on its own is enough to make the ball move at a constant speed and direction, and if you try this you'll notice the ball will continue in a straight line until it disappears off the screen.
Once the ball has moved we can then check each one of the static objects for a collision and then resolve it, using the method outlined above, if one is found. The ball class is constructed with a reference to the vector of solid objects, which is kept as a member of the class so we can easily read the shape data.
Earlier on I mentioned the sf::FloatRect::intersects() function, and the fact that it can be used to determine the overlapping area when two AABBs overlap, like so:
This overlap is useful in the manifold calculation because, depending on whether the width or height is greater, we can easily tell if the collision is happening in the X or Y axis. By subtracting the position of the static object from the ball's current position we also get a vector broadly representing the collision direction (remember we want to narrow this down to just one of the four AABB faces). Note that the origins of the static objects are set to their local centres, so that this works properly. These two values are then passed to the getManifold() function of the ball class.
From this the manifold calculation is pretty simple. If the width of the overlap is less that the height we are colliding in the X axis. If the x value of the broad collision normal is less than zero the ball is on the right of the static object, else it is on the left. The penetration is the width of the overlap. If the width is greater than the height of the overlap the calculation is the same, but performed on the Y axis instead. The calculated collision normal and penetration value can then all be packed neatly into an sf::Vector3f, where the z value is the penetration value, and then returned from the function.
The ball class's resolve() function takes the manifold and uses it to move the ball from its colliding position by moving it back along the normal by the penetration depth, and then reflects the ball's velocity about the collision normal. The reflection function can be seen in detail in the sample code.
Multiple Collision Types
This should be enough to have the ball bouncing merrily around the window. When looking at the code, however, you may have noticed that the manifold and resolve functions are separate when, strictly speaking, this needn't be so. On the other hand this post has only covered AABB collision - what if you want to collide circles together too? Well the theory behind that is basically the same, we just need a different method for calculating the manifold. In the second example I've added an alternate function for calculating the manifold of two circles. To detect if two circles are colliding, measure the distance between their centres. If it is smaller than the sum of the two circle's radii then we must have a collision. The penetration is the difference between the the summed radii and the current distance.
As a circle has no faces the collision normal is always a unit vector of the distance between the two centres. Plug these values into our manifold and the rest of the collision resolution remains the same.
Note that in the code I've used the lengths of the vectors squared - this is a square root optimisation which removes the unnecessary use of the square root function when comparing distances. The result of comparing squared distances will always be the same as comparing the root of the distances, and we only need to use the square root function when finding out the actual penetration if there is a collision. A third getManifold() function could also be created for AABB vs circle collisions quite easily from here - although I will leave that as an exercise for the reader.
Conclusion
That pretty much sums up what I wanted to cover in this post. As I stated earlier it is a very rudimentary look at the physics in games such as Pong or Breakout, and there are quite a few things which can be done if you want (and I encourage you to) to take this further. The method above does not take in to account if you wish to collide two dynamic objects together. At the very least the resolution of the penetration needs to be shared between the two colliding objects. This method does not account for the fact that in most cases you'll want to have at least some mass for your objects, so that when dynamic objects of different sizes collide they affect each other more realistically. The example code also won't scale very well - the small amount of static objects is fine as a demo, but in scenarios where many objects are involved I suggest some sort of spacial partitioning, such as a quad tree, to quickly cull any unnecessary testing in a broad phase pass. Below are a few links which I have found useful in the past, as well as links to the example source code.
Example 1
Example 2
Further reading:
Physics Engines for Dummies @ Wildbunny
Gamasutra pool hall physics
Writing your own physics engine
Wikipedia's quad tree entry
Comments
Post a Comment