Elegant way to simulate large amounts of entities within a game world

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.