4. Update Frequency Control - Prioritizing

Although everyone believed the consumer modems & bandwidths would probably increase a lot in the following years, keeping a low transfer rate had the advantage of keeping low server bandwith cost. After all, running thousands of players on a single server (which is the essence of MMOGs) would certainly need fat internet connections which are inevitably expensive.

Transmitting position updates of a populated 3D scene in 13 kbit/s (the throttle that was eventually set) raised the following problems:

• Which updates would have priority?

• The need for CPU-efficiency?

Several algorithms were tried. The principle of them is the same. For a particular observer, at a given time:

1. Determine which entities are in the neighbourhood of the observer, within the seamless environment, and communicate the changes of this list (called "vision”) to the client.

2. Associate a priority to each entity of this list based on distance.

3. Iterate over the entities in order of (highest to lowest), and compare their states with a copy of the state as known by the client. here significant difference is found, add an update record to the send buffer. Stop when then send buffer size has reached the bandwidth threshold.

Computing the list of visible entities

Two main algorithms are used in Ryzom.

The first one is used in “mainland” Ryzom. Space is partitioned by a grid, and computing the list of visible entities consists in taking entities from the same cell and iterating on the neighbour cells by drawing a spiral, until the desired number of visible entities is reached.

For Ryzom Ring instances, where areas are much smaller, a newer algorithm is used: dynamic groups are formed, based on the distance from an entity to the centre of gravity of the group. If an entity moves too far away from the group, the group is split in two: a new group is created.

In both cases the result is the same: a per-client set of associations between game entities and viewed entities. Explaining these algorithms in detail is beyond the scope of this article, but now we will see how and when the associations and their properties are transmitted to clients.

Priorities: relevance of information

One of the algorithms that we tried was built from the following approach: trying to correlate the update frequency of a property with the “number of pixels” eventually affected by a property change on the viewer’s screen. Practically, the first budget-based algorithm that was developped dealt with each property: each tuple (viewer client, viewed entity, property) was assigned a priority, and a data structure representing “shelves & buckets” was browsed when sending updates to the client. The priority helped assigning a property change event into the right bucket. It was computed from several criteria:

• Distance from observer to entity (the "manhattan distance" approximation is used for performance improvement)

• Magnitude of the difference between the copy of the state as known by the client and the actual value.
  
  For positions, we tackled the problem which would occur if the difference was eventually low while the entity had moved for a long path: for example, when walking around a wall, the starting position and the ending position might be very close, while in this case the change is “important”. Instead of comparing the positions, we compared “quantity of movement”, called mileage, that we had to accumulate every time an entity move was detected.
  
  Other properties were taken into account as well. For example, if a viewed entity suddenly put on their hat, without moving, the entity would get a higher update priority.

This algorithm proved too CPU-intensive for our target of 25 x 250 x 1000 pairs (1000 clients per front-end service, each displaying 250 entities having 25 dynamic properties). Hence a different algorithm was developed, computing a score for pairs (viewer, viewed entity) from the following criterion:

• Distance from observer to entity (the "manhattan distance" approximation is used for performance improvement)

The score of an entity was incremented proportionally to the inverse of the distance to the viewer, and would be reset when sending the state to the viewer client. Then another step was required to filter which properties would be sent to a viewer when processing a particular viewed entity.