Entity Management
I've finally come to a place where I'm beginning to add entities to my 3d "project." I have a class that stores the current state of the world, including the world geometry, things, the player, and more abstract things like the camera.
How should I store the things in this class? I like the idea of using std::vector a lot, but I want each thing to be able to have a unique integer that represents it to pass around functions (priamry to/from scripts). The obvious solution is to just have this code be the offset into the vector, but then I run into problems if I remove an item and all the items after the removed one have their indices shifted.
Alternatively I could use an std::map<int, Thing> which would work too, I suppose. Then I just run into the problem of generating the integer keys, which my inclination tells me to do by having the world AddThing function just keep incrementing a static int variable.
My third idea is to just have the vector approach, but add a "dead" flag to each item. When I remove the thing from the world I set the dead flag and when I loop through it (for Update and Render) skip the dead items. Then whenever I add a new item I just find the first dead item and overwrite.
Any opinions?
Thanks, ms
I would choose the vector solution. If you use a DWORD variable as your entity ID, you won't NEVER get any problems with not enough possible IDs for your entities after removing and adding again some more, because a DWORD variable has a range between 0 and 0xffffffff=4294967295. This should be quite enough for all entities managed by your manager during one game (or whatever) session.
I agree about never running out of room with the IDs but do you like the idea of the dead/alive flag? It saves a lot of trouble trying to organize the IDs when you remove an item from the world, and doesn't waste much memory. Is that would you mean by "the vector solution" (since there were two ideas that used vectors)?
The answer would depend on how you manage your game. For instance, in my game, i have all my objects stored in a std::list (not a vector because of very-frequent insertion/deletion), and i then iterate over the entire list every frame like so:
foreach object:
- Update
- (Remove if dead)
- Draw
I don't usually need to address a specific object in particular when i do this, so i have no concern for where in the list they appear.
Now, if you reference all your objects by some kind of ID or array index, then it get's trickier. You get around the problem of passing around pointers, but you need to make access faster. For that, i'd use a vector, not a map (for many objects, at least). But unless you use the dead/alive flag idea, your vector will just increase forever until it eats up all the memory -OR- you lose time deleting things and shifting memory as you mentioned.
To be very honest however, any structure will do. I did some tests on a particle system i made with *thousands* of particles. I tested the difference between a std::list and a std::vector when iterating over the list with many, many particles dynamically created and inserted and being deleted and removed from the container over the lifespan of an "explosion". There was little or no perceivable difference in framerates on my Athlon 2500.
I would say, create a std::map and use integers for keys (a simple counter++ would be fine for giving out new keys). If that doesn't work, then switch. But make sure it really does have an impact before you stress over it.
My best advice would be to create an iterface like GetObjectByID(). Then it doesn't matter how it's implemented, the interface never changes. You can implement it however you want, but not change any client code.
foreach object:
- Update
- (Remove if dead)
- Draw
I don't usually need to address a specific object in particular when i do this, so i have no concern for where in the list they appear.
Now, if you reference all your objects by some kind of ID or array index, then it get's trickier. You get around the problem of passing around pointers, but you need to make access faster. For that, i'd use a vector, not a map (for many objects, at least). But unless you use the dead/alive flag idea, your vector will just increase forever until it eats up all the memory -OR- you lose time deleting things and shifting memory as you mentioned.
To be very honest however, any structure will do. I did some tests on a particle system i made with *thousands* of particles. I tested the difference between a std::list and a std::vector when iterating over the list with many, many particles dynamically created and inserted and being deleted and removed from the container over the lifespan of an "explosion". There was little or no perceivable difference in framerates on my Athlon 2500.
I would say, create a std::map and use integers for keys (a simple counter++ would be fine for giving out new keys). If that doesn't work, then switch. But make sure it really does have an impact before you stress over it.
My best advice would be to create an iterface like GetObjectByID(). Then it doesn't matter how it's implemented, the interface never changes. You can implement it however you want, but not change any client code.
I agree that the implementation doesn't really matter. I already have a nice ThingInstance* World::GetThing(DWORD index) function that serves the purpose of just that interface you mentioned. The best thing about using the indices into the vector/list as the ID is that you get O(1) look ups. Maybe trying to figure out the best way would fall under the category of "premature optimization" but I just figure while I'm implementing it the first time, I may as well do it right.
leiavoia and hunta: Thanks for your help thus far
everyone else: I'm still interested in other opinions as well
leiavoia and hunta: Thanks for your help thus far
everyone else: I'm still interested in other opinions as well
Here is the simplified version of my entity manager:
It works fine and I don't think std::map will ever create performance problems.
class CEntityMgr{public: CEntityMgr() { m_NextID = 0; } unsigned int CreateEntity( ENTITY_TYPE Type ); CBaseEntity* GetEntity( unsigned int ID );private: typedef std::map< unsigned int, CBaseEntity* > EntityMap; EntityMap m_Entities; unsigned int m_NextID;};unsigned int CEntityMgr::CreateEntity( ENTITY_TYPE Type ){ CBaseEntity* pEntity = NULL; switch( Type ) { case ENTITY_CHARACTER: pEntity = new CCharacter; break; // ... } m_Entities[ m_NextID ] = pEntity; return m_NextID++;}CBaseEntity* CEntityMgr::GetEntity( unsigned int ID ){ EntityMap::const_iterator iEnt = m_Entities.find( ID ); if( iEnt == m_Entities.end() ) // Error return (*iEnt).second;}
It works fine and I don't think std::map will ever create performance problems.
Quote:How should I store the things in this class? I like the idea of using std::vector a lot, but I want each thing to be able to have a unique integer that represents it to pass around functions (priamry to/from scripts). The obvious solution is to just have this code be the offset into the vector, but then I run into problems if I remove an item and all the items after the removed one have their indices shifted.
A vector isn't a good idea, simply because you get O(n) search time and removal from the middle of the vector. And insertion is the same from the beginning/middle, but I assume you'll always add to the end so that would be constant time.
Quote:Alternatively I could use an std::map<int, Thing> which would work too, I suppose. Then I just run into the problem of generating the integer keys, which my inclination tells me to do by having the world AddThing function just keep incrementing a static int variable.
A much better solution. You get logarithmic search time and insertion (either O(ln(n)) or O(n ln(n)), can't remember) and it makes more sense if you want to your entities to be identified by unique keys. Granted you do have to generate unique entity keys, you might be able to get away with hashing [one-to-one] the actual memory address of the object and using that as a key, since you know no two live entities will ever have the same address. Just a thought.
Quote:My third idea is to just have the vector approach, but add a "dead" flag to each item. When I remove the thing from the world I set the dead flag and when I loop through it (for Update and Render) skip the dead items. Then whenever I add a new item I just find the first dead item and overwrite.
You're on the right track, but doing this with a vector doesn't save you anything, really. You make "removal" a constant time operation, but turn insertion into a linear time operation by having to search for a dead entity to make live again. And you have the runtime conditional check so you only do stuff on live entities.
All things considered, what I would do is create a map of IDs to entity objects (as pointers), and call this the "live" list. I would then use a stack of entity objects as the "dead" stack. When objects die they are removed from the live list and pushed to the dead stack. That way, no conditional is needed to see if an object is dead or alive, because it's implicit based on which list it's in. Whenever a new object is needed, we try to pop one from the dead stack and reset its parameters. Otherwise we create a new one. Instead of a map for the live list you could also use a hash_map, which gives you constant time insertion, removal, and searching. Although it isn't standard yet (it's under the stdext namespace right now), it's an extremely awesome container.
My Entity mgr is very similar to Arcibald Wearlot's above.
I make factory functions rather than a switch statement, but it boils down to the same thing.
The factory stores all objects.
The Session object stores the current game session, and contains a std::set of active & inactive entity ids.
Only active entities in the std::<set> are processed for AI, rendering, etc.
The inactive entities list is added to each frame as entities die, particles fade out, etc. and is used at the end of the simulation tick to remove the entities from the factory permanently.
I make factory functions rather than a switch statement, but it boils down to the same thing.
The factory stores all objects.
The Session object stores the current game session, and contains a std::set of active & inactive entity ids.
Only active entities in the std::<set> are processed for AI, rendering, etc.
The inactive entities list is added to each frame as entities die, particles fade out, etc. and is used at the end of the simulation tick to remove the entities from the factory permanently.
First off, thanks for all the ideas. It seems like a map's the way to go. Arcibald Wearlot, the factory is definately the construct to use to create them, and I appreciate the implementation idea. SimmerD, I like the idea of the factory functions; it saves you from hard-coding every entity type into the factory.
Eh, pardon me, but wouldn't O(n ln(n)) actually be noticably worse than the O(n) of the vector? I'm hoping that a map would perform at O(ln(n)). Does anyone know for sure?
Nice thought, Zipster. My problem with hashing the memory addresses is that when you move an item to the dead stack, and then back to the live stack (reborn as something new) it would have the same ID. That could be a problem if for whatever reason some script was holding a handle to thing 153, thing 153 was destroyed, a new thing was created (in slot 153), and then the script decided to perform some action on what it thinks is the item it originally was dealing with. I think I'll have to stick to an "auto"-incrementing DWORD.
Wow, where's the downside? I admittedly haven't looked in to this yet but it sounds like an unbeatable solution!
Zipster, your post was very informative and full of good ideas. I don't mean to pick on you with the above.
So it sounds like my final decision will be a [hash_?]map<DWORD, Entity*> and an object factory in which each class can define its own factory function and just call Factory::Register. Sounds like a winner to me.
Thanks for all your help!
ms
Quote:Original post by Zipster
You get logarithmic search time and insertion (either O(ln(n)) or O(n ln(n)), can't remember)
Eh, pardon me, but wouldn't O(n ln(n)) actually be noticably worse than the O(n) of the vector? I'm hoping that a map would perform at O(ln(n)). Does anyone know for sure?
Quote:Original post by Zipster
Granted you do have to generate unique entity keys, you might be able to get away with hashing [one-to-one] the actual memory address of the object and using that as a key, since you know no two live entities will ever have the same address. Just a thought.
Nice thought, Zipster. My problem with hashing the memory addresses is that when you move an item to the dead stack, and then back to the live stack (reborn as something new) it would have the same ID. That could be a problem if for whatever reason some script was holding a handle to thing 153, thing 153 was destroyed, a new thing was created (in slot 153), and then the script decided to perform some action on what it thinks is the item it originally was dealing with. I think I'll have to stick to an "auto"-incrementing DWORD.
Quote:Original post by Zipster
you could also use a hash_map, which gives you constant time insertion, removal, and searching
Wow, where's the downside? I admittedly haven't looked in to this yet but it sounds like an unbeatable solution!
Zipster, your post was very informative and full of good ideas. I don't mean to pick on you with the above.
So it sounds like my final decision will be a [hash_?]map<DWORD, Entity*> and an object factory in which each class can define its own factory function and just call Factory::Register. Sounds like a winner to me.
Thanks for all your help!
ms
Quote:Original post by ms291052
First off, thanks for all the ideas. It seems like a map's the way to go.
I don't!, i'll explain at end.
Quote:Original post by ms291052Quote:Original post by Zipster
You get logarithmic search time and insertion (either O(ln(n)) or O(n ln(n)), can't remember)
Eh, pardon me, but wouldn't O(n ln(n)) actually be noticably worse than the O(n) of the vector? I'm hoping that a map would perform at O(ln(n)). Does anyone know for sure?
map & set are O(log n) there are usually implemenated via red-black trees, note also ln n != log n.
Quote:Original post by ms291052Quote:Original post by Zipster
you could also use a hash_map, which gives you constant time insertion, removal, and searching
Wow, where's the downside? I admittedly haven't looked in to this yet but it sounds like an unbeatable solution!
hash_map/set are not currently part of the c++ standard, its an STL extension, and of course there are down-sides no such thing as perfect.
Quote:Original post by ms291052
Zipster, your post was very informative and full of good ideas. I don't mean to pick on you with the above.
So it sounds like my final decision will be a [hash_?]map<DWORD, Entity*> and an object factory in which each class can define its own factory function and just call Factory::Register. Sounds like a winner to me.
I think some issues have been over looked quite a bit here, using a set or map with no useful ordering to give you no advantage for things like say rendering, just using random generated IDs aren't useful keys.
I'll give you one scenario, when it comes to rendering because you have no useful ordering/structure you still have to iterate the entire scene (including objects out-side the view frutusm), you've gained almost nothing except overhead for no reason, a list would have been a much better choice (just as leiavoia suggested) if your going to iterate the entire scene with-out doing any sort of culling of objects list is the best way to go, unless you have some useful ordering your wasting time & resources using set/map.
Even if you do basic frutum culling via bounding volumes but using set/map to hold your objects with ID keys this would be equivalent to just using a list and check bounds against the view frustum, this still O(n) be it list, set or map.
Another scenario would be collision detection, you have the same thing you'll end up iterating the whole scene, map/set using ID keys gains you nothing for this operation, again even simple check bounding volumes, its still O(n) for list, set or map.
You see where i'm going? unless you have some useful ordering map/set will gain almost nothing over list but uneeded overhead.
i don't know how complicated your project is going to be but if you want any-thing better than sending all your objects to be rendered and O(n) for nearly everything you do, then look into O(log n) structures (trees). Look into scene graphs, spatial data structures be it space or model partitioning types.
Here is one example, bounding volume hierarchies (great for dynamic objects), a tree where bounding volumes are nested (one bounding volume is contained in another one which also contained in another one and so on parent-childing). When you iterate the tree for rendering at each node you check the if its bounding volume is out-side the view frustum if it is you cull entire branches! thats log n, it doesn't iterate the entire scene and your culling objects that are outside the view.
How are you going to achieve that with set/map unless you have useful key & ordering of elements? you can still do things like frustum culling with this set-up but you still have O(n) here.
if your not going to bother stick with lists.
[Edited by - snk_kid on January 19, 2005 5:29:00 AM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement