Thread: Minimizing array lookup times using effective indexing...?

  1. #1
    Registered User The Dog's Avatar
    Join Date
    May 2002
    Location
    Cape Town
    Posts
    788

    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
    Last edited by The Dog; 02-07-2011 at 04:18 AM.

  2. #2
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    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.

  3. #3
    Registered User The Dog's Avatar
    Join Date
    May 2002
    Location
    Cape Town
    Posts
    788
    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

  4. #4
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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?

  5. #5
    Registered User
    Join Date
    Jan 2011
    Location
    Venezuela
    Posts
    6
    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.

  6. #6
    Registered User The Dog's Avatar
    Join Date
    May 2002
    Location
    Cape Town
    Posts
    788
    >> 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...

    ?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Modify an single passed array element
    By swgh in forum C Programming
    Replies: 3
    Last Post: 08-04-2007, 08:58 AM
  2. how can I re-sort a map
    By indigo0086 in forum C++ Programming
    Replies: 8
    Last Post: 06-01-2006, 06:21 AM
  3. two dimensional dynamic array?
    By ichijoji in forum C++ Programming
    Replies: 6
    Last Post: 04-14-2003, 04:27 PM
  4. Creating 2D arrays on heap
    By sundeeptuteja in forum C++ Programming
    Replies: 6
    Last Post: 08-16-2002, 11:44 AM
  5. mode of an array
    By Need Help in forum C Programming
    Replies: 15
    Last Post: 09-17-2001, 08:03 AM