The object list problem

Hi Virvel,

This does not sound like a good idea -- in fact it sounds like a disaster that should be avoided at all costs.

I would be happy to help you figure out an alternative design approach, but I'm not actually sure what you are trying to accomplish?

1. If the lifetime of your objects is not obvious, use smart pointers to keep the objects alive until you don't need them anymore.

2. Remember that if you need some data to die along with an object (such as a sprite registered with the rendering system), you can make that data a member so that the destructor eliminates it.

3. Do you really need an array of all objects?

Quote:

Original post by yahastu Hi Virvel, This does not sound like a good idea -- in fact it sounds like a disaster that should be avoided at all costs. I would be happy to help you figure out an alternative design approach, but I'm not actually sure what you are trying to accomplish?

Yes, my first post was a litle bit unclear... sorry about that!

Here's the deal:

* My game will have different kinds of objects, such as sceneryObjects, playerObjects, physicObjects and so on.

* sceneryObjects and playerObjects will be rendered, ordered by their z-value. This is why I would like all renderable objects to be in the same list.

* playerObjects and physicObjects will be updated.

* Therefore, playerObjects has to be booth rendered and updated, and this is were i'm stuck... I have to sort the objects to be rendered based on some value, and also iterate through them and update them. Of course, in the draw loop I could check if the current object is a updateable object and if so, update, but this seems ugly. There has to be a "right" way to solve this!

ToohrVyk: Thanks for the link, i will look into it. Smart pointers seems a bit overkill for now though, and pointers to elements in a vector will almost certinaly cause problems, right?

edit: The segregation link is just what i'm talking about, thanks again!
edit2: I still have to order all renderable objects by their z-value, is it possible to just create a renderList, and push_back every new sceneryObject and playerObject that I create?

[Edited by - virvelvinden on February 22, 2009 4:25:46 AM]

This is similar to the relationship between databases and indices. An index is a particular ordering of the entries in the database. You can have multiple indices for a database, with each index representing a particular ordering.

In this case, you have one vector (or any container) that "owns" the objects. This vector controls the lifetime of these objects.

You can have one vector to serve as an update order index, holding pointers (or smart pointers) sorted by update order, another vector sorted by rendering order and so on. When you need to perform a particular operation (updating, rendering, etc), you simply iterate over the desired index to get the right order.

However, you need to ensure that the database is the only place where objects are created and destroyed, and whenever it changes, all the index vectors are updated (which could get expensive if you modify the database often).

For a broader and more complex discussion, search the forum for "component architecture".

Look at a resource system. What is it if not an unordered collection of resources of some type? And furthur, its solely purpose is to find a resource of a specific type and identifier quickly, or to construct or load it if it isn't available yet. It isn't interested in whether the resource is renderable or whatever. Not every and all objects are also resources, but many are. And I have several collections, namely one for each main kind of resource (so there isn't actually a collection of _all_ objects).

Integrating a resource as part of the current scene (i.e. a specific SceneGraph) means to create a specific SceneNode that refers back to its resource. This is a kind of instancing.

Animating the scene means that objects are altered, so that dependencies must be re-considered before rendering can take place. For this purpose a dependency graph is used, and the nodes of that graph refer back to the belonging objects where necessary.

Rendering a scene means to find all visible (i.e. not culled) objects and to create a couple of RenderingJob instances that populate a rendering queue. Such a rendering job obviously refers back to some renderable data stored with the objects and/or resources.

In summary, there is a couple of specific data structures (actually not simple arrays) that refer to instances in other data structures. Some of the structures have a long lifetime (e.g. the resource managers live very long) while others have a short one (e.g. the rendering queue). Some structures would live short normally but are more efficiently implemented by considering coherence (e.g. for collision detection).

All this works well by considering lifetimes and using smart pointers. In fact I second all points that ToohrVyk has made above.

Quote:

Original post by danien In this case, you have one vector (or any container) that "owns" the objects. This vector controls the lifetime of these objects. You can have one vector to serve as an update order index, holding pointers (or smart pointers) sorted by update order, another vector sorted by rendering order and so on. When you need to perform a particular operation (updating, rendering, etc), you simply iterate over the desired index to get the right order. However, you need to ensure that the database is the only place where objects are created and destroyed, and whenever it changes, all the index vectors are updated (which could get expensive if you modify the database often).

Exactly. But what if I used this approach (with one big object list, make it big so that it never has to change its memory allocations) and only deleted elements in it on special occasions, such as level changes? It would still be possible to add elements to it, as the new elements would go last in the list and wouldn't mess upp the pointers for the objects already in the list.

I should probably point out that the object classes will be really small, which will make the object list stay at a reasonable size.

It still feels a bit risky though, but I think I will give it a shot!

haegarr: I dont know, but trees and nodes and what not seems to advanced for this game, which will be a quite simple one.

Quote:

Original post by ToohrVyk 1. If the lifetime of your objects is not obvious, use smart pointers to keep the objects alive until you don't need them anymore. 2. Remember that if you need some data to die along with an object (such as a sprite registered with the rendering system), you can make that data a member so that the destructor eliminates it. 3. Do you really need an array of all objects?

QFE.

Quote:

Original post by ToohrVyk 1. If the lifetime of your objects is not obvious, use smart pointers to keep the objects alive until you don't need them anymore. 2. Remember that if you need some data to die along with an object (such as a sprite registered with the rendering system), you can make that data a member so that the destructor eliminates it. 3. Do you really need an array of all objects?

I read through the article and agree pretty much with everything you wrote in it, but I still wonder how you would facilitate interaction between different types of objects. I'm just going to pull a couple of quotes to help better illustrate my question:

Quote:

My advice is pretty simple: strive to keep one list per type of object. In your average video game, you would have a list of projectiles flying around, a list of AI-controlled opponents, and a player-controlled character.

Quote:

The only dupicated code is the traversal of the various lists (since instead of traversing a single list, now several lists must be traversed in order to reach all elements), and that code is not only very small, but also fairly easy to factor out (for instance, by implementing an iterator that traverses several containers in order).

Say then for instance you need to perform collision detection and that bullets, opponents, and the player character are the only types of "collidable" objects (say, for instance, objects inheriting from some hypothetical WithCollision class like in your examples) in your game world. Now simply iterating over just the opponent objects won't perform a full collision detection check as you miss potential collisions with bullets and the player. Do you just (in the code) make whoever is performing the collision detection know which lists it will have to go through each time it performs its checks, ie, is this what is meant by the second quote? That seems to most sensible to me, although I haven't really thought of any potential pitfalls to this.

Also, in your design, who is to maintain these different lists, the engine or the game (assuming the game is a client to an engine and utilizing its services)? If the engine, then you make it aware of the various types of objects that exist in a specific game, which as far as I can tell hampers reuse. Getting around this wouldn't be too hard I'd imagine -- you could either:

1) provide some interface to the engine that allows the game to establish new object lists keyed off some identifier and when it came time for the game to tell the engine to do various tasks (e.g., engine->handle_collisions()), you pass it some list of identifiers telling the engine which of its registered lists to iterate over

2) make the lists managed by the game and change the interface(s) of the engine so that the various operations take in as argument(s) the lists that that they need to operate over.

I personally prefer 2 a little bit more, but I'm just interested in hearing yours and others opinions on design in this case.

One thing I didn't see mentioned, pretty sure you shouldn't keep a pointer to anything inside an STL vector, because if it changes size pointers into it will become invalid. Maybe use an integer index instead. Or I suppose if you reserve() vector size then it would be ok?

Personally, I agree keeping different objects in different lists is more useful and convenient. For example:

- Ship List
- Projectile List
- Asteroid List
- etc...

To do collision I have function that collides a list of one object type to another. For example:

CollideShipsAsteroids(list shipList, list asteroidList)
{
// collide ships to asteroids
}

Nothing fancy, just a simple way to do it.

Quote:

Original post by EJH One thing I didn't see mentioned, pretty sure you shouldn't keep a pointer to anything inside an STL vector, because if it changes size pointers into it will become invalid. Maybe use an integer index instead. Or I suppose if you reserve() vector size then it would be ok?

Yes, I just made a quick implementation of this design and set the capacity to 10000 or something... Which should work fine, since I know I will never have more than 10000 objects.

...It's nice being the only team member sometimes :)

It works fine so far, btw!

There we have it. It is a pointer into a vector. It throws if you try to access out of range elements (bad user, no cookie). Pointer arithmetic works on it. If the vector reallocates, it works.

You can, of course, do better: some kind of insert-ordered collection (if you need that) with persistent iterators, and shared pointers. I mean, do you really need fast random access when you already don't have a handle to an element?

First why not have two vectors instead of one??
one holds "players"
one holds "physicObjects"

second, if your problem is to draw players and phydicObject according to their z-order, then you can design a function that order them out =) similar to the infamous swap function like so:

for(int i = 0; i < _v_players.size(); ++i)	for(int j = i+1; j < _v_players.size(); ++j)		if(_v_players[j]->get_z_order() > _v_players->get_z_order())			//Implemet assignemt operator for "Player" class for the sake of 			//swap function			swap_players(_v_players[j], _v_players);//Now after the players are ordered, simply draw themfor(int i = 0; i < (int)_v_players.size(); ++i)	_v_players->draw(/*arguments*/);

Quote:

Original post by virvelvinden Exactly. But what if I used this approach (with one big object list, make it big so that it never has to change its memory allocations) and only deleted elements in it on special occasions, such as level changes? It would still be possible to add elements to it, as the new elements would go last in the list and wouldn't mess upp the pointers for the objects already in the list.

If you can afford to keep all the objects that are created and destroyed over the course of the level in memory, then this will simplify things by using lazy deletion - instead of destroying objects immediately, you can just mark them as destroyed, to be really cleaned up later.

Quote:

Original post by virvelvinden I should probably point out that the object classes will be really small, which will make the object list stay at a reasonable size. It still feels a bit risky though, but I think I will give it a shot!

There are definitely risks and costs involved in keeping separate lists, mainly keeping them in sync. There is the cost of updating multiple lists when you modify the database list. There is the risk of other programmers not knowing or remembering to update the index lists or trying to delete objects from index lists (although wrapping up the object management subsystem and lists would prevent this).

Object ownership, management, and updating (and other real-time processing like rendering) has many possible architectural designs. It all depends on your needs and goals. A simple application used only by yourself, which is what I based my suggestions on, should implement a relatively simple solution that is good enough for what you need.

Other goals would require more complex designs. e.g, scalability through multithreading could be better served by multiple lists of objects that can be processed separately; flexibility and modularity could be achieved by breaking objects down into components, then updating components using appropriate subsystems.

You should check out http://gamearchitect.net/. It highlights some issues relevant to this discussion.

Quote:

Original post by romer Do you just (in the code) make whoever is performing the collision detection know which lists it will have to go through each time it performs its checks, ie, is this what is meant by the second quote? That seems to most sensible to me, although I haven't really thought of any potential pitfalls to this.

In the simplest version of the design, the collision handling system would just know which lists should be traversed because these lists are explicitly named in the code—that is, after all, a "game rule" that deserves to be named in the code in the same way that your formula for computing damage is named in the code.

In a slightly more complex version, an engine could provide functions for detecting collisions between two objects, or between objects in two groups. In that case, I would use either polymorphism or composition to have the game give the groups to the engine.

Quote:

If the engine, then you make it aware of the various types of objects that exist in a specific game, which as far as I can tell hampers reuse.

Why not? Of course, if you're using a mechanism as crude as inheritance or object-oriented polymorphism, you're in for some serious trouble as you are unable to notify your engine about your game types and end up restricted to your game inserting only limited functionality into the engine.

On the other hand, if your engine is based on module-based polymorphism (if you're not familiar with Objective Caml modules, think "namespace templates") inserting a new type of objects, with a corresponding list, into the engine is a breeze, because the engine is just a functor that you can instantiate once or several times with various lists.

Quote:

Original post by virvelvinden haegarr: I dont know, but trees and nodes and what not seems to advanced for this game, which will be a quite simple one.

The point I wanted to make is that having a "pointer nightmare" is a usual way (however, I wouldn't name it a nightmare at all). The examples I've shown are concepts used in games/engines nowadays a lot.

Which data structures and mechanisms are used in the end should simply depend on the problem to solve. Also simple games may have the need for e.g. collision detection, and hence may e.g. use a quad-/octree to solve this problem.

This is an interesting and important subject, and I've learnt a lot from this thread. I've also found a solution that I'm happy with, all thanks to you!

rating++;

thanks again