Friday, July 6, 2012

Day 18 - Entities LoD

Earlier I talked about "Entity Level of Detail", something that allows RS2 to handle more active entities than it be able to without.
So wtf is that. 

First let's see the most simple case, we do not perform LoD computations on entities.
No LoD
This is a simplified schematic top-down view of a game situation
 The green filled rectangle represents the portion of the world that is active, centered on the player.
"P" is the player.
"E" are entities, can be crates, zombies, whatever.
 With no LoD, everytime the world is updated, every entity is updated and there is no difference between a player or another entity.

This is fine and moraly satisfying to know the NPCs are as active and accuratly simulated as the player, but as discussed earlier we do not really need to do that and we can't do that if we want a large number of active entities around the player.
Some entities do not really need to be updated as frequently as others,  respective to the player.
So we introduce the LoD metric.
For each entity, we can compute a LoD with some formula, giving a number from 0 to 1.
LoD=1 means we want everything computed each frame.
LoD=0 means we will not update this entity at all.
In between values means we can simplify or skip some computations done on this entity.
More on what that means concretly later.
The less CPU time we spend on low LoD entities, the more entities can be active at the same time in the world.

The first idea that comes to mind is to give low LoD to entities that are so far from the player that they are culled by the rendering. Since they are not visible at all, why bother having smooth animations or accurate physics?
You can set this range to the camera far range, but since in RS2 I have a fog effect I set this range to the fog far range. Which is nice, since fog will be thicker at night and there will be more zombies at night. Nice coïncidence.
Distance LoD
Green circle : view range.
Orange : outside of view range.
Any entity inside or partially inside get full LoD. Entities outside the view range get lower LoD the farther they are.

We can push the idea further. Since we are in 3D the player views the world through a camera. Anything that is outside the camera frustum is not visible, even if in view range.
Distance and frustum LoD
In this picture the player is looking south.
Light green : the frustum.
Dark green : the view range.
Orange : outside of view range.
In this situation, only one entity is currently visible and will get full LoD.
Entities in range but out of the frustum will get moderate LoD, since even if not visible they could still potentially interact with the player : chasing him, throwing something at him...
Entities out of range will get distance based LoD.

We could find other ways to improve the LoD metric.
  1. Occlusion : an entity in range and in frustum but occluded by the world geometry could get a lower LoD.
  2. Prediction : increase LoD of entities that appear to be coming closer to the player, and conversely decrease LoD of entities appearing to move away. 

Every game frame, the world is updated and rendered.
During a world update frame we update the entities.
With no LoD or full LoD, an entity is always updated on a world frame.
With partial LoD, we can skip an entity update frame during a world frame.
But remember the game runs in realtime, so we have to accumulate time between entity frames so they are still moving and behaving at the same speed than full LoD entities.

LoD and Frames
The green bars are world updates. Since the game frame rate is variable, we can't predict when the next frame will happen so all computations have to be time-based and we accumulate time between two frames. This accumulated time between frames is called "elapsed time".
At full LoD, you can see an entity is running at the same frame rate than the world.
At half LoD, an entity will skip one frame every two frame. For this entity, the elapsed time between frames will be longer. Its animations and movements will appear more jerky and less smooth or its AI will appear less responsive. Its ok since if we attributed this entity a low LoD it means we don't care about that. Since we accumulate elapsed time, it will still move the same distance as a full LoD entity of the same speed.

In practice, we have to put some safeguards. We can't let LoD go below a threshold, or the physics will break, especially the collisions as I implemented a naïve physic system that respond badly to high elapsed times. As the player gets closer to an entity, its LoD increase and the physics glitches tend to fix themselves.

End of post.


  1. Very cool. Just one thing.
    That is not light green!!! :P

    1. Hey at least it's lighter than dark right? ^^

  2. Good article.
    I´d like to see a similar on AI.

    Keep it rolling!

    1. I will once I settled on something and it works. For now its just temporary stuff to get things going.

  3. That's not orange either :P

  4. This is interesting. I'm not a programmer, but you explained it in a way that I was able to understand this perfectly. This is pretty cool!

    1. Thanks! That means something for me! I was not sure I explained it properly.