Archived

This topic is now archived and is closed to further replies.

Sponzie

for loop bounds and a vector question

Recommended Posts

2 questions about a vector of bullets I use in my game m_Bullets is a vector containing pointers to bullet objects, and is a member of my player class. During the updating of the player, I check whether any of his bullets hit an enemy, using the following loop: for(int bullet = 0; bullet < m_NumberOfActiveBullets; bullet++) { float x, y; m_Bullets[bullet]->GetPosition(&x,&y); if(m_EnemyManager->CheckBulletCollision(x,y)) { m_Bullets[bullet]->Shutdown(); delete m_Bullets[bullet]; m_Bullets.erase(m_Bullets.begin() + bullet); m_NumberOfActiveBullets--; } } -> Since this is the first time I use vectors, I'm not sure whether the sequence (1) release bullet resources, (2) delete the bullet object and (3) erase the bullets position from the vector is correct. Is it? -> When I'm decreasing the number of active bullets in the loop, does this also decrease the m_NumberOfActiveBullets value used in the loop condition? If it's not (and I'm afraid so..), I'm checking an invalid bullet every once in a while. How can I solve this? edit: using square brackets and only a b doesnt look nice doh [edited by - Sponzie on November 15, 2003 2:03:31 PM]

Share this post


Link to post
Share on other sites
Ok, I think I see what you mean. Everytime an activebullet is removed your entire vector list gets shifted down to fill in the hole of the removed element. In such a case I think you want to check that same position in the vector again as this time around you''ll be checking a different item in the same index. I suppose a simple fix for it is to cancel out the bullet++ if you did the if by maybe putting a bullet-- inside the if. Or you can just move the bullet++ from the for into the else part of the if.





--{You fight like a dairy farmer!}

Share this post


Link to post
Share on other sites
Is this vector class the std::vector class from STL?

If so, you should probably use linked lists so that you don't have to resize the vector every time a bullet is taken out of it. Also, the size of the vector will change if you remove an element from it, so you'll skip items.

here's a little test app I put together showing you how to use the STL list object.


#include "stdafx.h"
#include <list>


// maximum bullets at any one time

const int MAX_BULLETS = 20;

// Your bullet class

class Bullet
{
public:
int nTimer;
};



std::list<Bullet*> g_bulletsActive; // the bullets that are active

std::list<Bullet*> g_bulletsFree; // storage of free bullets



// static array of the bullets to avoid allocations

Bullet g_bulletArray[MAX_BULLETS];



void FireBullet()
{
// fire a bullet

Bullet* pFireBullet = g_bulletsFree.front();
// set the timer

pFireBullet->nTimer = 10;

// remove it from the free list

g_bulletsFree.pop_front();

// add it to the active list.

g_bulletsActive.push_back(pFireBullet);

return;
}


void UpdateBullets()
{
// update the bullets

std::list<Bullet*>::iterator iter;

for (iter = g_bulletsActive.begin(); iter != g_bulletsActive.end(); /* empty */)
{
Bullet* pBullet = *iter;

// decrement the timer.

pBullet->nTimer--;

if (pBullet->nTimer == 0) // or HasHit() or what have you

{
printf("a bullet has expired\n");

// Remove it from the active list, getting the next

// iterator.

iter = g_bulletsActive.erase(iter);

// Take the bullet and store it in the free list

g_bulletsFree.push_back(pBullet);

}
else
{
// move to next bullet

iter++;
}

}

return;
}


int main(int argc, char* argv[])
{
// put all the statically allocated bullets in the free list

for (int i = 0; i < MAX_BULLETS; i++)
{
g_bulletsFree.push_back(&g_bulletArray[i]);
}

printf("size of bullets: %d active %d free\n", g_bulletsActive.size(), g_bulletsFree.size());

FireBullet();

printf("size of bullets: %d active %d free\n", g_bulletsActive.size(), g_bulletsFree.size());


while (g_bulletsActive.size() > 0)
{
UpdateBullets();
}

printf("size of bullets: %d active %d free\n", g_bulletsActive.size(), g_bulletsFree.size());


return 0;
}



Of course the bullet object wouldn't necessarily have a timer, it would have a way to test if it had hit anything, but your get the idea.

Using lists is good for cases when you don't know what order items are going to be added or removed from the list, or whether they will be added in the middle, front or end.


[edited by - Sphet on November 15, 2003 3:12:13 PM]

Share this post


Link to post
Share on other sites
Ah thanks, I didnt even see that problem yet. Actually, what I meant to ask was whether this

int x = 10;

for(int i = 0; i < x; i++)
{
x = 9;
f(i);
}

calls f(9) or not (are variables in the loop condition constant or not?)

The problem I''m having is that since I added this vector of bullets, my game crashes like once every 10 times it''s played.. depending (I believe) on the bullet-enemy collisions, and I thought the cause might be in this function.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Sponzie
Ah thanks, I didnt even see that problem yet. Actually, what I meant to ask was whether this

int x = 10;

for(int i = 0; i < x; i++)
{
x = 9;
f(i);
}

calls f(9) or not (are variables in the loop condition constant or not?)



No, f(9) wont be called. It would be, however, if you removed the x=9.

Share this post


Link to post
Share on other sites
As for the code within the loop :

(1) release bullet resources
Correct, however it would be better to do this in Bullet''s destructor instead of in a Shutdown() function. Or at least to have your destructor call that function automatically.
(2) delete the bullet object
Correct
(3) erase the bullets position from the vector
Correct

As for the loop itself, yes you do have a problem.
You''ll, be much better off using iterators rather than a loop counter. Iterators are the equivalent of pointers for STL containers. And they are meant, well, to iterate through a container


std::vector<Bullet*>::iterator itor = m_Bullets.begin()

while( itor != m_Bullets.end() )
{
float x, y;
(*itor)->GetPosition(&x,&y);
if(m_EnemyManager->CheckBulletCOllision(x,y))
{
(*itor)->Shutdown(); // Unnecessary with a proper destructor.
delete *itor;
m_NumberOfActiveBullets--;

// erase will correctly advance the iterator
itor = m_Bullets.erase(itor);
}
else ++itor;
}


Using the return value from erase ensures you are only checking each element in the vector once, regardless of what happens to their indices when one of them is deleted. And since a vector "knows" how many elements it contains, there should be no need for you to keep track of the number of active bullets : it''s simply m_Bullets.size();

Be warned though that, a vector is not the ideal data structure for the current task. Removing elements in the middle of a vector is expensive : as others mentioned, all the following elements must be shifted one place. A linked list would work better and, unless I am mistaken (which I could be), the code above would work with a std::list without modification (beside telling it to use ''list'' instead of ''vector'').

At any rate, one way you can gain speed is only call erase once, as the following example shows:


#include <algorithm>
#include <functional>

// This class provides the loop''s body as an inline function.
// This allows the loop to be faster (than using function
// pointers) and to carry more information (than a function
// pointer would), since it is a full-fledged object.

struct FnReleaseCollidedBullets // function of one parameter
: public std::unary_function<Bullet*&, bool> // Takes a Bullet* by ref, returns a bool.
{
private:
EnemyManager* manager;

public:
// The EnemyManager object (along with all the other state
// that could be necessary) is provided upon object construction.
// ''explicit'' disables implicit conversions, just to be safe.

explicit FnReleaseCollidedBullets( EnemyManager& manager_ )
: manager( &manager_)
{}

// I have heard some people have had problems with the
// typedefs provided by unary_function, so if it doesn''t
// work for you, replace result_type with bool and
// argument_type with Bullet*&

inline result_type operator()( argument_type bullet ) const
{
float x, y; // could be private members if we don''t need
// the function to be reentrant (no threading)
bullet->GetPosition(&x, &y);
if( manager->CheckBulletCollision(x,y) )
{
bullet->Shutdown(); // Unnecessary with a proper destructor.
delete bullet;
bullet = 0; // That''s why we pass by ref.
}

return bullet == 0;
}
};

// Now we use it. First check collisions, delete collided
// bullets and set the pointer in the container to NULL.

std::for_each( m_Bullets.begin(), m_Bullets.end(),
FnReleaseCollidedBullets(m_EnemyManager) );

// Now we compact the the vector (remove), by moving non-null
// elements over the null elements (in one pass), then we
// remove from the vector the extraneous copies that were left
// at the end (remove did ''shift'' the elements without reducing
// the size of the array, some elements have been duplicated,
// erase will remove those duplicates. This is cheap because
// we really hold pointers to Bullets.)

vector.erase( std::remove( m_Bullets.begin(), m_Bullets.end(), 0 ),
m_Bullets.end() );



It may seem a bit overkill but, once you have created an appropriate set of function classes (like FnRemoveCollidedBullets), most container manipulations become trivial.

Also note that we had to make sure and delete the bullets before throwing their pointers out of the vector. A technique called "smart pointers", which consists in creating objects that act like pointers, but manage deletion of the pointed-to object ''smartly'' (for example by counting how many smart pointers reference a given object, and deleting it when the last reference goes away), would simplify the code even more.

Yes, I''m aware you might not consider the above code simpler than your own. However, I do, as it is much easier (if maybe a bit verbose) to write a function object than to make sure all your loops are always correct

With smart pointers (like boost::shared_ptr), and a proper destructor, so that Shutdown() be unnecessary.


typedef std::shared_ptr<Bullet> spBullet; // smart pointer to Bullet
std::vector< spBullet > m_Bullets;


struct FnCheckBulletCollision // function of one parameter
: public std::unary_function<Bullet*&, bool> // Takes a Bullet* by ref, returns a bool.
{
private:
EnemyManager* manager;
public:
explicit FnCheckBulletCollision( EnemyManager& manager_ )
: manager( &manager_)
{}

inline result_type operator()( argument_type bullet ) const
{
float x, y;
bullet->GetPosition(&x, &y);
return manager->CheckBulletCollision(x,y);
}
}

m_Bullets.erase( std::remove_if( m_Bullets.begin(),
m_Bullets.end(),
FnCheckBulletCollision( m_EnemyManager ),
m_Bullets.end() );

// The function object tests for collision
// remove_if overwrites the pointers bullets that have collided
// the smart pointers call the destructor for those bullets
// the destructor releases the resources
// erase removes the leftover bullet pointers at the end of the vector.



Personally, I like that better than writing my own loops
It expresses what you are trying to achieve much better.
Your mileage may vary.


[ Start Here ! | How To Ask Smart Questions | Recommended C++ Books | C++ FAQ Lite | Function Ptrs | CppTips Archive ]
[ Header Files | File Format Docs | LNK2001 | C++ STL Doc | STLPort | Free C++ IDE | Boost C++ Lib | MSVC6 Lib Fixes ]

Share this post


Link to post
Share on other sites
I think its time for me to get a book like "The C++ Standard Library" soon.. but I'll try using iterators and lists for this problem as soon as I get home. Must be able to do so now!

Hopefully it was the only source of runtime errors for now


edit:

I've been reading the last example over a few times again, and I finally understand what's going on with the function object One more question though, how does this

m_Bullets.erase( std::remove_if( m_Bullets.begin(), m_Bullets.end(), FnCheckBulletCollision( m_EnemyManager )), m_Bullets.end() );

not result in repeatedly downsizing the vector (costly), while erasing one element at a time in a simple for loop does?


[edited by - Sponzie on November 17, 2003 2:07:32 PM]

Share this post


Link to post
Share on other sites