Bug in loop (involving vectors)

Hello,

I think there's something wrong with the following loop (because the program crashes sometimes at the moment a bullet hits a block), but I can't figure out what:

    //check collision bullets and blocks
    for (int i=bullet.size()-1;i>=0;i--)
    {
        for (int j=rect.size()-1;j>=0;j--)
        {
            if (collision_block(bullet[i],j))
            {
                bullet.erase(bullet.begin()+i);
                rect.erase(rect.begin()+j);
                
                //play sound effect
                sound.effect(EXPLOSION);
                
            }
        }
    }

We have two vectors of rectangles (it's SDL); vector<SDL_Rect> bullet; and vector<SDL_Rect> rect;. When there is collision between a bullet and a block (an element of rect), both sould be removed. To check for collision, the function bool collision_block(SDL_Rect,int) is called, that checks for collision between a rectangle (first parameter) and a specific element of the rect-vector (second parameter). I don't think there's anything wrong with the function, but here it is:

bool Map::collision_block(SDL_Rect box,int i)
{
        //returnvalue;
        bool r = true;
        
        //calculate sizes
        int a_left  = box.x;
        int a_right = box.x + box.w;
        int a_up    = box.y;
        int a_down  = box.y + box.h;
        
        int b_left  = rect[i].x;
        int b_right = rect[i].x + rect[i].w;
        int b_up    = rect[i].y;
        int b_down  = rect[i].y + rect[i].h;
        
        //check collision
        if (a_left >= b_right)
        {
            r = false;
        }
        if (a_right <= b_left)
        {
            r = false;
        }
        if (a_up >= b_down)
        {
            r = false;
        }
        if (a_down <= b_up)
        {
            r = false;
        }
        
        //if r is still true, there's collision
        return r;
}

Can anyone tell me what's wrong here? Btw, the problem doesn't always appear, most of the time the program runs fine. Thanks for any help.

Last edited on

PanGalactic (1658)

Hi Orimis,

You need to break from the inner loop after you play your sound effect because the bullet that bullet[i] points to no longer exists. That's only going to crash if its the last bullet in the vector (the first bullet you iterate on), which is why it is intermittent. Even though you are not crashing in the other instances when your bullet hits, you are wasting time comparing bullets that have already been compared. (Because, if it isn't obvious, bullet[i] now points to a previously compared bullet.)

Why iterate using indexes rather than reverse iterators?

Why doesn't Map::collision_block accept two SDLRects?

Why is the SDL_Rect not passed as a const reference?

And why are your last three "if" statements not "else if" statements? You are wasting time with comparisons that are not needed once r == false.

And, to be a real nitpicker, your a_* and b_* variables should be const ints.

Regards,

PanGalactic

Oromis (80)

You need to break from the inner loop after you play your sound effect

Thanks, that solved my problem :)

Why iterate using indexes rather than reverse iterators?

Reverse iterators? I don't have that much experiences with vectors; what do you mean?

Why doesn't Map::collision_block accept two SDLRects?

There are only two possible cases of collision; between the player and a block or between a bullet and a block. So there is no need for two SDL_Rects. But I agree there is no reason why I should not do that, and it would make the code more flexible I guess (there is no reason to make it a member of map either)...

Why is the SDL_Rect not passed as a const reference?

I never use const references, why would that be better?

And why are your last three "if" statements not "else if" statements? You are wasting time with comparisons that are not needed once r == false.

Good point. Chanced.

your a_* and b_* variables should be const ints

I normally use const values for global values that doesn't chance, like frames per seconds etc. Why should I use constant values here? Does a const int take less memery as an int?

Thanks for the feedback and help :)

PanGalactic (1658)

Reverse iterators? I don't have that much experiences with vectors; what do you mean?

Iterators are the way to iterate over STL containers. Reverse iterators allow you to start at the end and go to the beginning.

for (vector<SDL_Rect>::iterator it = bullets.rbegin(); it != bullets.rend(); ++it)
{
    ...
}

It looks funny to iterate over containers with an index in C++.

I never use const references, why would that be better?

Lets explore what happens in your method.

bool Map::collision_block(SDL_Rect box,int i)
{
    ...
}

When collision_block() is called, the SDL_Rect object, which is passed by value, is copied into the box parameter. When calling a function frequently, the overhead of this copying can really add up. Passing by reference eliminates this overhead -- you just pass what amounts to a pointer. Making it a const reference just says that the object won't be modified by the method. You will find this a very common way to pass arguments to functions in C++.

Why should I use constant values here? Does a const int take less memery as an int?

It can prevent programming errors. If you have no intention of changing a variable once it is set, declare it const. That way, common mistakes such as "if (a = b)" when you meant "if (a == b)" are caught by the compiler.

Oromis (80)

Oke, thanks. That makes all sense. I had seen passing by reference before, and I already wondered why someone would do that. This explains it. And I'll use iterators from now on :)

Thanks for the help.

PanGalactic (1658)

BTW, the code above for reverse_iterator should read:

for (vector<SDL_Rect>::reverse_iterator it = bullets.rbegin(); it != bullets.rend(); ++it)
{
    ...
}

Oromis (80)

Thanks, I already figured that out :) More difficult to find was how to erase an element using a reverse iterator... Could you check or the following loop is right? It does work, but maybe there are things that can be done better. The &(*i) for example looked very strange to me, but it was the only way it would compile.

//check collision bullets and blocks
    for (vector<SDL_Rect>::reverse_iterator i = bullet.rbegin(); i<bullet.rend(); i++)
    {
        for (vector<SDL_Rect>::reverse_iterator j = rect.rbegin(); j<rect.rend(); j++)
        {
            if (check_collision(&(*i),&(*j)))
            {
                bullet.erase((++i).base());
                rect.erase((++j).base());
                
                //play sound effect
                sound.effect(EXPLOSION);
                
                break;
                
            }
        }
    }

PanGalactic (1658)

I assume your check_collision() function declaration looks like:

bool check_collision(const SDL_Rect& a, const SDL_Rect& b);

If so, then you should just need to call it with:

check_collision(*i, *j);

The way your code is written it looks like your check_collision() takes pointers rather than references.

Now, for you other issue -- you are running into iterator invalidation. On thing that will help is to use algorithms. Actually, many time when you have a for loop, an algorithm will do the trick.

Here's a way aound the problem:

#include <algorithm>

// a predicate functor
struct Collision
{
    const SDL_Rect& a;

    Collision(const SDL_Rect& a) : a(a) {}

    bool operator()(const SDL_Rect& b)
    {
        // Your check collision code.
    }
};

typedef std::vector<SDL_Rect> Rects;
...

    //check collision bullets and blocks
    Rects::reverse_iterator i = bullet.rbegin();
    while (i != bullet.rend())
    {
        Rects::iterator j =
            std::find_if(rect.begin(), rect.end(), Collision(*i));
        if (j != rect.end())
        {
            rect.erase(j);
            i = bullet.erase(i);
            //play sound effect
            sound.effect(EXPLOSION);
        }
        else
        {
            ++i;
        }
    }

Note that erase() returns a valid iterator pointing to the next element.

One thing to note is to never use ">" or "<" with an iterateror. Use "!=". Always. It works with vectors, but that's the only container it will work with.

If it is impossible for a bullet to intersect with multiple rectangles, you can use "remove_if() instead of "find_if()" and "rect.erase()".

Last edited on

Oromis (80)

This is harder as I hoped it would be. I really appriciate your help.

You're right about the check_collision() function, I chanced it.

Note that erase() returns a valid iterator pointing to the next element.

Wouldn't this take the need for reverse iteration away? I tried the following loop, and now the program crashes when there's collision:

    //check collision bullets and blocks
    for (vector<SDL_Rect>::iterator i = bullet.begin(); i != bullet.end(); i++)
    {
        for (vector<SDL_Rect>::iterator j = rect.begin(); j != rect.end(); j++)
        {
            if (check_collision(*i,*j))
            {
                i = bullet.erase(i);
                rect.erase(j);
                
                //play sound effect
                sound.effect(EXPLOSION);
                
                break;
                
            }
        }
    }

Everything goes fine, until the last bullet on the screen hits something. I guess the problem is that the iterator is set one position after rect.end(), and so it != rect.end() returns true and the program gets into a infinite loop.

In another loop where I go through all blocks to move them, there's a new problem. The distance between the blocks is chancing, while all blocks sould move the same distance. This is the loop:

    if (!cheat)
    {
        //move all blocks
        for (vector<SDL_Rect>::iterator it = rect.begin(); it != rect.end(); it++)
        {
            it->y-=PPM;
            //check or block is still inside the screen
            if (it->y + it->h < 0)
            {
                //remove block if not
                it = rect.erase(it);
            }
        }
    }

The exact same construction for bullets works fine. PPM is a constant global values (Pixels Per Movement).

Oromis (80)

I solved it using a construction similar to your example (don't automaticly upgrade the iterator in the for-loop):

//move all blocks
        for (vector<SDL_Rect>::iterator it = rect.begin(); it != rect.end();)
        {
            it->y-=PPM;
            //check or block is still inside the screen
            if (it->y + it->h < 0)
            {
                //remove block if not
                it = rect.erase(it);
            }
            else
            {
                it++;
            }
        }

//...

 //move all bullets
    for (vector<SDL_Rect>::iterator it = bullet.begin(); it != bullet.end();)
    {
        it->y+=PPM;
        //check or bullet is still inside the screen
        if (it->y > screen->clip_rect.h)
        {
            //remove bullet if not
            it = bullet.erase(it);
        }
        else
        {
            it++;
        }
    }
    
    //check collision bullets and blocks
    for (vector<SDL_Rect>::iterator i = bullet.begin(); i != bullet.end();)
    {
        //i needs to be set; true
        bool set_i = true;
        
        for (vector<SDL_Rect>::iterator j = rect.begin(); j != rect.end(); j++)
        {
            if (check_collision(*i,*j))
            {
                i = bullet.erase(i);
                set_i = false; //i is set
                rect.erase(j);
                
                //play sound effect
                sound.effect(EXPLOSION);
                
                break;
            }
        }
        //if i needs to be set, add 1 to i
        if (set_i)
        {
            i++;
        }
    }

//...

void Map::draw()
{
    //go trough all rects
    for (vector<SDL_Rect>::iterator it = rect.begin(); it<rect.end(); it++)
    {
        //create temporary rectangle
        SDL_Rect temp = *it;
        //draw rectangle to the screen
        SDL_FillRect(screen,&temp,SDL_MapRGB(screen->format,255,200,0));
    }
    
    //go through all bullets
    for (vector<SDL_Rect>::iterator it = bullet.begin(); it<bullet.end(); it++)
    {
        //create temporary rectangle
        SDL_Rect temp = *it;
        SDL_FillRect(screen,&temp,SDL_MapRGB(screen->format,255,0,0));
    }
}

Everything is working perfectly now. Thanks for your help.

Topic archived. No new replies allowed.

Bug in loop (involving vectors)

C++

Forum