18
\$\begingroup\$

I find it hard to find a way to organize game objects so that they are polymorphic but at the same time not polymorphic.

Here's an example: assuming that we want all our objects to update() and draw(). In order to do that we need to define a base class GameObject which have those two virtual pure methods and let polymorphism kicks in:

class World {
private:
    std::vector<GameObject*> objects;
public:
    // ...
    update() {
        for (auto& o : objects) o->update();
        for (auto& o : objects) o->draw(window);
    }
};

The update method is supposed to take care of whatever state the specific class object needs to update. The fact is that each objects needs to know about the world around them. For example:

  • A mine needs to know if someone is colliding with it
  • A soldier should know if another team's soldier is in proximity
  • A zombie should know where the closest brain, within a radius, is

For passive interactions (like the first one) I was thinking that the collision detection could delegate what to do in specific cases of collisions to the object itself with a on_collide(GameObject*).

Most of the the other informations (like the other two examples) could just be queried by the game world passed to the update method. Now the world does not distinguish objects based on their type (it stores all object in a single polymorphic container), so what in fact it will return with an ideal world.entities_in(center, radius) is a container of GameObject*. But of course the soldier does not want to attack other soldiers from his team and a zombie doesn't case about other zombies. So we need to distinguish the behavior. A solution could be the following:

void TeamASoldier::update(const World& world) {
    auto list = world.entities_in(position, eye_sight);
    for (const auto& e : list)
        if (auto enemy = dynamic_cast<TeamBSoldier*>(e))
            // shoot towards enemy
}

void Zombie::update(const World& world) {
    auto list = world.entities_in(position, eye_sight);
    for (const auto& e : list)
        if (auto enemy = dynamic_cast<Human*>(e))
            // go and eat brain
}

but of course the number of dynamic_cast<> per frame could be horribly high, and we all know how slow dynamic_cast can be. The same problem also applies to the on_collide(GameObject*) delegate that we discussed earlier.

So what it the ideal way to organize the code so that objects can be aware of other objects and be able to ignore them or take actions based on their type?

\$\endgroup\$
  • 1
    \$\begingroup\$ I think you're looking for a versatile C++ RTTI custom implementation. Nevertheless, your question does not seem to be only about judicious RTTI mechanisms. The things you ask for are required by almost any middleware the game will use (animation system, physics to name a few). Depending on the list of supported queries, you could cheat your way around RTTI using IDs and indices in arrays, or you'll end up designing a full fledged protocol for supporting cheaper alternatives to dynamic_cast and type_info. \$\endgroup\$ – teodron Oct 25 '13 at 6:04
  • \$\begingroup\$ I'd advise against using the type system for game logic. For example, instead of depending on the result of dynamic_cast<Human*>, implement something like a bool GameObject::IsHuman(), which returns false by default but is overridden to return true in the Human class. \$\endgroup\$ – congusbongus Oct 25 '13 at 6:06
  • \$\begingroup\$ an extra: you almost never send a ton of objects to each other entity that might be interested in them. That's an obvious optimization you'll have to really consider. \$\endgroup\$ – teodron Oct 25 '13 at 6:20
  • \$\begingroup\$ @congusbongus Using a vtable and custom IsA overrides proved to be only marginally better than dynamic casting in practice for me. The best thing to do is for the user to have, wherever possible, sorted data lists instead of iterating blindly over the whole entity pool. \$\endgroup\$ – teodron Oct 25 '13 at 6:23
  • 4
    \$\begingroup\$ @Jefffrey: ideally you don't write type-specific code. You write interface-specific code ("interface" in the general sense). Your logic for a TeamASoldier and TeamBSoldier is really identical -- shot at anyone on the other team. All it needs of other entities is a GetTeam() method at its most specific and, by congusbongus's example, that can be abstracted even further into IsEnemyOf(this) kind of interface. The code doesn't need to care about taxonomical classifications of soldiers, zombies, players, etc. Focus on interaction, not types. \$\endgroup\$ – Sean Middleditch Oct 25 '13 at 7:37
11
\$\begingroup\$

Instead of implementing the decision-making of each entity in itself, you could alternatively go for the controller-pattern. You would have central controller classes which are aware of all objects (which matter to them) and control their behavior.

A MovementController would handle the movement of all objects which can move (do the route finding, update positions based on current movement vectors).

A MineBehaviorController would check all the mines and all the soldiers, and command a mine to explode when a soldier gets too close.

A ZombieBehaviorController would check all zombies and the soldiers in their vicinity, pick the best target for each zombie, and command it to move there and attack it (the move itself is handled by the MovementController).

A SoldierBehaviorController would analyze the whole situation and then come up with tactical instructions for all soldiers (you move there, you shoot this, you heal that guy...). The actual execution of these higher-level commands would also be handled by lower-level controllers. When you put some effort into it, you could make the AI capable of quite smart cooperative decisions.

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Probably this is also known as the "system" that manages the logic for certain types of components in an Entity-Component architecture. \$\endgroup\$ – teodron Oct 25 '13 at 10:56
  • \$\begingroup\$ That sounds like a C-style solution. Components are grouped in std::maps and entities are only IDs and then we have to make some sort of type system (maybe with a tag component, because the renderer is gonna need to know what to draw); and if we don't want to do that we are going to need to have a drawing component: but it needs the position component to know where to get drawn, so we create dependencies between components that we solve with a super complex messaging system. Is this what you are suggesting? \$\endgroup\$ – Shoe Oct 25 '13 at 12:20
  • 1
    \$\begingroup\$ @Jefffrey "That sounds like a C-style solution" - even when that would be true, why would it necessarily be a bad thing? The other concerns might be valid, but there are solutions for them. Unfortunately a comment is too short to address each of them properly. \$\endgroup\$ – Philipp Oct 25 '13 at 12:36
  • 1
    \$\begingroup\$ @Jefffrey Using the approach where components themselves don't have any logic and the "systems" are responsible for handling all the logic doesn't create dependencies between components nor does it require super complex messaging system (at least, not nearly as complex). See for example: gamadu.com/artemis/tutorial.html \$\endgroup\$ – user9790 Oct 25 '13 at 20:30
1
\$\begingroup\$

First of all, try to implement features so that objects stay independent of each other, whenever possible. Especially you want to do that for multi threading. In your first code example, the set of all objects could be divided in sets matching the number of CPU cores and be updated very efficiently.

But as you said, interaction with other objects is needed for some features. That means that the state of all objects must be synchronized at some points. In other words, your application must wait for all parallel tasks to finish first, and then apply computations that involve interaction. It is good to reduce the number of these synchronization points, since they always imply that some threads must wait for others to finish.

Therefore, I suggest buffering those information about the objects that are needed from inside other objects. Given such a global buffer, you can update all you objects independent of each other but only dependent on themselves and the global buffer, which is both faster and easier to maintain. At a fixed timestep, say after each frame, update the buffer with the current objects´ state.

So what you do once per frame is 1. buffer the current objects´ state globally, 2. update all objects based on themselves and the buffer, 3. draw your objects and then start over with renewing the buffer.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Use a component based system, in which you have a barebones GameObject that contains 1 or more components which define their behavior.

For example say some object is supposed to move left and right all the time ( a platform ), you might create such a component and attach it to a GameObject.

Now say a game object is supposed to slowly rotate all the time, you could create a separate component which does just that and attach it to the GameObject.

What if you wanted to have a moving platform that also rotated, in a traditional class heirarchy that becomes difficult to do without duplicating code.

The beauty of this system, is that instead of having a Rotatable or a MovingPlatform class, you attach both of those components to the GameObject and you now have a MovingPlatform that AutoRotates.

All the components have a property, 'requiresUpdate' which while true, the GameObject will call the 'update' method on said component. For example, say you have a Draggable component, this component on mouse-down (if it was over the GameObject) can set 'requiresUpdate' to true, and then on mouse-up set it to false. Allowing it to follow the mouse only when the mouse is down.

One of the Tony Hawk Pro Skater developers has the defacto write up on it, and it's well worth reading: http://cowboyprogramming.com/2007/01/05/evolve-your-heirachy/

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Favour composition over inheritance.

My strongest advice aside from this would be: Don't get drawn into the mindset of "I want this to be supremely flexible". Flexibility is great, but remember that at some level, in any finite system such as a game, there are atomic parts which are used to construct the whole. One way or another, your processing relies on those pre-defined, atomic types. In other words, catering for "any" type of data (if that were possible) wouldn't help you in the long run, if you don't have code to process it. Fundamentally, all code must parse / process data based on known specifications... which means a predefined set of types. How large that set? Up to you.

This article offers insight into the principle of Composition over Inheritance in games development via a robust and performant entity-component architecture.

By building up entities out of (differing) subsets of some superset of predefined components, you offer your AIs concrete, piecemeal ways of comprehending the world and actors around them, by reading those actors' components' states.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Personally I recommend keeping the draw function out of the Object class itself. I even recommend keeping the Objects location/coordinates out of the Object itself.

That draw() method is going to be dealing with low level rendering API of either OpenGL, OpenGL ES, Direct3D, your wrapping layer on those APIs or an engines API. It might be that you have to swap between then (If you wanted to support OpenGL + OpenGL ES + Direct3D for example.

That GameObject should just contain the basic information about it's visual appearance such as a Mesh or maybe a bigger bundle including shader inputs, animation state and so on.

Also you are going to want a flexible graphics pipeline. What happens if you want to order objects based on their distance to the camera. Or their material type. What happens if you want to draw a 'selected' object a different color. What about if instead of actually rending as soo as you call a draw function on an object, instead it puts it into a command list of actions for the render to take (might be needed for threading). You can do that kind of thing with the other system but it's a PITA.

What I recommend is instead of drawing directly, you bind all the objects you want to another data structure. That binding only really need to have a reference to the objects location and the rendering information.

Your levels/chunks/areas/maps/hubs/wholeworld/whatever get given a spacial index, this contains the objects and returns them based on coordinate queries and could be a simple list or something like an Octree. It could also be a wrapper to something implemented by a 3rd party physics engine as a physics scene. It allows for you to do things like "Query all objects that are in the view of the camera with some extra area around them", or for simpler games where you can just render everything grab the whole list.

Spacial Indexes don't have to contain the actual positioning information. They work by storing objects in tree structures in relation to the location of other objects. They can be though of as a kind of lossy cache allowing a quick lookup of an object based on its position. There's no real need to duplicate your actual X, Y, Z coordinates. Having said that you could if you wanted to keep

In fact your game objects don't even need to contain their own location information. For example an object that hasn't been put into a level shouldn't have x,y,z coordinates, that makes no sense. You can contain that in the special index. If you need to lookup the coordinates of the object based on its actual reference then you will want to have a binding between the object and the scene graph (scene graphs are for returning objects based on coordinates but are slow at returning coordinates based on objects).

When you add an Object to a Level. It will do the following:

1) Create a Location Structure:

 class Location { 
     float x, y, z; // Or a special Coordinates class, or a vec3 or whatever.
     SpacialIndex& spacialIndex; // Note this could be the area/level/map/whatever here
 };

This could also be a reference to an object in a 3rd party physics engines. Or it could be an offset coordinates with a reference to another location (for a tracking camera or an attached object or example). With polymorphism it could be either depending on if it's a static or dynamic object. By keeping a reference to the spacial index here when the coordinates are updated the spacial index can be too.

If you are worried about dynamic memory allocation, use a memory pool.

2) A binding/linking between your object, its location and the scene graph.

typedef std::pair<Object, Location> SpacialBinding.

3) The Binding is added to the spacial index inside of the level at the appropriate point.

When you are preparing to render.

1) Get the camera (It will just be another object, except it's location will be tracking the players character and your renderer will have a special reference to it, in fact that's all it really needs).

2) Get the camera's SpacialBinding.

3) Get the spacial index from the binding.

4) Query the objects that are (possibly) visible to the camera.

5A) You need to have the visual information processed. Textures uploaded to the GPU and so on. This would be best done in advance (such as on level load) but perhaps could be done at runtime (for an open world, you could load stuff when you are nearing a chunk but should still be done in advance).

5B) Optionally build a cached render tree, if you want to depth/material sort or keep track of nearby objects the might be visible at a later time. Otherwise you can just query the spacial index everytime it will depend on your game/performance requirements.

Your renderer will likely need a RenderBinding object that will link between the Object, the coordinates

class RenderBinding {
    Object& object;
    RenderInformation& renderInfo;
    Location& location // This could just be a coordinates class.
}

Then when you render, just run though the list.

I have used references above but they could be smart pointers, raw pointers, object handles and so on.

EDIT:

class Game {
    weak_ptr<Camera> camera;
    Level level1;

    void init() {
        Camera camera(75.0_deg, 1.025_ratio, 1000_meters);
        auto template_player = loadObject("Player.json")
        auto player = level1.addObject(move(player), Position(1.0, 2.0, 3.0));
        level1.addObject(move(camera), getRelativePosition(player));

        auto template_bad_guy = loadObject("BadGuy.json")
        level1.addObject(template_bad_guy, {10, 10, 20});
        level1.addObject(template_bad_guy, {10, 30, 20});
        level1.addObject(move(template_bad_guy), {50, 30, 20});
    }

    void render() {
        camera->getFrustrum();
        auto level = camera->getLocation()->getLevel();
        auto object = level.getVisible(camera);
        for(object : objects) {
            render(objects);
        }
    }

    void render(Object& object) {
        auto ri = object.getRenderInfo();
        renderVBO(ri.getVBO());
    }

    Object loadObject(string file) {
        Object object;
        // Load file from disk and set the properties
        // Upload mesh data, textures to GPU. Load shaders whatever.
        object.setHitPoints(// values from file);
        object.setRenderInfo(// data from 3D api);
    }
}

class Level {
    Octree octree;
    vector<ObjectPtr> objects;
    // NOTE: If your level is mesh based there might also be a BSP here. Or a hightmap for an openworld
    // There could also be a physics scene here.
    ObjectPtr addObject(Object&& object, Position& pos) {
        Location location(pos, level, object);
        objects.emplace_back(object);
        object->setLocation(location)
        return octree.addObject(location);
    }
    vector<Object> getVisible(Camera& camera) {
        auto f = camera.getFtrustrum();
        return octree.getObjectsInFrustrum(f);
    }
    void updatePosition(LocationPtr l) {
        octree->updatePosition(l);
    }
}

class Octree {
    OctreeNode root_node;
    ObjectPtr add(Location&& object) {
        return root_node.add(location);
    }
    vector<ObjectPtr> getObjectsInRadius(const vec3& position, const float& radius) { // pass to root_node };
    vector<ObjectPtr> getObjectsinFrustrum(const FrustrumShape frustrum;) {//...}
    void updatePosition(LocationPtr* l) {
        // Walk up from l.octree_node until you reach the new place
        // Check if objects are colliding
        // l.object.CollidedWith(other)
    }
}

class Object {
    Location location;
    RenderInfo render_info;
    Properties object_props;
    Position getPosition() { return getLocation().position; }
    Location getLocation() { return location; }
    void collidedWith(ObjectPtr other) {
        // if other.isPickup() && object.needs(other.pickupType()) pick it up, play sound whatever
    }
}

class Location {
    Position position;
    LevelPtr level;
    ObjectPtr object;
    OctreeNote octree_node;
    setPosition(Position position) {
        position = position;
        level.updatePosition(this);
    }
}

class Position {
    vec3 coordinates;
    vec3 rotation;
}

class RenderInfo {
    AnimationState anim;
}
class RenderInfo_OpenGL : public RenderInfo {
    GLuint vbo_object;
    GLuint texture_object;
    GLuint shader_object;
}

class Camera: public Object {
    Degrees fov;
    Ratio aspect;
    Meters draw_distance;
    Frustrum getFrustrum() {
        // Use above to make a skewed frustum box
    }
}

As for making things 'aware' of each other. That's collision detection. It would be implemented in the Octree probably. You would need to provide some callback in your main object. This stuff is best handled by a proper physics engine such as Bullet. In that case just replace Octree with PhysicsScene and Position with a link to something like CollisionMesh.getPosition().

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Wow, this looks very good. I think I've grasped the basic idea, but without more example I can't quite get the outer view of this. Do you have any more references or live examples on this? (I'll keep reading this answer for a while in the meantime). \$\endgroup\$ – Shoe Nov 1 '13 at 1:16
  • \$\begingroup\$ Don't really have any examples, it's just what I'm planning to do when I get time. I'll add a few more of the overall classes and see if that helps, There is this and this. it's more about object classes than how they relate or the rendering. As I haven't implemented it myself there might be pitfalls, bits that need working out or performance stuff but I think the overall structure is ok. \$\endgroup\$ – David C. Bishop Nov 1 '13 at 5:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.