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.

For every game I've made, I just end up placing all my game objects (bullets, cars, players) in a single array list, which I loop through to draw and update. The update code for each entity is stored within it's class.

I've been wondering, is this the right way to go about things, or is a faster more efficient way?

share|improve this question
3  
I notice you said "array list", assuming this is .Net, you should upgrade to a List<T> instead. It's almost identical, except that a List<T> is type-strong and because of that, you won't have to type cast every time you access an element. Here's the doc: msdn.microsoft.com/en-us/library/6sh2ey19.aspx –  John McDonald Jan 18 '12 at 16:08

9 Answers 9

up vote 24 down vote accepted

There is no one right way. What you're describing works, and is presumably fast enough that it doesn't matter since you seem to be asking because you're concerned about the design and not because it's caused you performance issues. So it is a right way, sure.

You could certainly do it differently, by for example keeping a homogenous list for each object type or by ensuring everything in your heterogenous list is grouped together such that you have improved coherency for the code that is in-cache or to allow parallel updates. Whether you'd see any appreciable performance improvement by doing this is difficult to say without knowing the scope and scale of your games.

You could also further factor out the responsibilities of your entities -- it sounds like entities both update and render themselves at the moment -- to better follow the Single Responsibility Principle. This can increase the maintainability and flexibility of your individual interfaces by decoupling them from one another. But again, whether or you'd see a benefit from the extra work that would entail is hard for me to say knowing what I know of your games (which is basically nothing).

I would recommend not stressing too much about it, and keep in the back of your head that it might be a potential area for improvement if you ever notice performance or maintainability issues.

share|improve this answer

The answer is "yes, this is fine." When I worked on big iron simulations where performance was non-negotiable, I was surprised to see everything in one big fat (BIG and F-A-T) global array. Later I worked on an OO system and got to compare the two. Although it was super ugly, the "one array to rule them all" version in single-threaded plain old C compiled in debug was several times faster than the "pretty" multithreaded OO system compiled -O2 in C++. I think a bit of it had to do with excellent cache locality (in both space and time) in the big-fat-array version.

If you want performance, one big fat global C array is going to be the upper bound (from experience).

share|improve this answer

I can propose some compromise between general single list and separate lists for each object type.

Keep reference to one object in multiple lists. These lists are defined by base behaviors. For example, MarineSoldier object will be referenced in PhysicalObjList, GraphicalObjList, UserControlObjList, HumanObjList. So, when you process physics, you iterate through PhysicalObjList, when process damaging from poison - HumanObjList, if Soldier dies - remove it from HumanObjList but keep in PhysicalObjList. To make this mechanism working you need to organize automatic insertion/removing object when it's created/deleted.

Advantages of the approach:

  • typed organization of objects (no AllObjectsList with casting on update)
  • lists are based on logics, not on object classes
  • no problems with objects with combined abilities (MegaAirHumanUnderwaterObject would be inserted into corresponding lists instead of creating new list for its type)

PS: As for self-updating, you will meet problem when multiple objects are interacting and each of them depends on others. To solve this we need to affect object externally, not inside self-update.

share|improve this answer

As others have said, if it's fast enough, then it is fast enough. If you are wondering if there is a better way, the question to ask yourself is

Do I find myself iterating through all of the objects but only operating on a subset of them?

If you do, then that is an indication that you may want have multiple lists holding only relevant references. For instance if you are looping through every game object to render them but only a subset of objects need to be rendered, it may be worth keeping a separate Renderable list for only those objects that need to be rendered.

This would cut down on the number of objects you loop through and skips the unnecessary checks because you already know all of the objects in the list are to be processed.

You'd have to profile it to see if you are getting much of a performance gain.

share|improve this answer
    
I agree with this, I generally have subsets of my list for objects that need to be updated each frame, and I've been considering doing the same for objects that render. However when those properties can change on the fly, managing all of the lists can be complex. When and object goes from being renderable to non-renderable, or updateable to non-updateable, and now you're adding or removing them from multiple lists at a time. –  Nic Foster Jan 18 '12 at 19:16

It depends almost entirely on your specific game needs. It can work perfectly for a simple game, but fail on a more complex system. If it's working for your game, don't worry about it or try to over engineer it until the need arises.

As for why the simple approach may fail in some situations, it's hard to summarize that in a single post, since the possibilities are endless and depend entirely on the games themselves. Other answers have mentioned for instance that you might want to group objects sharing responsibilities together into a separate list.

That's one of the most common changes you might be doing depending on your game design. I'll take the chance do describe a few other (more complex) examples, but remember there are still many other possible reasons and solutions.

For starters, I'll point out that updating your game objects and rendering them may have different requirements in some games, and therefore need to be handled separatedly. Some possible problems with updating and rendering game objects:

Updating Game Objects

Here's an excerpt from Game Engine Architecture which I would recommend reading:

In the presence of inter-object dependencies, the phased updates technique described above must be adjusted a little. This is because inter-object dependencies can lead to conflicting rules governing the order of updating.

In other words, in some games it's possible for objects to depend on each other and require a specific order of updating. In this scenario, you might need to devise a more complex structure than a list to store objects and their inter-dependencies.

enter image description here

Rendering Game Objects

In some games, scenes and objects create a hierarchy of parent-children nodes and should be rendered in the correct order and with transformations relative to their parents. In those cases, you might need a more complex structure like a scene graph (a tree structure) instead of a single list:

enter image description here

Other reasons might be for instance, using a spatial partitioning data structure to organize your objects in a way that improves the efficiency of performing view frustum culling.

share|improve this answer

I've used a somewhat similar method for simple games. Storing everything in one array is very useful when the following conditions are true:

  1. You have a small number or known maximum of game objects
  2. You favor simplicity over performence (i.e.: more optimized data structures such as trees aren't worth the trouble)

In any case, I implemented this solution as a fixed-sized array that contains a gameObject_ptr struct. This struct contained a pointer to the game object itself, and a boolean value representing whether or not the object was "alive".

The purpose of the boolean is to speed up creation and deletion operations. Instead of destroying game objects when they are removed from simulation, I would simply set the "alive" flag to false.

When performing calculations on objects, the code would loop through the array, performing calculations on objects marked as "alive", and only objects marked "alive" are rendered.

Another simple optimization is to organize the array by object type. All bullets, for example, could live in the last n cells of the array. Then, by storing an int with the value of the index or a pointer to the array element, specific types could be referenced at a reduced cost.

It should go without saying that this solution is not good for games with large amounts of data, as the array will be unacceptably large. It is also not suitable for games with memory constraints that prohibit unused objects from taking up memory. The bottom line is that if you have a known upper limit on the number of game objects you will have at one point in time, there is nothing wrong with storing them in a static array.

This is my first post! I hope it answers your question!

share|improve this answer
    
first post! yay! –  Tili Jan 18 '12 at 17:06

You say single array and objects.

So (without your code to look at) I'm guessing they're all related to 'uberGameObject'.

So maybe two problems.

1) You may have a 'god' object - does tonnes of stuff, not really segmented by what it does or is.

2) You iterate through this list and casting to type? or unboxing each. This has a big performance penalty.

consider breaking up different types (bullets, bad guys, etc) into their own strongly typed lists.

List<BadGuyObj> BadGuys = new List<BadGuyObj>();
List<BulletsObj> Bullets = new List<BulletObj>();

 //Game 
OnUpdate(gameticks gt)
{  foreach (BulletObj thisbullet in Bullets) {thisbullet.Update();}  // much quicker.
share|improve this answer
    
There's no need to perform type casting if there's some sort of common base-class or interface that has all the methods that will be called in the update loop (eg. update()). –  bummzack Jan 19 '12 at 8:21

Basically what you want to do is make up lists as you need them. If you redraw terrain objects all in one go, a list of just them could be handy. But for this to be worth while you'd need tens of thousands of them, and many 10,000's of things that are not terrain. Otherwise perusing your list-of-everything and using an "if" to pull out terrain objects is plenty fast enough.

I've always needed one master list, regardless of how many other lists I've had. Usually I make it a Map, or keyed table, or dictionary, of some sort so I can randomly access individual items. But a simple list is a lot simpler; if you don't randomly access game objects you don't need the Map. And the occassional sequential search through a few thousand entries to find the right one won't take long. So I'd say, whatever else you do, plan to stick with the master list. Consider using a Map if it gets big. (Though if you can use indexes instead of keys, you can stick with arrays and have something a lot better than a Map. I always ended up with big gaps between index numbers, so I had to give it up.)

A word about arrays: they are unbelievably fast. But when they get up around 100,000 elements they start to give Garbage Collectors fits. If you can allocate the space once and not touch it afterward, fine. But if you are continually expanding the array, you are continually allocating and freeing large chunks of memory and are apt to have your game hang for seconds at a time and even fail with a memory error.

So faster and more efficient? Sure. A Map for random access. For really large lists, a Linked List will beat an array if and when you don't need random access. Multiple maps/lists to organize the objects in various ways, as you need them. You could multi-thread the updating.

But it's all a lot of work. That single array is fast and simple. You can add other lists and things only when needed, and you probably won't need them. Just be aware of what can go wrong if your game gets big. You might want to have a test version with 10 times as many objects in as in the real version to give you an idea of when you are headed for trouble. (Only do this if your game is getting big.) (And don't try the multi-threading without giving it a lot of thought. Everything else is easy to get started with and you can do as much or as little as you like and back off any time. With multi-threading you'll pay a big price to get in, the dues for staying in are high, and it's hard to get back out.)

In other words, just keep doing what you're doing. Your biggest limit is probably your own time, and you are making the best possible use of that.

share|improve this answer
    
I really don't think a Linked List will outperform an array at any size, unless you often add or remove stuff from the middle. –  Zan Lynx Jan 18 '12 at 16:32
    
@ZanLynx: And even then. I think the new runtime optimizations help arrays a lot--not that they needed it. But if you allocate and free large chunks of memory repeatedly and rapidly, as can happen with big arrays, you can tie the garbage collector up in knots. (The total amount of memory is a factor here too. The problem is a function of size of blocks, frequency of free and allocate, and available memory.) Failure occurs suddenly, with the program hanging or crashing. Usually there is lots of free memory; the GC just can't use it. Linked lists avoid this problem. –  RalphChapin Jan 18 '12 at 20:07
    
On the other hand, linked lists have significantly higher likelihood to cache miss on iteration due to the fact that the nodes are not contiguous in memory. It's not nearly so cut-and-dry. You can alleviate the reallocation issues by not doing that (allocating up front if possible, because it often is) and you can alleviate the cache coherency issues in a linked list by pool allocating the nodes (although you still have the follow cost of the reference, it's relatively trivial). –  Josh Petrie Jan 18 '12 at 22:42
    
Yes, but even in an array, aren't you just storing pointers to objects? (Unless it's a short-lived array for a particle system or something.) If so, then there will still be plenty of cache misses. –  Todd Lehman Jan 19 '12 at 7:29

It is acceptable, although unusual. Terms like "faster" and "more efficient" are relative; typically you would organize game objects into separate categories (so one list for bullets, one list for enemies, etc.) to make the programming work more organized (and thus more efficient) but it's not like the computer will loop through all the objects faster.

share|improve this answer
1  
True enough in terms of most XNA games, but organizing your objects can actually make iterating through them faster: objects of the same type are more likely to hit the instruction & data cache of your CPU. Cache misses are expensive, especially on consoles. On the Xbox 360 for example, an L2 cache miss will cost you ~600 cycles. That's leaving a lot of performance on the table. This is one place where managed code has an advantage over native code: objects allocated close together in time will be close in memory as well, and the situation improves with garbage collection (compaction). –  Chronic Game Programmer Jan 25 '12 at 6:16

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.