Sign in to follow this  

Entity Management

This topic is 4713 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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)?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Here is the simplified version of my entity manager:


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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

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

Share this post


Link to post
Share on other sites
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 ms291052
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?


map & set are O(log n) there are usually implemenated via red-black trees, note also ln n != log n.

Quote:
Original post by ms291052
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!


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]

Share this post


Link to post
Share on other sites
Heh, I too have planned to use hash_map for my entities, so I will have do defend that idea.

So...
If you remember data-bases, they somethimes have several orders to nmanage entries. Trees with different ordering and hash-maps. And it turns out great.

So if I want to manage collision-objects, I'd do it with some spatial-division (any kind).

So if I want to manage rendering, I'd have to go with a strict order, like RBTree, but I could go with a hash-map of lists, where each list contains entities with using same model. With similar effect. I suppose.

So if I want to manage the very existence of an entity, I would go with a hash-map. It is quick, it is small, it is reliable (most of the time, that's the part where you would have to come with hash function of your own).

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

IHMO, using a few mappings in one project is inevitable, cause they are so different, they cannot be merged.

Cheers.
/def

Share this post


Link to post
Share on other sites
Quote:
Original post by deffer
Heh, I too have planned to use hash_map for my entities, so I will have do defend that idea.


You can defend it all you want but i wasn't actually talking about hash_map/set i was talking about plain (multi) map/set, hash_map/set don't impose ordering of elements.

Still how-ever just using any of these with-out any rationale is waste of time, what is a useful key & hashing function? if your using it for say spatial indexing for lookups thats a whole different story.

If you use hash_map/set where keys are just random generated integer IDs with default hashing function, sure you've may have gained efficent look-up speed but for what? most operations will involve iterating the whole scene which is still O(n) with that setup and that is the same with list but you don't need to generate any ids for list, so you've gained very little if anything at all.

[Edited by - snk_kid on January 19, 2005 7:34:01 AM]

Share this post


Link to post
Share on other sites
Okay i just re-read the whole thread, i missed the part about passing IDs to pass to scripting system, okay fair enough hash_map is a good way to go if your compiler/s has support for it, ignore my babbling.

Share this post


Link to post
Share on other sites
Yes, snk_kid, you are definately correct about the rendering and coldet, etc. Passing these thing IDs to scripts is important, so I believe a map is necessary. Right now I have an OctTree set up for culling of the level and nodes hold lists to things that they contain. I think as far as culling goes this is a good way to go and coldet is also sped up (I'm currently checking all objects in each node the thing I'm checking's in).

Yes, trees certainly have their places, and using the OctTree my things are kind of in a tree too. I think for just the entity <-> ID job for the scripts the hash_map<DWORD, Thing> works well.

Edited to add: I'm currently using VC++ 2002 so hash_map is definately supported, and thus far (i.e. the last day or two) has served me well.

Share this post


Link to post
Share on other sites
Quote:
Original post by ms291052
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.

You're absolutely right, which is why I said in my last paragraph you should store pointers to allocated objects and not actual objects [grin] That way you don't have to allocate/deallocate objects all the time, and the pointer values themselves remain constant.

Share this post


Link to post
Share on other sites
Zipster's idea is pretty consistent with our system.

We have an Entity Manager which has a map of all of our active game entities. These entities are both renderable and non renderable entities. They are stored as pointers to entities with the name of the entity as they key. We hash the text string into a 32 bit value so that the map works efficiently, and to speed up the searches. Each entity that is stored in the map is derived from a base class but each entity type is allocated out of a pool. These pools guarantee that we don't fragment memory and also allow us to establish a fixed memory foot print for the majority of our entity types.

When objects are created that can be renderable, they are submitted to a list. This list is used exclusively for rendering. Because your entities contain both visible and non-visible entities, the render list is a subset of the list, and is submitted to the rendering manager for drawing. In our case, we actually maintain multiple render lists as buckets for forground, mediumground and background, but this is an optimization for our specific game type.

When objects die, they are removed from the map, and if renderable, removed from the render lists. Once destroyed, they return to the entity pool of their type. For things that are created often each entity type factory creates a unique ID to prevent hash collisions ( like powerups ). They also tend to be objects that no one really wants to hang on to from scripts or other game code.

We also have an enumerated list that is auto generated that lets people use fixed const unsigned long hash IDs instead of having to rely on runtime string hashing for fixed objects. This enum include only contains objects which have infinite lifetime, and is generated as part of our build step. This lets us request access to game entities explicitly while making our code break if the entity is ever removed by an artist or a design change.

Anyways, I've kind of rambled, but I thought I'd dump our situation here for you.

Sphet

Share this post


Link to post
Share on other sites
how about this

1->2->3->4->5->6->7->8->9->10

this shall be a linked list of objects

you could allocate a array and use it as a linked list where the id == the pointer shift factor

now lets say you want to remove 2 and 3

1->4->5->6->7->8->9->10->2->3

you just move the to the back of your linked list, but the memory address stays the same

now you just store a variable with the number of objects alive and you should be fine

all you do is swaping a few pointers

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by snk_kid
note also ln n != log n.


In Big-O notation, ln n and log n are equivalent.

Share this post


Link to post
Share on other sites
of course they are log = lg n / lg 10

log is the logarithmus to the basis 10

lg is the logarithmus

ln= lg n/ln e

lg n / lg x where x is the basis is the logarithmus to the basis x

ld = lg n / lg 2 ....


e== euler`s number *don t know how you call it in english

Share this post


Link to post
Share on other sites
Didn't read entire thread so pardon me if it was mentioned before.

You could use a vector, and do sth like this

int xxxManager::create ()
{
if (freeIDs.size()
{
take item from freeID's list/prio-queue/whatever structure you use
create new item on objects[id];
return id;
}
else
{ objects.push_back();
return objects.size()-1;
}
}

void xxxManager::destroy (int id)
{
// validity checks ...
delete objects[id];
freeIDs.push_back (id);
}

So need for re-organising id's, the few 'holes' which appear
are filled up quickly and holes only take 4 bytes (1 ptr)

Regards
Roger

Share this post


Link to post
Share on other sites

This topic is 4713 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this