Video game entity storage and structures

Question

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.

Answer 1

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!

Answer 2

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.

Answer 3

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.