7
\$\begingroup\$

In the light of DRY, it seems desirable to store a collection of related game objects in one container only. However, one might need sub-collections of these objects in various contexts. It might be sensible store these specific sub-sets in specific more suitable containers. This increases the effort to track objects across containers, for instance when objects are removed from the game world.

What are possibilities to simplify such a design and what are the typical trade-offs?

To illustrate:

In a multiplayer role playing game, the server might hold a collection of game characters in a map suitable for lookup by id.

world
    map<id, Character> allCharacters

A character may also reside in a certain game level. In order to identify all characters being present in a level it may seem suitable to introduce a container for each level which holds the characters currently present on it. This way you can execute common logic for all characters in that level.

world
    map<id, Character> allCharacters

    [levels]
        level1
           vector<Character> charactersOnPlayfield
        level2
           vector<Character> charactersOnPlayfield
        ...

Going even further, when a character interacts with the world messages should only be routed to characters in range. This interest management could be achieved by dividing the each level into a grid of cells each of which in turn store the characters currently standing on it.

world
    map<id, Character> allCharacters

    [levels]
        level1
           vector<Character> charactersOnPlayfield
           [cells]
               cell1
                   vector<Character> charactersOnCell
               cell2
                   vector<Character> charactersOnCell
               ...
        level2
           vector<Character> charactersOnPlayfield
           [cells]
               cell1
                   vector<Character> charactersOnCell
               cell2
                   vector<Character> charactersOnCell
               ...
        ...

The Character objects at different levels of abstraction introduce the need to think carefully about object ownership and life-time.

Note that the Character objects stored in the containers would naturally be references, not copies. Also, I am assuming that no garbage collection is in place.

|improve this question
\$\endgroup\$
6
\$\begingroup\$

I would advice against actually having multiple lists like that and instead use some kind of signal/slot library instead (which basically is the observer pattern) to make the "calling a function on all objects in this area/zone" pattern easier.

Objects could manage what signal they connect to themselves pretty easily, i.e. every time they move they disconnect from the signal representing their old slot and connect to the new one, if you're going to be that fine grained.

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ That, or by building read-only observable/filtered collections which base their contents off of another collection. Alternatively, you could build partitioned collections which can be viewed in terms of the child collections (one representing each 'partition') or the entire (aggregate) collection. I generally go with one of those approaches unless there is some compelling reason for an object to have discrete membership in separate collections (usually, there isn't). In either case, you need to give consideration to concurrent access, and you'll probably want snapshot/versioning capability. \$\endgroup\$ – Mike Strobel Aug 9 '10 at 17:54
3
\$\begingroup\$

Every Character should, one way or another, know all the containers it's contained in. That can be explicit (an actual list of the containers that reference it), computable (the character coordinates are stored, from which the actual cell vectors can be derived), or unspoken ("characters might also be stored in any of these six lists and I'm not going to bother keeping track of which"). Or any combination of the three. The important part is that it's easy and efficient to find every location that looks at a character.

There should also be a canonical storage that stores every character in the game, such as your allCharacters map up there.

A character is alive if and only if it's contained in allCharacters. If you want to remove it from allCharacters, you remove it from every container that contains it also (which, as per first paragraph, should be reasonably efficient) and you're set.

This assumes you don't have garbage collection - if you do, you can mostly get away with letting the GC take care of it. If you end up with leaks, just make a weak-reference container holding every entity, and use that for analyzing which entities are leaking.

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ Thanks that is helpful. I am assuming no garbage collection, added that to my question. \$\endgroup\$ – jmp97 Aug 9 '10 at 8:21
  • \$\begingroup\$ I've never used a platform in which I can rely on the GC for gameplay logic. Most platforms have a delay - variable-length, for generational GCs - that might be dozens of frames long, before they will really collect something. Some languages like Python do ensure finalization of non-circular references immediately, but it's very rare to not have them in games especially at death (A and B shooting each other; one dies). \$\endgroup\$ – user744 Aug 9 '10 at 11:03
  • \$\begingroup\$ @Joe, I'm not really talking about using it for gameplay logic, but you can easily use it for the difficult parts of cruft collection. With jmp97's hypothetical, you can have a "player is still alive" flag, and then add a simple conditional to the "interaction broadcast" system to make sure a player's alive before sending stuff to it. (Or bake that into the data structure traversal.) At that point your gameplay logic is centralized in that simple flag and you can also rely on the GC cleaning up the memory later. \$\endgroup\$ – ZorbaTHut Aug 9 '10 at 18:11
2
\$\begingroup\$

In answering my question from the experience I had so far, I basically see these options:

Extract your more specific collection of objects from the more general collection each time you need it

  • pro: central object repository
  • con: computational overhead

Store your more specific collection in specialized containers as provided in the example for this question

  • pro: quick lookup / pre-sorted data
  • con: more involved tracking of objects

Use caching for certain perspectives on / sub-sets of the game objects

  • pro: middle-ground between 1 and 2
  • con: need to devise caching strategy which can complicate matters

Factors for choosing one of these options include

  • how often is the specific collection of objects required
  • what is the cost for tracking the objects across the multiple containers (it might just be relevant in case of object removal)

The observer pattern can help to propagate the need to change the other sub-sets of objects.

|improve this answer
\$\endgroup\$

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.