C++ question: How to keep track of many bullets?

[t]

Hello,
I was wondering how to keep track of the bullets that my player's ship shoots. There may be any number of bullets alive at one time, 0 to n.

Any suggestions? Perhaps a linked list (with c++ std library, ie stl) ? an array of max_bullets?

[stampsm]

just set up an multi dimensional array with the first dimension array recording the bullet id and the other dimension info about the bullet such as state( array in use), position, vector,and any other info about it
you can then go through the array one bullet at a time each cycle and update it's info and check ,for example, if it hit something
with this you can have other stuff affect it such as wind ect
your array should look something like this

bullet id
1 2 3 4 5 ......
state 1 1 0 1 1
positionx 10 11 20 13 15
positiony 5 5 5 5 5
positionz 3 3 3 3 3
vectorx 1 1 1 1 1
vectory 0 0 0 0 0
vectorz 0 0 0 0 0
........


in this example the state tells if the bullet exists ie if it is flying through the air
the positionx is where in the x axis it is
the positiony is where in the y axis it is
the positionz is where in the z axis it is
the vectorx is the velocity in the x axis
the vectory is the velocity in the y axis
the vectorz is the velocity in the z axis

the 3rd bullet has a state of 0 so it doesn't exist so you can just ignore the values in it
you can use this format for any projectile such as a rock a bullet or even a missle

this may be a little more than you need and it takes more processing power but it gives you the greatest possible flexibility
you will have to create your array ahead of time so you will have to have a limited number of bullets but if you plan it right you won't run out of bullet id's
and whenever a bullet hits something or dies because of a timeout you implimented (so the bullet doesn't fly for forvever) just set it's state value to 0
when you create a bullet just scan for a state of 0 and use that id since the bullet no longer exists you can overwrite it's data with new data
you will probable have to customize this to exactly what you need but it should work
i like this way because it gives you the possibilty of weapons such as a those in tribes 2 that don't have line of sight and can bounce off of wall realisically, also they can hit targets that weren't there when they were fired
you can probable use the same array for all of the projectiles by just adding another spot in the second dimension that has info on the type of bullet


ps if you don't need this much flexibility, can't do this, or don't have enough processing power just do like the tech demo does and give it a straight line if fire that checks if it colides with a object


i think i explained it good but if you still don't understand tell me and i will try to explain better

or if there are errors tell me so i don't have to figure them out latter on my own

[stampsm]

just set up an multi dimensional array with the first dimension array recording the bullet id and the other dimension info about the bullet such as state( array in use), position, vector,and any other info about it
you can then go through the array one bullet at a time each cycle and update it's info and check ,for example, if it hit something
with this you can have other stuff affect it such as wind ect
your array should look something like this

bullet id
1 2 3 4 5 ......
state 1 1 0 1 1
positionx 10 11 20 13 15
positiony 5 5 5 5 5
positionz 3 3 3 3 3
vectorx 1 1 1 1 1
vectory 0 0 0 0 0
vectorz 0 0 0 0 0
........


in this example the state tells if the bullet exists ie if it is flying through the air
the positionx is where in the x axis it is
the positiony is where in the y axis it is
the positionz is where in the z axis it is
the vectorx is the velocity in the x axis
the vectory is the velocity in the y axis
the vectorz is the velocity in the z axis

the 3rd bullet has a state of 0 so it doesn't exist so you can just ignore the values in it
you can use this format for any projectile such as a rock a bullet or even a missle

this may be a little more than you need and it takes more processing power but it gives you the greatest possible flexibility
you will have to create your array ahead of time so you will have to have a limited number of bullets but if you plan it right you won't run out of bullet id's
and whenever a bullet hits something or dies because of a timeout you implimented (so the bullet doesn't fly for forvever) just set it's state value to 0
when you create a bullet just scan for a state of 0 and use that id since the bullet no longer exists you can overwrite it's data with new data
you will probable have to customize this to exactly what you need but it should work
i like this way because it gives you the possibilty of weapons such as a those in tribes 2 that don't have line of sight and can bounce off of wall realisically, also they can hit targets that weren't there when they were fired
you can probable use the same array for all of the projectiles by just adding another spot in the second dimension that has info on the type of bullet


ps if you don't need this much flexibility, can't do this, or don't have enough processing power just do like the tech demo does and give it a straight line if fire that checks if it colides with a object


i think i explained it good but if you still don't understand tell me and i will try to explain better

or if there are errors tell me so i don't have to figure them out latter on my own

[stampsm]

just set up an multi dimensional array with the first dimension array recording the bullet id and the other dimension info about the bullet such as state( array in use), position, vector,and any other info about it
you can then go through the array one bullet at a time each cycle and update it's info and check ,for example, if it hit something
with this you can have other stuff affect it such as wind ect
your array should look something like this

bullet id
1 2 3 4 5 ......
state 1 1 0 1 1
positionx 10 11 20 13 15
positiony 5 5 5 5 5
positionz 3 3 3 3 3
vectorx 1 1 1 1 1
vectory 0 0 0 0 0
vectorz 0 0 0 0 0
........


in this example the state tells if the bullet exists ie if it is flying through the air
the positionx is where in the x axis it is
the positiony is where in the y axis it is
the positionz is where in the z axis it is
the vectorx is the velocity in the x axis
the vectory is the velocity in the y axis
the vectorz is the velocity in the z axis

the 3rd bullet has a state of 0 so it doesn't exist so you can just ignore the values in it
you can use this format for any projectile such as a rock a bullet or even a missle

this may be a little more than you need and it takes more processing power but it gives you the greatest possible flexibility
you will have to create your array ahead of time so you will have to have a limited number of bullets but if you plan it right you won't run out of bullet id's
and whenever a bullet hits something or dies because of a timeout you implimented (so the bullet doesn't fly for forvever) just set it's state value to 0
when you create a bullet just scan for a state of 0 and use that id since the bullet no longer exists you can overwrite it's data with new data
you will probable have to customize this to exactly what you need but it should work
i like this way because it gives you the possibilty of weapons such as a those in tribes 2 that don't have line of sight and can bounce off of wall realisically, also they can hit targets that weren't there when they were fired
you can probable use the same array for all of the projectiles by just adding another spot in the second dimension that has info on the type of bullet


ps if you don't need this much flexibility, can't do this, or don't have enough processing power just do like the tech demo does and give it a straight line if fire that checks if it colides with a object


i think i explained it good but if you still don't understand tell me and i will try to explain better

or if there are errors tell me so i don't have to figure them out latter on my own

[Saalen]

Instead of searching a free slot in the list, I would rather delete invalid bullets and create a new one when needed. Runtime behaviour improved from O(n) to O(c)

[t]

I use a std library vector at the moment. and when a bullet expires i remove it from the list. Works reasonably well.

[Guest]

Instead of searching a free slot in the list, I would rather delete invalid bullets and create a new one when needed. Runtime behaviour improved from O(n) to O(c)

We can do even better than this:

* Assume you have an array with space for N bullets. If you have more than N bullets, well, you need to deal with that (alloc more? drop some older ones? disallow more bullets?

You keep track of how many bullets you have. Let's say 0 at the start. All the bullets are always sorted at the front of the array.

* when you add a bullet you simple add it at the last position, increment the number of bullets in your array, and are done. This is O(1)
* when you delete a bullet, copy over the data from the last bullet to the free slow, and decrease the number of bullets. This is also O(1).

Take care when walking the array and deleting at the same time, if you delete pos #4, and copy #8 (the last) to #4, you need to resume walking at #4, not #5, otherwise you would miss the update for bullet #4. (which might not be critical, but still)

So, adding/deleting is O(1), the optimum. And it doesn't take any memory allocation/reallocation/freeing, which is very good (because very fast

But you need still to walk all the bullets and update them, and when you have many of them (machine gunner is trigger happy?) this might pose a problem

I knew the Algorithmn Complexity classes would pay off

Best wishes,

Tels

[Domarius]

Not directly on topic, but I just wanted to share my idea for saving processing power on hundreds and hundreds on individual bullets.

Shoot every individual bullet, but every 10 bullets or something, shoot out a long invisible rectangle that will roughly represent the area that those 10 bullets take up. This is what enemies test collision with, instead of each individual bullet. Its like one big bullet. (The damage caused by it will be worth 10 bullets) The big bullets come out often enough to be end to end to each other, if you're firing in a straight line.
The idea is, you're animating lots of little bullets, but you only test collision with the few big bullets.

I got the idea from watching the way you shoot the machine gun in F-15 Strike Eagle - lots of bullets are coming out, but the 'bullet explosion' on the plane being hit is only happening every so often.

Not what you'd want for player to player interaction, but player to NPC, or NPC to NPC interaction, you could probably get away with doing it this way (allowing more processing time for other things).

[Tels]

Interesting idea. You might also want just to test the "long line", and if there was no collision, ignore it, and if there was, check all the bullets in the line starting with the front bullet. That way it would be accurate and faster (if you have really lot's of bullets, that is)

Cheers,

Tels

[Domarius]

Interesting idea. You might also want just to test the "long line", and if there was no collision, ignore it, and if there was, check all the bullets in the line starting with the front bullet. That way it would be accurate and faster (if you have really lot's of bullets, that is)

Cheers,

Tels

That's a good idea - then it could become an 'optimisation' for player to player stuff as well. With a bit more work - That idea would involve associating the "long block" with the appropriate 10 bullets, so you know which ones to check for collision when the block collides, and also being extra careful about the placement of the "long block" so it more closley represents the area taken up by the 10 bullets as possible (but not nessecarily perfectly)