Opinion on lots of bullets in game

Sage
Posts: 1,403
Joined: 2005.07
Post: #1
What you think the best way to handle a large array of objects being quickly created and deleted is?

Im thinking about doing it like this, Well I want to have an unlimited number, but I could easily make it a maximum of screenwidth*screenheight, but thats possible excessive, im not sure.

So anyway, if a bullets needs to be destroyed, then I set that element of the array to NULL creating a space in the array,
and when I do my tick loop, which moves the bullets according to thier velocity. Ill say
Code:
if(bullet[i] == NULL && !(bullet[i+1] == NULL)) {
   copy bullet[i+1] into bullet[i]
}
do bullet stuff ,
if (bullet[i] was NULL && bullet[i+1] wasnt) {
   i++
} // so as to skip bullet[i+1], because we just did moved that bullet,

This way, it will move all the spaces towards to end of the array, but there will only be small number of copies each frame, the number of bullets there are as opposed to something like

Code:
if(bullet[i] == NULL) {
   j++;
   while(bullet[i+j] == NULL)
   j++;
   copy bullet[j] into bullet[i]
}
do bullet stuff ,
which will do a bigger number of copies if theres gaps near the start of the array,

or should I keep track of where the spaces are in another array?
Any ideas, suggestions anything would be interesting.

Sir, e^iπ + 1 = 0, hence God exists; reply!
Quote this message in a reply
Moderator
Posts: 1,140
Joined: 2005.07
Post: #2
You could always just construct a doubly linked list to store them in.
Quote this message in a reply
Sage
Posts: 1,403
Joined: 2005.07
Post: #3
that would be slower for adding to but faster for removing from right?
also how would it compare for looping through each frame and moveing each bullet?

Sir, e^iπ + 1 = 0, hence God exists; reply!
Quote this message in a reply
Moderator
Posts: 1,140
Joined: 2005.07
Post: #4
it would be faster for adding since you won't have to copy the entire array whenever you need to resize it. You can always add to the beginning or the end, depending on which pointers you keep track of. For removing, it would be slower since you basically have to loop to the point in the list, but you could remedy that by queuing the bullets you want to delete, then delete them when you're looping through to update them. To loop through and update the bullets, it would probably be slightly slower since the memory isn't linear. However, that effect should be very small.
Quote this message in a reply
Moderator
Posts: 1,560
Joined: 2003.10
Post: #5
With that many objects onscreen at once, managing the array that contains them will almost certainly not be your bottleneck. We all know what they say about premature optimization, so just implement it in whatever way is easiest now, and optimize later if and only if Shark tells you to.
Quote this message in a reply
Sage
Posts: 1,403
Joined: 2005.07
Post: #6
Well the first way works ok just now its hard to test because theres only one character shooting but im just interesting in different ways to tackle the problem.
Im only going to resize the array once in a while because Ill increase it in stages of 20 if theres not enough room, and reset it to length 20 every level I think, to save memory..
so about 95% of the time to add I just do bullet[i].x = new_x. etc..

Sir, e^iπ + 1 = 0, hence God exists; reply!
Quote this message in a reply
Member
Posts: 184
Joined: 2004.07
Post: #7
Here's what I usually do instead- I just leave the null slot in the array and in looping through the array just make sure that if any pointers are null they are just skipped over. Then when I create a new object it will fill up the lowest null slot (and then, if there are no null slots, the size of the array is increased- I usually use an STL vector so this is done automatically.) I don't worry about shrinking the array, because assuming the game was able to handle a full array, it should be able to handle skipping over that many null pointers.

Also if you don't care about the order of your array, you can move the object in the last slot of your array into the new empty slot- then you only have to copy one pointer instead of every one after the null slot. So there are a number of options available to you.

Asymptotically the doubly-linked list method is the fastest, but has a fairly large overhead, since each element needs an additional two pointers. It's also not as simple to implement, which is a concern in my hobbyist programming where I'm pressed for time.
Quote this message in a reply
Sage
Posts: 1,403
Joined: 2005.07
Post: #8
Quote:you can move the object in the last slot of your array into the new empty slot
That is very good, I hadn't though of that yet ill definitly be doing that instead because that in effect reduces the size of the array and so I have less iterations to do when looping, and it fills the gaps in quicker.
Quote:Asymptotically the doubly-linked list method is the fastest
Are you ceartain its faster?

Sir, e^iπ + 1 = 0, hence God exists; reply!
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #9
I suppose it depends on wether you're dealing with, say, 500 bulllets or a million bullets. if you're talking about the lower bound, go with a doubly linked list. In fact, to save yourself some time, just go with std::list, and have your bullets keep their iterator on hand. I do this to manage shadow-casting sets in my game and it hauls ass. Each shadow caster has its iterator into the world's shadow casting set, so both insertion & removal are constant time.

However, if you're dealing with hundreds of thousands of bullets, then you might want to look into clever solid-block allocation strategies with sweeping reallocation, done periodically but not every tick.
Quote this message in a reply
⌘-R in Chief
Posts: 1,237
Joined: 2002.05
Post: #10
More Bullets!
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Adding lots of static shapes in Chipmunk - performance question TomorrowPlusX 3 7,006 Jul 11, 2011 01:39 PM
Last Post: Skorche
  Second Opinion Sought MstrPBK 12 3,904 Oct 2, 2008 07:04 PM
Last Post: AnotherJake
  Keeping track of bullets Bossa Nova 3 2,577 Jun 26, 2003 09:09 PM
Last Post: OneSadCookie