首页 > Computer > 带宽限制下的视觉实体属性传播


1. Introduction


The Saga of Ryzom is a persistent massively-multiplayer online game (MMORPG) released in September 2004 throughout Europe and North America, localised in 3 languages so far. It has been developed by Nevrax since 2000, and was taken over by Gameforge in late 2006.

The Sage of Ryzom是一款在2004年9月发布的MMOPRG,最开始发布在欧洲和北美,目前已经被本地化为3种不同的语言。它由Nevrax在2000年开发,在2006年末时由Gameforge接管。

The Nevrax team built Ryzom from scratch, starting with the Nevrax Library (NeL), made available as free software under the General Public License (GPL). On top of NeL, a server technology was created to handle an immersive virtual world. This article focuses on the network techniques developed to display a smooth scene of moving entities, the dynamic properties of which are propagated to all connected end-user clients having an avatar in the same virtual area.

Ryzom由Nevrax团队独立开发,包括了Nevrax Library (NeL),该库基于GPL协议发布。在NeL之上,开发出了一项服务器技术用来处理高度仿真的虚拟世界。这篇文章关注于所开发出的如何平滑地移动实体和将动态属性传播给所有相同区域内其他客户端的网络技术。

I would like to thank Daniel Miller, CTO of Nevrax and Gameforge France, for his enlightening contributions and reviews of this article.

Daniel Miller,Nevrax和Gameforge France的CTO,感谢他所做出的巨大贡献和对这篇文章的最终审查。

Purpose of the Works


Our client software had to display an animated 3D scene figuring moving and animated entities. Players would have direct control over their avatars, as point & click control (the alternative usually found in 2D or ¾ perspective games, even sometimes in 3D games) was considered not immersive enough. While the role-playing genre usually does not require fast input from the players, like in first person shooters (where the first player to shoot, will be the one who survives) or in sport games (where synchronization is very important for collective actions), movements had to be consistent & smooth.


We wanted visible micro-teleportations, or position jolts, to be less frequent than in other MMOGs, in which, at least at the time when the Ryzom project started, entities often seemed to go back in time or jump forward. Another important feature was to allow the characters to move in a seamless environment, without loading time between predetermined small geographical zones, during which the player would be idle.

在Ryzom 项目启动的时候,其他游戏中的实体经常会出现一些位置回退和跳跃前进的情况,我们希望在我们的游戏中,这类可以看见的位置跳转或者位置颠簸情况要比其他MMOG少。另一个重要特性是允许玩家在一个无缝的环境中移动,不会出现一些预先定义的小地理区域的加载过程,因为在这些加载时间里,玩家只能停下来等待。

In the present article, which explains the techniques we tried and which ones were eventually chosen, a visual property refers to any dynamic state or attribute of a player or non-player entity that must be known by client software to render it, such as position & heading, 3D model identifier, clothes set, current animation, etc. We assume the client software has local access to some static data such as 3D models, textures and animations. In most of the document we will focus on the propagation of position, because the continuous nature of position paths makes greatly noticeable when smooth propagation is not achieved.

在这篇文章中,将会解释一些我们曾经尝试过和最终我们所选择的技术。视觉属性是指客户端软件在渲染玩家或NPC实体时所需要的任意的动态状态或者描述属性, 比如位置和头顶文字,3D模型ID,服装,当前播放的动画,等等。我们假设客户端软件能够在本地获取到类似于3D模型,贴图和动画这些静态数据。这篇文章的大部分内容将重点关注于位置的广播,因为当平滑自然的位置路径广播未实现时,客户端将非常容易地看出来。



In an online game, especially a massively multiplayer one, the bandwidth constraints prevents from trivially sending every position change to all players. At the planned time of Ryzom launch, 56k modems still were widespread among players, ADSL was still in its infancy. Our MMORPG had to work nominally on a 56k or even 14k connection.


Besides, in an online game, cheating utterly destroys the game experience of the victims (the players put at a disadvantage) and must be prevented. From the ever-popular adage “Don’t trust the client”, even more present as Nevrax’s founders’ intention was to release the Ryzom client under a free software license, it was quickly clear that the client would be a display and input device, while all game logic would have to be on the server.


Handling dynamic game information on the server side would prevent the appearance of player-made radars, for instance. Then, after excluding a peer-to-peer network solution, the bandwidth constraints did not only originate from the low bandwidth available in consumers’ homes, but also in the server farms that we would have to rent.


MMORPG playing experience was known to come with lag, an unpleasant noticeable delay between an action and its viewing, often visible as a stopped animation or animation jerk. This lag phenomenon had to be minimized by design. It usually originated either from an inadequate information propagation system under tight bandwidth constraints and latency-prone networks such as the Internet, or from delay in CPU-processing by the server.


Our work then had to focus on studying the known techniques of visual property propagation, and possibly creating better ones. The CPU performance of the software was also critical, to avoid time-consuming peaks.


2. Dead Reckoning – Extrapolation

导航预测算法 — 推理

Early distributed simulation projects, such as Distributed Interactive Simulation (DIS), dealt with moving objects having high-inertia movements. In this aircraft simulation context, uniform rectilinear movements are the norm, and variation from these occur in a gradual way. It is then possible to replicate the movements by simulating a replica of an actuated entity, and applying behaviour change events.


For example, if the actuated entity reduces its speed by s, an update is sent to the replica to make it reduce its speed by s as well. Of course, the update can take a non-negligible time to transit from the actuator to the observer. The position of the replica is extrapolated until the update is received, leading to a position correction, thus the actual path observed on the replica may be slightly different than the original one.


This positional inaccuracy may be lowered by introducing additional information in the update message: for example a timestamp stating from which point the speed change was done will make the replicated path finally rejoin the original one, although the temporary phase during when the update message is transitting will have a different path.


Then, we need to implement an algorithm that will blend the temporary inaccurate path with the corrected path, the result of which will depend on the depth of the blending (using the history of previously received positions, for example [Bernier]).


To reduce the frequency of updates, we can send an update only when the original path and the replicated path diverge by a defined amount (Figure 1) (it may then be necessary to run both the master entity and the replicate by the master process to compare them). We now have a dead reckoning system (see prototype screenshot on Figure 2), named after the ancient naval navigation techniques used when the stars were not visible.


However, in most MMORPG the primary controlled avatar is a humanoid, which is not known for high-inertia movements but random movements. Using Dead Reckoning would lead to frequent state correction updates, increasing both network traffic and visible jolts (because a quick position jump is sometimes needed when the blended replicated path differs to much from the original path).


Dead Reckoning may still be used for vehicles, AI entities having steady movements (although too steady movements for AI entities might not be wanted, because of their unnatural feeling). To allow for a large number of player-controlled entities, we focused on a different strategy: transmitting “good-old” position updates, but simulating interpolated natural movement in a virtual time space and maintaining total control of update frequency.


3. Virtual Time Space – Interpolation

虚拟的时间空间 – 插值

Yahn W. Bernier of Valve, made a presentation about Half-Life & Team Fortress Networking at the Game Developer Conference in 2000 [Bernier]. The idea was that instead of trying to predict the future (the principle of Dead Reckoning), why not make the past look like the present? When a client has received all updates for all entities in a scene, they are able to display an accurate and smooth animated view of the scene.

Vavle的Yahn W. Bernier在2000年的游戏开发者大会上做过一段关于Half-Life & Team Fortree Networking的发言。其中有一个想法是,除了试图预测未来之外(也就是导航预测算法的原理),为什么不可以将过去的情况作为现在来处理呢?当一个客户端接收到场景内所有其他实体的所有更新包后,他们就可以非常平滑地显示出场景的实际动画。

That is why a delay, called Lag Compensation Time (LCT), is introduced between the real action and the display on the other side of the transmission pipeline. The higher the LCT, the higher the number of updates received, the smoother the movements: if an avatar reaches a position before the next position is received from the server then it will have to stop and wait.


This results in jerky start-stop movement, especially if the position update rhythm varies, which is unavoidable when coming over the Internet. The goal of the LCT is to ensure that this doesn’t happen, but the LCT needs to be as small as possible as it represents a lag or temporal inconsistency.


If two players have their screens side by side (Figure 3), they obviously will notice that their display is shifted in time. In some other situations, it may be noticed: for example, when two characters are trying to run together at the same time, they will have the feeling the other one is always behind, because their controlled character is not shifted in time (that would be a terrible control experience!).


This raises the problem of interaction between objects displayed in present time space (the player’s avatar) and objects displayed in a past time space (remote characters, AI entities). One solution is to make the LCT vary according to the distance from the player’s avatar. This idea is called temporal perception, or presentation time or sometimes local perception filters and comes from the analogy with the appearance of the stars in the sky: the farther the distance, the longer the time the light takes to come to us [Singhal-Zyda].


Anyway, if we want more accurate movement around the player’s avatar than at distant sight, updates of entities in the immediate vicinity of the observer should then have a higher priority than updates from distant entities. The goal is to minimize the error magnitude: a foreground entity (such as a melee adversary) may be displayed in a strikingly wrong position with less than 1 meter of positional error, while an entity farther away may not be perceptibly badly positioned despite a positional error of several meters which may only correspond to only a few pixels or less. With position updates that are less frequent for distant entities, the required LCT is greater. A flexible LCT allows one to minimise the lag for nearby characters while still avoiding jerkiness for background characters


It means we need a way to control the frequency of updates of viewed entities.


Time Synchronisation


Maintaining times across several machines needs a synchronization mechanism. Common synchronization schemes compute a delta between the local time of the client machine and a reference time, and transmitting a timestamp relative to the reference time. However, we noticed that many consumer PCs had internal clocks with a different speed, leading to desynchronization.


Moreover, for our server applications we adopted a flexible time system based on “ticks” sent by a conductor service, that would increase the current game cycle at a rate that was sustainable by all server applications: if a service had a sudden increase of workload, all services would wait for it, avoiding a vicious circle of congestion. The client time synchronization was thus based on the average time between two received messages, assuming the server regularly sends a message to each client.


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:


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.
Associate a priority to each entity of this list based on distance.
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.

对于Ryzom Ring副本来说,区域一般都比较小,所以采用了一种新的算法:根据实体当前位置与组重心的距离来创建动态组。如果实体移动到离组很远的地方,就将组一分为二:创建一个新组出来。

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:


l Distance from observer to entity (the “manhattan distance” approximation is used for performance improvement)

l 观察者到实体的距离

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.


Arbitrating which properties are to be sent


When iterating over viewed entities sorted by descending priority, we compare the current value of the properties to the previous values stored during the last send. If they don’t match, by a sufficient threshold, we include them in the update record to be sent. The mileage trick described in the previous section was retained for position arbitration. As this comparison is a critical part because it is called a large number of times, we used several tricks to optimise it. We later optimised the whole step by comparing only properties relevant to the entity type. For example, we know in advance that an intelligent plant is a still entity in Ryzom, so we don’t need to compare the positions.




To reduce the number of operations to do in a game cycle, a system to split up computation over several game cycles was added. As a result, only an incremental subset of visibility pairs is prioritised at a time.


Another optimisation consisted in taking advantage of the multiprocessor machines we had (and later, hyper threaded multiprocessors): the computation part and the sending part were pipelined using several threads.


Low-level optimisations were also done: by displaying the assembly code generated by the C++ compiler, we could rework the data structures so that the processor had minimal overhead and cache misses when accessing them.



  最直接的同步方案就是客户端在每次发生位置改变时都向服务器报告 ,服务器再转发给周围的其他玩家,其他客户端将对应的游戏实体移动到新的位置上。
  我们以一个实际的例子来说明如何减少这种误差的影响。假设玩家A以速度V从P1点去到P2点,A的网络延时为T1,在A旁边有个玩家B,他的网络延时为 T2。B收到服务器转发过来的移动包时,A在其自己的客户端上已经移动了T1+T2的时间,在这段时间内他自己已经走过了V*(T1+T2)的距离。如果这时在B的客户端上开始将实体A从P1移动到P2,那显然两个客户端上看到的A的位置始终存在V*(T1+T2)的误差。
  为了使A在 B客户端上显示的位置与其实际位置的误差尽可能的缩小,一个简单的做法是直接将A的位置向前拖V*(T1+T2)然后开始移动,这样两者之间的误差便消除了。但这样会使得客户端的显示太鲁莽,要让其看起来平滑一些,我们可以考虑使用一些算法,比如计算出A从当前位置走到P2点还需要的时间,然后加快其速度使其在规定的时间内到达P2点,这样A和B看到的最终时间是相同的,但中间过程还是存在较多误差。另一种较好的做法是先让A以一个可接受的较快速度移动到其当前应该所在的位置稍前一点的地方,然后以正常速度移动到P2点,这样后面的移动情况与其实际移动情况基本吻合了。