Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Assume you have a game in which there are many (many many) entities serving some functions, not all of which are constantly needed or need to be considered in every frame. The concrete problem I am working on in which this issue is present is a detailed simulation of a body including its organs.

In the game each creature has its own body which is separated into smaller parts (torso, legs etc.) and sometimes these parts contain organs, which serve a specific function within the body. Whether or not an organ currently serves a purpose or is active is never actually clear. After all, an animal might have an empty stomach which therefore does not need to digest anything. It would be quite ridiculous to check or simulate every object in each frame and very costly as soon as you have many creatures in the world. So I was thinking about a way to smartly differentiate between objects that need to be updated and those that don't.

What I came up with seems like an at least ok solution. It creates a simple queue/stack (essential is that each element gets removed as soon as it's read; the order is irrelevant) called the "attention stack" where objects that need to be simulated reside. Objects that need attention would simply put themselves onto the stack or are put there by other objects. These objects would probably implement a simple interface with a simulate()-function.

Applied to my previous digestion example this would mean:

The player chooses something to eat (assume it's bread) from the inventory and puts it into the mouth of his character and the mouth is put onto the attention stack. In the next frame the the mouth is taken from the stack and its simulate()-function is called. Since it's a mouth it would be reasonable to simulate chewing here. This could go on for a few frames in which the mouth keeps putting itself onto the stack until it decides the food is ready to be swallowed. In this case the mouth puts the chewed bread into the stomach (I know it doesn't go there directly, but the esophagus is left out for simplification), which is then also put onto the attention-stack. In the next frame the simulation of the digestion-process is started. And so on for the rest of the necessary organs.

A foreseeable problem with this are idling objects. A sleeping animal is a good example of this. It could be done as previously described by keeping the sleeping animal on the stack and checking each time if it needs to wake up, but that seems wasteful since that's the only thing being done. To make idling objects more efficient I was planning to add a sort of schedule which stores jobs to be performed at a specific time. If an animal goes to sleep it would put a job on that schedule which would be scheduled for a certain amount of time after the animal went to sleep. This job would then take care of putting the sleeping animal onto the attention stack again. Now, you could say that a sleeping animal that isn't on the attention stack could miss being attacked by something because its A.I. is not simulated, but this is prevented if the attacking object takes care of putting that animal onto the stack again.

Now, I honestly don't know if this is even close to an elegant solution to this problem due to a lack of experience. Am I close to something usable? How is this usually done or does anybody have any suggestions or better solutions?

share|improve this question
add comment

7 Answers 7

up vote 8 down vote accepted

This is exactly the way we solved this problem in Stendhal. In our case there are lots of things that happen periodically, but not every turn: Healing spells, plants growing a little further, corpse degenerating, items on the ground expiring.

We have a turn number that is increased in every turn. And we maintain a map of future turn numbers pointing to a set of objects that need to be notified in that turn.

share|improve this answer
    
what if something else interacts with the object in the meantime? For example the sleeping animal might be waked up by a hitting stone. Should you remove the schedule of the animal in that case? –  Emiliano Oct 14 '10 at 14:00
    
That depends on the situation: If the action done is harmless (like waking up while already being awake) we just let it happen. But if the action uses up some resource, we search through the pending queue and remove it. –  Hendrik Brummermann Oct 14 '10 at 17:35
add comment

Sounds like a similar problem to that of inputs: you have 100+ keys on the keyboard but don't want to check each individual key on every frame, so what do you do?

Two answers: polling or system messages.

Polling = at any point when it would actually matter in the game, query the state of the keyboard keys (or the objects, in your case). The rest of the time, ignore them.

Messages = have each keyboard key (object) put something in a message queue when it's pressed or released (when it needs attention). On each iteration of the game loop it looks through the queue and resolves all messages before proceeding.

share|improve this answer
add comment

So I'm going to take a step back from implementation and review the question from a design perspective. Do you have a solid plan for displaying all the detail you want to include in this simulation?

For example:

  • Can the player tell the difference between an animal with an empty stomach and an animal with a full one?
  • Does this information matter to them in any way, when they are making interaction choices within your game?
  • Could a player watching the animal consistently predict the outcome of your simulated events, or would a random number suffice?

Basically the general rule of thumb is to not make your simulation any more complicated than its outputs. At the end of the day if the only animations you have for sheep are graze, sleep, run away. Then it really doesn't matter how many factors go into the decision about which state to choose. All players are going to see is sheep that sleep at night, run from danger and eat during the day.

Behavior simulation is a ton of fun to work on, but always keep the end users experience in mind.

share|improve this answer
    
Yes the player will be able to tell the difference and there are a few effects this has on gameplay, but it's more of a 'gimmick' for fun at the moment. Sort of like the wound system in Dwarf Fortress, which is also very detailed but negligible. But as you already mentioned it is a lot of fun to work on and that is my main focus right now. –  Marc Müller Aug 23 '10 at 5:02
add comment

I had a similar problem on a game I worked on a few years back - the simulation of objects was complex and couldn't really be performed in detail on every object in the world.

The solution was to use the LOD concept to the simulation. Objects within the view of the player would run the full simulation. Objects far away from the player ran a highly simplified simulation periodically. As objects came into the player's view they would transition from course, periodic simulation update to detailed, regular updates.

share|improve this answer
    
+1 for mentioning LOD –  egarcia Dec 5 '10 at 10:12
add comment

Solution with a schedule is good. Note that every entity should have a list of pointers to its future actions, which gives possibility to invalidate future actions if necessary. Ie. sleeping animal wakes up instantly when attacked, so you have to invalidate its wake-up action in the future.

share|improve this answer
add comment

There's a design pattern for this. I think it's called Database Objects?

Basically, you keep one "template" sheep that can represent all the non-special sheep in the game world, draw them all the same way, keeping the unique data within the template object, say as a table of sheep locations and/or time-since-shear. Then whenever you need to make a sheep unique, you can create a specific instance to track that unique sheep.

The same goes for animations. If it's an idle animation or event common to every instance, that can reside in the template instance, where more specific animations can be scheduled separately.

A long time ago, I wrote a game for a programming contest whose main loop just called animate() on the entire scene. It used function pointers to replace idle animations with others as required, and used the technique to support inherited animation (eg spinning a character that's standing on a spinning disc).

That's similar in nature to using a delegate for animation.

share|improve this answer
2  
Flyweight pattern, do you mean? –  topright Oct 1 '10 at 17:58
add comment

Would a state machine work? The animal is either in e.g. sleeping state, eating state, running state etc. For each state you associate a list of active organs. So each frame you visit each animal, switch on state, lookup list of organs for that state and execute update on each of the organs.

share|improve this answer
    
I think that would complicate things because it has to be possible for multiple things to occur within the animal. For instance, just because the stomach is digesting something doesn't mean the heart stops beating or the animal stops walking. Sure, you could define a set of states, each of which takes certain functions into consideration, but the amount of the states would be insanely huge. –  Marc Müller Aug 24 '10 at 9:59
    
Multiple things can happen per state, because you store all active organs on a state and execute each one each frame. A lot of what happens in your simulation seem to fit with state transitions though. E.g. Chewing -> Digesting. But I guess you are right that an animal can not have only one state. There are state transitions happening say with the limbs that are unrelated to state transitions happening in the digestive system. But maybe it is just more complicated that what you have. Just thought it might be something to consider. –  Adam Smith Aug 25 '10 at 10:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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