Jump to content

  • Log In with Google      Sign In   
  • Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at $59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.


Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!






Arkanong part 2: basic collision detection

Posted by molehill mountaineer, 17 November 2013 · 504 views

c++ sfml collision detection
When I last posted about my SFML/C++ pong clone (now dubbed 'arkanong' because I suck at namegiving) I ended up with a non-moving paddle and ball. While that's all well and good the game won't be very exciting if we can't bounce the ball around, so that's exactly what I put in next.

Here's how it works:

in function Game::initialize()
sf::Clock timer;
    while(!IsExiting())
    {
	    Tick(timer.restart());
    }
When the game is loaded a clock object is made which will keep track of the amount of time that has passed since we last called Tick().

The Clock::restart function resets the clock and returns the elapsed time since the last time we called Clock::restart().

Tick() is the fuction that is responsable for updating the position of objects and drawing them. We will call tick() for every new frame that we draw to the screen - in other words: the clock is storing the amount of time that has passed since we drew the last frame.

You may be wondering why we pass the frame time to Tick() . Suppose we didn't supply this parameter and just moved the paddle by 3 pixels every time we draw a frame. Now we give the game to our friends Peter and Paul for playtesting.

Peter has a monster PC and runs the game at 70 frames per second

=> 70 Tick() calls per second

=> paddle moves at 70 * 3 pixels = 210 pixels per second

Paul's setup is more modest and runs the game at 30 frames per second

=> 30 Tick() calls per second

= paddle moves at 30 * 3 pixels = 90 pixels per second

If you've ever played an old DOS game on a modern PC and the game looked like it was being fast-forwarded this is what's going. The solution is to fix your timestep


in function Game::Tick(sf::Time& frameTime)
case IsRunning:
	    m_mainWindow.clear(sf::Color(0,0,0));
	    m_pObjectManager->updateAll(frameTime);
	    m_pObjectManager->drawAll(m_mainWindow);
	    m_mainWindow.display();
Tick doesn't really do anything special except check the gamestate and pass the frameTime to the objectManager.

The objectManager does exactly what is says on the tin: it manages game objects - updating, drawing & performing collision detection happens in this class.



Inside ObjectManager::updateAll(sf::Time& frameTime)
void ObjectManager::updateAll(sf::Time& frameTime)
{
    std::map<std::string, VisibleObject*>::const_iterator it = m_objects.begin();
    while(it != m_objects.end())
    {
	    
		    //perform collision checks
		    if(it->second->isInitialized())
		    {
			    if(it->second->getBoundingType() == VisibleObject::boundingType::Rectangle
				    ||it->second->getBoundingType() == VisibleObject::boundingType::Undeclared)
				    performRectToBorderCollisionChecks(it->second);

			    if(it->second->getBoundingType() == VisibleObject::boundingType::Circle)
				    performCircleToBorderCollisionChecks(it->second);

			    //update positions
			    float remainingTime = frameTime.asSeconds();
			    float timeStep = 0.00001;
			    while(remainingTime >= timeStep)
			    {
				    it->second->update(timeStep);
				    remainingTime -= timeStep;
			    }
	    
			    }
   
	    ++it;
    }
}
The ObjectManager is where most of the magic (or horror, depending on your point of view) happens.
First we retrieve the bounding type of the object we're updating. The bounding type is an enumeration for the type of collision detection we want to perform.
If we're talking about a rectangle (= paddle) we do rectToBorder detection, in case of circles it's circleToBorder. Right now we're only checking the borders of the window for collisions, later we'll implement circleToRect collision detection (for bouncing the ball off the paddle) and CircleToCircle detection
(for bouncing balls off each other).


The final step in the updateAll function is to change the position of the object we're updating.
We're consuming the frameTime in steps of 0.00001. For an in depth explanation of how this works
check out the link 'fix your timestep' I posted above.


function ObjectManager::performRectToBorderCollisionChecks(VisibleObject* object)
void ObjectManager::performRectToBorderCollisionChecks(VisibleObject* object)
{
    sf::Vector2f overshootCorrection;

    float halfWidth = object->getSprite().getLocalBounds().width / 2;
    float halfHeight = object->getSprite().getLocalBounds().height / 2;

    unsigned int windowRight = Game::getInstance()->getWindowDimensions().x;
    unsigned int windowTop = Game::getInstance()->getWindowDimensions().y;

    sf::Vector2f position = object->getSprite().getPosition();
    float leftSideX = position.x - halfWidth;
    float rightSideX = position.x + halfWidth;
    float topSideY = position.y + halfHeight;
    float bottomSideY = position.y - halfHeight;

    if(leftSideX <= 0) //we hit the left side
	    overshootCorrection.x = -1 * leftSideX; //reverse overshoot

    if(rightSideX >= windowRight) //we hit the right side
	    overshootCorrection.x = windowRight - rightSideX;

    if(topSideY >= windowTop) //we hit the top of the window
	    overshootCorrection.y = windowTop - topSideY;

    if(bottomSideY <= 0) //we hit the bottom of the window
	    overshootCorrection.y = -1 * bottomSideY;


    object->getSprite().move(overshootCorrection);
}
This is the simplest of the two collision detection algorithms.
"Overshoot" is the term I've chosen to label the amount by which the paddle has gone past the window.
We move the paddle back by that amount to ensure that it never goes past the edges.
If you're having trouble understanding this perhaps this illustration will help. (click to expand)

Attached Image
void ObjectManager::performCircleToBorderCollisionChecks(VisibleObject* object)
{
    //we're going to assume the radius of the circle is the width of the sprite
    float radius = object->getSprite().getLocalBounds().width / 2;
    float angle = ((GameBall*)object)->getAngle();
    sf::Vector2f position = object->getSprite().getPosition(); //get centre of circular object
    float margin = 0.5f; //pixel margin on collision detection
    radius += margin;

    sf::Vector2f overshootCorrection;

    unsigned int windowRight = Game::getInstance()->getWindowDimensions().x;
    unsigned int windowTop = Game::getInstance()->getWindowDimensions().y;
    float distanceToRight = windowRight - position.x;
    float distanceToBottom = windowTop - position.y;
    


    bool flipXDirection = false;
    bool flipYDirection = false;

    if(position.x < radius)  //distanceToLeft == position.x
    {
	    //we bounced on the left side
	    flipXDirection = true;
	    overshootCorrection.x += (radius - position.x);

    }
    if(distanceToRight < radius)
    {
	    //we bounced on the right side
	    flipXDirection = true;
	    overshootCorrection.x -= (radius - distanceToRight);
    }
    if(position.y < radius) // distanceToBottom == position.y
    {
	    //we bounced on the top
	    flipYDirection = true;
	    overshootCorrection.y += (radius - position.y);
    }
    if(distanceToBottom < radius)
    {
	    //we bounced on the bottom
	    flipYDirection = true;
	    overshootCorrection.y -= (radius - distanceToBottom);
    }
    
    //bounce ball off sides
    if(flipXDirection || flipYDirection)
    {
	    object->getSprite().move(overshootCorrection); //correct overshoot

	    //determine quadrant of the angle at which the ball is hitting the sides
	    bool q1 = angle <= 90;
	    bool q2 = (angle > 90) && (angle <= 180);
	    bool q3 = (angle > 180) && (angle <= 270);
	    bool q4 = (angle > 270) && (angle <= 360);


	    float newAngle = angle;
	    
	    if(flipXDirection)
	    {
		    if(q2 || q4)
			    newAngle -= 90.0f;
		    else
			    newAngle += 90.0f;
	    }
	    else //flip Y
	    {
		    if(q1 || q3)
			    newAngle -= 90.0f;
		    else
			    newAngle += 90.0f;
	    }

	    //limit degrees to range [0:360]
	    if(newAngle < 0.0f)
		    newAngle += 360.0f;

	    if(newAngle > 360.0f)
		    newAngle -= 360.0f;
	    


	    //we will assume all spherical objects are gameballs (for now)
	    ((GameBall*)object)->setAngle(newAngle);
	    
    }

}
Bouncing the ball off the sides is a bit more complex. Not only do we correct the overshoot, but we have to reverse the X or Y direction of the ball too.
Since we're storing the movement of the ball as an angle and speed this means adding or subtracting 90°. We can know which operation to perform based on the quadrant that the angle falls in. You can see the four quadrant illustrated below, it comes down to dividing the 360° into four slices.
Working with angles may seem needlessly complex (and it is for the current version of the game) but it will
come in handy once I start doing stuff like bouncing balls off each other.
Check out these illustrations if you want to get a better picture of what's going on.


Attached Image
Attached Image


The final thing I want to show you is the way the angles and speed are used to move the ball around.
sf::Vector2f GameBall::getVelocities() const
{
    sf::Vector2f result;
    double angleInRadians = m_angle * (3.1415926 / 180.0f); //converting degrees to radians


    //prevent rounding errors
	 angleInRadians *= pow(10, 5);
	 angleInRadians = ceil(angleInRadians);
	 angleInRadians /= pow(10, 5);


    //get x and y components of velocity
    result.x = m_speed * std::cos(angleInRadians);
    result.y = -1 * (m_speed * std::sin(angleInRadians)); //y grows downwards
    return result;
}
This code does the following things:
1) convert degrees to radians for use with std::cos and std::sin
2) raise the radian by power 5, round it and revert back to prevent floating point rounding errors
3) m_speed is the distance that the ball travels in pixels. This is easy to figure out if we're
moving down or right, since the movement vector would be (0, m_speed) and (m_speed,0) respectively.
But we're moving diagonally, therefore we need to figure out how many pixels x and y need to be in order for the distance of the vector to be equal to m_speed.
This is what cos and sin does - it calculates the ratio of m_speed we attribute to x and y. This comes down to trigonometry so brush up if this code seems weird to you (check out khan academy and udacity physics section - the links are in my previous post).
Note that y grows downwards, so if you want to go up you decrease the y coördinate. That's why I multiply with -1 to make sure the ball heads in the right direction.


You can find the project in its current state here. This will be subject to change as I add things so you might want to store a local copy. I'm always looking for cleaner code so if you have any suggestions I'd love to hear them.
Thanks for reading!




December 2014 »

S M T W T F S
 123456
78910111213
14151617181920
21222324 25 2627
28293031   
PARTNERS