带宽限制下的视觉实体属性传播
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月發(fā)布的MMOPRG，最開始發(fā)布在歐洲和北美，目前已經(jīng)被本地化為3種不同的語言。它由Nevrax在2000年開發(fā)，在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團隊獨立開發(fā)，包括了Nevrax Library (NeL)，該庫基于GPL協(xié)議發(fā)布。在NeL之上，開發(fā)出了一項服務(wù)器技術(shù)用來處理高度仿真的虛擬世界。這篇文章關(guān)注于所開發(fā)出的如何平滑地移動實體和將動態(tài)屬性傳播給所有相同區(qū)域內(nèi)其他客戶端的網(wǎng)絡(luò)技術(shù)。
?
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.
我們的客戶端軟件需要顯示一個包含移動實體及其動畫的3D動畫場景。玩家會通過類似鼠標點擊等行為來直接控制自己的角色。與需要對移動完全進行同步和平滑顯示的第一人稱射擊游戲和體育游戲不大一樣，角色扮演類游戲通常并不需要非常快速的輸入處理。
?
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?項目啟動的時候，其他游戲中的實體經(jīng)常會出現(xiàn)一些位置回退和跳躍前進的情況，我們希望在我們的游戲中，這類可以看見的位置跳轉(zhuǎn)或者位置顛簸情況要比其他MMOG少。另一個重要特性是允許玩家在一個無縫的環(huán)境中移動，不會出現(xiàn)一些預(yù)先定義的小地理區(qū)域的加載過程，因為在這些加載時間里，玩家只能停下來等待。
?
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.
在這篇文章中，將會解釋一些我們曾經(jīng)嘗試過和最終我們所選擇的技術(shù)。視覺屬性是指客戶端軟件在渲染玩家或NPC實體時所需要的任意的動態(tài)狀態(tài)或者描述屬性, 比如位置和頭頂文字，3D模型ID，服裝，當前播放的動畫，等等。我們假設(shè)客戶端軟件能夠在本地獲取到類似于3D模型，貼圖和動畫這些靜態(tài)數(shù)據(jù)。這篇文章的大部分內(nèi)容將重點關(guān)注于位置的廣播，因為當平滑自然的位置路徑廣播未實現(xiàn)時，客戶端將非常容易地看出來。
?
Challenges
挑戰(zhàn)
?
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.
對一個在線游戲，特別是一個大量玩家同時在線的游戲來說，帶寬的限制將使得我們不能直接將所有的位置改變消息發(fā)送給所有的玩家。在Ryzom項目立項的時候，56K調(diào)制解調(diào)器在玩家中仍然被廣泛使用，ADSL仍處于起步階段。我們的MMORPG必須在56K甚至14K的連接下工作。
?
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.
此外，對一款在線游戲來說，作弊行為完全地毀掉了受害者的游戲體驗，所以必須有技術(shù)手段來防止這類行為的出現(xiàn)。“不要相信客戶端”已經(jīng)成為一句越來越流行的格言了，而最近Nevrax創(chuàng)始人的計劃是要將Ryzom客戶端在自由軟件協(xié)議之下發(fā)布，這更加迅速地顯示出客戶端只是一個顯示和輸入設(shè)備，所有的游戲邏輯都必須在服務(wù)器端完成。
?
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.
在服務(wù)器端處理動態(tài)的游戲信息將有效地防止作弊行為的出現(xiàn)，比如一些玩家制作的用于偷看其他玩家數(shù)據(jù)的雷達。然后，避免使用點對點的網(wǎng)絡(luò)方案，這樣也導(dǎo)致帶寬的限制不僅僅只出現(xiàn)在使用低帶寬的玩家電腦上，在租用帶寬的服務(wù)器機房也會出現(xiàn)。
?
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.
MMORPG的游戲體驗與延遲是聯(lián)系在一起的，經(jīng)常在發(fā)出的動作指令與其顯示效果之間出現(xiàn)一段可以看見的而且令人非常不愉快的停頓，有時是動畫停止，有時是動畫顛簸。這種延遲現(xiàn)象必須通過設(shè)計來使其最小化。它通常是由于在嚴格的帶寬限制和高延遲的網(wǎng)絡(luò)環(huán)境下使用了不合適的信息廣播系統(tǒng)而導(dǎo)致，也有可能是由于服務(wù)器的CPU處理導(dǎo)致了延遲。
?
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.
我們的工作就必須關(guān)注于學(xué)習(xí)當前已知的視覺屬性傳播技術(shù)，并且盡可能地創(chuàng)建一個更好的技術(shù)。為了避免高的時間開銷，軟件的CPU性能也是很重要的。
?
?
2. Dead Reckoning – Extrapolation
導(dǎo)航預(yù)測算法 -- 推理
?
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.
早期的分布式仿真項目，比如DIS，只處理具有高度慣性行為的移動對象。在這項飛機飛行模擬實驗中，只是標準的勻速直線運動，然后做一些漸進的變化。這樣它才能通過模擬一個實際實體的復(fù)制品來復(fù)制其移動，并且應(yīng)用一些行為改變事件。
?
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.
比如，如果實際的實體降低速度s，一個更新數(shù)據(jù)包將會發(fā)送給它的復(fù)制體以使其也降低速度s。當然，這個更新包將會有一段無法避免的傳輸時間。在更新包到達之前，該復(fù)制體對象的位置還在繼續(xù)按原來的速度改變，這樣就必然導(dǎo)致了需要有一個位置修正，也使得在復(fù)制體上觀察到的對象移動路徑與其實際路徑會有一些輕微的偏差。
?
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.
這種位置上的偏差可以通過在更新包中引入額外信息來降低：比如一個表示速度從什么時候開始改變的時間戳可以使得復(fù)制體的移動路徑最終與實際路徑合并上，雖然在更新包傳輸?shù)倪^程中，復(fù)制體還是會產(chǎn)生一個不大一樣的路徑。
?
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]).
這樣，我們需要實現(xiàn)一種算法來將臨時的不準確路徑與其正確的路徑進行混合，最終的結(jié)果依賴于混合的深度(比如可以使用之前收到的位置歷史數(shù)據(jù))。
?
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.
為了降低更新的頻率，我們可以只在原始路徑和復(fù)制體的移動路徑發(fā)生指定數(shù)量的偏離時才發(fā)送更新包(這可能需要在主處理器上同時運行主實體和其復(fù)制體的運動模擬，以用來對這兩條路徑進行比較)。現(xiàn)在我們就有了一個導(dǎo)航預(yù)測系統(tǒng)，該系統(tǒng)以古代航海學(xué)上在星星不可見時用來導(dǎo)航的技術(shù)而命名。
?
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).
?但是，在大多數(shù)MMORPG中，主要被控制的對象都是人類角色，他們的運動都是高度隨機的。使用導(dǎo)航預(yù)測算法可能會導(dǎo)致非常頻繁地發(fā)送狀態(tài)校正更新包，網(wǎng)絡(luò)流量和視覺上的震動都會大大增加(因為當混合后的復(fù)制體路徑與原始路徑相差較大時，有時候不得不做一些迅速的位置跳轉(zhuǎn))。
?
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.
導(dǎo)航預(yù)測算法仍然可被用于交通工具，AI控制對象這類具有大體上固定移動規(guī)律的實體。為了能夠處理大量玩家控制的實體，我們轉(zhuǎn)向了另外一種不同的策略：傳輸"good-old"位置更新包，同時使用插值的方法模擬一段時間內(nèi)的自動移動，并且保持對更新頻率完全控制。
?
?
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年的游戲開發(fā)者大會上做過一段關(guān)于Half-Life & Team Fortree Networking的發(fā)言。其中有一個想法是，除了試圖預(yù)測未來之外(也就是導(dǎo)航預(yù)測算法的原理)，為什么不可以將過去的情況作為現(xiàn)在來處理呢？當一個客戶端接收到場景內(nèi)所有其他實體的所有更新包后，他們就可以非常平滑地顯示出場景的實際動畫。
?
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.
這也是為什么會有一個延遲，也被稱為滯后補償時間(LCT)，被引入到實際動作和在網(wǎng)絡(luò)傳輸管道的另一端顯示之間。LCT越高，所接收到的更新包也越多，移動也就會越平滑：如果一個角色到達了一個位置，但這時從服務(wù)器發(fā)來的另一個位置更新包又還沒到，那么它將不得不停下來等待。
?
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.
這將導(dǎo)致停停走走式的移動，特別是當位置更新包發(fā)送頻率不規(guī)則時，這也是在通過internet發(fā)送數(shù)據(jù)時無法避免的問題。LCT的目標就是確保這樣的情況不會發(fā)生，但是LCT又需要盡可能的小，因為它代表著滯后或時間不一致的情況。
?
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!).
如果兩個玩家的屏幕挨在一起，他們顯然會發(fā)現(xiàn)，他們的顯示位置一直在交換。在另外一些情況下還可能會注意到：比如，當兩個角色試圖同時移動時，他們會感覺到另一個玩家一直在自己后面，因為他們控制的角色一直都沒有發(fā)生位置交換(那將會是一個非常嚴重的操作體驗)。
?
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].
這也產(chǎn)生了一個顯示在當前時間空間的對象(玩家自己控制的角色)與顯示在過去時間空間的對象(遠程角色對象，AI控制實體)之間的交互問題。一種解決方案是讓LCT隨著與角色對象的距離而變化。這一方案被稱作暫時感知，或呈現(xiàn)時間，或者有時候叫做本地感知過濾，這是來自于對天空中星星出現(xiàn)情況的推理：距離越遠，光線到達我們這里需要的時間就越長。
?
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
無論如何，如果我們希望使玩家附近的實體比遠處的實體更準確地移動，那我們就應(yīng)該將觀察者附近對象的更新包的優(yōu)先級設(shè)置高一些。目的是為了最大限度地減少誤差幅度：跟前的一個實體(如正在戰(zhàn)斗中的對手)最多只能出現(xiàn)1米以內(nèi)的位置誤差，而遠處的一個實體盡管位置偏離了好幾米，但顯示出來的結(jié)果可能只有幾個象素距離的誤差，甚至還會更少。遠處的實體應(yīng)用低頻率的位置更新，這樣需要的LCT就可以比較大。靈活的LCT可以盡可能地減少近處玩家的延遲，同時也能夠避免遠處玩家實體的位置顛簸。
?
It means we need a way to control the frequency of updates of viewed entities.?
這也意味著我們需要一種方法來控制被觀察對象的更新包的發(fā)送頻率。
?
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.
在多臺機器之間維護時間需要一種同步機制。通常的同步方案是，在本地機器時間與服務(wù)器時間之間計算一個差值和參考時間，然后傳輸與參考時間之間的時間戳。但是，我們注意到一些機器的內(nèi)部時鐘速度不一樣，這樣會導(dǎo)致錯誤的同步。
?
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.
此外，我們的服務(wù)器應(yīng)用程序采用了一種靈活的時間系統(tǒng)，該系統(tǒng)基于一個可發(fā)送”ticks”的指揮服務(wù)，這樣可以以所有的服務(wù)器應(yīng)用程序都接受的比率增加當前游戲循環(huán)的速度：如果一個服務(wù)突然增加了工作負載，所有的服務(wù)都可以停下來等它，以避免惡意循環(huán)的阻塞。客戶端時間同步因此基于收到的兩個消息包的平均時間，假設(shè)服務(wù)器定期地發(fā)送數(shù)據(jù)包到所有的客戶端。
?
4. Update Frequency Control - Prioritizing
更新頻率控制 - 優(yōu)先級策略
?
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.
雖然大家都認為消費者的調(diào)制解調(diào)器和帶寬在未來幾年內(nèi)會增加很多，但是保持一個低的傳輸率仍然具有降低帶寬使用費用的優(yōu)勢。畢竟，運行一臺支持數(shù)以千計的玩家同時游戲的服務(wù)器(這也是MMOG的本質(zhì))仍然需要很大的網(wǎng)絡(luò)連接，而這也不可避免地是相當?shù)陌嘿F。
?
Transmitting position updates of a populated 3D scene in 13 kbit/s (the throttle that was eventually set) raised the following problems:
在一個比較熱鬧的3D場景中以13kb/s的速度(一般設(shè)置的瓶頸值)傳輸位置更新包也給我們帶來了以下問題：
- Which updates would have priority?
- 哪些更新包具有高的優(yōu)先級
- The need for CPU-efficiency?
- 需要的CPU效率是多少
Several algorithms were tried. The principle of them is the same. For a particular observer, at a given time:
我們也嘗試了多種算法，他們的基本原理也都是相同的。對一個特定的觀察者來說，在一個給定的時間：
Computing the list of visible entities
計算可見實體
?
Two main algorithms are used in Ryzom.
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.
第一種被用于Ryzom的大陸。空間被一個網(wǎng)格所劃分，首先獲取與要計算的實體在同一網(wǎng)格的實體，然后以螺旋狀的方式遍歷周圍的網(wǎng)格，并添加其中的實體，直接找到足夠數(shù)量的實體。
?
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副本來說，區(qū)域一般都比較小，所以采用了一種新的算法：根據(jù)實體當前位置與組重心的距離來創(chuàng)建動態(tài)組。如果實體移動到離組很遠的地方，就將組一分為二：創(chuàng)建一個新組出來。
?
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.
這兩種情況的結(jié)果都是相同的：每個客戶端游戲?qū)嶓w都與一個其可見的實體集合相關(guān)聯(lián)。解釋這些算法的細節(jié)已經(jīng)超出了本篇文章的范疇，但接下來我們將看到這些關(guān)聯(lián)和他們的屬性是如何以及何時發(fā)送給客戶端的。
?
Priorities: relevance of information
?優(yōu)先級：信息的相關(guān)性
?
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:
我們曾經(jīng)嘗試過的一種算法是通過以下方法構(gòu)造的：試圖將一個屬性的更新頻率與該屬性更新所引起的觀察者屏幕上受影響的象素數(shù)量相關(guān)聯(lián)。實際上，第一個基于預(yù)算的算法被開發(fā)用來處理每個屬性：每個元組(觀察者客戶端，觀察的實體，屬性)被賦予一個優(yōu)先級，還有一個數(shù)據(jù)結(jié)構(gòu)用于表示"架子和桶"，這些在發(fā)送更新包到客戶端時會被瀏覽到。優(yōu)先級幫助將一個屬性的改變事件映射到一個正確的桶上。它是通過一些標準計算出來的：
?
- 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.
客戶端所知道的狀態(tài)拷貝與其實際數(shù)據(jù)之間的差值
?
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.
對于位置來說，我們解決了當實體移動了一段很長的距離而實際差值卻非常小時可能會引起的問題：比如，當在墻上行走時，開始點和結(jié)束點可能會非常接近，而在這種情況下的改變又是很重要的。我們通過比較”移動的數(shù)量”來代替移動的位置，這樣我們也就不得不在每次檢測到實體移動之后都進行累積。
?
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.
其他屬性也同樣被列入考慮。比如，如果一個被觀察實體突然戴上了他的帽子，而并沒有移動，這個實體也同樣會獲得一個比較高的更新優(yōu)先級。
?
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:
這個算法在我們25*250*1000個元組(每個前端服務(wù)有1000個客戶端，每個客戶端顯示250個實體，每個實體有25個動態(tài)屬性)的目標上被證明是太過于耗費CPU資源的。因此，另外一個不同的算法又被開發(fā)出來，通過下面的標準為每個元組(觀察者，被觀察的實體)計算分值：
?
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.
實體分值的增長與它到觀察者的距離成反比，當狀態(tài)更新包被發(fā)送到觀察者的客戶端后，分值被重置。另外一個步驟用來對特定的被觀察的實體進行處理，以決定哪些屬性需要發(fā)送給觀察者。
?
Arbitrating which properties are to be sent
決定哪些屬性需要被發(fā)送
?
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.
當根據(jù)優(yōu)先級遍歷被觀察的實體時，我們會將實體當前的屬性與保存下來的上一次發(fā)送更新時的屬性值進行比較，發(fā)送改變過的部分。如果他們不匹配，我們會在有足夠的資源時將他們包含進更新數(shù)據(jù)包中并且發(fā)送。上一節(jié)中描述過的路程跟蹤被保留用來做位置仲裁。這個比較也是一個非常關(guān)鍵的部分，因為其被調(diào)用的次數(shù)非常多，我們也使用了相當多的手段來對其進行優(yōu)化。我們隨后通過僅比較那些與實體類型有關(guān)的屬性來對整個步驟進行了優(yōu)化。比如，我們提前已經(jīng)知道在Ryzom中智能植物是一種位置固定的實體，這樣我們就不需要比較它的位置屬性是否已改變了。
?
Optimizations
優(yōu)化
?
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.
為了減少一個游戲循環(huán)中所做的操作的次數(shù)，我們添加了一個用來將游戲循環(huán)分隔為多個游戲循環(huán)的系統(tǒng)。這樣，一次只會有一部分的可見實體做優(yōu)先級計算。
?
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.
另一項優(yōu)化策略在于使用多處理器的優(yōu)勢：計算部分和發(fā)送部分被安排在不同的線程中。
?
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.
低級的優(yōu)化處理也做過：通過顯示c++編譯器生成的匯編代碼，我們重新設(shè)計了數(shù)據(jù)結(jié)構(gòu)，以使得處理器在獲取這些數(shù)據(jù)的時候盡可能地減少緩存未命中的情況。
?
?
原文地址：
http://www.gamasutra.com/view/feature/1421/propagation_of_visual_entity_.php
總結(jié)
以上是生活随笔為你收集整理的带宽限制下的视觉实体属性传播的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 网络游戏的位置同步
- 下一篇： flex采用blazeds实现服务器向客