Best way to organize entities in a game?

Question

Let's say I'm creating an OpenGL game in C++ that will have many objects created (enemies, player characters, items, etc.). I'm wondering the best way to organize these since they will be created and destroyed real-time based on time, player position/actions etc.

Here's what I've thought of so far: I can have a global array to store pointers to these objects. The textures/context for these objects are loaded in their constructors. These objects will have different types, so I can cast the pointers to get them in the array, but I want to later have a renderObjects() function that will use a loop to call an ObjectN.render() funtion for each existing object.

I think I've tried this before but I didn't know what type to initialize the array with, so I picked an arbitrary object type, then cast anything that wasn't of that type. If I remember, this didn't work because the compiler didn't want me dereferencing the pointers if it no longer knew their type, even if a given member function had the same name: (*Object5).render() <-doesn't work?

Is there a better way? How to commercial games like HL2 handle this? I imagine there must be some module etc that keeps track of all the objects.

Thanks!

Answer 1

I'm not sure I fully understand the question but I think you are wanting to create a collection of polymorphic objects. When accessing a polymorphic object, you must always refer to it by a pointer.

Here is an example. First you need to set up a base class to derive your objects from:

class BaseObject
{
public:
    virtual void Render() = 0;
};

Then create the array of pointers. I use an STL set because that makes it easy to add and remove members at random:

#include <set>

typedef std::set<BaseObject *> GAMEOBJECTS;
GAMEOBJECTS g_gameObjects;

To add an object, create a derived class and instantiate it:

class Enemy : public BaseObject
{
public:
    Enemy() { }
    virtual void Render()
    {
      // Rendering code goes here...
    }
};

g_gameObjects.insert(new Enemy());

Then to access objects, just iterate through them:

for(GAMEOBJECTS::iterator it = g_gameObjects.begin();
    it != g_gameObjects.end();
    it++)
{
    (*it)->Render();
}

To create different types of object, just derive more classes from class BaseObject. Don't forget to delete the objects when you remove them from the collection.

Answer 2

You should make a superclass of all your objects that has a generic render() method. declare this method virtual, and have each subclass implement it in its own way.

Answer 3

The way I've been approaching it is to have a display layer that knows nothing about the gameworld itself. its only job is to recieve an ordered list of objects to draw onto the screen that all fit a uniform format for a graphic object. so for instance, if it's a 2D game, your display layer will receive a list of images along with their scaling factor, opacity, rotation, flip, and source texture, and whatever other attributes a display object could have. The view may also be responsible for recieving high level mouse interactions with these displayed objects and dispatching them somewhere appropriate. But it's important that the view layer not know anything sementically about what it is that it's displaying. Only that it's some kind of square with a surface area, and some attributes.

Then the next layer down is a program whose job it is simply to generate a list of these objects in order. It's helpful if each object in the list has some kind of unique ID, as it makes certain optimisation strategies possible in the view layer. Generating a list of display objects is a much less daunting sort of task than trying to figure out for each sort of character how its going to physically render itself.

Z sorting is simple enough. Your display object generating code just needs to generate the list in the order that you want, and you can use whatever means you need to to get there.

In our display object list program, each character, prop and NPC has two parts: A resource database assistant, and a character instance. The database assistant presents for each character a simple interface from which each character can pull up any image/statistics/animation/arrangement etc that the character will need. You'll probably want to come up with a fairly uniform interface for fetching the data, but it's going to vary a little from object to object. A tree or a rock doesn't need as much stuff as a fully animated NPC for example.

Then you need some way of generating an instance for each type of object. You might implement this dichotomy using your language's built in class/instance systems, or depending on your needs, you may need to work a little beyond that. for example, having each resource database be an instance of a resource database class, and each character instance being an instance of a "character" class. This saves you from writing a chunk of code for every single little object in the system. This way you only need to write code for broad categories of objects, and only change little things like which row of a database to fetch images from.

Then, don't forget to have an internal object representing your camera. Then it's your camera's job to query each character about where they are in relation to the camera. It is basically going around each character instance and asking for its display object. "What do you look like, and where are you?"

Each character instance in turn has its own little resourcey databasey assistant thing to query. So each character instance has available to it all the information it needs to tell the camera what it needs to know.

This leaves you with a set of character instances in a world that's more or less oblivious to the nitty gritty of how they are to be displayed on a physical screen, and more or less oblivious to the nitty gritty of how to fetch image data from the hard drive. This is good- it leaves you with as clean a slate as possible for a sort of platonically "pure" world of characters in which you can implement your game logic without worrying about things like falling off the edge of the screen. Think of what sort of interface you would like if you were to put a scripting language into your game engine. Simple as possible right? As grounded in a simulated world as possible, without worrying about little technical implementation details right? That's what this strategy lets you do.

Additionally, the separation of concerns lets you swap out the display layer with whatever technology you like: Open GL, DirectX, software rendering, Adobe Flash, Nintendo DS, whatever- Without having to fuss around too much with the other layers.

In addition, you can actually swap out the database layer to do things like reskin all the characters- Or depending on how you built it, swap in a completely new game with new content that reuses the bulk of the character interactions/ collision detection/ path finder code that you wrote in the middle layer.

Answer 4

For my soon-to-be personal game project, I use a component-based entity system.

You can read more about it by searching "component based game development". A famous article is Evolve Your Hierarchy from the Cowboy programming blog.

In my system, entities are just ids - unsigned long, a bit like in a relational database. All the data and the logic associated to my entities are written into Components. I have Systems that link entity ids with their respective components. Something like that:

typedef unsigned long EntityId;

class Component {
    Component(EntityId id) : owner(id) {}
    EntityId owner;
};

template <typename C> class System {
    std::map<EntityId, C * > components;
};

Then for each kind of functionality, I write a special component. All entities don't have the same components. For example you could have a static rock object that has the WorldPositionComponent and the ShapeComponent, and a moving enemy that has the same components plus the VelocityComponent. Here's an example:

class WorldPositionComponent : public Component {
    float x, y, z;
    WorldPositionComponent(EntityId id) : Component(id) {}
};

class RenderComponent : public Component {
    WorldPositionComponent * position;
    3DModel * model;
    RenderComponent(EntityId id, System<WorldPositionComponent> & wpSys)
        : Component(id), position(wpSys.components[owner]) {}
    void render() {
        model->draw(position);
    }
};

class Game {
    System<WorldPositionComponent> wpSys;
    System<RenderComponent> rSys;
    void init() {
        EntityId visibleObject = 1;
        // Watch out for memory leaks.
        wpSys.components[visibleObject] = new WorldPositionComponent(visibleObject);
        rSys.components[visibleObject] = new RenderComponent(visibleObject, wpSys);
        EntityId invisibleObject = 2;
        wpSys.components[invisibleObject] = new WorldPositionComponent(invisibleObject);
        // No RenderComponent for invisibleObject.
    }
    void gameLoop() {
        std::map<EntityId, RenderComponent *>::iterator it;
        for (it = rSys.components.iterator(); it != rSys.components.end(); ++it) {
            (*it).second->render();
        }
    }
};

Here you have 2 components, WorldPosition and Render. The Game class holds the 2 systems. The Render component has an access to the position of the object. If the entity doesn't have a WorldPosition component, you can choose default values, or ignore the entity. The Game::gameLoop() method will only render visibleObject. There is no waste of processing for non-renderable components.

You can also split my Game class into two or three, to separate display and input systems from the logic. Something like Model, View and Controller.

I find it neat to define my game logic in term of components, and to have entities that only have the functionality that they need - no more empty render() or useless collision detection checks.

Answer 5

Is there a better way? How to commercial games like HL2 handle this? I imagine there must be some module etc that keeps track of all the objects.

Commercial 3D games use a variation on the Scene Graph. An object hierarchy like the one Adam describes is placed in what is usually a tree structure. To render or manipulate objects, you simply walk the tree.

Several books discuss this, and the best I've found are 3D Game Engine Design and Architecture, both by David Eberly.