大家好，你們能聽到我講話嗎？這個演講的內容是介紹RNG（隨機數字生成）的一些黑暗秘密。如你在大屏幕上看到的，Squirrel已經介紹了一些RNG的基礎概念。首先，我想詳細講解幾點。他的演講更偏重理論，而我的更偏重實際應用一些，不僅僅會討論一些在游戲開發中遇到的RNG相關的潛在的問題，還會介紹解決這些問題的工具。這個題目“黑暗秘密”不太好，會讓人以為Squirrel探討了黑暗的、復雜的數學公式，不過我們的重點是談論如何使用那些數學公式。

首先我是誰？為什么你們要聽我的演講呢？這些是我參與制作的游戲。
?

有很多！在一些大工作室，我參與了《爐石傳說》的制作，設計了游戲的一些原型，這是我制作的最好的一款游戲了。我只在那里工作了一年，當然是制作CCG（交換卡牌游戲），其中有很多隨機數字生成。我獨立開發過很多游戲，比如右下角的《Overland》，是一款roguelike類型游戲，其中有很多隨機生成的關卡。現在我在Direwolf工作，位于科羅拉多州的丹佛市，我仍然負責開發CCG。也許以后會在這干下去，也許不會。

不過我們來談談使用RNG吧。我們從一些基礎的、作為一名程序員在這個領域必須要面對的問題決策開始。這款解謎游戲《Connectrode》是我之前在2011年制作的，我的妻子非常喜歡，試玩了這款游戲的未成品。

這款俄羅斯方塊風格的游戲會隨機生成一些方塊。有一天晚上我的妻子向我抱怨道：在一行中出現了9個顏色相同的方塊！我意識到我需要修復這個bug。我采用俄羅斯方塊游戲所使用的方法，有時人們將這個方法稱為套袋方法（Bagging）。
?

這是用來為你的游戲加入隨機性的一個基礎方法。如果你像我一樣每一輪都投擲一次骰子來從6個數字中隨機得到一個數字，你會得到一個均勻分布。不過有的時候你不希望這個隨機性過于隨機，一個簡單的方法是——這其實是一個設計決定，或者桌游設計者會這樣說——“這里不應該使用骰子，而應該使用一副紙牌。”從數學上來講，投骰子是對一個隨機集合進行取樣，允許樣本的重復，取樣不會改變該集合；而使用紙牌的話，你從中抽出一張牌后這張牌不會回到牌組中。
?

這樣可以確保在分布中不會產生重復的結果。多數使用套袋方法的游戲都有一個套袋，套袋中包含一個隨機集合。考慮紙牌的洗牌。我們可以使用三副紙牌洗牌——實際上拉斯維加斯的賭場現在就是這樣做的，為了防止人們在黑杰克21點游戲中作弊。他們把三副或者更多副紙牌混在一起洗牌，這樣會改變紙牌分布的隨機性。因此如果你發現相同的分布規律一次又一次地出現，那么你要重點考慮一下它，這種情況對我來講并不常見，不過你應該使分布更加平穩。另外我們還要考慮邊緣情況。如果你同時洗三副牌，然后當沒有牌的時候重新洗牌，首先你會想到你能得到的最大組合是三個黑桃尖。接著如果你重新對一副新牌洗牌，這時會產生一種邊緣情況——字面意義上的邊緣情況，即在一個套袋的末尾你有可能得到三個黑桃尖，而在另一個套袋的開始你又得到了三個黑桃尖。
?

這個邊緣情況作為隨機性的一個特殊情況值得考慮，因為這是RNG的第一個黑暗秘密：如果你沒有提前計劃使其不可能發生，那么每個隨機的邊緣情況可以發生，（最終！）將會發生在一個玩家上。
?

作為一名游戲程序員，你是確保這個問題不發生的最后一道防線，有的時候你要和設計師一起解決這個問題。我在Direwolf的這些CCG設計師同事，他們非常擅長數學。不過我也有和一些擅長美術的設計師工作過，他們的數學應用能力這方面很糟糕，所以有的時候程序員要站出來說“你考慮過這些了嗎？”即使這通常是設計師的工作。

這里我引用了話劇《Rosencrantz and Guildenstern Are Dead》，其中的角色在整部劇中不斷地投擲硬幣，每次都是正面。這個概率非常小，不過在游戲中有的玩家有可能會擲出100次壞點。如果在數學上可能，那么最終一定會發生。你要把這點考慮進去。而這個問題的解決方法就是……這是暴雪的開發者發表的一篇藍帖，介紹了《暗黑破壞神3》使用的方法，對于這種打裝備的游戲來說，這個問題的解決非常重要。他們加入了一個我稱之為“保底機制（Pity Timer）”的東西。
?

這里的藍字解釋道：“掉裝備的概率很低。而對于有的玩家總也打不到一個裝備。”因此他們加入一個保底機制，以確保一段時間不掉裝備后一定會掉裝備，使其按照預期的機制運行，即玩家最后總會打出傳奇裝備。RNG最大的黑暗秘密是——你會時常遇到這個問題，我想詳細談談這一條——就是總的來講，人的大腦不是很擅長處理概率問題。
?

在很多情況下，人腦很容易錯誤地理解概率，因此引入諸如保底機制之類的機制可以……嗯……玩家知道裝備有百分之一的掉落概率，然后殺了二百只怪，他明白從邏輯上有可能殺的這兩百只怪什么裝備都沒有掉落，不過他還是會很不爽地抱怨。他們沒有預料到會經常出現這種情況，除非坐下好好地進行一番數學計算。而我們有關RNG的很多技巧模擬了他們的預期，使得隨機性朝著玩家認為應該的那樣進行，即使在數學上并不正確。保底機制正是一個例子。不過玩家仍然會經常抱怨RNG不公平，討厭它，詛咒它……

事實上我之前恰巧聽到這個故事，有個叫做《Urban Dead》的游戲，一個MMO網頁游戲，我很喜歡玩。游戲中包含隨機點數，如果你點擊攻擊按鈕，系統會擲點決定攻擊點數。一個玩家寫道：如果在溝槽中點擊攻擊按鈕，然后進行攻擊，然后在溝槽中等待八秒鐘后再次攻擊，他總會攻擊成功。而在游戲的維基頁面的頂端，這名開發者說道：“這根本不可能！我使用一個隨機數字生成器了！”
?

如果你之前聽了Squirrel的演講，那么你應該不會被這點驚到。不過結果證明玩家是正確的。開發者只是簡單地將當前時間以秒為單位輸入到rand（）函數中。而Squirrel的演講提到了它最低的兩位其實是不可靠的。因此每過八秒鐘奇怪的事情可能就會發生。我覺得這個開發者很滑稽，首先否定了這個問題，后來才意識到這個問題。所以你不能輕易地種種子。在我們的例子中我們可能犯這個錯誤，所以你要透徹地思考這個問題以便你的游戲中不會出現此類bug。玩家們通常會懷疑此類按鈕有bug，懷疑RNG是否出了問題。不過總會有巧合發生嘛。好了，這是游戲編程的黑暗秘密，我要把這些概念綜合在一起：對于任何可能的事情，設計師總會改變他們的思路。
?

這對于打裝備的游戲尤其適用。我的觀點是，如果在設計一款打裝備的游戲，或者以打裝備為主的游戲時，設計師應該對其進行調整，因為這會對玩家體驗以及一些你可能想不到的事情造成巨大影響，我們一會兒會提到。沒錯，玩家獲得一件傳奇裝備的體驗非常重要，他們要確保有保底機制，使玩家殺死boss足夠多的次數后一定能得到傳奇裝備。

在這里我想要介紹一個工具，它能讓你控制裝備的掉落，詳細來說這是一個查找表。沒錯，查找表可以表示骰子，也可以表示一副紙牌，或者其它的東西。一個加權的查找表可以這樣創建：假設有52個元素，每個元素代表一張牌，每張牌的起始權重為1。如果權重可以被修改，那么這就成了一個強力的工具。你可以將一張牌的權重減為零，當它被抽走后，然后在后面再重新設置。你還可以表示很多其他內容。這里我用來表示打boss掉的裝備，普通裝備權重為1，罕見裝備權重為0.5，罕見裝備掉落的概率為普通裝備的一半。
?

這里我實現了一個保底機制。首先這是嵌套在查找表中的查找表，有助于你響應設計者的要求，使你有很大的自由可以修改裝備掉落的參數，并且加入一些細節，就像我們在這里為傳奇裝備加入保底機制那樣。在下一張幻燈片我會介紹一些更復雜的情況。

動態加權是另一個實用的工具，在這個例子中根據保底機制傳奇裝備的加權會動態改變，最終會掉落。大家能看到我的鼠標嗎？實際上這里我加入了回調函數，這第二個的意思是每當掉落的裝備不是傳奇別時，傳奇裝備的權重會增加。不過這仍然有悖于我的規則，即你應該考慮所有的邊緣情況，從數學上講你沒有百分之百地確保傳奇裝備最終一定會掉落，除非同時減少其他元素的權重。這是另一種實現這個機制的方法。不過在這個例子中我只是在傳奇裝備沒有掉出的時候簡單地增加它的權重而已。當掉落后，將它的權重設置為初始值。這是一個很好的可維護的方法。

將這些串在一起：剛才我展示的一款我獨立開發的游戲《Angry Henry And The Escape From The Helicopter Lords: Part 17, TheRe-Reckoning》，沒錯這個就是全名，為了節省我們的時間我爭取不再重復它。在這個MMO游戲中，大boss是WalrusCopter，殺死他會掉裝備，分為普通，罕見和傳奇三個不同級別。
?

這是最初的實現方法，而現在我為傳奇別裝備加入了之前我們探討的保底機制，使它的權重動態改變。
?

這里還加入了另外一層考慮，我聽說很多打裝備的MMO都有這個問題，即裝備和游戲的經濟緊密相關。我們的這個MMO游戲最初使用這個簡單的實現，后來設計人員表示“我們遇到了一個問題，騎士使用的傳奇裝備在拍賣所的價格要比武士的傳奇裝備貴，我們應該改變這一點。”該如何回應這個問題呢？我推薦使用查找表的嵌套功能，為傳奇裝備創建子查詢表，這樣我們不僅有保底機制，還可以根據各職業的玩家人數設置不同職業裝備的權重，這涉及到供求關系，你控制了裝備的供給那么需求自然會上升。

以上是我實際遇到的一個問題。你可以通過使用如查找表之類的工具使你的代碼盡量整潔且易于維護，以應對一些意想不到的問題，我推薦你使用這些工具。

我們來看這個例子：游戲系統生成這個裝備，生成這個裝備，你可以看到傳奇裝備的權重在增加，直到最后生成傳奇裝備。
?

如果一直沒有生成傳奇裝備那么它生成的概率會不斷增加。然后會進入下一步的查找表，投出另外一個隨機點數。每顆鉆石代表一個隨機的點數。命中后傳奇裝備的權重會重置。查找表是一個很有用的工具，可以用來表示任何類型的隨機性，包括更簡單的情況，可以用在嵌套的樹形圖中，使代碼整潔并易于維護。

接下來，我想拓展一下Squirrel沒有深入探討的問題，即使用他的Squirrel噪音庫實現一些不同的隨機散列，包括隨機生成一個世界。我想展示一下如何使用散列解決和RNG相關的問題，其中包含“深度重復（Deep Echoes）”問題。
?

我會解釋它的含義。這是游戲中另一個比較奇怪的地方，有的玩家留言稱他們在不同世界之間隨機穿梭時，在一個世界中看到了一座和另外一個世界中相同的城市。
?

這種情況可能發生，因為通常在這種游戲中你要種種子，買QQ號平臺將種子賦給城市，然后城市會根據被賦予的種子隨機生成它的構成。在這個例子中，我們有一個名為“僵尸宇宙（ZombieUniverse）”的宇宙，我們為這個頂層的宇宙設置一個種子，然后它使用該種子生成一系列的子級，即下一層的星系，然后星系又生成不同的太陽系，每個太陽系又生成不同的行星，每個星球上又有不同的城市，以及沒有顯示在這里的，每個城市隨機生成的居民。

我在這里標記為紅色的地方是你可能遇到的一種奇怪的情況。首先解釋一下，上一層種子的作用是為了生成下一層的種子，因此頂層宇宙的種子被用來生成每個星系的種子，每個星系的種子是使用上一層的種子通過RNG得到的。那么最終我們會遇到的一個問題是有可能隨機種子在不同的情況中被使用了兩次，如果下面所有的內容都是使用那個種子生成的，那么你會得到完全相同的樣式。在這個例子中，這兩個太陽系中的所有內容都完全相同——它們所包含的行星，以及行星中的城市，甚至城市中的居民以及他們的名字、職業都是完全相同的，任何隨機生成的內容現在卻彼此重復，而游戲原本應該是隨機的，充滿噪音的，不可預測的，然而現在情況卻恰恰相反。我甚至昨天晚上還在解決這個問題，最終得到了一個解決方案。這個方法有一些要注意的地方，我想要分享一下我們探索解決這個問題的過程，尤其是使用隨機散列作為工具，雖然對于我們的結局方法不是最好的工具。那么，我來展示一下Unity中的一個項目來說明這個問題。希望你們都能看清楚。好了，我們稍等一下它生成，這個時間它還檢查了是否有重復。在這個嵌套的結構，太陽系包含行星，行星包含城市，城市包含居民。由于這是個“僵尸宇宙”，所以居民的名字都是RARGB，ABGGA，RRGGA，看大家都在笑我還是別讀了……
?

BRRRR！這個城市一定很冷，在北半球上吧……我們花了很長時間來解決這個問題，你會發現仍然有一些城市的種子是一樣的。同樣的名字或者種子。這里檢查種子是否相同。現在我先不使用它。我要說明的是最終我們選擇使用不同的算法來生成下面層級，而不是只依賴上一層的種子或者其它數據，這樣可以避免下一層級的重復。假設我要生成一個行星，我需要生成那個行星的內容，在這個例子中即行星的名字。為了生成它的子級，我想要使用一個其它的種子，該種子是該行星獨有的。在這個例子中，你可以看到種子的數值，除此之外還有個索引值（Index）。很明顯，這三個子級的索引分別為0,1,2。然后我可以使用它來單獨識別出這個行星。等一下……這里有兩個行星的名字相同……哦，它們的種子不一樣！好了，重點是你可以使用某一層級的索引沿著鏈條向上遞歸以識別該特定層。

直到24小時以前我依舊使用的是我的第一個解決方法——我對這個方法并不滿意——即我們預先生成所有的種子，然后使用暴力算法確保唯一性。我并不想采用這個方法，原因之一是我們另外限制了每層可以擁有的子級的數量（即限制了最大索引數），然后只要我們生成的內容數量沒有溢出，我們可以取唯一的索引數，將它們加在一起，然后乘以底數3這個最大的索引數，而不是底數2或者底數10，這樣構建出一個獨特的整數代表該元素的地址，這個元素遞歸的索引。有了這個后，我們可以將它作為一個隨機數字的查找表。這個方法有些笨拙，因為我們施加了一些限制。
?

我們發現的一個更佳的方法是使用隨機散列；將這個N維地址輸入到一個散列函數，就是Squirrel剛才展示的那個函數。嗯……這一行可能不是那么好懂，我來解釋一下：在C#中這一行的作用是把所有的層級都放入到一個數組中，然后將其輸入到散列函數中。我們可以將任意數量的整數輸入到該函數，并會輸出一個唯一的大隨機數。
?

不過這個例子不保證唯一性，因此仍有重復的可能性。現在行星會基于其父級的種子生成它的內容，但是當生成子級時它使用的是對它來講唯一的東西，這樣就可以避免生成同樣的子級了。這是InitializeChildren方法，該函數會生成種子。
?

事實上，每當我要使用種子生成一個特定的元素，比如行星，居民（事實上居民不會調用該函數，因為它沒有任何子級）等，我使用頂層（即宇宙）的種子。在實際使用中我發現我需要改變每一層預先生成的種子，所以如果行星擁有同樣的索引那么它們的名字會相同。這個例子展示了現在的情況：現在我們可以有兩個太陽系，它們的隨機種子值相同，不過它們的子級不一樣了，不會再發生重復情況了。
?

我要解釋一下為什么這很重要。當然你不希望宇宙的不同部分彼此相同，不過這種重復情況的確會發生，除非你有一個完美的散列函數，當然這樣的散列函數并不存在。最終在某處你一定會得到兩個擁有相同種子的元素，而你不希望它們相同。這完全是為了玩家的感覺。如果他們不認為這些是隨機的，那么這些就不是，比如我可以生成兩座城市，它們的道路布局可能相同，但是它們的內容是完全不同的，那么玩家可能不會注意到這個使城市與眾不同的表面上的元素和其它的城市是相同的，因為它們的所有上級內容都是不同的，而它們的子級內容也不同，因為我們解決這個深度重復的問題了。這一點很重要。
?

對了……忘記解釋這個例子一個重點了，也許你已經注意到了所有種子的數值都很小，這里為了示范的效果我將種子的大小限制在0到63之間迫使這個問題出現。我這樣做是為了突出這個問題，使大家明白了……首先，大家應該看到了使用這個隨機散列方法時一些需要注意的地方，當我們不使用唯一的查找表后我們遇到了一個新的問題，即當我生成下一級的元素時，我使用的是一個由散列函數得到的種子，不過這里再強調一下，這個散列函數有可能產生重復的結果。現在，的確有可能兩個太陽系包含同樣的行星，在我的例子中它們的名稱相同，在其他的例子中有可能位置相同。這看上去很糟糕，兩個行星的城市完全相同，城市的名稱完全相同。

對于這個“廣義重復（Broad Echoes）”問題，我把它留給觀眾們作為一項作業，因為我的演講超出時間了。
?

這個問題其實沒有一個完美的答案，因為從數學上講如果你有一個函數，輸入參數的數量大于輸出參數的數量，你總會遇到鴿巢問題，即如果鴿子的數量大于巢穴數量，那么最終總會有一個巢穴中有兩只或以上的鴿子。當遇到這個問題時，要在編譯時預先生成一個包含互不重復的種子列表，不過如果你要求輸出的種子數超出限制，你仍會得到重復的種子。不過這里我們介紹了如何使用一個元素本身的獨特性使得下一層生成的內容不會雷同。

看上去要到時間了，不過我還想推薦兩篇我搜到的文章，它們介紹了這些工具，以及推薦了這些工具的其它使用方法。
?

DanCook，在他的Lost Garden博客上很好地介紹了裝備表，以及它們如何嵌套，比我介紹的要有深度更詳細。在Unity的博客上也有一篇博客關于使用可重復的隨機數字，噪音以及散列，這篇文章令我大開眼界讓我感受到了這個工具有多么的強大。你可以在上面找到更多信息。我會將這個演講內容放在MathForGameProgrammers.com上。謝謝大家！

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的游戏编程中的数学——随机数字生成（RNG）的黑暗秘密的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。