Objects in a game

The array approach would be fine if you want a fixed number of objects, its probably necessary if you're developing for an old micro or some sort of low-resource embedded platform. Otherwise, use a linked list. I mean, what happens if you want to dynamically create new objects? Like an object that creates others, or a trap that instantiates objects?

Actually, on most systems (including embedded systems), your best bet is to use lists, rather than arrays.

Usually, their memory overhead for the list is negligible when compared to the average size of data (and equivalent to that of an array in most cases), and the sequential access overhead is in the same pool as the array overhead.

Besides, maybe it's just me, but I don't see any advantages an array would have over a correclty implemented list system (in my case, usually a singly-linked list with managed memory and an auxiliary list containing "free" nodes) in this particular situation. (Why would you need random access?)

Use the best of both worlds.

Create a linked list, and when something is killed, flag it as dead. When creating a new list, check if the list is full of alive entities. If it is, add a new object. Otherwise, reuse the old one.

Grozzler, maybe having dead objects floating around is the best an array can provide, however I don't think this is good enough to be kept for a list.

The good thing with a list is the fact that you can keep two lists at any time : a list of alive objects, and a list of dead objects. And because they're lists, moving an object, depending on its state, from one to the another is constant-time.

Using this method, you will never have to run and check through all possible elements every time you want to update the alive element(s), or when you want to add a new element, which is precisely why using a list is preferable to an array.

Complexity-wise, where m is the number of alive objects and n is the total number of objects :

Best-of-both-worlds:
Insertion: O(n)
Removal: O(1)
Update: O(n)

Two-list-system:
Insertion: O(1)
Removal: O(1)
Update: O(m)

What would be the point of having an alive list and a dead list? You'd use twice the new and deletes, which is the bane of linked lists to begin with.

I really don't see how an if on every object in your list would slow your program down at all, but you'd save 100s of potential new and delete calls.

Grozzler, it looks like you don't understand my method (which could be linked to the fact that I'm not explaining it well enough ;) )

The parts of that method go as follows:

Insertion :
If the "dead" list is empty, create a new node (or page of nodes) and add them all to the "dead" list.
Take the first element of the "dead" list, fill it with information from the caller, and add it to the "alive" list.

Update :
Run through the "alive" list and call the update functions on the objects. If an object is marked as "dead", remove it.

Removal :
Remove the object from the "alive" list, clean it (if necessary), and add it to the front of the "dead" list for further use.

So deletion will only be performed when the entire list is deleted (once in the program's lifetime, hopefully), and new objects are created only when the number of objects exceeds the number of objects created so far. Besides, you can allocate pages of nodes instead of single nodes (in a deque fashion) to further reduce the amount of "new" calls.

So in the end, my method uses fewer new calls, fewer delete calls, and fewer if() branches.

Ap: this method will use twice the memory of a list-based method, and have a far greater complexity when removing items from the "live objects" array.

Remember that if you absolutely want to avoid runtime allocation of objects, you can create an array of list nodes, add them all to the "dead" list, and use the method I presented above (but throwing an exception when the "dead" list is empty, instead of allocating new nodes). Actually, this is the exact method being used in my current project (embedded game).

I must really be missing something.

Insertion (Monster Created):
Your Method: You have 1 new call (new node, not new monster) and 1 delete call (delete node, not delete monster) (99% of the time, depending on if the dead list is full).

My Method:: I search my list. If there hasn't already been a monster killed, I add a new node and a new monster (2 new calls). If a monster has already been killed (and isn't used again already), I have 0 news and 0 deletes.

Update (Monster Updating):
Our Method: We both have an if for every monster to check if its alive or dead, just for different purposes.

Removal (Monster Killed):
Your Method (Trigged from Update): You set a new spot in the death list, and delete from the alive list (both nodes, not monsters).

My Method: I call SetDead() and do nothing.

I really just don't see how I lose, I have way less new and delete calls and we both have to check dead status during the update.

If I've missed something (and I'm guessing I have), please fill me in.

Quote:

Original post by GroZZleR I must really be missing something.

Hopefully we'll be able to clear this out :)

It looks that you assume the following : "insert in a list <=> allocate a node", "remove from a list <=> delete a node". This is wrong in my case: when I say "move the node from one list to the other", I don't delete the node in one list, and allocate it in the other: I move it. Here's a short code snippet from my insertion method:

if(unused==0){enlarge( );}Ozone::QueueManager::Basic<T>::TQMBContainer<T>*temp=unused;unused=unused->next;temp->next=first;temp->target=added;first=temp;

first and unused are the pointers to the heads of the "alive" and "dead" lists, respectively (nodes are of type Ozone::QueueManager::Basic::TQMBContainer). The contents of the node (of type T) is node->target. node->next is a pointer to the next node in the list.

The above code performs exactly that: it takes the first unused node (if any), fills it up with data, and makes it be the first used node instead.

As you can see from the above, if there are unused nodes left, no memory allocation is performed, the nodes are simply moved from one list to the other.

The same occurs (but in an opposite direction) when an object dies: its node is cleaned, then moved back to the unused list instead of being deleted.

So in the end, we both allocate memory in the same case: where there are no free "dead" monsters/nodes to be used.

This is dynamite stuff. Thanks for the replies.

The dual list system sounds good, but I was wondering what would be the procedure for something where thousands or more objects could be created and killed in a short space of time, e.g. a poor example would be rockets or bullets (poor because you could just reuse destroyed bullets and fire them all over again.. but cant think of anything else right now). What would you do for memory management in this case? Not deleting the objects and just adding them to a "dead" list would mean building up a massive list of objects. Would you periodically trim down (i.e. delete all the elements in) the list when it gets over a certain size? or perhaps only add certain kinds of objects to the "dead" list and use delete on others? or should you make it so that "dead" objects can be filled with new variable values and reused as a new "alive" object?

Keep it coming!

For fire and bullets I would use a static list. Keep the "projectile" objects seperate from the objects that don't need to be created and deleted in mass every frame.

I'm excited about the answer to this, so I'm going to add my own question too.

Wouldn't each bullet as an object be a problem as a linked list? Especially when you empty a chain gun on some bad guy...each of those bullet "objects" may only exist for less than a half a second, so that's a lot of new/delete calls. I'd almost guess you'd handle bullets abstractly, unless it was a rocket launcher or a sniper rifle.

Sorry my mind was gone at the first post, when I wrote "static list" I meant to write "fixed-length array".... (chuckle) sorry for the confusion.

I would use the array precisely to avoid multiple new and delete calls. Also - Random access is good for projectiles while checking collissions and the likes.

Nuget5556 : I... fail to see how random access comes in handy when detecting collisions.

I mean, either you'll run through the entire set of objects, in which case you only need sequential access, or you'll use a more sophisticated collision detection method, that selects the objects that could collide together. But that selection could use pointers to objects instead of array indices anyway, so I don't think this would need random access either.

But of course, there may be cases I didn't envision :)

Also, over the course of this thread, we've come to the conclusion that using a certain implementation (with two lists), it was possible to keep the advantages of a list (O(1) removal/insertion) without doing any new/delete calls (other than those same that would be needed to increase the size of the array anyway), so using an array only to avoid new/delete calls is not a good idea.

Dangerdave: if there was a moment where there was an insane amount of objects flying around, you can almost be sure the same thing could happen again at least once.

However, you could work with something like pre-allocation: whenever you reach a certain area in your level, you compute the probable amounts of objects each part will need (chaingunner monsters might need lots of bullet-objects, destructible objects might need spark-objects), and whenever your engine has some time on its hands, allocate a bit of memory so you get close to the expected amount, or deallocate a bit of memory if you had too much. (By allocate, I mean create new nodes+objects, and adding them to the dead list, and by deallocating, I mean deleting pages full of dead objects).

But still, remember that unless you're talking about millions of objects, usually the size of such data structures in memory is completely negligible when compared to textures, for instance (a single 256*256 texture amounts to 65536 dwords, which at an average of 20 dwords per object makes it equivalent to a list of 3300 objects), so IMHO you shouldn't need to bother about trimming lists under 5k-10k objects.

Serratemplar: we've discussed before a list-like data structure that can manage a lot of object births/deaths without allocating much data (if any), simply by keeping dead objects around so they can be reused whenever an object birth happens.

In the case you mentioned above (with the chaingun), there would be a maximum of, say, 10 alive bullets in the world at any time (because of their speed), so there would simply be 10 generic bullets moving in between the "alive" and "dead" lists without any new/delete's happening.

May you not tap to attack.