Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I finally have all the working input/output of a game engine.

However, I'd like to be able to put an amount of about 2000 shots being simulated in a region, total. I have done other games where all the data was stored in a linear array and iterated every turn, and referenced by index number. This method seems to be fast enough, grants random access instantaneously and I'd say it "just works". However, inserting a new element requires searching for an empty space, and iterating over the "inactive" shots.

Considering the amount of max shots, what would be the best approach to this? Am I thinking too much about this, perhaps, and the array is a good enough system?

The engine works in C99. Shots will be destroyed when out of "practical" range and collisions will be done around the player rather than the entire working map. The game is real-time action style so updating needs to be quick, and shots might need to be accessed by position, which is another weakness of the array approach (unless I add that information to "slices" of the main map, I guess).

To summarize. What would be the best data structure in terms of insertion speed, allowing random access and iterating without gaps? A name, if it exists, would be enough.

share|improve this question
    
I'm a bit confused but from what I can see you may want something like this: stackoverflow.com/questions/7252274/… –  quasiverse Sep 4 '11 at 1:23
2  
I will invoke the magic words: Measure Before Optimizing. You probably don't even need to do anything more and any effort you spend now will be better spent on bigger problems or better game play. –  Patrick Hughes Sep 4 '11 at 2:55
add comment

migrated from stackoverflow.com Sep 4 '11 at 2:13

This question came from our site for professional and enthusiast programmers.

4 Answers

I don't think you can find anything other than "array" if you want random access power. "Hash" could be it but using "hash" for saving shots doesn't seem to be right. I would stick to "array" but change the way of finding empty or inactive slots.

The way I used for my game is

  1. Define one indexFirstEmpty pointing to the first empty slot.
  2. Insert a new shot into the first empty slot and increase indexFirstEmpty .
  3. Delete a dead shot by swapping it with the last valid shot ( slot[indexFirstEmpty - 1] ) and decrease indexFirstEmpty. Don't forget to check valid range and self swapping.

With this way, you don't have to iterate the array to find an empty slot. This works because I don't care the order of shots in the array as long as they are partitioned correctly. If you want to keep the order of shots, you need a different way but it will be slower than the one I suggested. Good Luck!

share|improve this answer
    
How do you know it will be slower if you don't know what it is? –  quasiverse Sep 4 '11 at 1:42
    
Because it will require more work to keep the order. no? –  young Sep 4 '11 at 1:58
add comment

This is similar to young's answer but allows you to keep indexes to items and ensure they do not move (ie if you insert an item into position i, it will always be i until you delete it). Note this is similar to the answer described in this question.

  1. Keep an index to the last empty slot.
  2. When you delete an item, push it's index onto a stack, queue or linked list
  3. To get the next value, check if the s/q/ll is empty. If so, allocate the last empty slot as indicated by the index and increment the index. Otherwise, pop off the top value of the s/q/ll and allocate that.
share|improve this answer
    
It will not keep the order as you could insert new shot in the middle of the list. –  young Sep 4 '11 at 1:57
    
My idea of "order" is different from yours then. I will edit it to make it more clear –  quasiverse Sep 4 '11 at 2:03
    
stack is best for the available elements; its O(1) to add to it or remove from it. Further, such a stack is easily implemented as a singly linked list. Finally, it's possibly to store this list using the available elements themselves; either re-purpose an existing attribute (they're not in use, if they're on the free list), or add an attribute to maintain the list. –  JustJeff Sep 4 '11 at 2:32
    
A linked list sounds fairly horrible to use for a stack. A resizable array has the same algorithmic properties and better constant properties. –  user744 Sep 5 '11 at 3:43
add comment

Can you move stuff around in your array? Something I've done in the past to keep items packed (when the exact sequence is irrelevant), is whenever you delete something out of the middle somewhere, relocate the last element of the array into the empty slot. This keeps the storage tight, so you can always add a new element at the end in O(1) time, without worrying about all kinds of holes.

Another thing you can do is add a field to the struct (assuming your array is an array of structs) to implement a singly linked list for the "empties" in the array, in this case, the new field is the array index of the next element in the list. Now, it's a singly linked list, but you use it like a stack; always add to/remove from the head end. You keep another int that indexes the first element in this free-elements list, so you can always allocate an empty slot in O(1). Whenever you free a slot, you set its next-element index to the current head of the free list, and change the head to index the just deallocated element.

share|improve this answer
add comment

All 3 suggestions sound pretty good. I am mostly inclined towards Young's and Quasiverse's answers (I think with a stack). JustJeff's answer is also quite interesting, and I might use that one for other type of entities.

On second thought I might not really need to keep track of the shots in exact order although the order-aware answers are still certainly useful.

Thanks a lot everyone! Unfortunately because the post was moved (honestly didn't know there was a whole game dev Stack site....!) I cannot pick any of the answers, sorry about that.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.