Minimizing array lookup times using effective indexing...?

Hi

I've decided to get into games development and have quite a bit of catching up to do.
Currently, I'm writing a shmup engine (which I've done before, but I lost my code!).

For my bullets, I have an object pool which can grow to +2000 objects very quickly.

What strategies can I use to minimise the time to find an available object in the pool?

Currently I'm using arrays for performance reasons, but I don't like the linear search required
to find an available object...

Any alternatives?

[EDIT]
I'm thinking of using a running index together with a stack for object's that die ie. when an object in the pool dies,
push the index of that object onto the stack. In this way I could use the stack until it's empty before I initiate a linear search.
Come to think of it, I could push all indexes onto the stack and then use the stack exclusively... Any suggestions?

Thanks

I assume you are updating the bullets each frame? Why not use something like a linked list to store the bullets, you need to go through it once a frame either way and you can just erase nodes as bullets die and push back new bullets when they are added to the game. You will have a linear complexity for updating (which you would have anyway) and constant removal and constant adding.

Hi

Bullets are created and removed outsidet the game's update method as I'm utilising BulletML and because I prefer it this way. The overhead of the iteration required for updating active bullets is acceptable for me.

Thanks

There is a simple solution to your problem. You don't need to 'find' empty holes or array indices if you never have any. So what type of data structure has or could have constant time insertion and removal and O(n) iteration?

If you are coding in C++ you are better off using vectors for this kind of thing. It gives you the speed of arrays plus a bunch of other features to optimize your code, including array resize, .at() method, among others.

I would also optimize the hittest code for each bullet, which will be the one taking most of the computing time. Try to define square sections around objects and just don't compute anything that doesn't go there. Reading about particle algorithms should help you greatly in this endeavour. Good luck.

>> There is a simple solution to your problem. You don't need to 'find' empty holes or array indices if you never have any. So what type of data structure has or could have constant time insertion and removal and O(n) iteration?

I'm currently using an array and a stack. The stack is initialised with all the pointers in the array. The stack only ever contains dead bullets.

I don't want to use 1 container exclusively as I don't see how it averts the need to find an
available object...

?