Jump to content
  • Advertisement
Sign in to follow this  
throttler

Keeping track of bullets in a 2D game

This topic is 3810 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello. I am currently programming a simple 2D-shooter with the help of direct3d. The bullets are only animated in the y-direction, the x-position is decided by the position of the shooter at the moment the bullet is fired. My class design is as follows; http://img99.imageshack.us/img99/3531/classdesignpongha6.th.jpg Game cycle; GameLoop -> GameInput -> GameLogic -> GameRender -> Window::MessageQ() -> GameLoop GameInput holds a struct which sets game events to true or false, e.g. DIK_LEFT sets moveLeft to true. GameLogic is mainly for enforcing the game rules, and to set the new positions for objects that are going to be rendered. GameRender renders the sprite objects at the new positions, I send it this data by using a struct argument. /////////////////////////////////////////////////////////////////////////////////////// My problem is as follows; I am trying to find a good and efficient way to keep track of fired bullets, then check bullets for collision or if they are out of bounds. I was thinking of perhaps putting an Alive boolean variable in the object-struct (which is used by gamelogic to set positions, and gamerender to render at the given positions). That way I could set Alive to true when the bullet is fired, and to false when it is out of bounds or has hit a target. By using this method I was thinking of just looping through the array of gameobjects to find one that has Alive = false, and then assign that to a new bullet. This way I could also loop through to figure out which bullets (Sprites) that should be rendered and which ones that shouldn't. I feel that there has to be a smarter way to solve this, and I hope someone with more experience can at least point me in the right direction. All help and comments are appreciated. Thanks :)

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by throttler
I feel that there has to be a smarter way to solve this


Why is this not a smart way? It seems to work exactly for what you need. Indeed, this is exactly what I would do for something simple like a bullet that travels in one direction in a 2D plane with little or no animation.

You can allocate memory and free it for every bullet, using linked lists, but that would probably be slower and is certainly more work on your part. Just create an array with more bullets than you'll ever need (depending on the number of guns/players in your game and their rate of fire, this is easy to calculate). Looping through won't take a long time or anything.

Can you think of any problems with your solution? I certainly can't.

Share this post


Link to post
Share on other sites
There is a smarter way, yes. Read up on std::vector, and on C++' standard library in general. It contains quite a bit of usefull functionality.

In other words, I'd use a std::vector, add a new bullet to it whenever one is fired, and remove it from the vector when it's out of bounds. This means that only live bullets exist, which means less manual management. And performance isn't significantly worse, either. That is, as long as you keep some things in mind, such as that a vector may create duplicates of your bullets when it resizes itself. It'll clean up these duplicates, sure, but this can reduce performance and mess up non-POD objects. It's often better to store pointer-to-objects in a vector, or, even better, smart pointers, to save yourself the hassle of manually managing the memory.

Yep, C++ is quite complex. ;)

Share this post


Link to post
Share on other sites
Actually you don't even need an "IsAlive"-variable. "IsAlive" is implicitly give by the object's on-screen position (pseudo-code):

def fireBullet(x, y)
foreach bullet bullet in bulletList
if IsOffscreen( bullet ) -- implies "dead"
bullet.SetPosition(x, y)
return -- edit: finished
end
end
end

def renderBullets()
foreach bullet in bulletList
if IsOnScreen( bullet )
RenderObjectAt( bullet, bullet.GetPosition() )
end
end
end

def hitTarget(bullet)
bullet.SetPosition(offScreenX, offScreenY) -- implies "dead" bullet
end


In big-O notation, both operations are O(N), where N is the number of bullets
in your bullet array (e.g. max. number of bullets "alive"). Trying to reduce
this effort is probably not worth it - remember the Golden Rules Of Optimization: 1. "Don't do it." 2. "Don't do it yet.". [smile]

To put it short, I totally agree with Gauvir_Mucca - your approach is fine.

[Edited by - darookie on January 14, 2008 7:05:54 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Captain P
There is a smarter way, yes. Read up on std::vector, and on C++' standard library in general. It contains quite a bit of usefull functionality.

In other words, I'd use a std::vector, add a new bullet to it whenever one is fired, and remove it from the vector when it's out of bounds. This means that only live bullets exist, which means less manual management. And performance isn't significantly worse, either.

Yep, C++ is quite complex. ;)

A pre-sized vector of reasonable size with no removing or adding at runtime is
the most simple and probably more efficient way. Removing elements from the
middle of a std::vector is a quite expensive operation and the worst case
implies O(N2) copy operations (e.g. all bullets in a fully allocated
vector die within a single frame in the same order they've been spawned).

While I agree to use C++ containers, I'd prefer a pre-sized vector or even a boost.array over a fully
dynamic, resizing std::vector any day. I'm pretty confident the profiler will
be on my side, since setting (or - as I demonstrated - not even setting) a simple flag is much more efficient than moving bullet instances around in memory
every few frames. Plus you won't even need dynamically allocated bullets unless
you have tens of thousands of them [smile].

Feel free to correct me, though - show me some numbers [wink].

Share this post


Link to post
Share on other sites
How many bullets are we talking about here? Will this be a bullet-hell shooter? Will your player ever get so powered up that he fires millions of bullets in 300 directions at once? If not then you might not have to worry about the performance hit you'd take if you used a vector to store your bullets.

If you do care about performance, look into using an unrolled linked list.
It's basically a linked list of arrays and it's quick to iterate through, add to, and remove from (although random access is much slower). If you stick with an array and use an "alive" flag, you will be iterating over a lot of dead elements every frame. If you use a vector, you will have to reserve enough space for it to hold enough bullets or else it will need to resize itself, which is an expensive process.

I don't use C++ so I can't help you with any standard implementations of them, but unrolled linked lists are pretty easy to make if you can't find one yourself.

Share this post


Link to post
Share on other sites
Quote:
Original post by Hombert
If you stick with an array and use an "alive" flag, you will be iterating over a lot of dead elements every frame. If you use a vector, you will have to reserve enough space for it to hold enough bullets or else it will need to resize itself, which is an expensive process.

The advantage of using an upper limit (e.g. I would never resize the vector) is that yo can fine-tune it to meet your target platform's performance.
And yes, keeping two additional lists (alive and dead) that only index into the actual bullet
array à la freelist could save you from iterating over dead elements. However,
unless iterating over a relatively small array and querying a simple flag only really becomes a performance
issue, I personally wouldn't worry too much about it. But again - without any numbers and profiling it's a moot point anyway...

Share this post


Link to post
Share on other sites
It's not too hard to implement a fixed pool with a dynamic list of active/dead bullets that scales pretty well in performance with the number of bullets you intend to have.

Example:
std::vector<Bullet> bulletPool( MAX_BULLETS );
std::vector<Bullet*> bulletList;
bulletList.reserve( MAX_BULLETS );
int numActiveBullets = 0;

void addBullet(int x, int y)
{
// Take from the pool if necessary
if(numActiveBullets == bulletList.size())
{
bulletList.push_back( &bulletPool.at(numActiveBullets) );
}

// Spawn the bullet and increment the counter
bulletList[numActiveBullets]->spawnAt(x, y);
++numActiveBullets;
}

void killBullet(int index)
{
// Inform the bullet its about to die
bulletList.at(index)->kill();

// Swap the pointer with the last active one and decrement the counter
std::swap(bulletList[index], bulletList[--numActiveBullets]);
}


Edit: Changed activeBullets to bulletList.

[Edited by - dmatter on January 15, 2008 9:01:33 AM]

Share this post


Link to post
Share on other sites
I almost see how that would work but where does "activeBullet" come from? Did you mean to say "bulletList"? If so, then you'd run into problems when deleting bullets, as you'd wind up with multiple elements of bulletList pointing to the same element of bulletPool in some cases.

Share this post


Link to post
Share on other sites
Quote:
Original post by Hombert
I almost see how that would work but where does "activeBullet" come from? Did you mean to say "bulletList"?

Oops sorry yes, that's what I meant.
Quote:
If so, then you'd run into problems when deleting bullets, as you'd wind up with multiple elements of bulletList pointing to the same element of bulletPool in some cases.

I don't see how that would be the case.
The bulletList is partitioned into two sections; the front partition is for live bullets and the end parition is for dead ones. When you delete a bullet it simply gets swapped with the very last live bullet thus expanding the dead partition into the live partition.
Ideally I should really have added a check to ensure that the index does not exceed the number of live particles as otherwise this would cause problems.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!