Back to General and Gameplay Programming

The object list problem

virvelvinden · 2009-02-24T12:51:25

Hi, Today I began writing something that after a while, started to look like this: http://www.gamedev.net/community/forums/topic.asp?topic_id=487312 That is, from a big object vector that holds all (ALL) objects, I create smaller vectors containing pointers to the big vector. The smaller vectors would be called "objectsToRender", "staticObjects" and so on. After a while, i figured this could lead to loads of nasty pointer errors, and judging from the answers in the above thread this approach is indeed a bad idea. I really like the theory of this method though, any tips on how to make a safe implementation? Or are there other design approaches that you recommend? Thanks for any help.

General and Gameplay Programming Programming Unity

Started by virvelvinden February 21, 2009 04:07 PM

15 comments, last by virvelvinden 15 years, 2 months ago

virvelvinden

133

Author

February 22, 2009 02:41 PM

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!

NotAYakk

876

February 22, 2009 05:10 PM

template<typename T>struct VectorElementPointer {  VectorElementPointer(): source(), index() {}  VectorElementPointer(std::vector<T>& source_, int index_): source(source_), index(index_) {}  std::vector<T>* source;  int index;  T& operator*() { return source->at(index); } // throws  T const& operator*() const { return source->at(index); } // throws  T* operator->() { return &**this; }  T const* operator->() const { return &**this; }  VectorElementPointer& operator+=(int other) { index+=other; return *this; }  VectorElementPointer& operator-=(int other) { index-=other; return *this; }  VectorElementPointer& operator++() { ++index; return *this; }  VectorElementPointer& operator--() { --index; return *this; }  VectorElementPointer operator++(int) { VectorElementPointer tmp = *this; ++*this; return tmp; }  VectorElementPointer operator--(int) { VectorElementPointer tmp = *this; --*this; return tmp; }  VectorElementPointer operator+(int other) const { VectorElementPointer tmp = *this; tmp+=other; return tmp; }  VectorElementPointer operator-(int other) const { VectorElementPointer tmp = *this; tmp-=other; return tmp; }  bool operator==(VectorElementPointer const&other) const { assert(Comparable(*this, other); return index == other.index && source == other.source; }  bool operator< (VectorElementPointer const& other) const { assert(Compariable(*this, other); if (source != other.source) return source < other.source; return index < other.index; }  bool operator> (VectorElementPointer const& other) const { return (other < *this); }  bool operator!=(VectorElementPointer const& other) const { return !(*this == other); }  bool operator>=(VectorElementPointer const& other) const { return !(*this < other); }  bool operator<=(VectorElementPointer const& other) const { return !(*this > other); }};

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?

Hussain Hani

120

February 22, 2009 08:34 PM

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*/);

danien

138

February 23, 2009 02:12 AM

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.

Cabal Entertainment Software Jobberwokky.com - Jobs in creative industries in Asia Pacific

ToohrVyk

1,596

February 23, 2009 03:53 AM

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.

Blog — Facebook

haegarr

7,408

February 24, 2009 02:50 AM

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.

virvelvinden

133

Author

February 24, 2009 12:51 PM

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

The object list problem

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

The object list problem

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines