開放世界遊戲中的大地圖背後有哪些實現技術？
諸如GTA，武裝突襲之類的遊戲中，開發者是如何實現超大地形的？對於這一問題有什麼主流的解決方案？
補充：例如一些開發者提到的浮點精度問題是如何解決的？又如果npc在玩家視野之外是如何運算的？？
----------------------------
本文同時發在我的 Blog，在那裡或可獲得更好的閱讀體驗：
[知乎] 開放世界遊戲中的大地圖背後有哪些實現技術？----------------------------
首先肯定一下，這是一個非常有趣的問題。在這個答案里，我將嘗試先回答主幹問題，再對補充說明裡的幾個問題簡單說一下。
下面是本文將涉及到的一些相關技術的列表，（需要說明的是，這些技術單獨來看並不複雜，實際動手實現並理解各種取捨以後，在項目當中針對具體的需求去設計和搭配才是關竅之所在）
----------------------------
一、程序技術篇：演算法和架構（Programming Algorithms Architecture）
1. 無限循環的平鋪地圖（Infinite Tiling）2. 可預測隨機數和無限宇宙（Predictable Random）3. 精度問題解決方案（Precision Problem Solving）4. 超大地形的處理 （Terrain Visualization） 4.1 古典演算法（從 GeoMipMapping，Progressive Mesh 到 ROAM）4.2 層次的藝術（Quadtree 和 Chunked LOD）
4.3 以GPU為主的技術（Paging，Clipmap 到 GPU Terrain）5. id tech 5 的 megatexture （超大地表上的非重複性海量貼圖）6. 過程式內容生成 （Procedural Content Generation） 6.1 過程式紋理（Procedural Texturing） 6.2 過程式建模（Procedural Modeling）二、內容製作篇：設計和創造（Content Design Creation）
1. 隨機地圖類遊戲 (Diablo II) 中地圖的拼接2. 無縫大世界 (World of Warcraft) 中區域地圖的拼接3. 衛星地質數據的導入，規整化和再加工（一些飛行模擬類遊戲）4. 超大地圖的協同編輯：並行操作，數據同步，手動和自動鎖的運用
三、異次元篇：我們的征途是星辰大海
1. 終極沙盒（EVE）：當規模大到一定程度——宇宙級別的混沌理論與蝴蝶效應2. 打通兩個宇宙（EVE Dust）：發現更廣闊的世界——宇宙沙盒遊戲和行星射擊遊戲聯動----------------------------
## 一、程序技術篇：演算法和架構（Programming Algorithms Architecture）
### 1. 無限循環的平鋪地圖（Infinite Tiling）
我們就從最平淡無奇的無限循環平鋪地圖說起吧。這應該是最原始，也是最沒有技術含量的開放世界構築方式了。
技術上由於過於樸素，也沒什麼好說的，就是在同一個坐標系內像鋪地磚那樣展開，坐標對齊即可，就是接頭處需要注意一下，不要穿幫就行。但是千萬別因為簡單就小看這個技術喲，上面列表裡面的不少技術都是在循環平鋪的基礎上發展起來的，下面我們就來瞧一瞧吧。
按照維度的不同，循環平鋪有下面三大類：
a. 在一維方向上擴展的橫版捲軸遊戲（以動作類遊戲為主）和縱版捲軸遊戲（以射擊類遊戲為主）。這些類型的遊戲里，為了避免循環平鋪給玩家帶來的重複的疲勞，捲軸遊戲會添加一些隨機或動態的元素，比如超級瑪麗里的背景上雲朵的位置，分出多個層次以不同速率捲動的背景層，等等。
b. 在二維方向上循環平鋪的固定視角2D遊戲。這一類遊戲里，比較典型的就是 Diablo。暗黑中的隨機地圖生成，在本質上，就是疊加了一定的隨機性，約束和邊界條件的循環平鋪效果。
c. 在 3D 遊戲里循環平鋪高度圖，形成連綿不斷的地形效果。這在早期的模擬飛行射擊類遊戲里比較常見，現在已經很難搜到圖了，我在上大學的時候寫的第一個地形渲染 demo 就是平鋪的，可惜剛剛翻硬碟已經找不到了555。這一類遊戲，在平鋪時適當地輔以一些貼圖的變化，可以在很省內存的條件下，做出非常不錯的效果。
找不到遊戲內的圖，拿下面這個高度圖來湊數吧。請大家腦補一下，把下面這個灰度圖立體化之後，一塊一塊像地磚一樣循環平鋪以後，3D渲染出來的連綿起伏的直抵地平線（好吧，直抵遠裁剪面）的山脈的壯觀效果吧。
----------------------------
### 2. 可預測隨機數和無限宇宙（Predictable Random）
（本節內的描述和演算法，部分參考了《Game Programming Gems I》 [「2.0 Predictable Random Numbers」](Graphics and Game Gems Database) 一文，請感興趣的同學自行查找原文通讀）
有個傳說中的遊戲叫 Elite ，不知道有沒有同學玩到過。據說這遊戲運行在32K內存的機器上，其中16K還是只讀的ROM。這遊戲據說擁有難以匹敵的遊戲深度：近乎無限個行星，每一個都有各自的名字和特徵。
可預測隨機數本身是遊戲內運用非常廣泛的一個技術，這裡我們著重談一下它在為遊戲提供（微觀上）更豐富的細節和（宏觀上）更廣闊的世界的作用。這一技術的最重要原則是，為了在一個遊戲世界中給出無限空間的幻覺，我們需要滿足兩個分解條件，可以把它們成為宏無限（macro-infinite）和微無限（micro-infinite）」。前者涉及到問題的空間規模，後者則任意一個對象所支持的最小細節層次級別。
----------------------------
從實現上來說，如何設定隨機種子是這個技術的核心。由於給定一個隨機種子，生成的隨機序列是完全可預測的，那麼根據遊戲內的一些時空的設定，通過對隨機種子進行一些定製，得到在遊戲內任意某個時刻和某個空間點上完全可預測的行為就是可行的了。
最簡單的是使用以下幾個元素與隨機種子配合計算：
1. 世界坐標（即 X Y Z 值，既可以表示空間中的某個點，也可以表示某個區域）2. 系統時間（可以用真實時間，也可以用遊戲內設計者定義的時間，如果是前者的話需要考慮離線時的處理）3. 正態分布（在遊戲里建一個查找表即可，這是最廉價的方案）這些因素加上對應的隨機序列，已經可以營造出宏觀上比較有深度的一個宇宙空間了。理論上，如果所有的隨機性都是由給定的隨機種子產生，而這些隨機種子要麼是遊戲定義的常量，要麼是查表得到，要麼是均勻流逝，要麼是由更高層次的隨機種子生成，那麼這樣一層一層上溯到盡頭的話，任何一個遊戲內的宇宙，都可以歸因到一個初始的種子，這個種子，就是決定論中經典物理學的所謂的第一推動吧。其實如果真做到了這一點，我們大可以把這個種子交給玩家，在首次進入遊戲的時候擲一個 2^64 骰子。這是真正的上帝創世的感覺，想像一下，上帝說，要有光，於是擲出了骰子，第一推動怦然落地，整個時空的巨大齒輪開始運轉，在不同的時間點和空間點上，更多的隨機序列被生成出來...
這幅圖來自於遊戲 Frontier：Elite II（出自[這篇文章](http://rakanalysis.wordpress.com/2010/09/26/from-the-archive-frontier-elite-ii-a-retrospective-review/)），下面配的字樣是：「This picture doesn"t even begin to show the scale of the universe.」 大家感受一下。
----------------------------
微觀上本質上也是一樣的，只是把發散的過程倒過來，變成了逐級收斂的過程。為了在某一個點上放大時，能得到儘可能細緻，準確和一致的表現，我們需要對較低層次的世界定義更豐富的規則和約束，比如黑洞對周圍的影響情況，雙星體系的軌道，恆星的種類與行星個數之間的對應關係，不同恆星繫結構下行星表面的大氣構成，等等。這樣才能較好地平衡多樣性和獨特性，帶來更真實的模擬效果和更令人信服的遊戲體驗。
----------------------------
### 3. 精度問題解決方案
當足夠大尺度的世界被創建出來時，就會自然而然地遇到精度的問題。同時這也是補充說明中提到的一個問題，這裡我們簡單介紹一下幾種實踐中的解決方案。
先描述一下問題吧，我們知道，IEEE754 中規定的32位浮點數中，有23位是用來表示尾數的。也就是說，對於接近1的浮點數，可能會帶來 2E-24 左右的誤差（大約是 0.0000001192）以現實單位計算的話，如果遊戲世界是邊長為100km的正方形，那麼在這個正方形的最遠角落裡，我們的最小空間單位是約 7.8 毫米；而如果是中國這麼大的面積的話，空間誤差將達**半米**左右。那麼可以想像一下，如果是宇宙級別的遊戲，採用32位浮點數作為全地圖精度，那麼實際誤差可能會有多麼大。
在實踐中，這種誤差可能會帶來以下這些影響：
1. 無法將相鄰的對象對齊。這種情況，場景美術（關卡設計師）應該會比較頭疼，這對於遊戲的編輯器來說是大問題了。物件沒法在引擎編輯器里對齊；在不同的平台上，對齊也不一樣；甚至不同的編譯器，同一個編譯器的不同版本編出來的引擎；對齊都不一樣 ... 所以說處女座不要做 LD :P。
2. 模型間的穿插和裂縫 本來封閉的牆角可能漏個洞，本來放在地上的石頭變成了懸浮在空中。這實際上是上一種的變種。3. 骨骼動畫的抖動 由於世界矩陣往往參與骨骼動畫的運算，誤差可能會被逐級放大，在那些最遠離根骨骼的骨頭上（也是玩家最容易注意到的地方），抖動可能會發生得非常劇烈。4. 物理模擬失真 一些柔體的模擬可能會直接失敗，而剛體也可能會產生怪異的運動。碰撞系統也可能無法正常工作。所有這些一旦發生，都是很容易覺察的。一旦你發現在一個很大的坐標上有這些問題，而接近原點處問題卻消失了，那麼很有可能就是精度在作怪。而需要注意的是，出現這種問題，只和遊戲中出現的數字的規模和跨度有關，和遊戲選擇了什麼樣的長度單位（如用毫米還是公里做單位）無關。
----------------------------
那麼怎樣使用有限的坐標精度來描述較大尺度的世界呢？
最直接的方案是 使用雙精度浮點數 （64 位），如果這是可接受的選擇，那麼就不必費心引入後面討論的複雜度了。
其次是 區域劃分法 。我看到 @Milo Yip 同學已提到，不過這裡出於完整性的考慮，再簡單說一下。正如 Milo 同學所說，「把世界劃分成不同的區域，在區域內的計算使用其局部坐標系統。」相對應的跨區訪問，需要對應的「本地A -&> 世界 -&> 本地B」的坐標轉換。
還有一個方案是 節點中轉法。正如行動電話的基站用來承載和協調整個通信網路那樣，我們在遊戲的給定活動區域使用靜態信標，所有的邏輯上與之相關的單位，都以該信標的坐標作為參考單位，這樣也可以做到把數據訪問局部化。相距足夠遠的兩個物體（相當於上面的跨區訪問）交互總是通過靜態信標來完成（正如行動電話網路中發生的那樣），這樣的好處是相關的複雜度可以隔絕在這個中轉系統的內部。
此外 @凱丁 同學提到了一個坐標轉換法，「所有位置信息都以角色位置為中心做一次轉換」。這正是 《Game Programming Gems IV》 [「4.0 Solving Accuracy Problems in Large World Coordinates」](Graphics and Game Gems Database) 文中的方案。這個方案可以解決部分問題（主要是渲染相關的問題），但是仍有一些問題需要考慮，比如：1. （上面提到的）編輯器內操作的物體，在序列化到文件中時，精度丟失的問題。2. 大部分物理模擬通常需要一個角色無關，攝像機無關的全局坐標系。等等。
----------------------------
### 4. 超大地形的處理 （Terrain Visualization）
終於說到對超大地形的處理了。可以說從上世紀九十年代起，超大地形的可視化，一直是3D遊戲領域熱門的話題。今天我們就借著這個機會，把相關的演算法和實現理一理吧。
考慮到篇幅太長的話，俺的手指頭招架不住，再一個不少對這個話題感興趣的同學可能壓根就不是程序員，一些實現細節可能我就只是簡單提一下，貼代碼什麼的還是算了，盡量保證整篇文章的信息濃度適中吧。
----------------------------
總的來說，這十多年來，地形渲染技術的發展史就是一部生動的對現代GPU的開發，利用和改進史。整個過程大致可以分成三個階段：一開始，GPU處理頂點能力很弱，這個時期的各種精巧演算法（如一些VDPM和後期的ROAM），**儘力在用CPU來降低頂點的總量**，避免一不留神壓垮圖形系統；後來，圖形系統的能力上去了，人們開始更多地考慮到**把地形系統融入到通用的場景管理**中去，如四叉樹八叉樹什麼的就是在這個階段被廣泛應用的；再往後，GPU已經很強大了，CPU由於要承擔更複雜的遊戲邏輯，越來越成了整個系統的瓶頸，這個階段，人們琢磨的更多的是，怎麼**利用GPU給CPU減負**了，一直到如今，由 GPGPU 帶動起來的異構計算，也都是這個路數。
----------------------------
由於內容比較雜，超大地形這個段落，按上面的描述，咱們分為三個小段分開來講吧。讓俺先沏上一杯碧螺春，為客官一一道來。
#### 4.1 古典演算法（從 GeoMipMapping，Progressive Mesh 到 ROAM）
GeoMipMapping 是從紋理的 MipMapping 技術演化來的一個地表處理技術，原理上是根據任何一小塊地形在屏幕上顯示的實際尺寸（主要跟與攝像機的距離和起伏程度有關）來選擇對應密度的網格，然後把不同解析度的網格之間以某種方式拼接起來（沒有這一步的話就會有裂縫），本質上是一種比較粗糙的區域 LOD 演算法。順便說一下，由於那時候針對頂點級的處理很多，導致這種T型裂縫很常見，以至於有個專門的名字叫「T-Junction」，針對這個的處理在當時也有很多方案。
這是俺剛剛到老硬碟里刨出來的大三時寫的 GeoMipMapping 代碼，編了一下居然還能跑起來。有點土，別介意：P 可以看到不同的 MipMap 級別是用不同的顏色渲染的，也可以看到接頭處 T 型裂縫的處理。唉，這代碼勾起了俺的青蔥回憶啊，那就順便再來兩張 T 型裂縫的示意圖和消除過程吧。
----------------------------
----------------------------
Progressive Mesh 是後來很流行的技術 Simplygon 的前身，原理上基本也是一致的，就是以某種方式漸變性地化簡某個給定的 Mesh。
漸進式網格有兩種：視點無關的 （View-Independent Progressive Mesh，VIPM） 和視點相關的 （View-Dependent Progressive Mesh，VDPM）。兩者的區別就是，前者預先離線生成好所有的漸變過程，運行時直接用就行（也是後來 Simplygon 採用的方案），而後者隨著攝像機的位置和角度的變化，生成對應的簡化模型。兩相對比，VIPM的好處是運行時運算開銷低，簡化模型的效果好，缺點是費內存（因為數據都存下來了，當然後來增量的方式能省一些），而VDPM在當時是不錯的選擇，因為跟VIPM相比不用費額外的內存，而且對於視點（就是攝像機）變化不劇烈的應用，不需要每幀處理和更新對應的簡化模型（普通的MMO類的一般一秒一次就夠了），此外由於一些簡單的遮擋剔除和背面剔除，能夠比VIPM裁掉多得多的頂點（一般能多裁1/3到一半吧，在當時這可是頭等大事）。
總的來說，至少在當時，兩者的應用都比較廣泛，而到了後來，顯存越來越大，匯流排卻越來越緊張，VDPM這種典型的刷頂點的演算法（比較費匯流排帶寬）就逐漸失去了市場，這是後話了。
大家可以在[這裡](3d Page (www.cbloom.com/3d))看到一些 PM 在地形渲染上的應用。圖咱就不上了，大家可以到 Simplygon 的網站上去看。
----------------------------
ROAM 可算作是上面提到的 VDPM 更進一步了。這個演算法實際上借鑒了當時主流引擎的標配BSP的思路，想利用二叉樹這個最簡潔的空間描述數據結構，把（CPU端的）頂點消減發揮到極致。整個地表被組織成一個巨大的二叉樹，有兩個隊列，一個是分割隊列，一個是合併隊列，分別用於處理攝像機移動時，增加進入視野的區域細節和消減退出視野的區域細節。精心設計的 ROAM 效果非常華麗（尤其是在線框模式下），你會看到在各種因素的影響（包括局部坡度，與攝像機的夾角，遮擋情況等等）下，各種三角形像魔術般的不斷地變幻，生成和擦除超多的細節，效果非常魔幻。我印象很深的是當時連續打Quake3兩個小時完全無感的我，調試這玩意的時候，每每不到十分鐘眼就花了。
網上找了兩張比較典型的 ROAM 大家感受一下吧。
----------------------------
----------------------------
#### 4.2 層次的藝術（Quadtree 和 Chunked LOD）
其實用於空間管理的樹狀結構有四叉樹和八叉樹（還有上面的二叉樹），但地表通常以前者居多。是因為，從小範圍來看，變化劇烈的地形是3D的，適合八叉樹在xyz三個方向上擴展；但當尺度大到一定規模之後，地形通常退化為相對扁平的2D空間，就像攤平了的地球表面那樣，在豎直的Z方向上變化相對不大，而XY平面則是可能無限延伸的。
Quadtree 四叉樹很直白，具體的細節我就不講了。值得一提的是四叉樹往往也同時用於場景管理的快速剔除和查找，從理論上來講，四叉樹是一個平面上最迅速的用於剔除空間，定位一個物體，內存開銷也是相對較低的數據結構。當用於地形渲染時，頂點剔除的效率也很高，我印象中僅次於高度優化的 ROAM。內存開銷低主要是因為四叉樹是可以完美展開到一個位數組裡的，這樣的話意味著整個樹的利用率達到了百分之百——所有的空間都用來存儲數據而不是維持結構。
不過四叉樹也不是啥都好，T型裂縫就比 GeoMipMapping 難處理，因為存在跨級的多段 T 縫，如下圖：
除此之外還有一些細節問題，這裡就不一一說明了，地形的四叉樹渲染還是有很多細節需要細心處理的，此處暫且放下不表。
----------------------------
Chunked LOD 是一種雜合改良的 LOD，其實糅合了上面說的不少細節，本質上是一種分區塊地消減細節的技術。所謂 Chunk 是批量處理的一種方式，只是一種粒度劃分的單位而已，跟現在 Java 的 GC 里分區回收概念上差不多。
下面是典型的 Chunked LOD 後的效果：
頂點多次過濾優化後的效果：
效果在當時還是很驚艷的。通常不到50k的渲染數據量已經能有非常逼真的效果了。
----------------------------
#### 4.3 以GPU為主的技術（從 Paging，Clipmap 到 GPU Terrain）
上面的基本上都是傳統方案，這一節我們將逐漸過渡並挨個介紹一下以 GPU 為運算主體的演算法。
----------------------------
所謂分頁（Paging）實際上是仿效虛擬內存的運行機制的一種方法。由於地表的頂點數據都是靜態數據，適合常駐顯存。當世界尺度較大時，顯存沒法一次放入所有數據，那麼系統就像虛擬內存那樣，把那些暫時沒有用到的數據交換出去。隨著遊戲的進行，Paging In/Out 也在不斷進行，輔以一定的非同步機制，載入到顯存的延遲可以被很好地掩蓋。玩家的直觀感受就是：哇，海量的細節。
----------------------------
而 Clipmap 則比 Paging 更進一步，以金字塔的形式逐級把數據排列好，直接整體更新和渲染。從這裡也可以看出 GPU 時代人們的思維方式的逐步變遷。從以前頂點級別（Vertex Level）的「錙銖必較」，到後來的一次多塞一點也無所謂，只要批次（Batch）少就 OK。下圖可以看出 Clipmap 的基本思路。
----------------------------
所謂的 GPU Terrain Rendering 就是把高度圖從內存里經由 2D Vertex Texture 搬到 VS 里去生成三角面，這樣的好處是 CPU 和內存就被徹底解放出來了。只是訪問上有一些限制，不像直接處理內存那樣方便。具體的細節可以看這裡：[GPU Gems 2: Terrain Rendering Using GPU-Based Geometry Clipmaps](GPU Gems - Chapter 2. Terrain Rendering Using GPU-Based Geometry Clipmaps)
在 GPU 上做還有個巨大的好處是可以藉助 Gaussian Noise 即時生成更多的細節了。直接拿一小塊預生成的高斯噪點圖在需要的時候疊加一下，就能在沒太大額外開銷的情況下，增加各種細節。如下圖所示：
----------------------------
隨著大家對 GPU 理解的深入，地形的處理又有很多的小技巧可以做，尤其是在 PS 裡面，比如法線生成，動態uv展開，光照按需疊加/衰減什麼的。不過呢據我所知沒有什麼非常別具一格的架構上的新思路了，所以就不再深入了。
### 5. id tech 5 的 megatexture （超大地表上的非重複性海量貼圖）
megatexture 在當年（2007）是一個非常值得一提的技術。在這個技術出現之前，幾乎所有的地表渲染用到的貼圖都是若干張 blend 到一起後，以 tiling 的形式重複平鋪在地表上的（包括比較典型的魔獸世界也是如此），這樣的直接後果是圖片的種類用多了耗資源，用少了又很容易感到單調和重複。而 megatexture 則是一張全局的超大貼圖，從根本上避免了重複這個問題，理論上（實踐上也是）能夠生成非常壯麗和獨特的地質風貌，是傳統的刷地表無法創作出的效果。可以說這個技術讓真正的全景地貌成為可能。
----------------------------
技術上的細節puzzy老師寫過一個 pdf，強烈推薦感興趣的同學搜來看一下（可以搜「 **ID Tech 5 中"Megatexture"針對地形的D3D9 基本實現原理 - 姚勇**」），珠玉在前，我就不啰嗦了。就來一張效果圖吧（好吧我知道能堅持看到這兒的同學，這圖基本上肯定都看過了）
全局超大貼圖對一個開放性世界的價值不言而喻。想像一下，跟拿樂高積木拼接出來的視覺效果（傳統的 texture blending and tiling）相比，一幅萬米畫卷上，每個像素都可以隨意描繪，是一種什麼感受。 比如，你可以相對輕鬆地實現「整個世界的地貌瞬間被密集核彈蹂躪了一場之後」的效果。如果你想模擬整個生態環境的變遷，在不同粒度上的整體性修改更是無價之寶。
----------------------------
### 6. 過程式的內容 （Procedural Content Generation）
「過程式生成」是一個不是很恰當的翻譯，實際上更貼近本意的說法是「以程序的手段生成」，這裡我們簡潔起見，仍使用過程式生成的字樣吧。
過程式的內容生成是隨機技術的在視覺效果上的一個重要衍生。這個技術雖然到最近才被廣泛應用，但實際上從技術角度講，在很久以前就已經有比較成熟的實現了。我手頭的 2003 年出版的翻譯版 Game Programming Gems III 中 就有 4.16 和 4.17 連續兩篇文章以「程序手段生成的紋理」作為主題。這是構建超大規模的世界的一個重要的技術工具，尤其是與上面的 megatexture 技術結合起來，可以創造出非常令人震撼的視覺複雜度。
下面是 sourceforge 上一個開源的項目 [PCity - Procedural Modeling and Rendering of Cities](http://pcity.sourceforge.net/)
可以看出，對於過程式生成來講，只要有非常小的初始數據集（meta-data），可以在宏觀上達到很大尺度和複雜度的視覺效果。
過程式生成有兩大分支，一個是過程式紋理，另一個是過程式建模（上面的 PCity 屬於後者），下面我們分別來談一談。
#### 6.1 過程式紋理（Procedural Texturing）
人們發現，自然界中有很多視覺效果是可以用數學公式加上一些簡單的隨機性來模擬的，比如雲彩，水流，火焰，木紋，大理石，草地，夜空，大氣等等，程序生成的紋理效果大大豐富了普通紋理能表現的效果，就好像是物理引擎給遊戲增加了活力一樣。一個普通的噪點圖，在不同的情境下，作為輔助參數來參與生成動態紋理，可以產生出近乎無窮無盡的變化。
這是過程式生成的雲，出處在[這裡](http://www.indigorenderer.com/content/cloud-render)。
這是過程式生成的外觀，使用了 Allegorithmic 公司的 Substance Designer，出處在[這裡](Procedural Textures Using Allegorithmic Substance Designer)
這裡是一些分解材質，相當於過程式紋理的圖素，出處在[這裡](3DTotal Tutorials)。
#### 6.2 過程式建模（Procedural Modeling）
過程式建模特指以程序的手段動態建模。這是一個更大的話題，現在比較成熟的中間件的代表是 Speedtree，比如下面這個效果：
完全不同風格的紋理，模型的任意雜合，隨意生成，效果也非常真實，非常適合做恐怖遊戲。在 Speedtree 的網站上還可以看到長成茶壺的樹之類的奇葩。我還記得有一年的GDC，在 IDV 的 Speedtree 的展台看到的一段華麗視頻，就是各種藤蔓植物在幾秒鐘之內長滿了一個峽谷內的整個大壩，電影級的效果非常震撼，不知道現在網上是否還能找到。
----------------------------
過程式建模是一項非常迷人的技術，我本人也曾被深深吸引，在上面投入過一段時間的精力。2010年時，我在開發一款飛行射擊類的 MMO，當時接觸到了 [Gamr7](GAMR7 | LinkedIn) 的過程式建模技術，感覺很不錯，在飛行類遊戲中，地面物體的建模可以完全以程序方式生成，這個對當時的我來說吸引力太大了。那時我花了一個月把 Gamr7 的技術集成到自己的框架里，並在上海世博會期間，與 [Bernard Légaut 先生](Sign Up | LinkedIn) 一起在世博會的法國企業館展示了合作成果。摘兩張當時的 PPT 吧。
截圖中的素材基本上都是使用了過程式自動生成的（不是美術手放上去的），樹是用 speedtree 生成的。
總得來說，過程式建模是一項潛力遠遠沒有得到釋放的技術，現有的工具還處於比較原始的階段。在當年 PPT 的技術展望（Beyond the Tech）一節中，我寫到「（過程式建模帶來的）更高級的抽象使我們可以控制更高的複雜度，從而帶來更豐富的細節 (Higher abstraction makes much more details and complexities manageable) 」時至今日，受限於技術的發展，這仍只在某個特定的主題（如 Speedtree 的植被模擬和一般的城市模擬）內有效。對於隨機性的粒度，我們仍缺乏有效的手段去控制。當年展望時的兩大 Expectation（一個是建立起模式和庫抽象從而滿足不同層次上的復用需求，另一個是如何統一過程式技術中的無序和有序，有效地控制隨機性的粒度），現在據我所知仍是所缺甚多，頗為渺茫。當然了，對有志之士，這也不失為一大探索方向。
## 二、內容製作篇：設計和創造（Content Design Creation）
聊完了程序方面的內容，我們來簡單講講超大規模世界在設計和製作方面的一些情況。這方面因為我不是專家，只是做一下簡單的介紹，不足之處，還請專業人士指正。
### 1. 隨機地圖類遊戲 (Diablo II) 中地圖的拼接
在暗黑二，暗黑三和類似的遊戲「火炬之光」等遊戲中，通過巧妙的拼接，理論上可以通過組合，生成近乎無限大的地圖。
這是暗黑三第二章里所有地圖的可能的部件形狀：
這是拼接之後的樣子：
除了拓撲結構上可以任意排列組合以外，在每一個分片上預留足夠多的通用介面也很重要。比如一扇拱門，可以是閉合不可交互的狀態，也可以通向下一個直角走廊，也可以是通往一個副本的入口。
要注意標準化的組件如果太多也會讓玩家覺得單調和重複感過強，火炬之光在這一點上就做得不錯。下圖是火炬之光生成好的地圖樣貌：
可以看到效果還是很不錯的，一眼看過去已經不太有重複感了。
### 2. 無縫大世界 (World of Warcraft) 中區域地圖的拼接
無縫世界類遊戲的區域拼接和上面的隨機生成類遊戲的區域拼接是很不一樣的。
可以看出，不同的區域之間有著很長的接壤線和完全不規則的邊緣。在這種情況下，為了簡化製作，大部分邊界區域以高山作為阻隔。你幾乎不怎麼會看到有建築橫跨兩個不同的區域，原因也是在此。
在沙盤製作時，通常的做法是在整個世界地圖（對應的世界編輯器）中規劃好每個區域的範圍，也就是分區分塊。每個區域由不同的設計師在場景編輯器中分開製作。在製作當前場景時，與該場景接壤的幾個場景的最新版本都會載入上來，編輯器中可以提供一些方便的工具，便於在接壤處對齊。主要是高度的對齊和貼圖的融合。前者通常的選擇是高度上用 Smooth 工具平滑過渡到鄰接場景，後者通常最簡單的處理方法是真正的過渡點兩邊使用同一種貼圖即可，實際的美術風格過渡（如果需要的話）在鄰接地圖的接壤線附近完成。
一些貫穿不同地圖的元素（如河流等）可能需要世界編輯器的參與來指定水平面的高度和區域範圍之類的參數，但這一類元素通常不會太多，因為它們沒有明顯的 Gameplay 貢獻，反而加劇了不同場景之間的耦合。
如果遊戲有動態的天氣/環境氛圍系統，那麼不同場景之間需要做一些平滑的過渡，這些程序用普通的插值實現就可以了，設計師一般只用關心當前場景內的表現即可。當然有的遊戲這個過渡做的不好，玩家體驗非常生硬，也是有的。
總得來說，這一類無縫大地圖的複雜度主要是在編輯器的協同方面（後面我們會再提到）,實際的創作複雜度較前面的隨機地圖生成為低。
----------------------------
### 3. 衛星地質數據的導入，規整化和再加工（一些飛行模擬類遊戲）
超大規模的開放性世界地圖，還有一類是直接使用衛星地質數據以加強整個世界真實性的。據我所知，育碧出品的 Tom Clancy"s H.A.W.X. I II （就是國內翻譯的 鷹擊長空 I II）就是使用了 GeoEye 的商業級高解析度衛星地圖。
既然用了真實的衛星地質數據，這一類遊戲同樣能生成非常震撼的效果，也就不用多說了。找兩張截圖大家感受一下吧：
這一類的缺點是不能模擬真實世界中沒有的環境（當然拿去再創作的不算）。
這種真實數據的數據源就沒什麼好說的了，我簡單說一下導入後的處理。通常導入後的貼圖需要美術在色彩和明暗上二次加工一下，得到和遊戲匹配的整體氛圍。需要提供比較精確的工具給美術進行高度圖和高解析度紋理的擬合。此外通常這一類地質數據是沒有 NormalMap 的，需要提供工具生成一下。
還有就是，河流和湖泊這一類水體的處理，3D遊戲通常在渲染效果方面對水面特效照顧得比較多。如何生成跟真實環境相匹配的河流和湖泊是一大難點。因為一般遊戲里是有一個絕對水平的特效面片的，而如果給真實環境中得來的高度數據上配一個這種特效面片，通常無法跟真實的貼圖相吻合（尤其是在山脈和峽谷等地形中的水體）如何提取真實的高解析度貼圖中的水面信息，自動生成對應的3D水面，也是一大話題。當然，如果不怕費事，也可以由美術直接做出來了事。
----------------------------
### 4. 超大地圖的協同編輯：並行操作，數據同步，手動和自動鎖的運用
現在咱們回過頭來聊一聊在 wow 這一類超大地圖裡，如何在多人團隊內協同編輯的問題。
----------------------------
對於美術（這裡專指負責場景的設計師）來說，常見的最簡單做法是每人一塊（或多塊）區域地圖，團隊內維護一個公共的物件和貼圖庫。（物件和貼圖可以由專門同事製作，需要時也可外包）在這種情況下，美術的並行化程度很大程度上取決於團隊自身能力，對場景編輯器沒有特殊的技術上的需求。
超大地圖的場景編輯器在載入周邊鄰接的區域地圖時，需要顯式地標示出其版本和上次修改日期，這樣可以把鄰接區域的修正工作量降到最低。最好的做法是能夠通過版本管理軟體，在有同事修改了鄰接區域以後自動更新並重新載入（當然可以稍有延時，不用那麼即時），這樣的並行工作效率可以達到最高。
真正的難題通常發生在策劃那邊，當需要編輯跨區任務或事件時，如果對 Ownership （也就是場景實體的所有權問題）管理不善。跨區系統可能會產生各種層出不窮的 bug。比如同一個 npc 承擔了多個跨區職責時，其中的狀態就可能會互相干擾，在殺掉某個 npc 這一類任務中更易出現，造成難以重現的 bug。這就需要提供明確的所有權管理機制，明確跨區訪問的一般規則，提供簡單的全局狀態檢測工具，在設計時就能提示出絕大多數潛在的衝突。當然，這些的先決條件是所有的區域數據，要麼提供中央資料庫管理，要麼工具做到在團隊網路內實時同步。
----------------------------
最後我們來說一下真正有趣的實踐，就是「真正的」協同編輯。也就是任意個美術和任意個策劃可以工作在任意個區域里。是的，你沒看錯，這才是終極的開發自由度。其實如果這是一個如典型的 WOW 那樣的 MMORPG 的話，這就跟「所有的玩家登錄到同一個伺服器一起遊戲」是同一個概念了。所不同的是，這裡的「玩家」實際上全部是開發團隊的成員，而且他們是有能力創造和修改這個遊戲世界的。
只要想通了這個概念，實踐上並不像想像中那麼複雜。由於美術和策劃對同一個地圖關注的焦點不同，我們只要把他們工作有交集的部分處理好，他們就能一起愉快地玩耍了。實踐上來看，兩者的交集通常是 a. 整個區域的邏輯高度圖和 b. 所有的相對碰撞關係。也就是說，美術和策劃的工作內容里，只要不涉及到這兩者，都可以隨便搞，但如果影響到了這兩者，編輯器需要有能力提示正在修改的人會影響到什麼（或按默認行為自動處理），通常是不難做到的。舉個例子，策劃放好 npc 後，美術去調整高度，把 npc 站的廣場弄成一個山坡，那麼要麼提示美術這麼干可能會影響到策劃的設計，要麼自動把對應的 npc 都重新調整位置，吸附在新的地表高度（一般編輯器允許設置為吸附到地表）。
當兩個美術在修改同一區域時，就涉及到鎖的問題了。鎖有兩種，一種是在編輯時自動觸發，場景地表以區域為單位，物件以 Instance 為單位，當編輯時自動把 Owner 設為當前編輯者，提交改動到伺服器時可以選擇繼續鎖或是釋放鎖。一種是手動鎖，就是美術框住一片區域，主動加鎖，這樣有些時候更方便。編輯器製作者需要考慮的一些細節有：鎖住的區域在其他開發者的機器上，需要比較顯眼的提示信息；保險起見總是多鎖一定的範圍，以方便地表平滑等工具編輯時對周邊區域的影響，等等。
----------------------------
## 三、異次元篇：我們的征途是星辰大海
上面兩部分「程序技術篇」和「內容製作篇」已經把大規模開放世界講得差不多了，下面的內容我取名叫「異次元篇」，也是隨便侃侃，大家隨便看看就好。
### 1. 終極沙盒（EVE）：當規模大到一定程度——宇宙級別的混沌理論與蝴蝶效應
對於開放式世界來講，如果沒有真正與這個世界的尺度相配的開放式的交互，那麼仍然是一個死氣沉沉的世界。EVE，正是一個為了開放式交互而打造的超大的沙盒宇宙。
在這個宇宙中，玩家擁有很高的自由度去探索，創造，建設，摧毀（針對自然環境而言），配合，領導，同盟，背叛（針對社會環境而言）。這遊戲我就不展開介紹了，有興趣的同學可以去看一下 [EVEWiki](EVEWiki)。有趣的是，當沙盒大到一定程度時，它會在很多方面展現出一種自平衡的性質，就像經濟學中那隻「看不見的手」，自然生態學中地球這個大型生態系統的自我調節和自我修復。在我看來，這也是開放式遊戲的最大的魅力之一，也讓系統的複雜度進一步接近真實世界。
### 2. 打通兩個宇宙（EVE Dust）：發現更廣闊的世界——宇宙沙盒遊戲和行星射擊遊戲聯動
跟上面列舉的諸多成功遊戲範例不同的是，我接下來要說的，是一個雖然雄心勃勃，但卻沒有成功的例子。
EVE 的製作商 CCP，是一個來自冰島的很有趣也很有追求的工作室。在 EVE 的大尺度宇宙成功地運行了若干年後，他們選擇了一個更大的挑戰——設計另外一個大型多人在線遊戲，把新老兩個宇宙之間聯繫起來，讓兩個遊戲內的玩家可以互動，相互交談，配合，僱傭，指派任務，火力支援或其他的互動，最終打通兩個宇宙，讓兩個大型多人在線遊戲之間達到有機的協同和交互。
CCP 從一開始就沒有掩飾這個雄心勃勃的計劃，這是一個令骨灰級玩家們震驚和眩暈的設計，也是一個電子遊戲行業從未有過先例的構想。
這個構想是如此令人敬畏和富有吸引力，以至於我在拿到 offer 後毫不猶豫地投身 CCP Shanghai 的懷抱。在遊戲行業，我感到很幸運，能夠有機會參與到這樣一個項目中來。然而由於一些大大小小的原因，這個項目最終雖在 PS3 平台上線，卻沒有取得預期的成功。這裡既然與主題無關，我就不打算談論更多的細節了。
在 CCP 兩年間，我只是一個很普通的工程師，這裡的工作經歷極大地拓寬了我的眼界，讓我知道了什麼是真正的 fearless，對先行者們，我始終滿懷敬意，對於自己有機會能參與這樣的一個項目，我也始終心懷感激。
----------------------------
謝謝你們，讓我能在晚上凝視夜空的時候，腦海中浮現出更廣闊的世界。
----------------------------
（全文完）
Gu Lu[2014-11-16]----------------------------
[2014-11-17] 補記：一開始看這個話題有趣，想著說兩句。沒想到一動筆就停不下來，一口氣寫了七八個小時我也是蠻拼的。其間或有錯漏疏敝之處，讓行家笑話了。如發現錯誤，請不吝指正，在此先行謝過。如引發了有趣的想法，也歡迎在評論中一起討論。
[2014-11-18] 補記：今天中午有半個多小時 Blog 無法訪問，後來聯繫 FarBox 才曉得是流量已經超上限，因為我用的是基礎版，每個月100MB流量，可以用5年。結果今天一天的流量就把5年的配額全用完了……剛回到家以後亡羊補牢了一下，把 png 都換成了 jpg，省一點是一點吧 
FarBox 反應很迅速，贊一下
另：文章無版權，可隨意轉載；是否註明出處，亦無要求。
本文同時發在我的 Blog，在那裡或可獲得更好的閱讀體驗：[知乎] 開放世界遊戲中的大地圖背後有哪些實現技術？- 細節層次（level of detail, LOD）：模型需要支持細節層次，以減少幾何渲染量，以及紋理數據的內存量及內存頻寬。LOD有分離散及連續方式。詳情可參與《Level of Detail for 3d Graphpics (豆瓣)》。
- 串流（streaming）及緩存（caching）：把數據塊在運行時非同步載入，並按某些條件御載（如least recently used／LRU）。
- 可見性檢測（visibility determination）：除基本的視錐剔除（view frustum culling），還需要離線或線上進行遮擋剔除（occlusion culling）。
除了渲染方面，也要考慮遊戲模擬方面的部分。例如物理碰撞數據的載入，以及是否進行遊戲邏輯的LOD等。
----
更新：浮點數精度問題由於浮點數的精度有限，單精度浮點數只有不足7個十進位數位，如果距離用米作為單位，離原點1公里的坐標，其精度只有大約1毫米。這對於渲染及模擬都有影響。
解決的方法之一，是把世界劃分成不同的區域，在區域內的計算使用其局部坐標系統。當對象從一個區域移動至另一區域，要進行坐標轉換。但最麻煩的情況是兩個區域的遊戲對象互相交互，在交互時要把其中一個遊戲對象的坐標轉換至另一對象的坐標系。謝邀。這個問題問得不是很具體。如果只是渲染超大地形的話，分塊+LOD就可以了，實現個cache用IO線程動態地把需要的地形塊stream進來就行了。
開放地圖大世界的一個關鍵就是Streaming技術超大地圖不光要解決渲染地形這個問題,其他連帶的還有各種數據,比如尋路數據,模型數據等,這裡統稱為map data。Streaming 說白了就是把map data分塊保存,比如128m*128m為一個Chunk,每次streaming根據人當前的位置load周圍3*3塊數據。一般而言和遊戲邏輯相關的數據這樣就OK了，但是很多情況下，和視覺相關的數據還不能這麼簡單的處理，比如遠處的風景和遠處的地形(總不可能只讓玩家看到128m*1.5的範圍的東西吧，除非你是一個topdown視角的遊戲)，所以還要考慮lod；地形lod個人覺得CDLOD技術還是很不錯的，過渡非常平滑，唯一的問題是必須支持VTF(除了某些手持設備這個好像標配，所以這個不是問題)。有時候為了處理地圖邊緣這種地方還會用到Terrain Skirt。關於精度問題，就得把所有位置信息都以角色位置為中心做一次轉換了。NPC在視野外的問題，個人沒做過console（網遊這些都是在伺服器計算的），基本上只更新邏輯了，根據重要程度來設置邏輯的更新頻率。還有一個比較常用的思路就是Hierarchical，也就是分層去處理超大地形上的邏輯，比如尋路之類
推薦閱讀：
※一個完整的遊戲副本包括哪些要素？
※用國外的3d遊戲開源引擎製作遊戲，是否可以說這款遊戲是自己寫的？
※如何有效地學習ue4的源碼？或者說有什麼地方要注意的？
※Unity上面有什麼好的熱更新方案？
※在 Ubisoft 工作是什麼樣的感覺？