What is the most elegant and efficient way to model a game object hierarchy? (design bothers)

Question

I've got the following code, think simple shooter in c++:

// world.hpp
//----------
class Enemy;
class Bullet;
class Player;

struct World
{
  // has-a collision map
  // has-a list of Enemies
  // has-a list of Bullets
  // has-a pointer to a player
};

// object.hpp
//-----------
#include "world.hpp"

struct Object
{
  virtual ~Object();
  virtual void Update() =0;
  virtual void Render() const =0;

  Float xPos, yPos, xVel, yVel, radius;  // etc.
};

struct Enemy: public Object
{
  virtual ~Enemy();
  virtual void Update();
  virtual void Render() const;
};

// Bullet and Player are similar (they render and update differently per se,
/// but the behavior exposed to World is similar) 

// world.cpp
//----------
#include "object.hpp"

// object.cpp
//-----------
#include "object.hpp"

Two problems with this:

1, Game objects knowing about other game objects.

There has to be a facility that knows about all objects. It might or might not have to expose ALL objects, it has to expose some of it, depending parameters of the enquirer (position, for one). This facility is supposed to be World.

Objects have to know about the World they're in, to query for collision information and other objects.

This introduces a dependency where both Objects' and World's implementation have to access to object's header, thus World won't include its own header directly rather than by including object.hpp (which in turn includes world.hpp). This makes me feel uncomfortable -- I don't feel that world.cpp should recompile after I make a change to object.hpp. World doesn't feel like it should work with Object. It feels like bad design - how can it be fixed?

2, Polymorphism -- can and should it be used for anything beyond code reuse and logical grouping of game entities (and how)?

Enemies, Bullets and Player will update and render differently, surely, hence the virtual Update() and Render() functionality -- an identical interface. They're still kept in separate lists and the reason for this is that their interaction depends on which lists two interacting objects are - two Enemies bounce off each other, a Bullet and an Enemy destroys each other etc.

This is functionality that's beyond the implementation of Enemy and Bullet; that's not my concern here. I feel that beyond their identical interfaces there's a factor that separates Enemies, Bullets and Players and this could and should be expressed in some other way, allowing me to create a single list for all of them -- as their interface is identical!

The problem is how to tell an object category from another if contained within the same list. Typeid or other form of type identification is out of the question - but then what other way to do it? Or maybe there's nothing wrong with the approach?

Answer 1

This is probably the biggest issue I encounter when designing similar programs. The approach I've settled on is to realize that an object really does not care about where it is in absolute terms. All it cares about is what is around it. As a result, the World object (and I prefer the object approach to a singleton for many good reasons which you can search for on the Internet) maintains where all the objects are, and they can ask the world what objects are nearby, where other objects are in relation to it, etc. World should not care about the content of Object; it will hold pretty much anything, and the Objects themselves will define how they interact with each other. Events are also a great way to handle objects interacting, as they provide a means for World to inform an Object of what's going on without caring what an Object is.

Hiding information from an Object about all objects is a good idea, and should not be confused with hiding information about any Object. Think in terms of people - it's reasonable for you to know and retain information about many different people, though you can only find that information out by encountering them or having someone else telling you about them.

EDIT AGAIN:

All right. It's pretty clear to me what you really want, and that is multiple dispatch - the ability to handle a situation polymorphically on types of many parameters to the function call, rather than just one. C++ unfortunately does not support multiple dispatch natively.

There are two options here. You can attempt to reproduce multiple dispatch with double dispatch or the visitor pattern, or you can use dynamic_cast. Which you want to use depends on the circumstances. If you have a lot of different types to use this on, dynamic_cast is probably the better approach. If you have only a few, double dispatch or the visitor pattern is probably more appropriate.

Answer 2

I think you'd want to hand a reference to the World to the game object. This is a pretty basic tenet of Dependency Injection. For collisions, the World can use the Strategy pattern to resolve how specific types of objects interact.

This keeps knowledge of different object types out of the primary objects and encapsulates it in objects with knowledge specific to the interaction.

Answer 3

Objects have to know about the World they're in, to query for collision information and other objects.

In short - no, they don't. Classes like the World can handle most of that and all the Object has to do is behave appropriately when the World tells it that there's been a collision.

Sometimes you might need the Object to have some sort of context in order to make some other type of decision. You can pass the World object in at that point when needed. However, iInstead of passing the World, it's better to pass in some smaller, more relevant object depending on what sort of query is actually being performed. It is likely to be the case that your World object is performing several different roles and the Objects only ever need transient access to one or two of those roles. In that case it's good to split the World object up into sub-objects, or if that's not practical, have it implement several distinct interfaces.

Answer 4

After giving it much thought I realized that although Objects DO need to have access to a World, it is NOT World's responsibility to serve up nearby Objects to Objects.

This is what I had the Arena non-object (never instantiated + all static members, contains lists of the required object categories - bullets, enemies, visuals etc.) for, however it introduced a similar dependency structure as having the category lists as part of World (which is why it didn't feel like a good solution):

// object.hpp
//-----------
#include "world.hpp"

// NOTE: the obvious virtual and pure virtual methods are omitted in the following code
class Object
{...};

class Enemy: public Object
{...};

class Bullet: public Object
{...};

class Player: public Object
{...};

// arena.hpp
//-----------
#include "object.hpp"

struct Arena
{
  // has-a lists of object categories and a (pointer to a) player
}

// object.cpp
//-----------
#include "arena.hpp" // for the damn dependencies

// arena.cpp
//-----------
#include "arena.hpp"

So, the solution, or what it seems to be at this point, is to have the entirety of the object( categorie)s not one compilation level above or below the declaration of the objects, but on the same level.

// object.hpp
//-----------
#include "world.hpp"

class Object
{
  static World *pWorld;
  ...
};

class Enemy: public Object
{
  typedef std::list<Enemy*> InstList;
  static InstList insts;
  ...
};

class Bullet: public Object
{
  typedef std::list<Bullet*> InstList;
  static InstList insts;
  ...
};

class Player: public Object
{
  static Player *pThePlayer;
  ...
};

// object.cpp
//-----------
#include "object.hpp"

Even if there are further headers for specializing enemies, bullets etc. their (and others') categories' lists are fully available for them by including object.hpp which they obviously have to anyway.

About the polymorphism bit and why the different categories are kept in separate lists: the object categories' base classes (Bullet, Enemy, Player) can provide "event handlers" for hitting objects of certain types; they, however aren't declared on Object level rather than category level. (e.g. we don't care about bullet-vs-bullet collisions, they're not checked and not handled.)

// object.hpp
//-----------
#include "world.hpp"

class Object
{
  static World *pWorld;
  ...
};

class Bullet: public Object
{
  typedef std::list<Bullet*> InstList;
  static InstList insts;
  ...
};

class Player: public Object
{
  static Player *pThePlayer;

  void OnHitBullet(const Bullet *b);
  ...
};

class Enemy: public Object
{
  typedef std::list<Enemy*> InstList;
  static InstList insts;

  virtual void OnHitBullet(const Bullet *b);
  virtual void OnHitPlayer(const Player *p);
  ...
};

EDIT, for completeness' sake:

// game.hpp
//-----------
#include "object.hpp"

struct Game
{
  static World world;

  static void Update(); // update world and objects, check for collisions and
                        /// handle them.
  static void Render();
};