Archived

This topic is now archived and is closed to further replies.

JSwing

Game design vs programming: implementing Relationships

Recommended Posts

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]

Share this post


Link to post
Share on other sites
Game Developer Magazine had an excellent series wherein the author wanted to solve pretty much this exact problem. His basic solution was to combine some of the features of regex with some of the features of database operations. He suggests taking a look at the work being done in AI research on graph traversal, particularly SNePS.

Hope that helps,
ld

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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

Share this post


Link to post
Share on other sites
quote:

I find it frustrating that something so simple and obvious to my brain (Bobo is in the Room) doesn't translate easily to code.



Don't be frustrated. This sort of thing does become easier over time.

There are literally tons of methodologies, patterns, algorithms, data structures, recommendations, etc. for every kind of problem in software devleopment. These ideas/plans are a good starting point when trying to solve a problem. They don't always tell the whole story though.

The articles/resources section here on gamedev is a pretty good listing of what you might be looking for.

http://www.gamedev.net/reference/

From what you've been writing it sounds like Design Patterns might be of interest to you.

http://www.amazon.com/exec/obidos/ASIN/0201633612/qid=1084997057/sr=2-1/ref=sr_2_1/002-9570935-5143231

It seems to be the de facto standard for commonly used OOP methodologies



[edited by - rsegal on May 19, 2004 4:09:15 PM]

[edited by - rsegal on May 19, 2004 4:09:48 PM]

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You gonna draw some dfd''s too?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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 ...

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
liquiddark:
Thanks for the link. The article was not as helpful as I''d hoped, but it was informative. The followup articles spent too much time on his (hypothetical) syntax instead of practical implementation.

liquiddark, RolandofGilead, ddn3, AP:
You present several different methods to attack the problem. The event model, embedding static pointers in the objects (thus creating a node graph), the database model, even custom design for the implementation. This is all good. If anyone else has any other techniques, please contribute.


Each technique seems to focus on single purpose, and can be inefficient for a different one. Triggered events work fine for simple flags, but choke at traversing a node graph. Embedded object pointers work well for traversing a node graph but get tangled with conjunctions. The database model works well for conjunctions, but can get very slow for simple flag checks or node graph traversal.

Since any given Relationship (fact, etc) can be used for several different purposes this creates a problem. Can we develop some robust guidelines for when to use each implementation? Is it better to have a mix, or just focus on one technique?

At some point the game design may change, so the optimum technique may change. Can we write or structure our programs to make it fairly easy to switch from one technique to another? Or is this just a rare occurence?



The second half of the problem, the program flow control, has a similar difficulty. How does the program flow (the functions, procedures, etc) change?

One can perform real time checks (if...then else) in the middle of a function. But this can mean a lot of time spent checking for rare conditions. If the design has a lot of conjunctions (if A and B but not C...else if P and Q...) then this becomes ugly.


Or one can use function pointers and simply follow the current path (doFunction->nextFunction()). This pre-loads the program path whenever an event changes, so no need for the real time checks.

At first glance this doesn''t work well when there is a single decision point with a lot of options because only one of the function pointers will be taken. The indirection can also be slower.

Is there another technique here? And when to use one over another?


JSwing

Share this post


Link to post
Share on other sites
The flow-control half of your problem sounds like a possible candidate for delegates, if you have access to such a creature.

So, for example, say Bobo is carrying a metal sword. When he picks up the sword it could subscribe to his AreaEffectHit multi-cast delegate, which subsequently might get called by a fireball, for example, and hence call into not just Bobo''s TakeDamage() instance method, but also the sword''s method.

A delegate wraps up the chain in a simple and reasonable way, and carried objects would then have to subscribe to their container''s delegate. This gets into the question of how to manage things like damage reduction. Perhaps a class hierarchy of delegates with considerations for this type of thing would work.

ld

Share this post


Link to post
Share on other sites
A visual editor for this kind of thing would do wonders for producing Sensor/Trigger/Effect systems. My system isn''t really event-based, I was just giving that as the example for a communication method between all those concepts. A tree would also kick ass and provide a way to avoid recursion(and it would certainly look like a graph in a visual editor). Speaking of, one could have any method simulated by the editor but it would be really cool to have many techniques available and just pick and choose with the editor which ones to do.

Here''s a random thought, the two examples JSwing gave can also thought to fall into different categories based on the level each operates on. The ogre-room example can be thought more of a method of controlling the engine, while the artifact/graveyard example changes the state of the game.

I think we need more examples and then give ways from various techniques on how to solve them.

Share this post


Link to post
Share on other sites