I'm beginning to regret the shift to STL vector containers for managing groups of Agents. In fact, I should've just created a static array[MAX_AGENTS] than go down this route.
At the moment, the base class constructor registers an ID with an Entity Manager that is unique to that (often inherited) class. This ID is used for sending and receiving messages.
Today has been a major crash-fest as I see what happens when you try deleting random agents from the game.
1. The MessageDispatcher continues to process messages from IDs that are no longer in existance in the game and attempt to send messages to them.
2. Delete an element from a vector, all the other elements afterwards get shifted along one to close the gap. This means that constructors and copy constructors get called for all those elements. All of them end up with new IDs that are no longer aligned with those waiting in the Message Stack.
3. Regarding 2) Even if I set the copy constructor to re-assign the ID from the (soon to be deleted) Agent, the actual memory location that EntityManager points to is still the old one that is going to be deleted.
Time for (yet another) implementation rethink of the basics.
[UPDATE - these problems are now fixed. :) ]
If object has a unique ID, why not just store them in a hash table, with IDs as keys?
ReplyDeleteWell, this is what the STL map can do (i.e., pair <int, Agent>), and I had thought about this, but chose against it because of performance issues (elements are not sequential in memory as you'd find in a vector and elements could be scattered across a memory page which means slow access times).
ReplyDeleteHowever, in practice, for a few thousand elements, the look-up time is probably negligable.
It's more that I need to rethink what happens when these classes are shifted about it containers. Compulsorily, a new one is created, it's details copied over, and the old one deleted. The order goes:
New item created (ID = ?)
New item = Old item (ID = old_ID)
Old item deleted
However, when the new item registers it's new memory location to the EntityManager, it gets summarily deleted again when the Old item calls it's own destructor.
I'm thinking I'll just have to create a maintenance function that empties the EntityManager and then re-populates it with existing classes (who's locations in memory may have changed, but who wish to keep the same IDs).
This will mean the MessageDispatcher class won't have to worry about IDs that exist but have changed location.
PS - lol, HI! ^_____^
Boo, you have no blog. We are to be denied the joys of theorem proving... :}
ReplyDeleteProblem Solved:
ReplyDeleteA) Constructors may not allocate an ID by default. (ID:0 is considered dud).
B) SetID(int) member does the following:
- Check for existing ID in entitymanager.
- Delete existing one, if found.
- Register new memory location of ID.
C) SetID(int) can be called from a special constructor "i.e., Agent(int), Captain(int)"... but most importantly, can be safely called from a Copy Constructor (i.e., SetID(oldClass.ID()))
- This means STL containers can create, copy, delete and generally bounce classes around in memory as much as it wants to.
D) An entity with, say, ID:1 can be bounced around for the whole game and never need to change it's ID.
This comment has been removed by the author.
ReplyDeleteI'm a big fan of http://www.boost.org/doc/libs/1_43_0/libs/smart_ptr/shared_ptr.htm
ReplyDeleteSo I'd do something like...
typedef boost::shared_ptr<Agent> AgentPtr;
Then whatever STL container you want:
typedef std::map<AgentPtr> AgentMap;
or
typedef std::list<AgentPtr> AgentList;
It did wonders for eradicating my memory problems.
That should have been:
ReplyDeletetypedef std::map<int, AgentPtr> AgentMap;
But you get the idea.
Thanks, I've been having a look into the Boost libraries recently. I'll probably play around with it in a standalone test project just to get used to it.
ReplyDeleteAlso, it turns out that the crashes were directly the result of me not obeying the rule of three. I forgot the assignment constructor, so when I deleted an element inside the vector, the program couldn't properly shift each element along.
But yep, the Boost library looks great and I'll probably integrate it in at some point.
And yes, I got bitten by that square bracket HTML catch on this blog as well. Hah, there must be some add-on that can keep it verbatim.
ReplyDeleteYeah, I don't use STL vectors for my object lists, I use an STL list instead. For the very reasons you ran into.
ReplyDeleteQuestion: Do you intend to support multiplayer? If so, you're going to want to do two things: get the entire input system event driven and create a random number class that can be synchronized between multiple clients.
Well, as if you don't have enough input on this, here are my two cents!
ReplyDelete1. Don't put real objects in your vector array, use pointers and manually new/delete them when adding/removing, allowing stl to shuffle/copy as needed without worrying about it. (or use smart pointers as suggested above, but am more comfortable without 'em)
2. Actually, don't use a vector for your entity list, use a stl , as Viridian mentioned
3. When you run Update(), first copy the entire stl list to a temporary one, and run Update() on each entity in that list. (this way you can add/remove objects freely during entity logic)
4. After running update, run a pass on the real list and erase objects that are marked for deletion.
5. Avoid crashes: During each deletion, call an OnEntityDeleted(ent) in your message manager so it can run through and kill any messages to or from that entity.
6. Also send a message to anyone else who would need to know when a message is deleted, probably this includes each entity, as they may be targeting an entity that was deleted, etc.
7. If you're concerned about all those extra messages flying around, look into a sigslot solution. This would let objects that "care" (like a message, or entity) register to receive notification when an entity is deleted.
Hi Seth, thanks for the suggestions. A few days ago I had a re-think and re-implemented things in a similar way as these suggestions.
ReplyDeleteAs an aside, correcting the classes solved all the memory problems. Just bad/lazy coding ethic on my part. (I had a missing assignment operator)
The entity manager is actually already implemented as a STL map with (ID, ptr*) so grabbing a handle to an Agent is pretty quick.
Also, Captains use a container of pointers to the pool of Agents which makes things much easier (recruiting and dismissing is as easy as deleting these elements). They can send messages to their armies, etc.
To be honest, for now, I'm not sure I'll actually need to dynamically delete agents in-game. Ones that are killed off tend to lie around with their Update state not doing anything (until they are removed from the map), but they still have properties (you can still query them in the original, if memory serves). Also, they can be re-utilised as a new agent if the maximum limit of agents is reached, but to be honest, I can't really see that happening, even if you left the game running for a year.
I see what you guys are saying about the lists. I think I'll keep the vectors for now. I do like being able to just do a linear Update() sweep across them each game loop iteration and use the EntityManager for actually accessing things.
But I'll implement things so that I can swap in a list if I get in trouble again.
I guess I just like the thought of things sitting neatly with each other in memory.
If only my sense of house cleaning was similarly aligned...
"I think I'll keep the vectors for now. I do like being able to just do a linear Update() sweep"
ReplyDeleteOh, btw, I know you can do this with lists as well! (in case that wasn't obvious) :]
You probably already know this, Nick, but for anyone out there who doesn't, the erase-pull trick is useful for actually deleting dead objects from a list.
ReplyDeleteIt takes this form:
vector::iterator iObjects = g_GameObjectsVector.begin();
for( iObjects; iObjects !- g_GameObjectsVector.end(); ) // note that there is no iteration here.
{
if( (*iObjects)->IsDead() ) // The unit is flagged as to be removed
{
GameObject* pObjectToDestroy = (*iObjects);
iObjects = g_GameObjectsList.erase(iObjects); // this erase call sets the iterator to the next valid object after removing the current one. This is the erase-pull.
delete pObjectToDestroy;
}
else
{
++iObjects; // No deleting on this object, just iterate normally.
}
}
I hope this helps someone; it took me a while to figure this out :)
Very useful! In fact I actually got caught out with that one when I started learning STL.
ReplyDeleteI was trying to see what would happen if I deleted a certain element.
I hadn't read up that the erase() method actually returns the location of the updated iterator.
What I had was...
it=objects.begin();
while(it!=objects.end) {
if(*it->SomeCondition())
{
objects.erase(it);
}
it++; // RED ALERT! - RED ALERT! ;)
}
Recipe for disaster! ;)
Oh, can you elaborate on the following?
ReplyDeleteGameObject* pObjectToDestroy = (*iObjects);
delete pObjectToDestroy;
Does the erase() not call the destructor and de-allocate the object for you? i.e., will the following delete not delete a previously deleted memory location?
Or have I misread, is g_GameObjectsVector actually a container of object pointers, not objects themselves?
Yes, as mentioned before, you really shouldn't be making lists (or vectors or anything else) of objects because of the amount of copying/moving that can be done. All your lists should be of pointers.
ReplyDeleteAaaah, I realise now I misread Seth and see what you both mean now.
ReplyDeleteI've been working with popping actual objects into containers as I need them. (and hence the pointless data copying and risk of memory leaks associated with incomplete copy/assignment constructors)
What I should've been doing is adding a pointer to the object to the list and then dynamically allocating/deleting the object as needed, hence any shuffling going on in the container is going to be on pointer locations, not actual objects (and not incurring all the heavy cost of data shifting). Seems so simple (and obvious), now I think of it. Durrrr...
Sorry, the STL is still quite new to me (~2 months usage so far). I've been recommended a couple of books:
"Effective STL: 50 Specific Ways to Improve the Use of the Standard Template Library"(Scott Meyers) - supposedly a good book about the 'gotchas' of STL usage...
and
"The C++ Standard Library: A Tutorial and Reference" (Nicolai M. Josuttis)