Culling problem

[Ventus]

Hello, I've been trying to implement a culling algorithm in my game, but instead of only calling draw() when the tiles are in view, it draws everything untill the camera starts moving (side-scroller camera). After that, it just stops drawing everything.

Here's my best attempt so far:

        sf::View cam = target.getView();
    sf::FloatRect screenRect(sf::Vector2f(
                cam.getCenter().x - (cam.getSize().x/2.f),
                cam.getCenter().y - (cam.getSize().y/2.f)),
                cam.getSize());

        for (int i = 0; i < m_map.size(); i++)
        {
                for (int j = 0; j < m_map[i].size(); j++)
                {
                        if (m_map[i][j].x != -1 && m_map[i][j].y != -1 && screenRect.intersects(sf::FloatRect(m_map[i][j].x * 32, m_map[i][j].y * 32, 32, 32)))
                        {
                                m_tilesprite.setPosition(j * tileSize, i * tileSize);
                                m_tilesprite.setTextureRect(sf::IntRect(m_map[i][j].x * tileSize, m_map[i][j].y * tileSize, tileSize, tileSize));
                                target.draw(m_tilesprite);
                        }
                }
        }

m_map is a 2d vector of sf::Vector2i that contains coordinates for tiles in the current level.

What am I doing wrong?

[Hapax]

Do you call the provided code only after the camera has moved (or after an event has occurred)

When is it called?

Are you setting all values of m_map prior to this code being called?

Are you drawing them anywhere else in your code?

What is m_tilesprite?

More information is needed to solve this problem and you are the only one with that information. You will need to either provide the information or solve it yourself. Providing a minimal and complete example would certainly help answering your question more quickly.


Also, sf::Vectors can be used in arithmetic.
For example:

sf::FloatRect screenRect(sf::Vector2f(
        cam.getCenter().x - (cam.getSize().x/2.f),
        cam.getCenter().y - (cam.getSize().y/2.f)),
        cam.getSize());

can be simply rewritten as:

sf::FloatRect screenRect(cam.getCenter() - (cam.getSize() / 2.f), cam.getSize());

[Ventus]

Thanks for the reply. I'll address all of your questions in order:

• This code is called after the camera movement has been processed.
• The call is made after clearing the screen and before drawing the player sprite.
• No, the code from the previous post is only called once each frame.
• m_tilesprite is a sf::Sprite that represents the tiles, defined by what the current tile to draw is.

Here's the main function:

#include <SFML/Graphics.hpp>
#include "Player.hpp"
#include "WorldMap.hpp"

int main()
{
        sf::RenderWindow wnd(sf::VideoMode(1280, 720), "Test");
       
        sf::View cam(wnd.getDefaultView());

        WorldMap map;
        map.loadMap("resources\\maps\\map.txt");

        Player player(200.f);
        player.setPosition(1280.f / 4.f, 720.f/ 2.f);

        while (wnd.isOpen())
        {
                if (sf::Keyboard::isKeyPressed(sf::Keyboard::A) && !sf::Keyboard::isKeyPressed(sf::Keyboard::D))
                        player.run(Player::direction::left);

                if (sf::Keyboard::isKeyPressed(sf::Keyboard::D) && !sf::Keyboard::isKeyPressed(sf::Keyboard::A))
                        player.run(Player::direction::right);

                if (player.getPosition().x + player.rect.getSize().x > screenDimensions.x / 2)
                {
                        if (player.getRight())
                                cam.setCenter(player.getPosition().x + (player.rect.getSize().x / 2), player.getPosition().y);
                        else
                                cam.setCenter(player.getPosition().x - (player.rect.getSize().x / 2), player.getPosition().y);
                        wnd.setView(cam);
                }

                wnd.clear();
                map.Draw(wnd); //this is the call to what i originally posted.
                wnd.draw(player.sprite);
                wnd.display();
        }
        return 0;
}

Here's a cleaner version of the Draw call:

    sf::View cam = target.getView();
        sf::FloatRect screenRect(cam.getCenter() - (cam.getSize() / 2.f), cam.getSize());

    for (int i = 0; i < m_map.size(); i++)
    {
        for (int j = 0; j < m_map[i].size(); j++)
        {
            if (m_map[i][j].x != -1 && m_map[i][j].y != -1 && screenRect.intersects(sf::FloatRect(m_map[i][j].x * tileSize, m_map[i][j].y * tileSize, tileSize, tileSize)))
            {
                m_tilesprite.setPosition(j * tileSize, i * tileSize);
                m_tilesprite.setTextureRect(sf::IntRect(m_map[i][j].x * tileSize, m_map[i][j].y * tileSize, tileSize, tileSize));
                target.draw(m_tilesprite);
            }
        }
    }

tileSize is 32.

And here's the loadMap function:

void WorldMap::loadMap(const char* filename)
{
        std::ifstream file(filename);
        m_tempmap.clear();
        m_map.clear();

        if (file.is_open())
        {
                std::string tileLocation;
                file >> tileLocation;
                m_tiletexture.loadFromFile(tileLocation);
                m_tilesprite.setOrigin(sf::Vector2f(0.f, 0.f));
                m_tilesprite.setTexture(m_tiletexture);
                while (!file.eof())
                {
                        std::string str, value;
                        std::getline(file, str);
                        std::stringstream stream(str);
                        while (std::getline(stream, value, ' '))
                        {
                                if (value.length() > 0)
                                {
                                        std::string xx = value.substr(0, value.find(','));
                                        std::string yy = value.substr(value.find(',') + 1);

                                        int x, y, i, j;

                                        for (i = 0; i < xx.length(); i++)
                                        {
                                                if (!isdigit(xx[i]))
                                                        break;
                                        }
                                        for (j = 0; j < yy.length(); j++)
                                        {
                                                if (!isdigit(yy[j]))
                                                        break;
                                        }

                                        x = (i == xx.length()) ? atoi(xx.c_str()) : -1;
                                        y = (j == yy.length()) ? atoi(yy.c_str()) : -1;
                                       
                                        m_tempmap.push_back(sf::Vector2i(x, y));
                                }
                        }
                        m_map.push_back(m_tempmap);
                        m_tempmap.clear();
                }
        }
}

m_tempmap is a vector of sf::Vector2i, used to be pushed into m_map.

I'm running on 64-bit Windows 7 OS, compiling with Visual Studio Community 2013 and SFML version is the latest, 2.3.2.

Sorry for the long post. 

[Hapax]

Unfortunately, since this code is not compilable, I cannot run it myself.
Have you output the values of the map data after loading? Confirm that there are no unexpected values. Just a single -1 can err.
As mentioned before, if you could post a complete and minimal example, others would be able to compile and test it for you.

(click to show/hide)

m_tempmap is a vector of sf::Vector2i, used to be pushed into m_map.

It's often thought to be better to use a single-dimensional array/vector as opposed to a multi-dimensional one.
In the case of tile data, a single dimension would hold row after row. To access the specific two dimensional storage, multiplication (*) and modulus (%) is used. The SFML Tile Map Example shows this concept in use.
One advantage of this approach would be that you would no longer find need of a temporary vector.

map.loadMap("resources\\maps\\map.txt");

There is no reason to be having escaped slashes in paths.
Use forwards slashes instead as they don't need escaping and work across platforms (yes, even Windows!)

map.loadMap("resources/maps/map.txt");

It looks much nicer, doesn't it? 

map.Draw(wnd);
wnd.draw(player.sprite);

Although this suggestion isn't strictly necessary, it can tidy up the drawing code:
You can inherit Map and Player from sf::Drawable and then define the virtual draw function to draw it to the target (window).
In Player's case, the draw function would simply be "target.draw(sprite);" but the Map's draw function would be pretty much your current draw function.
See here for information about inheriting from sf::Drawable.

while (!file.eof())

There are problems with using this loop condition.
Just googling "eof bad" brought up a number of explanations.
From the first result that I got (at http://stackoverflow.com/questions/5837639/eof-bad-practice):

You can use eof to test for the exact condition it reports - whether you have attempted to read past end of file. You cannot use it to test whether there's more input to read, or whether reading succeeded, which are more common tests.

So, use it with if, not with while.

[Ventus]

So i did my best to create a complete and minimal example, here's the code:

#include <SFML/Graphics.hpp>

int main()
{
        sf::Vector2i screenDimensions(1280, 720);
        sf::RenderWindow wnd(sf::VideoMode(screenDimensions.x, screenDimensions.y), L"Test");
        sf::View cam(wnd.getDefaultView());
        wnd.setView(cam);

        const int level[8][16] =
        {
                { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
        };

        wnd.setFramerateLimit(60);

        // Create clock to measure frame time
        sf::Clock frameClock;

        wnd.setKeyRepeatEnabled(false);

        sf::RectangleShape shape(sf::Vector2f(10.f, 10.f));
        shape.setPosition(screenDimensions.x / 4.f, screenDimensions.y / 2.f);
        sf::Vector2f movement(0.f, 0.f);
        float speed = 200.f;

        while (wnd.isOpen())
        {
                sf::Event event;
                while (wnd.pollEvent(event))
                {
                        switch (event.type)
                        {
                        case sf::Event::Closed:
                                wnd.close();
                                break;
                        case sf::Event::KeyPressed:
                                if (event.key.code == sf::Keyboard::I)
                                        wnd.setFramerateLimit(0);
                                else if (event.key.code == sf::Keyboard::O)
                                        wnd.setFramerateLimit(60);
                                break;
                        }
                }

                sf::Time frameTime = frameClock.restart();

                if (sf::Keyboard::isKeyPressed(sf::Keyboard::F))
                        shape.setPosition(screenDimensions.x / 4.f, screenDimensions.y / 2.f);

                if (sf::Keyboard::isKeyPressed(sf::Keyboard::A) && !sf::Keyboard::isKeyPressed(sf::Keyboard::D))
                {
                        movement.x -= speed;
                        shape.move(movement * frameTime.asSeconds());
                        movement = sf::Vector2f(0.f, 0.f);
                }

                if (sf::Keyboard::isKeyPressed(sf::Keyboard::D) && !sf::Keyboard::isKeyPressed(sf::Keyboard::A))
                {
                        movement.x += speed;
                        shape.move(movement * frameTime.asSeconds());
                        movement = sf::Vector2f(0.f, 0.f);
                }

                if (shape.getPosition().x + shape.getSize().x > screenDimensions.x / 2)
                {
                        cam.setCenter(shape.getPosition().x + (shape.getSize().x / 2), shape.getPosition().y);
                        wnd.setView(cam);
                }

                wnd.clear();
                sf::View veiw = wnd.getView();
                sf::FloatRect screenRect(veiw.getCenter() - (veiw.getSize() / 2.f),
                        veiw.getSize());

                for (int i = 0; i < 8; i++)
                {
                        for (int j = 0; j < 16; j++)
                        {
                                if (screenRect.intersects(sf::FloatRect(level[i][j] * 32, level[i][j] * 32, 32, 32)))
                                {
                                        sf::RectangleShape rect(sf::Vector2f(32.f, 32.f));
                                        rect.setPosition(j * 32, i * 32);
                                        wnd.draw(rect);
                                }
                        }
                }
                wnd.draw(shape);
                wnd.display();
        }
        return 0;
}

Sorry for taking so long to reply.

On a side note, i'm now compiling with Visual Studio 2015.

[Hapax]

complete and minimal example

When you post a complete and minimal example, it would help if you also stated what you expect it to do and what it actually does (for you).

This is what I get (cropped):

but I have no idea if this is what you want.

[Ventus]

As I said on my first post, when you move the square past the middle of the screen, things stop being drawn.
Basically, when the camera moves the tiles "mess up" and even though they don't appear, the window is losing some framerate (in my test it goes around 500 frames lost per second in a decent map (not too big, not too small).

The game should avoid drawing things that do not intersect with the screen rectangle, so the current behavior is not desired.

As you might have noticed, the square can be moved by pressing A or D.

[Ventus]

Seems i've made a mistake.

in line 87, i forgot to add a condition, should look like this:

if (level[i][j] == 1 && screenRect.intersects(sf::FloatRect(level[i][j] * 32, level[i][j] * 32, 32, 32)))

[Hapax]

if (level[i][j] == 1 && screenRect.intersects(sf::FloatRect(level[i][j] * 32, level[i][j] * 32, 32, 32)))

Actually, that line is the error!
The FloatRect that you are creating should not start at the definition of the level (the contents of level[j]) but the position of that tile. Try this:

if (level[i][j] == 1 && screenRect.intersects(sf::FloatRect(j * 32, i * 32, 32, 32)))

[Ventus]

Oh, you're right! Thanks 
But there's still a little bit of a problem... I think the culling is not working, the framerate is still considerably low...
Maybe considering the map size, a large map could reduce the framerate in those for loops? Or am I missing something here?

(This might be a bit off topic but I was considering using the SFML tutorial tilemap class as a base to use vertex arrays in this,  but I don't know if/how I could implement it and still do collision tests on the map)

EDIT: I made a mistake again, the culling is working, the rate was just my impression.

[Hapax]

Oh, you're right! Thanks 

You are welcome! 

This might be a bit off topic but I was considering using the SFML tutorial tilemap class as a base to use vertex arrays in this,  but I don't know if/how I could implement it and still do collision tests on the map

My suggestion would be to use the Tile Map to represent what is being drawn to the screen and update their values depending on the current "camera" position on the entire "level" data. Then, you could still use your actual level data for determining what "type" of tile is at any position so you can use that for collisions etc..

I used a tile map in this way in my entry for the SFML game jam 4, called Bring It Back. It should be quite simple to have a look through. Although, I'd do some things differently now (and if I had more time), it's likely that I'd still use the same level-data-and-tile-map-concept that was used there.

[Ventus]

My suggestion would be to use the Tile Map to represent what is being drawn to the screen and update their values depending on the current "camera" position on the entire "level" data. Then, you could still use your actual level data for determining what "type" of tile is at any position so you can use that for collisions etc..

I used a tile map in this way in my entry for the SFML game jam 4, called Bring It Back. It should be quite simple to have a look through. Although, I'd do some things differently now (and if I had more time), it's likely that I'd still use the same level-data-and-tile-map-concept that was used there.

The same project of the method getLost()? 

Anyway, I think I got what you meant... Store the map data as usual and do collisions normally, and then just
use the vertex array to draw, right?

[Hapax]

The same project of the method getLost()? 

Totally accidentally named, I swear! I wish I'd done it on purpose 

Anyway, I think I got what you meant... Store the map data as usual and do collisions normally, and then just
use the vertex array to draw, right?

That's right, where the vertex array is updated from a selected range of the map data.

[Ventus]

I think I got the hang of this, just one question: Is culling combined with the vertex array unecessary? I think it could potentially become a problem with really really big maps if it draws everything, but I could be wrong so...

Btw, thanks for all the help 

[Hapax]

If you're using a vertex array/tile map that only displays a select number of tiles (which would be selected from within the view's range) from the map data, that would be the culling.
Displaying the entire map data - even the parts that are offscreen, however, would not be the best thing to do.