I've run into a recurring problem trying to translate my game design(s) into code, and I need some help. Some bits of game design translate very easily, others don't seem to have a reasonable analogue. Pardon the length of this post. Game objects Game objects translate directly into classes (objects, structures, whatnot). By game object I mean something you can point to as a conceptual whole. That is a Bobo the Ogre (and here are his numbers), that is Marvin Gardens (and here is its rent), etc. There's a lot of information available on ways to code classes (and inheritence, and so forth), and I feel comfortable with the translation. Game process Game processes translate directly to functions (procedures, methods, etc). A series of steps to follow that may in turn trigger other processes, and so forth. There is a lot of information about writing and organizing functions, and I feel comfortable with these too. Relationships between game objects Here's where the game design and the code design diverge, and I need help. A relationship defines a particular state between two game objects. Might be more than two, but solving for two gives me the rest. The relationship itself does not necessarily contain any state information - the relationship is the state itself. Example:

Game object: Bobo the Ogre (monster)
Game Object: Room

########################
#......................#
#..########............#
#..#      #............#
#..# Ogre #............#
#..#      +............#
#..########............#
#......................#
########################

The Ogre is in the Room.
The Room contains the Ogre.

Ogre <----relationship----> Room
  

I didn't include the exact location of the Ogre since it's not necessary for the relationship. A Relationship: a) depends on the existence of two game objects. If either of the game objects is removed, then the relationship no longer exists. b) doesn't necessarily exist at any point in the game. 'Permanent' relationships can be simply hard-coded into the game objects or procedures. Relationships are necessarily transitory. c) is generally bi-directional, or can be described starting from either object. A relationship between game object A and B may not be described the same going from A to B as from B to A, but it can be described starting from either object. See the example above. d) does not necessarily contain any data values. There's another non-obvious feature. Relationships must have a significant impact on the game. At a minimum, some process might need to check if a certain relationship exists, or what the other end of the relationship affects. Sometimes the presence, absence, creation, or destruction of a relationship changes what code is run. So: e) must have an impact on the gameplay or code process. Sounds vague, I've got some examples later on. There just doesn't seem to be an easy, elegant way of expressing them in code. Some approaches I have seen: 1) Overcode the objects. Create a bunch of extra pointers (or lists) in each of the game objects. Bobo the Ogre would have a Room pointer, which is NULL when he walks around outside, and each Room has a list of pointers to all the monsters it contains. This doesn't seem to scale well. The objects quickly bloat with a bunch of NULL pointers and other artifacts. 2) A separate 'Relationship' object. This would be the OOP approach. Create a separate, abstract Relationship class with several different types. The game objects then each have a list of pointers to the relationship objects they are part of, and each relationship has pointers to the two game objects they connect (as well as type information). I'm not quite comfortable with this approach. It seems to require a lot time spent identifying, sorting, managing, and comparing relationships and types rather than actually doing the effects. Abstraction makes the objects very ignorant. 3) A lot of runtime checks. Everytime you run through a process (procedure, function), you include a lot of conditional checks. If this relationship exists then do that, if that relationship exists, do this other thing. This results in a lot of spaghetti code. Maintenance is a nightmare. 4) A very complex set of function pointers or function objects. The function or procedure that creates the Relationship also changes one or more other functions directly as a consequence. Creating, destroying, or altering a Relationship means doThis() becomes doThat(), so the function pointer whatDoIDoNext changes from one to the other. This is a sort of LISP approach. This creates a tangled weave of behavior, not unlike the runtime checks in (3) above. It gets worse when different instances of the same object type need to use different routines because different Relationships exist for one instance than another. It's somewhat elegant, but potentially slow because of the indirections, and I'm not confident about using it. Maybe each of these is a good approach under different circumstances? If so, what are some good guidelines? Or is there another approach? Or a language where relationships are built-in? I find it frustrating that something so simple and obvious to my brain (Bobo is in the Room) doesn't translate easily to code. Before you respond, I've included some examples below, to give you an idea of why (and where) it matters. The three object diagram:

Game Object <-- Relationship --> Game Object <-- Relationship --> Game Object
                    ^                               ^
                    |                               |
                     ----------Rule Change ---------
  

This is a pretty common setup. When A has a particular relationship to B, and B has a particular relationship to C, then do X. Example: Game object: Bobo the Ogre (monster) Game Object: Room Game Object: Hero Rule: If the hero is near a room, then update the contents of that room (monster locations) each turn. If not, then just represent the monster's movements by a small chance he appears at the door.

########################
#......................#
#..########............#
#..#      #............#
#..# Ogre #............#
#..#      +...@........#
#..########............#
#......................#
########################

becomes

########################
#......................#
#..########............#
#..#......#............#
#..#.O....#............#
#..#......+...@........#
#..########............#
#......................#
########################

Hero <---- is Near ---> a Room <--- Contains --> Bobo the Ogre
              ^                           ^
              |                           |
               ----Update Ogre Position---

  

The first trick is that these two relationships exist independently of each other. The Hero may be near the Room, but the Ogre may be outside. Or the inverse. Tracking a false state for all of the possible relationships is impossible, but the code needs to be able to evaluate what the changes to make with reasonable speed. In this case, there is a common object that is in both relationships (the Room), so maybe the decision making should be closely tied to the middle object. The four object diagram:

Object  <----relationship-----> Object
                ^
                |
		Rule to Follow
                |
		    v
Object  <----relationship-----> Object
  

This is a bit trickier. Example: If the player is holding one or more evil artifacts, and there is a graveyard on the map, then every (time interval), each graveyard spawns a number of zombies equal to the number of evil artifacts held.

Hero  <---- holding (some) ----> evil artifact(s)
               ^
               |
		Spawn (number of) Zombies
               |
               v
Map  <------ contains (some) -----> Graveyard(s)
  

Assume there is a condition that can convert existing map areas to graveyards, and that the hero has a means to destroy graveyards (in addition to picking up and dropping evil artifacts), so at any time any of the Relationships may come into existence, or stop existing, or change numeric values. Further assume that this a fairly rare set of conditions. If the hero isn't holding any evil artifacts, or the map doesn't contain any graveyards, then there is no need to spawn zombies; there doesn't even need to be a check (ie, you shouldn't need to calculate spawning zero zombies). If the code solution needs to spend time checking for these conditions every time interval, then it needs to check for other conditions as well - the whole process soon slows down looking for non-existent conditions (spawn zombies? no spawn rats? no rising water level? no ...etc) It's frustrating because I can express the game rules very simply, define what the conditions are very simply, but turning them into good code is much more difficult. Is there a good generic solution, or set of approaches? If there are mulitple approaches, then what are some good criteria to decide between them? Any links on teh subject? Books? When I run into this I can hack out working code, but I'd like something better. JSwing edit:spacing [edited by - JSwing on May 17, 2004 5:54:53 PM]

Thx for the link. It led me to Rules Based AI programming, which in turn led to RETE, a well known algorithm for Rules Based Programs. It''s not perfect, but it''s a great starting point.

Thx again,
JSwing

You''ll need conceptual clarity before you can realise the structural design solutions. I''m sensing you want to create boundless worlds with infinte recurisve interactive elements, all within a cohesive and consistent framework. Well, possible but difficult I think.

Clarify for yourself what you want not in terms of preconcived relationships but in less constrictive terms. Your locking yourself into the notions of relationships and hiearchies to solve a problem which in my opinion has yet to be defined. So it''s premature to design a conceptual framework for the project before you have a clear idea of what your trying to achive.

From your example i would rephrase it as :

-Proximity sight, the ability to visual objects through walls based upon ability.

-Artifacts which spawn things based upon promixity of triggers, can have preconditions.

and so on and so on. Get a big list of features which you want, and then look for patterns. Once you start to see patterns, they will point your way to designing your logical modules and their hiearchies.

From those 2 feaures, you can design any number of solutions, which don''t involve the relational forms which you''ve adopted.

Good Luck!

-ddn

Thx for the replies.

rsegal:
I own the Patterns book, it was the first place I looked. It doesn''t have what I''m looking for. The two closest patterns are the Observer (which covers some pieces) and a Mediator/Strategy mix, which would cause a signifcant explosion in objects and much code just to manage them efficiently.

I found nothing in the gamedev articles that is applicable.

Further searching on the web reveals there is a bunch of relationship-oriented software, but it''s generally a finished commercial product, or closed implementation. Very little on how to construct and organize such a system, nor on how to integrate a rules based system with a non-rules based system. Example: the Alloy software at MIT (alloy.mit.edu). The Rete alogirthm is an exception, and I have yet to check out the Game Developer Magazine that liquiddark mentioned..


ddn:
What I''d like is an easy construct to represent Relationships (a state between Objects), so I can more easily translate my designs on paper into code. That''s not going to happen, so I''d be happy with some solid guidelines or patterns that I can use with confidence. Once I''ve got this, it becomes easier to expand, alter, and test out the game designs.

I agree that individual relationships have very different criteria for existing, and have different results (effects). I think they fall into some very general patterns, which suggests to me that some general solutions (or at least guidelines) ought to exist.

Relationships aren''t hierarchal, like data objects, and they''re not procedural, like functions. They''re more like a node graph.

You''re right that my original problem statement is incomplete. It should include: what are the best strategies to represent (store, track, manage) Relationships in code, and how to integrate the storing/tracking with the effects they cause?

So far I think that how the relationships are represented depends a lot on how the Relationship is used.

Relationships used as:

1) Flag. If Relationship A exists (or doesn''t exist), then do X (or don''t do X). Involves one and only one relationship. I''m not sure if triggers fit here or should be a separate category.

2) Traversing the graph. Starting from Object X, do something that involves some data that is part of Object(s) on the other end of the relationship. This may involve traversing several relationships to get to the target data or Object (traversing nodes in a Object-Relationship-Object-... graph).

3) Conjunction. When Relationship A exists AND Relationship B exists then the game rules change. The two relationships are not inherently connected, but their conjunction has effects in the game.


Of course, any given relationship can have multiple uses, and its use may change if the software grows. The Rete algorithm is great at handling conjunctions, but a network of pointers embeded in game objects is easier for graph traversal.


Then there is the question of how to handle the effects. When to use a runtime check during a process, and when to change the processes as the relationships change (via some sort of function pointer).

I don''t have the answers yet, I''m just working through the problem. Responses are welcome.

JSwing

You gonna draw some dfd''s too?

I found the best way for me to conceptualise relationships was in a sense of parent child relationships. The ogre can only be in one room (a parent object) and the room can contain multiple ogres (children collection).

I then decided that object should be responsible for maintain its parent pointers and informing its parents about what its doing. So the ogre leaves the room for another room, it tells the old room that its leaving (so it can remove the ogre from its children collection) sets its room pointer to the new room and tells the new room its arriving.

Re: outside. you could have an abstract class Area which both Room and Outside sub-class. That way the ogre has a pointer to an Area object and the Area object has a collection of game objects ...

Neat post. I meant to reply earlier. I think about programmable game design as well. I''d love to see more examples. It is very complex, which is why I think the most concrete, agreed upon handling of this topic generally goes along the lines of "run your game logic in scripts". I''d very much prefer to specify the game logic in scripts but still run it reasonably fast in code.

One problem is that the way in which computers operate doesn''t allow them to do relationships very well, and certainly not bi-directional ones.

So what do computers do well? What do video games involve? Processing and interaction, repsectively. So basically we need a way to process changes(if it doesn''t change we can just leave it alone-like a run animation or physics system). I''m using my own terms here, and I haven''t exactly implemented this, but I''ve been thinking of a system based on 3 things.

Sensors/Triggers/Effects
Sensors(censors?) define ways of detecting when things interact, like a tripwire(or ownership of a key).
Triggers are functions which run when things interact, like an explosion(or door opening animation).
Effects are rule/state changes, like losing a life(or a door status changing from closed to open).

Functions which do the job of sensors should already be a part of one''s engine. Collision detection is a set of sensors(that is checked every frame). You wouldn''t check other sensors every frame though(imagine a 2d scrolling shooter that checks every single enemy wave to see if it is time for *any* of them, every frame). This problem can be alleviated somewhat in production a little bit by intelligent design of maps, large areas can start with one sensor, like IsPlayerHere. Another paradigm can be applied in conjunction with STE, which I call Events. Events can be used to bind the other three together. Events are notifications of things that have happened, like a sensor detecting an interaction or an effect or trigger being activated. Once you''re notified, you can do something about them, like activating triggers, effects, sensors, and/or more events. Since they''re all on the same level and able to call others, one must avoid infinite recursion and activating too many elements.

I do believe that these things can be implemented in a number of paradigms.