Hetergeneous Collections of objects in a List

Greenbean

Ahem, quite a mouthfull, but I'll conitinue anyway just incase someone knows this stuff.

You've got a collection of objects, they all derive from a base class - lets say they are employee (baseclass), manager, cashier and floorman.

Now you stick all these in a list which accepts employee objects (a cool thing you can do in oo design). Then you want to iterate through the list and call a function "calculatePay()" on all of them. This is a virtual function in the employee class, with a standard default implementation, and of the subclasses also derive their own version of calculatePay().

Now typically if you ask cashier in this case to do the "calculatePay()" function it will perform its local version, but it seems in the list that it performs the base class version only Pretty useless then, perhaps its because the list is declared as a list of employee objects. Now I do have extra tags in there that can help me identify the class at run time (ie each object holds an enumerated variable that says its "employee", "cashier" etc. So perhaps theres a way of looking at object at runtime, asking what its tag is and doing some sorta funky casting ie:

if(i->getTag() == CASHIER)
(cashier*)i->calculatePay();
else
i->calculatePay();
//which would be the default base class, seemingly regardless if the function is virtual or not

i being the current object in the list which we are examining.

Any thoughts?

satchmo

Yeah you've got the right idea, does that code work? The only possible problem I can see is that I think the -> operator has a higher priority than type-casting, so it might perform the method call before casting the object. You can fix this with good old-fashioned brackets, ie

((cashier*)i)->calculatePay();

and that should work.

Greenbean

Ooops, this is just a little more tricky than I just mentioned.
'i' isn't the object, its the iterator in the list. So it can be imagined as a reference to the object which is a cashier.... soooo...

((cashier)*i).calculatePay(); // we deference the iterator to point to the actuall object... I may be wrong here

is the code I need. But this just simply tells me that I can't convert an employee object to a cashier object, which is correct - but the object is actually a cashier object in the first place. Ugh I hate pointers. Fact is, I think I'm going way down the wrong road.

Is there any reason why I couldn't just call the virtual function calculatePay() exactly the same for all the objects:

i->calculatePay()

and expect it to use the correct version for each class?

satchmo

Well, no, I don't think so, but I thought you said above that this didn't work? Maybe it'd be easier if you posted up the code for your list. How are you creating the objects? It should be something like
Employee* e=new Cashier();
and then calling e->calculatePay() would automatically call the Cashier's calculatePay method, but it could still be stored in an array/list of Employee objects.

Greenbean

hmmm I haven't been creating objects like you were saying.... I just instanciated them normally and threw them in. Rather than throwing up code (which isn't actually employee, cashier, they were just examples) I'll give your way an attempt first.

Greenbean

Ok, I give up heres the code to peruse.

To outline, GameObject is the super class (the employee of this case) and SpaceShip is the subclass (the cashier of this case). The function that is being overriden is the:
void updateMovement(GameObject g);
function (the calculatePay() of this case). This takes a gameobject as a parameter for objects that use other objects to figure out their movments to use - ie a spaceship rotating around a, erm, tiger.

---

//The list code, standard template library list

typedef list<GameObject> GAMEOBJECTLIST;
GAMEOBJECTLIST::iterator i;
GAMEOBJECTLIST::iterator j; //two iterators on purpose


//Create an example object to rotate around

GameObject tigerMesh( "tiger.x",
D3DXVECTOR3( 0.0f, 0.0f, 0.0f),
D3DXVECTOR3( 0.0f, 0.0f, 0.0f),
createNewId());
gameObjectList.insert(gameObjectList.end(), tigerMesh);


//A spaceship to rotate around the tiger

GameObject* eagleShip=new SpaceShip();

eagleShip->setPath("eagleShip.x");
eagleShip->setPosition(5.0f, 0.0f, 0.0f);
eagleShip->setRotation(0.0f, 0.0f, 0.0f);
eagleShip->setId(createNewId());
eagleShip->setTargetId(tigerMesh.getId());
gameObjectList.insert(gameObjectList.end(), *eagleShip);

//Create some ground for clarity
GameObject ground( "plane.x",
D3DXVECTOR3( 0.0f, 0.0f, 0.0f),
D3DXVECTOR3( 0.0f, 0.0f, 0.0f),
createNewId());
ground.offsetPosition(0, -0.75f, 0);
gameObjectList.insert (gameObjectList.end(), ground);

for (i = gameObjectList.begin(); i != gameObjectList.end(); ++i)
{ i->updateMovement(getGameObject(i->getTargetId()));
}


//Ignore all the getTargetId, getGameObject stuff - all thats happening here is the correct gameObject is being passed to the updateMovement() function. Thats why there is a second iterator j around, so as to perform other actions on the list midway through a traversal of it by iterator i.

//Heres the GameObject declaration:

const int HEALTH = 100; //Full health
const int CDRADIUS = 10; // arbitrary choice

enum OBJECTTYPE{ GAMEOBJECT, SPACESHIP};

class GameObject : public D3DMesh
{
public:
GameObject();
GameObject(char *path, D3DXVECTOR3 iposition, D3DXVECTOR3 irotation, int iD);

virtual void updateMovement(GameObject object) {/*Do nothing by default*/;}

void setHealth(int h) { health = h; }
int getHealth() { return health; }

void setCDRadius(int r) { cDRadius = r; }
int getCDRadius() { return cDRadius; }

void setId(int iD) { id = iD;}
int getId() {return id;}
OBJECTTYPE getObjectType() {return objectType;}

void setTargetId(int iD) {targetId = iD;}
int getTargetId() {return targetId;}

void setUpdated(bool b) {updatedStatus = b;}
bool updated() {return updatedStatus;}

protected:

int cDRadius;
int health;
int id;
int targetId;
bool updatedStatus;
OBJECTTYPE objectType;
};

//And heres the SpaceShip declaration

enum MOVETYPE{ MOVETO, CIRCLE};

#include "GameObject.h"

class SpaceShip : public GameObject
{
public:
SpaceShip();
SpaceShip(char *path, D3DXVECTOR3 iposition, D3DXVECTOR3 irotation, int iD);
void updateMovement(GameObject object);
void setMovementType(MOVETYPE m) {movementType = m;}

private:
MOVETYPE movementType;
};


//With updateMovement implementation in the .cpp file looking like this:

void SpaceShip::updateMovement(GameObject object)
{
if (targetId == -1)
{
//do nothing, theres no target
}
else if (movementType == CIRCLE)
{
int circleRadius = object.getCDRadius() + 1; //choose the collision detection radius, plus 1
D3DXVECTOR3 objPosition = object.getPosition();

// use timeGetTime();
float turningRate = (float)timeGetTime(); //make a function for figuring out the
//turning rate with respect to time

setRotation(0.0f, sinf(turningRate), 0.0f);
setPosition(-5*sinf(turningRate),0.0f, 10-10*cosf(turningRate));
}

}

---

Now the code may be a pile of donkey's arse in places and please feel free to tell me how to improve it, but the main problem is in getting that updateMovement() function for SpaceShip to take place when its called on a SpaceShip object rather than calling the updateMovement function for GameObject. Perhaps the answer is blazingly obvious when you review the code?

satchmo

So what's happening when you try to run/compile that?

[edit]stupid suggestion removed[/edit]

Greenbean

Runs grand, except the spaceship isnt moving anywhere. Not that the movement function for the space ship is done well or anything, but I'm sure it should move in some way. Stepping through with the debugger and setting breakpoints in the SpaceShip's updateMovement() function shows that this part of the code doesn't get activated when the spaceship object is selected from the list and instead it steps through to the GameObjects updateMovement() function.

I'm stumped really, lack of experience with polymorphism - I think with arrays I'd seen this stuff work before - like in college tutorials - but arrays don't bare thinking for what I want to do - these gameobjects are fairly heavy pieces of data - each containing a mesh, textures and control data and I'm sure the list setup will become necessary for future operations (such as sorting the list for back to front rendering etc).

satchmo

I can't really see any problems, although I'm not really familiar with the STL lists - I find it's usually easier to just implement a list of your own that does exactly what you want.

What happens when you call eagleShip->updateMovement() directly? Stick some couts into both updateMovement functions, it's easier than setting breakpoints.

satchmo

I think I know why it isn't working, but I don't think you're going to like it.... :eek:

It would seem that STL templates don't take kindly to polymorphism. In fact they store the objects directly, and so bypass any advantages polymorphism might offer. This means that you're going to have to write your own GameObject linked list - it's not hard to do, and is probably a good idea in the long run anyway.

If you don't want to do this, a suggested solution can be found here, but I couldn't make heads or tails of it at this time of the morning.

Good luck, sorry I couldn't be of more help. Let us know how you get on....

Greenbean

Thanks, I'm not too sure about creating my own list... what exactly would that entail?

GameObjectList which takes game objects as its components; Create my own ordering/de-ordering of things, insert, remove all done with pointers, that sorta thing; And end up with it being able to handle the polymorphism correctly?

Where did you find that link though? Searching the web for documents and finding them like that is some skill. It discusses all the things I've been thinking and explains how they would or wouldn't work - with a sorry conclusion.

Thanks for the help jazz!

nucular

This is more of a workaround than a solution. I could probably write a decent polymorphic solution using templates but I don't have time at the mo.

This should put you on the right track anyway.

The problem is with the object contained within your list and therefore we need to move what changes in the list to a more suitable place.

The most obvious solution is to delegate the task to a helper object.

for example
class GameObjectHelper{

public:

virtual void updateMovement() == 0;


}

class SpaceShipHelper:public GameObjectHelper {

void updateMovement();

}


void SpaceShipHelper::updateMovement() {

// do spaceshipstuff

}

//in your main code
SpaceShipHelper myHelper;

eagleShip->setHelper(myHelper);

This gives the necessary level of indirection to your code and should most definitely not have any major impact on the performance of the code.

All this will really do is move the part of your code that needs to know about polymorphism to within the contained object rather than outside the container.

You could add the required polymorphism using a template version of the GameObject class which calls the required version based on it's initialisation routine.

The key to the idea above is to think in terms of 1 to 1 relationships.

There is probably a decent amount of work involved in this however it is probably more viable than the other solutions available.

If you have any questions I will do my best to answer.

good luck and I hope this is some help.

satchmo

Not a bad idea that.

If you do want to make your own linked list, it really isn't as hard as it sounds. In fact it's very simple, the only part that might be complicated is sorting it (if you feel that's necessary). Mergesort is one of the better solutions for this, you can find the algorithm easily through google.

Likewise, I could explain making linked lists here, but it's probably better if you find an explanation on the web somewhere - there's plenty of them out there, and diagrams make things much easier to understand. The advantage of this is that properly written, polymorphism will come built in, without any extra effort. Simply set each node to contain a GameObject object, and then store your new SpaceShip()s or new Missile()s or whatever there. Then you can loop through the list and simply call updateMovement() on each object.

If you get confused, we'll still be here...:)

Corinthian

Another approach would be to move the polymorphic call inside the function being called through your iterator

i.e.

class GameObject
{
// ... loads of stuff

// not virtual, to be called by the code looping through
// your iterator
void updateMovement()
{
// polymorphic call here
this->reallyUpateMove();
}

protected:
virtual void reallyUpdateMove() = 0;
};


Then implement reallyUpdateMove() in all your derived classes.

This would avoid having to have a parallel hierarchy of helper classes.

nucular

Originally posted by Corinthian


protected:
virtual void reallyUpdateMove() = 0;
};


Then implement reallyUpdateMove() in all your derived classes.

This would avoid having to have a parallel hierarchy of helper classes.

I think you missed the point slightly. The polymorphism will not work as is, due to the implementation of the STL not due to the implementation described by Greenbean.

Your implementation although slightly better as it allows you to enforce constraints before the calling of a protected method does not solve the problem he was facing. (Also I have a sneaking suspicion your code will not compile from what I gathered from the article referenced above, reason being that as the compiler detects that an actual reference is being stored in the list it will not allow the class to have a pure virtual function).

As for the writing of a linked list approach. It is definitely a good way of solving the problem especially if you have never written a linked list as it is one of the most important data structures.

Personally, I think if you have never implemented a linked list go with that. It will stand to you in the future.

As Jazz said, You can always post back up here.

Corinthian

Ahhh, silly me. Now I see what's really going on.

The vector template is actually making a copy of the objects that you're trying to store in it. Unfortunately it doesn't know anything about the derived objects so they're copied as base objects, and what actually ends up in the vector is a collection of base objects and no derived ones (hence why my code wouldn't compile, as the vector template is going to create GameObjects behind my back).

Here's another attempt at a solution / workaround.

Write a small wrapper class that will store a pointer to a base object, and store that in the vector instead.

e.g.

class GameObjectSTLWrapper
{
private:
GameObject *go;

public:
GameObjectSTLWrapper(GameObject *t)
{
go = t;
}

void updateMovement()
{
go->updateMovement();
}
}

Still no need for me to have parallel helper object hierarchies or to implement a linked list.

nucular

There is no need for a parallell hierarchy. If what i said led you to believe that then I should probably have been clearer.

My Intention was that GameObject would be a fixed class. Inheritable at a future point if necessary but in essence a fixed hirerarchy. (essentially your wrapper but having the properties inherited from D3DMesh and anything else associated with any and all game objects.) Any variable properties/ functionality would then be implemented in the helper object (probably could be titled better).

We essentially came to the same solution on different paths. I think however the helper object solution provides a better picture of the actual problem space.
Feel free to disagree as this is one of the most interesting threads I have found on the boards.

Corinthian

The penny (finally) drops. Your solution is indeed essentially the same, with your GameObject taking the place of my wrapper class.

I would think that having an explicit wrapper class is probably a bit clearer when trying to understand the code in six months time, although this is obviously subjective.

Anyway, how about storing pointers in the template, instead of actual objects. So we would have

list<GameObject*> instead of list<GameObject>

This way there would be no object copying going on behing the scenes, as the template would be dealing with the pointers all the time. Calling updateMovement through the iterator would change from

i->updateMovement();

to

(*i)->updateMovement();

and this would give the expected polymorphic behaviour.

Any opinions.

nucular

Yes this is the first solution that would normally be reached for but as you can see it will not work. The basic reason is consider calling a function createEnemy() which creates the enemy and adds it to the list of GameObject pointers.
When the function has completed the destructor is called leaving an invalid reference in the list. could get extremely messy.

Nice idea tho'

Quote from the article referenced by Jazz:
It becomes apparent that one level of indirection is needed to solve the problem. An obvious solution is to change the list of shapes to a list of pointers to shapes, so that the list declaration in the code fragment above would be:
list < shape* > shapeList;

and list would be populated:
shapeList.push_back(&e);
shapeList.push_back(&r);

This solution seems to work, but it will likely lead to run time errors, for if variables e and r are automatic, they will be destructed at end of thier blocks. If the list's scope lives on past the end of this block, it will be left containing invalid objects (pointers to arbitrary places in or beyond the stack).

Greenbean

I went with the pointers option there as a stop gap measure yesterday or so - its far from ideal, I don't like putting stuff on the heap memory. I'm going to do the list option as this is the best recommended one, but as the article mentioned, the stl link is very efficent and thats something I'd hate to loose with my leaky slow list. Still I'm doing this all for the experience, so after I do the list I'll give that neat helperobject idea a try. I sorta understand it, but the actual details are still a little shady in my head, but I'll look at it later.

Two questions though....

Stuff allocated to heap memory - does it deallocate after the program has stopped running?

Templates, what are they?

satchmo

No, if you create an object with new, then you have to manually delete it when you're done:

GameObject* g=new GameObject();
....
delete g;

The destructor of a class is usually a good place to clean up its dynamically allocated memory.

If it's an array you've allocated, then you use delete[]:

GameObject* garr=new GameObject[10];
....
delete[] grr;


If you allocate memory at runtime with new and then don't delete it when the program exits, the allocated piece of memory will be unusable until you reboot - this is a memory leak.

Objects created normally, like
GameObject g();
are put in stack memory, and are therefore automatically popped off once it's done.

Greenbean

Yeah, ok. Currently I've several of those gameObjects and a SpaceShip being created in a part of the code which has only a small region of existence (its the constructor of another class). Meaning stuff like

delete eagleShip;

isn't going to make much sense outside of that scope, the compiler isn't going to know about any eagleship. Hmm, this current workaround isn't a good idea at all, if I keep testing the program I'm simply going to run out of memory sooner or later.

I'm just not fond of creating global objects anyway, I plan to have an object manager which loads into memory and out of memory the objects I need at that time, and thats gonna require copies of the objects where I know them to be and can delete them.

Don't worry I'll give you plenty to discuss when I work on this list stuff some more

Corinthian

AFAIK it's up to the operating system what happens to memory allocated with new when the process exits. Most modern OS manage memory on a per process basis, so memory allocated with new belongs to the process it is allocated in, and is released by the OS when the process exits.

Nonetheless, it's very poor practice (as in it wouldn't be accepted in any kind of serious development effort) to not delete things yourself if you allocate them with new.

Mind you I could be talking total nonsense (and was not too many messages ago :-(

Greenbean

"Likewise, I could explain making linked lists here, but it's probably better if you find an explanation on the web somewhere - there's plenty of them out there, and diagrams make things much easier to understand. The advantage of this is that properly written, polymorphism will come built in, without any extra effort. Simply set each node to contain a GameObject object, and then store your new SpaceShip()s or new Missile()s or whatever there. Then you can loop through the list and simply call updateMovement() on each object."

I want to discuss this some more. I created my own singly linked list, made up of nodes containing the game objects. Unfortunately it seems to me that the end result of this is no better than making an STL list of gameobjects. I think it still won't work any better by making my own list - the compiler was complaing about the insertion of SpaceShip objects... perhaps I've done something wrong. It started getting horribly messy when I tried to change my list to only hold pointers to gameobjects.. and whats the point, I could do that with the STL list.

I'm certainly glad I had a look at lists, it is probably the easiest way to finally sort out pointers and references in your head.

One plan of action is to closely and guardedly watch the addition and deletion of gameobjects using another class which interfaces with the rest of the game. It will add objects and delete them from the list properly.

So it will add objects to the memory heap and delete them as necessary - the rest of the game will request it to do these operations. The STL list will be made up of references to the objects rather than direct copies.

Alternatively I could use that helper object system and keep the copy of the objects in the STL list (which is supposed to be pretty efficent about things and be very careful with memory management).

Any thoughts.

satchmo

Well let's see some code, like your
GameObjectNode GameObjectList::addGameObject(GameObject* gObj)
method or simliar. And maybe your GameObjectList.h.

Greenbean

class GameObjectNode
{
public:

	friend class GameObjectList;

private:
	GameObjectNode();

	GameObject data;
	GameObjectNode* next;
};

----------------------------------------------------------------------
----------------------------------------------------------------------


//This is a circular list, objects get added to the back and removed 
//from the front - queue fashion.
class GameObjectList  
{
public:
	GameObjectList();

	void addGameObject(GameObject g);  
//Creates a new node with the game object

	GameObjectNode* deleteGameObject(int id); 
//Deletes game object with this Id 
//and returns pointer to next node

	GameObject& getGameObject(int id);
	GameObject& iterate();
	bool isIterated() {return iterated;}

private:

	void resetIterator();

	bool	iterated;
	GameObjectNode *head;
	GameObjectNode *tail;
	GameObjectNode *nodeIterator;
};

-----------------------------------------------------------------
-----------------------------------------------------------------

#include "GameObjectList.h"

GameObjectList::GameObjectList()
{
}

void GameObjectList::addGameObject(GameObject g)  
//Creates a new node with the game object
{
	GameObjectNode *n = new GameObjectNode();

	n->data = g;

	if (head == NULL) //0 elements
	{
		head = n;
		tail = n;
		resetIterator();
	}
	else
	{
		tail->next = n;
		tail = n;
		tail->next = head;
	}

	resetIterator();
}

GameObjectNode* GameObjectList::deleteGameObject(int id) 
//Deletes game object with this Id
{
	if (head == NULL) //0 elements
	{
		return NULL;
	}
	else if ((head == tail) && (head != NULL)) //1 element
	{
		delete tail;
		head = NULL;
		tail = NULL;
		nodeIterator = NULL;
		return NULL;
	}
	else if ((head != tail) && (head != NULL))
	{
		GameObjectNode *currentN;
		GameObjectNode *previousN;

		currentN = head;
		previousN = head;

		for (currentN = head; currentN != tail; currentN = currentN->next) 
		{
			if (currentN->data.getId() == id)
			{
				if (currentN == head)
				{
					head = currentN->next;
					delete currentN;
					resetIterator();
					return head;
				}
				else
				{
					previousN->next = currentN->next;
					delete currentN;
					resetIterator();
					return previousN->next;
				}
			}
			previousN = currentN;
		}
		return NULL; //No matching id
	}
	return NULL; //The list is linked wrongly
}

GameObject& GameObjectList::getGameObject(int id)
{
	GameObjectNode *currentN;
	for (currentN = head; currentN != tail; currentN = currentN->next) 
	{
		if (currentN->data.getId() == id)
		{
			return currentN->data;
		}
	}
}

GameObject& GameObjectList::iterate()
{
	GameObjectNode* temp = nodeIterator;
	nodeIterator = nodeIterator->next;

	if (temp == tail)
	{
		iterated = true; 
	}

	if (temp == head) //reset the iterated variable
	{
		iterated = false;
	}

	return temp->data;
}

void GameObjectList::resetIterator() 
//An auxillary internal function to try keep things in proper order
{
	nodeIterator = head;
	iterated = false;
}

That covers just about all my list stuff. The iterator function is there because when doing an iteration of the list in the rest of the game I don't want to be refering to GameObjectNode.. I don't want anyone to know about that - but its probably envitable that I would have to comprise on that.