Help with performance, Object Collision with Walls in a player class

[Ganado]

Before you read anything, note that this probably isn't what you'd call a "complete and minimal example" (at least, not the second spoiler of code, although both aren't terribly long), so if you don't feel like trying to figure out why my performance is horrible, please don't waste your time for me, I understand!

This is the Object Collision I've been working on.

• mPlayer is an sf::RectangleShape
• mWalls is an std::vector<sf::RectangleShape>

This may look long, but it is an example is for a very basic case:
The player is a direct member of the game class.
The walls are direct members of the game class.
This handles top-down, 8-directional movement.
For both x-axis movment and y-axis movement, if it is colliding with a wall, it finds how far the Player is into the wall, and moves it back by that difference amount.

(click to show/hide)

/**
 * Handles moving the player,
 * and Player-Wall object collision.
 */
void Game::updatePlayer(sf::Time deltaTime)
{
    sf::Vector2f movement(0.f, 0.f);
    float difference = 0.0f;

    /////////////////////////
    ///  X-Axis Movement  ///
    /////////////////////////
        if (mIsMovingLeft)
            movement.x -= PlayerSpeed;
        if (mIsMovingRight)
            movement.x += PlayerSpeed;
    mPlayer.move(movement.x * deltaTime.asSeconds(), 0);
    sf::FloatRect currPlayerRect = mPlayer.getGlobalBounds();

    /// X-Axis Player-Wall Collision ///
    for (int i = 0; i < mWalls.size(); i++)
    {
        if (mPlayer.getGlobalBounds().intersects(mWalls[i].getGlobalBounds()))
        {
            if (mIsMovingLeft)
            {
                difference = mWalls[i].getGlobalBounds().left
                             + mWalls[i].getGlobalBounds().width
                             - currPlayerRect.left;
                mPlayer.move(difference, 0);
            }
            else if (mIsMovingRight)
            {
                difference = currPlayerRect.left + currPlayerRect.width
                            - mWalls[i].getGlobalBounds().left;
                mPlayer.move(-difference, 0);
            }
        }
    }

    /////////////////////////
    ///  Y-Axis Movement  ///
    /////////////////////////
        if (mIsMovingUp)
            movement.y -= PlayerSpeed;
        if (mIsMovingDown)
            movement.y += PlayerSpeed;
    mPlayer.move(0, movement.y * deltaTime.asSeconds());
    currPlayerRect = mPlayer.getGlobalBounds();

    /// Y-Axis Player-Wall Collision ///
    for (int i = 0; i < mWalls.size(); i++)
    {
        if (mPlayer.getGlobalBounds().intersects(mWalls[i].getGlobalBounds()))
        {
            if (mIsMovingUp)
            {
                difference = mWalls[i].getGlobalBounds().top
                             + mWalls[i].getGlobalBounds().height
                             - currPlayerRect.top;
                mPlayer.move(0, difference);
            }
            else if (mIsMovingDown)
            {
                difference = currPlayerRect.top + currPlayerRect.height
                             - mWalls[i].getGlobalBounds().top;
                mPlayer.move(0, -difference);
            }
        }
    }
}

The X- and Y-Axis movements are separated to allow for sliding. I'm not sure if there's a better way to do this, but that isn't really the problem right now.

Basically, the above code works great. It seems to be handle 10,000 sf::RectangleShape objects (the walls) just fine (the problem with 10000 rectangles is drawing them all, but that's unrelated, and was just a performance test).

HOWEVER, when I tried to "apply" this code to a more complicated project, the performance is unbearable against even a not-so-high number of walls (I believe around 40 or 80 rectangles).

(click to show/hide)

// game.cpp
void Game::update(sf::Time deltaTime)
{
    //Player movement:
    mPlayer.update(deltaTime, *this);

// player.cpp
void Player::update(sf::Time deltaTime, const Game &game)
{
    sf::Vector2f movement(0.f, 0.f);
    float difference = 0.0f;

    int currentRoom = game.getCurrentRoom();

    /////////////////////////
    ///  X-Axis Movement  ///
    /////////////////////////
        if (mIsMovingLeft)
            movement.x -= Speed;
        if (mIsMovingRight)
            movement.x += Speed;
    mBody.move(movement.x * deltaTime.asSeconds(), 0);


    /// X-Axis Player-Wall Collision ///
   
    sf::FloatRect currPlayerRect = mBody.getGlobalBounds();
    for (unsigned int i = 0; i < game.getRooms()[currentRoom].getInnerWalls().size(); i++)
    {
        if (mBody.getGlobalBounds().intersects(game.getRooms()[currentRoom].getInnerWalls()[i].getGlobalBounds()))
        {
            if (mIsMovingLeft)
            {
                difference = game.getRooms()[currentRoom].getInnerWalls()[i].getGlobalBounds().left
                             + game.getRooms()[currentRoom].getInnerWalls()[i].getGlobalBounds().width
                             - currPlayerRect.left;
                mBody.move(difference, 0);
            }
            else if (mIsMovingRight)
            {
                difference = currPlayerRect.left + currPlayerRect.width
                            - game.getRooms()[currentRoom].getInnerWalls()[i].getGlobalBounds().left;
                mBody.move(-difference, 0);
            }
        }
    }


    /////////////////////////
    ///  Y-Axis Movement  ///
    /////////////////////////
        if (mIsMovingUp)
            movement.y -= Speed;
        if (mIsMovingDown)
            movement.y += Speed;
    mBody.move(0, movement.y * deltaTime.asSeconds());

   
    /// Y-Axis Player-Wall Collision ///
    currPlayerRect = mBody.getGlobalBounds();
    for (unsigned int i = 0; i < game.getRooms()[currentRoom].getInnerWalls().size(); i++)
    {
        if (mBody.getGlobalBounds().intersects(game.getRooms()[currentRoom].getInnerWalls()[i].getGlobalBounds()))
        {
            if (mIsMovingUp)
            {
                difference = game.getRooms()[currentRoom].getInnerWalls()[i].getGlobalBounds().top
                             + game.getRooms()[currentRoom].getInnerWalls()[i].getGlobalBounds().height
                             - currPlayerRect.top;
                mBody.move(0, difference);
            }
            else if (mIsMovingDown)
            {
                difference = currPlayerRect.top + currPlayerRect.height
                             - game.getRooms()[currentRoom].getInnerWalls()[i].getGlobalBounds().top;
                mBody.move(0, -difference);
            }
        }
    }
}
 

I am sure that it's the Object Collision part of the code that's causing the unplayable performance in the second block of code, it can handle the draw calls just fine when I comment out the X- and Y-collision segments. I understand that implementing a Quad-tree or something would increase performance, but the problem here is definitely something that should be fixed at its source instead of trying to cut around, especially with so little walls.

Anyway, so, if you have the time, please look through and compare the two blocks of code I have. I can see why the second block of code is more complicated, but the performance hit is unbearable, and I don't understand why this disparity exists!



EDIT:

Okay, so I've been tinkering with it some more, and so far it seems to be that the accessor "getter" methods that are causing the most problems.
doing this:

    int num_walls = game.getRooms()[currentRoom].getInnerWalls().size();
    for (unsigned int i = 0; i < num_walls; i++)
    { /*commented out code*/}

compared to this:

   for (unsigned int i = 0; i < game.getRooms()[currentRoom].getInnerWalls().size(); i++)
   { /*commented out code*/}

seems to give a huge performance boost right off the bat...

my get___() methods are currently returning the member itself, nothing special.
ex:

std::vector<sf::RectangleShape> Game::getRooms()
{
    return mRooms;
}

Would returning a reference instead really save that much performance? Sorry if that's more of a C++ question than an SFML one...

[eXpl0it3r]

The problem with the code is not the length, but the complexity. In order to understand just half of what's there, you'll have to go over everything many times.

Anyways as far as performance goes, just run a profiler and will instantly tell you, where the bottleneck is, though it seems you have found it yourself.
Personally, I'd never use such a complex function calling mess. If you're always working with the "current room" then just save a reference to it, there's no need to constantly retrieve the vector and access it. Temporary variables shouldn't be overused, but also not underused. If it helps making the code more readable, you won't really lose anything, the compiler is quite good at optimizing things.

If you just return the vector, you're always making a fully copy of the vector, meaning you have to allocate new memory (and release it at some point again). With increasing size of the vector, this will take longer and longer and besides that, you're probably not even interested in having a copy of the data. If you don't manipulate the data in the vector, then just return a const reference.

[Ganado]

Thanks for reading,
at the beginning of the Player::update() function, I added this local variable

std::vector<sf::RectangleShape> inner_walls_copy = game.getRooms()[game.getCurrentRoom()].getInnerWalls();

It isn't a const reference, I should be able to change that later, but I understand.
Is there ever a danger of returning a const reference for something like this?
Anyway,

    ...
    int num_walls = inner_walls_copy.size();
    for (unsigned int i = 0; i < num_walls; i++)
    //for (unsigned int i = 0; i < game.getRooms()[currentRoom].getInnerWalls().size(); i++)
    {
        if (mBody.getGlobalBounds().intersects(inner_walls_copy[i].getGlobalBounds()))
        {

            if (mIsMovingLeft)
            {
                difference = inner_walls_copy[i].getGlobalBounds().left
                             + inner_walls_copy[i].getGlobalBounds().width
                             - currPlayerRect.left;
                mBody.move(difference, 0);
            ...
    }
     ...

This code seems to now make the game run with any stuttering, even when in debug mode (which should be expected for such a simple simulation). Thanks a lot for the help! I think I need to think of a better way to structure my code maybe... at least I'm not making a copy of the game itself every update ;p


Edit: Upon further testing (increasing the number of walls to 1040), this one line, even if just called once per update cycle, causes a load of performance loss.

std::vector<sf::RectangleShape> inner_walls_copy = game.getRooms()[game.getCurrentRoom()].getInnerWalls();

So yeah I definitely need to make it start returning a const reference in Game::getRooms() and in Room::getInnerWalls(). Hopefully that will fix the problem..

[eXpl0it3r]

Is there ever a danger of returning a const reference for something like this?

Not sure what you refer to with 'like this', but generally speaking you should only ever return references, if you can assure that the referenced object stays alive longer than the reference itself.
If the object dies, while there's still a reference around, accessing that reference will lead to undefined behavior - most likely a crash.

Thanks a lot for the help! I think I need to think of a better way to structure my code maybe... at least I'm not making a copy of the game itself every update ;p

You're welcome and yeah I guess it could be worse.

[select_this]

Is there ever a danger of returning a const reference for something like this?

Only if the object that the reference refers to falls out of scope, which would make the reference invalid.

EDIT: eXpl0it3r beat me to it

[Ganado]

Yep, calling

game.getRooms()[game.getCurrentRoom()].getInnerWalls();

every update is what's causing the issues, I will make it a const reference for each vector accessor instead when I have time.