Sign in to follow this  
Exomoto

Storing various game entities.

Recommended Posts

How do you guys store/segregate your game entities? The prototype I'm currently working on has multiple lists for things like enemies, inanimate objects, different bullet types, explosions, etc. This has served me well up until now, but having to constantly write template functions to run through a list (updates, collisions, recycling) and then make multiple calls to that function for lots of different lists seems a bit messy. Is there a tidier way of doing this?

Share this post


Link to post
Share on other sites
You didn't specify a language, but I use either interfaces or abstract base classes. For example, I might have an entity manager that holds a Collection<Entity>. An Entity interface (or class) might specify things like "tickUpdate", "move", "add", "remove" etc. The entity manager can iterate over all entities and call the appropriate method without caring how the specific entity implements those methods.

Share this post


Link to post
Share on other sites
Sorry for not being specific. I'm using C++.

At the minute my project has a generic Entity base class, followed by GUIEntity and GameEntity child classes (probably not necessary to split the two but it made sense at the time). From there I have derived classes for the various object types which are extended with functions/variables suitable for those particular entity types. These types are then broken up into varying lists, so I can check lists/objects with other lists/objects for things like collision.

I'd like to use a simpler system like the ones mentioned already, but how is using one entity list better? I would've thought that keeping a big list of different object types would make testing for interactions more expensive?

Share this post


Link to post
Share on other sites
well couldn't you do something like this


struct GameEntites //this will store any an all objects that effect the game

char ObjName[30];
ObjId *id;//pointer to a Object ID enum or array.
bool ObjExplode = NULL;
int ObjStatBonus = 0;//change an have more code to determine the statbouns on object.



thats a basic concept on how it could be done so you don't have to make more then on struct or template for different objects that effect the game.

Share this post


Link to post
Share on other sites
Wouldn't that still require me to traverse the entire list of available objects to find all objects of a certain type? In my current project there's likely to be a 200+ objects on the screen at any one time, many of which will be bullets, so would having a single list be suitable?

Share this post


Link to post
Share on other sites
The simplest solution is to use an interface or store all 'updateable' entities in their own list so that you only have to traverse this list and call update on them. Their update methods should automatically get/send the data required in order to update the game. Collisions should be a part of this update process.

And This may be slightly off topic, but you may want to consider approaching the idea of an entity differently. A component system solves this problem due to the loose definition of an entity.

Share this post


Link to post
Share on other sites
It can be useful to maintain both an all-entities list and type-specific lists. The only mildly tricky part is object deletion, but it's not that hard with a little planning, and especially not with smart pointers.

Share this post


Link to post
Share on other sites
Well with the struct style I should you; you can use a file system to handel all the objects so basicly you create a program that can make the object files. So then it would be like a Object Creater program where you can give it a ID, Name, Explosion Rate, Stat Bonus, Cost, Level Req, Gender Req, Stat Req, Chest Spawn Location, Drops from which monster, Sells from somewhere-cost an so on. Or you could do this all in a MySQL database so all the stuff is portable over to a Website easier so then you can do a WoW Armory style page on your site an so people can look up item stats an abunch of differnt stuff.

Hope I've helped.

Share this post


Link to post
Share on other sites
This is actually something I've thought about myself, and one approach is a custom categorising container. I'm a Java guy, so I don't know how you'd do it in C++, but basically you need objects implementing an interface that returns an enum that categorises them somehow, and a container containing an array of arraylists (or vectors, in C++), one for each value of the enum.

Then you just have the add method check the value of the enum and put it in the relevant arraylist, write a custom iterator to iterate over each arraylist sequentially, and access each arraylist's iterator to iterate over only a single category.

Basically, it does the organisation work for you with only a minimal expenditure of effort up front and it's no harder to call than using a standard arraylist/vector, all you lose is order-of-entry iteration over elements regardless of type (which probably isn't a benefit). It's only useful if you want to iterate over certain subsets of data regularly, though.

Share this post


Link to post
Share on other sites
I'm thinking a good option would be to keep a list of all entities in a manager class, along with functionality to modify that list, use a factory pattern to add entities to the list, and give each created entity access to the manager class so they can handle their own collisions/deletion/etc during updates. In this case, would it be a good idea to store an iterator in each entity which can be used to erase/recycle that entity as needed?

Share this post


Link to post
Share on other sites
Quote:
Original post by Exomoto
How do you guys store/segregate your game entities?

The prototype I'm currently working on has multiple lists for things like enemies, inanimate objects, different bullet types, explosions, etc. This has served me well up until now, but having to constantly write template functions to run through a list (updates, collisions, recycling) and then make multiple calls to that function for lots of different lists seems a bit messy.

Is there a tidier way of doing this?


////////////////////////////////////

I use a component based system. All components are separated into ComponentData(const from the pov of the running game,mutable by editor/(de)serializer) and ComponentInst(mutable from the pov of the running game) counterparts. ComponentInst's const-ref ComponentData's (one to one). This separation of const and mutable data allows the game to run in the editor (important for iteration time). Since the running scene cannot change the const ComponentData's, you restart the scene in it's pristine state by destroying all EntityInst's and ComponentInst's and recreating them (compose and link).

My system breaks down like this:

////////////////////////////////////

SceneData (concrete class): editable/(de)serializable but const collection of archetypes, EntityData's and SceneComponentData's

SceneInst (concrete class): mutable collection and manager of EntityInst's, EntityComponentInst's and SceneComponentInst's. Maintains active component lists (per family). handles spawning/despawning. routes updates to individual components in a well defined manner.

SceneComponentData (abstract base class): editable/(de)serializable but const data of a SceneComponent. Examples include "BulletPhysicsWorldComponentData", "AudioManagerData", "LightingManagerData"

SceneComponentInst (abstract base class) : mutable instance portion of a SceneComponent. const-refs instance of paired SceneComponentData subclass. Examples include "BulletPhysicsWorldComponentInst", "AudioManagerInst", "LightingManagerInst"

Archetype (abstract base class) : editable/(de)serializable but const builder /blueprint for an entity. Also a collection of EntityComponentData's. Examples include "BasicModelArchetype", "SkyboxArchetype", "StaticLightArchetype", "CameraArchetype", "GlobalArchetype". Usually a predefined mix of component's, but user supplied component mixes are possible (but more complicated and infrequently needed).

EntityComponentData (abstract base class) : editable/(de)serializable but const data for a given entity component. examples include "BulletPhysicsObjectComponentData", "ShipControllableData", "ModelAnimatableData", "CameraControllableData", "AudibleComponentData", etc..

EntityComponentInst (abstract base class) : mutable instance for a given entity component. examples include "BulletPhysicsObjectComponentInst", "ShipControllableInst", "ModelAnimatableInst", "CameraControllableData", "AudibleComponentData", etc..

EntityData (concrete class) : Spawn Record for an entity - has TransformNode, Name, Archetype and misc entity initialization properties.

EntityInst (concrete class) : mutable instance for an entity - const-refs EntityData. container for EntityComponentInst's

The main difference between a scene component and an entity component in this system is that there will only ever be one of a given scene component. They tend to be used for scene-singleton objects. example: The "BulletPhysicsWorldComponentInst::Update()" method is where the call to bullet's physics tick update would actually be called (once per frame).

////////////////////////////////////

In my system, A requirement was the ability to be data driven (by the designer/artist), and be run within the editor for improved iteration time.

////////////////////////////////////

you can see more info (with pseudocode)here

mtm

[Edited by - tweakoz on December 31, 2009 8:51:53 AM]

Share this post


Link to post
Share on other sites
I use an Aspect/Component-type system in my latest code. So only entities with Spatial aspects ( and thus a world bounding box ) get put in the hash grid for spatial queries.

Similarly, only entities with a Physics component get put into the physics system at all.

So with this system, there is some automatic filtering when querying for physics or spatial information, because only relevant objects are in the structures to begin with.

There is some waste WRT things like a localized audio object. Do I put the audio range bounding box in the spatial query, and make all entities nearby have to grab that and ignore it? Or do I put it into the physics system and mark it as a phantom object with no collision...

I think I will put it in the spatial query system, but add some flags to each entry, so the spatial query functions can filter out things that are not relevant to your search. You could have an audio flag, one for visuals ( to ignore invisible objects for instance ), etc.

Right now my Aspects are :

default( name )
spatial ( position, orientation, current & last bounding box )
physics ( mass, velocity, box2d info )
visual ( sprite info, visual extents - may differ from spatial extents )
controller ( for player control keys right now )
brain ( for scriptability and/or ai )
editable ( for editor selection info, in-progress property edits, drag info )
audio ( any sounds attached to this entity )
parent ( attached child entities )
child ( which parent am I bound to )
collision ( for non-physics things like triggers, and gameplay pick-ups )
subscribe ( any entities subscribing to my updates )

Share this post


Link to post
Share on other sites
Thanks for the responses guys, it's appreciated.

When using a single entity list stored in an entity manager class, I want to give each individual entity access to that list so that it can remove/erase itself, search the list for objects colliding with itself, and so on. In this case, would it be best to make the list available to all entities, or give each entity a pointer to the manager class?

Also, slightly unrelated, but should vectors for things like velocity and acceleration for entities be kept private, with accessor/mutator functions being used to reach them from outside the class? Or is it fine to make them public? I don't think it's a huge deal but it would be handy to know if there's a standard approach.

Share this post


Link to post
Share on other sites
Give entities a way to signal that they want to be removed, and directly hand them the information about whether anything is colliding with them. You don't want entities directly messing with their container.

Re your second question: The basic idea with OO and encapsulation is not to expose data, but actions that modify the data. You might expose vectors and stuff with accessors for read-only access, but who besides the entity itself has any business messing with those values at all? I might expose functions like ApplyForce(vector), which would change the velocity and stuff, but only the entity should be directly modifying those values.

Share this post


Link to post
Share on other sites
Quote:
Original post by theOcelot
Give entities a way to signal that they want to be removed, and directly hand them the information about whether anything is colliding with them. You don't want entities directly messing with their container.

Re your second question: The basic idea with OO and encapsulation is not to expose data, but actions that modify the data. You might expose vectors and stuff with accessors for read-only access, but who besides the entity itself has any business messing with those values at all? I might expose functions like ApplyForce(vector), which would change the velocity and stuff, but only the entity should be directly modifying those values.


So I take it this checking for collisions would be a generic function held in the container class/wrapper, which is called from the game state, and then used to call the appropriate function from the entity class if any collisions have occurred?

Share this post


Link to post
Share on other sites
An adaptation of the way I do it now would be something like this:

struct Entity{
void Collide(const EntityCollisionInfo& info){
//info contains all the information I can use
//about what I just collided with
}
};


Entity is entirely responsible for responding sensibly. The tricky part is sending all the information needed for a response in one package. It helps that my game is heavily data-driven, so its easy to send all the information in a single object without resorting to RTTI. In a game with an entity inheritance hierarchy, you might include a pointer to the original entity, perhaps a const pointer for good measure.

This function is called by the simulation code, that manages all the entities. I think that's what you mean by the "game state".

Share this post


Link to post
Share on other sites
Thanks a lot for the help so far guys, it's been immense.

theOcelot: In the example in your last post, where would I add Sprites for things like explosions? The most obvious seems to be in the class of the object which was destroyed, but that would require giving the object access to the list of game objects.

Another way of doing it would be to make the object signal to the list it's contained in that it can be removed (a destroyed bool maybe), and create the appropriate explosion object during the cleanup loop. Would this be a good idea?

Share this post


Link to post
Share on other sites
Quote:
Original post by Exomoto
but having to constantly write template functions to run through a list (updates, collisions, recycling) and then make multiple calls to that function for lots of different lists seems a bit messy.


This is, pretty much, the simple way, and you'll get over the sense of apparent "messiness". The upside of keeping each entity type in its own list is that you never have to wonder about the exact type of an entity; it's implied by the container. The list-of-everything really only makes sense so long as you really only need the bit of interface that's common to every entity type. There's dynamic_cast, yes, but it gets even messier.

The basic rule is that inheritance and (classical) polymorphism are for forgetting type information (when it would only get in your way) and templates (used for compile-time polymorphism) are for remembering it (when you really need it). :)

Share this post


Link to post
Share on other sites
It depends on whether the explosion is just a sprite, or can actually have an effect on other entities. By my philosophy, if it can have an effect on other entities, it needs to be an entity. If it's just a graphical entity, I might add it to a list of other "just sprites", like explosions and effects, and update them independently.

I allow entities to have a pointer to the simulation they live in, and it has a function called add_entity, which can be called by entities. It's not quite as bad as letting them mess with the list. If you took my philosophy, you might also have a function named add_sprite, which takes a simple sprite and adds it to a list to be managed.

As for when it should be created and by whom, just do what makes sense from the perspective of each of the objects involved, particularly that of the entity doing the exploding. If the entity always needs to explode when it dies, then it needs to make sure that happens itself. However, if whether it explodes depends on information that should only reasonably be known by the simulation as a whole, then the simulation will have to add the explosion itself.

I definitely recommend a destroyed bool.

Share this post


Link to post
Share on other sites
What about allowing entities access to other entities? For example, my current prototype has a fang object which attaches to enemies and drains energy, which is then passed to the player. Currently this is done by detecting when the fang has attached to an enemy and then passing that enemy object to an enemy instance held in the fang object. The enemy is then drained, destroyed, and then enemy instance in the fang object is set to NULL. Is this an acceptable approach or a bit too messy? (I think my software engineering knowledge is a bit lacking).

Share this post


Link to post
Share on other sites
Hey again guys,

After working with my prototype a little and doing some research, I decided that the best way to move forward was to start again from scratch and take a component-based approach. I've also switched to DX10 since I've been studying it anyway.

Things were going well but I've run into a problem. Basically I have a Shape component which stores a pointer to a vertex buffer, a pointer to an index buffer, an ID, and some functions like Init() and Draw(). This is the component responsible for drawing various things to the screen, although for now I just have one instance which holds a box and is a component of the Player class.

The problem is, I want to be able to create a Shape in my App class which is then passed to the appropriate entities when necessary. However, because this component has two pointers to buffers, deleting one copy anywhere results in the buffers being freed and the game throwing an exception.

This issue means even creating one Shape component in App and then passing it to Player results in an exception when the application closes. How should I avoid this?

Share this post


Link to post
Share on other sites
Sorry, I thought I replied to your last post, but apparently it got lost.

The quickest way out of your current problem would be to pass a Shape* to the Player rather than a copy. However, it's probably not a good idea for a mesh to directly be a component; I would want the component to be a higher-level object that not only contains the mesh, but handles animations and whatever else needs handling. It depends on which flavor of component-orientation you're using.

The general problem of multiple objects sharing references to dynamic data is a separate one. You'll need to somehow keep track of how many objects are using the given resource. The easiest way to do this is to use a boost::shared_ptr to the resource instead of a plain pointer. A shared_ptr increases an internal reference count when it is copied and decreases it when it is destructed. Then when all the shared_ptr's are destructed, the ref count goes to zero and the resource is freed, either using delete or a custom function.

When you have an unrelated question, it's best to start a new thread.

Share this post


Link to post
Share on other sites
Quote:
Original post by theOcelot
Sorry, I thought I replied to your last post, but apparently it got lost.

The quickest way out of your current problem would be to pass a Shape* to the Player rather than a copy. However, it's probably not a good idea for a mesh to directly be a component; I would want the component to be a higher-level object that not only contains the mesh, but handles animations and whatever else needs handling. It depends on which flavor of component-orientation you're using.

The general problem of multiple objects sharing references to dynamic data is a separate one. You'll need to somehow keep track of how many objects are using the given resource. The easiest way to do this is to use a boost::shared_ptr to the resource instead of a plain pointer. A shared_ptr increases an internal reference count when it is copied and decreases it when it is destructed. Then when all the shared_ptr's are destructed, the ref count goes to zero and the resource is freed, either using delete or a custom function.

When you have an unrelated question, it's best to start a new thread.


No problem, I figured out an adequate fix for my last problem after a decent amount of sleep.

I've switched to passing a Shape* since my last post, and resorted to releasing the buffers in a CleanUp() function, which is called once in the App() destructor. Using a shared_ptr sounds much more flexible though so I'll switch to that.

Edit: Cutting this question out, there's really no need to store a vertex and index array once the appropriate buffers are filled.

And apologies for not creating a new thread, I'll think ahead next time.

[Edited by - Exomoto on January 15, 2010 7:45:33 PM]

Share this post


Link to post
Share on other sites

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