Creating the Past, Present, and?Future with Random Walks

John Manslow

2.1 Introduction

? 隨機(jī)性在許多游戲中扮演著重要的角色，它增加了游戲的可玩性，迫使玩家去適應(yīng)不可預(yù)測(cè)的事件。它通常采用隨時(shí)間變化的隨機(jī)數(shù)值，也稱為隨機(jī)游走（random walks）。這些變量可能會(huì)影響天氣模擬中的能見度或云量、NPC的情緒或商品價(jià)格。

? 本章將描述正態(tài)分布隨機(jī)游走的統(tǒng)計(jì)特性，并將展示如何對(duì)其進(jìn)行塑造和操作，以便它們?cè)谑艿侥_本約束和響應(yīng)玩家交互的同時(shí)保持隨機(jī)性。

? 我們首先描述如何生成一個(gè)簡(jiǎn)單的隨機(jī)游走，并討論它的一些局限性。然后，我們將展示如何利用隨機(jī)游走的統(tǒng)計(jì)特性來克服這些限制，以便在隨機(jī)游走的過去和未來的任意時(shí)間點(diǎn)上有效地進(jìn)行采樣。

? 接下來，我們將討論如何在特定時(shí)間點(diǎn)確定隨機(jī)游走的值，如何控制隨機(jī)游走在區(qū)間內(nèi)的走勢(shì)，以及如何將隨機(jī)游走的值限制在特定的范圍內(nèi)。最后，我們描述了如何生成具有任意概率分布的隨機(jī)游走，并且能夠與玩家充分交互。本書的網(wǎng)站包含了本章所描述的所有的文檔和C++源代碼。

2.2 Problems with a Basic Random Walk

??簡(jiǎn)單的隨機(jī)游走包含一個(gè)初始變量?x=x0，之后在游戲中的每個(gè)時(shí)刻 t，都會(huì)從一個(gè)正態(tài)分布函數(shù)上采樣一個(gè)樣本（隨機(jī)取一個(gè)值進(jìn)行計(jì)算）。這個(gè)方法是快速而有效的，生成的隨機(jī)游走將從一個(gè)初始值開始，然后每個(gè)時(shí)刻隨機(jī)的變化，可能上升，也可能下降。

? 這種方法并非沒有問題。

? 例如，我們?nèi)绾斡?jì)算出兩天后x的值是多少？ 同樣地，玩家在兩天前觀察到的某個(gè)特定的x，這個(gè)x的值現(xiàn)在又是什么樣的？?假如玩家兩天前剛好拜訪過一個(gè)星球，又該如何去模擬這個(gè)星球的商品價(jià)格變化？

? 這就是隨機(jī)游走可能會(huì)出現(xiàn)的問題。

2.3 Solving the Extrapolation Problem Using Statistical Methods
? 解決外推問題的一種方法是快速模擬隨機(jī)游走的缺失部分。然而這種方法常受到計(jì)算性能的制約，比如在游戲中模擬經(jīng)濟(jì)系統(tǒng)，這種需要同時(shí)建模大量隨機(jī)游走模型的時(shí)候。

??幸運(yùn)的是，我們可以使用統(tǒng)計(jì)方法，只需要基于兩天前最后一次觀測(cè)到的x值，就可以精確計(jì)算出x在之后這兩天里的分布情況。具體地說，中心極限定理告訴我們，如果x在時(shí)間t0時(shí)具有值x0，那么在時(shí)間t時(shí)，x的分布函數(shù)為：

? 這是一個(gè)正態(tài)分布，具有以下兩個(gè)特征：均值x0，即最后一次觀測(cè)值；方差（t-t0）σ^2xx，其中（t-t0）是自最后一次觀測(cè)以來的時(shí)間；σ2是一個(gè)參數(shù)，用于控制隨機(jī)游走偏離起點(diǎn)的速度。事實(shí)上，由于分布是正態(tài)的，所以 x 在大約95%的時(shí)間里取值范圍都是：

? 圖2.1a顯示了使用上述等式生成的隨機(jī)游走，x0 = 90，?σ2 = 1

? 圖2.1b顯示了將σ2的值增加到5會(huì)使隨機(jī)游走變化的更迅速。

? 我們可以通過從p(x)中取樣來為x選擇一個(gè)特定的值，雖然這個(gè)x在技術(shù)上來講，與用隨機(jī)游走模擬兩天的值不同，但鑒于大多數(shù)玩家并不具備相應(yīng)的數(shù)學(xué)知識(shí)，且真實(shí)值和采樣值具有相同的統(tǒng)計(jì)特性，因此玩家不大可能分辨出差異。

? 方程2.1實(shí)際上為我們提供了一種比前面提到的簡(jiǎn)單方法更好的隨機(jī)游走生成方法。特別是，因?yàn)?t-t0 表示連續(xù)樣本之間的時(shí)間，所以我們可以在模擬游戲世界的時(shí)間步的同時(shí)，以一種恒定的方式更新隨機(jī)游走；即使不同平臺(tái)的更新間隔時(shí)間不同，隨機(jī)游走的統(tǒng)計(jì)特性也不會(huì)發(fā)生變化。

??要使用方程2.1生成隨機(jī)游走，首先為x0選取一個(gè)用于p(x)的初始值，接著，從p(x)中采樣以獲得下一個(gè)值x1；然后，可以令x0 = x1，接著從p(x)中采樣x2；然后，繼續(xù)令x1 = x2，從p(x)中采樣x3，以此類推。

? 在每種情況下，時(shí)間間隔應(yīng)該是隨機(jī)游走兩次觀察的間隔，也可以是游戲世界兩次更新的間隔，但如果玩家沒有注意到這種變化，也可以設(shè)置成不規(guī)則的。

??方程2.1的一個(gè)有趣的特點(diǎn)是，它是時(shí)間可逆的，因此生成過去的x跟生成未來的x一樣容易。考慮一下，如果玩家第一次訪問一個(gè)星球，需要查看商品價(jià)格的歷史記錄。公式2.1可用于生成表示歷史價(jià)格的一系列樣本。這與在時(shí)間上向前生成樣本的方式完全相同，只是x1將被解釋為x0之前，x2將被解釋為x1之前，依此類推。

??雖然能夠在時(shí)間上向前和向后推斷隨機(jī)游走是非常有用的，但是我們經(jīng)常需要做更多的工作。例如，如果玩家觀察到一個(gè)變量的值，但我們需要確保它在一小時(shí)后有其他特定的值，會(huì)發(fā)生什么情況？

? 這種情況時(shí)有發(fā)生，比如一個(gè)規(guī)定好一定會(huì)出現(xiàn)的事件----比如一場(chǎng)戰(zhàn)爭(zhēng)后商品價(jià)格發(fā)生波動(dòng)，打雷下雨前一定烏云密布。由于我們現(xiàn)在在隨機(jī)游走中有兩個(gè)固定點(diǎn)，即最近觀測(cè)到的值和一個(gè)指定的未來值，所以外推方法已經(jīng)不足以完成這個(gè)任務(wù)，需要通過內(nèi)插方程來實(shí)現(xiàn)。

2.4 Using Interpolation to Walk toward a Fixed Point

? 到現(xiàn)在，我們已經(jīng)可以從與單個(gè)固定值相關(guān)聯(lián)的隨機(jī)游走中生成樣本，而要實(shí)現(xiàn)內(nèi)插方法，只需要將隨機(jī)游走與兩個(gè)固定值相關(guān)聯(lián)即可。我們通過計(jì)算x相對(duì)于每個(gè)固定值的概率分布，然后將它們相乘來實(shí)現(xiàn)這一點(diǎn)。由于公式2.1表示正態(tài)分布，我們可以很容易地寫出插值點(diǎn)的概率分布：

? 這里x0是第一個(gè)指定值，出現(xiàn)在時(shí)間t0；xn是第二個(gè)指定值，出現(xiàn)在tn；x是任意時(shí)刻t的隨機(jī)游走插值。和以前一樣，為了獲得x的特定值，我們需要從這個(gè)分布中取樣。插值x保證在t0時(shí)從x0開始，在t0和tn之間隨機(jī)游走，在時(shí)間tn時(shí)收斂到xn。

? 因此，插值使得在特定時(shí)間點(diǎn)精確地確定隨機(jī)游走的值成為可能，同時(shí)使隨機(jī)游走可以自由地在兩者之間游走。

? 要使用公式2.2生成一個(gè)隨機(jī)游走值，可以用從p(x)從采樣得到的x0和xn去生成x和x1的下一個(gè)值。接下來，使用x1代替x0并再次從p（x）中采樣以生成x2，依此類推，這可以在時(shí)間上向前或向后進(jìn)行。插值方程具有分形性質(zhì)，無論插值區(qū)間有多小，都會(huì)揭示同樣多的細(xì)節(jié)。

??這意味著它可以遞歸地應(yīng)用于解決一些問題，比如允許玩家查看某一特定商品的25年歷史價(jià)格，同時(shí)也允許玩家放大任一時(shí)間線，來查看微小的價(jià)格變動(dòng)。

2.5 Restricting the Walk to a Fixed Range of Values

? 到目前為止，隨機(jī)游走還有一個(gè)潛在的不受歡迎的特征：只要時(shí)間t足夠長(zhǎng)，它可能會(huì)便宜到原理起始點(diǎn)的任意一點(diǎn)上。但是在實(shí)踐中，我們通常希望它的值處在一個(gè)合理的范圍內(nèi)。這可以通過添加一個(gè)統(tǒng)計(jì)約束來實(shí)現(xiàn)，它約束x的值在無限長(zhǎng)的時(shí)間內(nèi)必須遵循某一特定的概率分布。

??如果我們選擇均值x*和方差σ*2的正態(tài)分布，則外推方程變成：

插值方程變成：

? 根據(jù)這些方程式生成的隨機(jī)游走在大約95%的時(shí)間里都被約束在 x*±1.96·sqrt(σ*2) 這個(gè)范圍內(nèi)。只有十億分之一的概率會(huì)超過 x*±6.11·sqrt(σ*2)。

? 圖2.2a顯示了根據(jù)等式2.3生成的隨機(jī)游走，其中x* = 90，σ*2 = 100。

? 如果十分明確必須將隨機(jī)游走的值保持在固定邊界之間，則最好使用無約束外推和內(nèi)插方程，并對(duì)它們生成的值進(jìn)行后置處理。如果這是通過判斷隨機(jī)游走的值是否越界來完成的，則隨機(jī)游走將有一條很重要的統(tǒng)計(jì)特征，即其行為對(duì)用于生成它的時(shí)間步是不變的。要了解這在實(shí)際中是如何工作的，我們將生成一個(gè)限制在[0,1]區(qū)間的隨機(jī)游走。?

??這可以通過使用無約束外推和內(nèi)插方程生成一個(gè)變量x*來實(shí)現(xiàn)，但要向玩家呈現(xiàn)一個(gè)x，需要遵守以下規(guī)則：

? x將在區(qū)間[0,1]內(nèi)表現(xiàn)出我們需要的隨機(jī)游走的性質(zhì)，并且從長(zhǎng)期來看將趨向于均勻分布。圖2.2b顯示了在使用此技術(shù)生成的區(qū)間[0,1]里面的隨機(jī)游走。如果我們簡(jiǎn)單地要求x是非負(fù)的，那么取x*的絕對(duì)值就足夠了；這樣做會(huì)產(chǎn)生一個(gè)總是非負(fù)的隨機(jī)游走，從長(zhǎng)遠(yuǎn)來看，它也會(huì)趨向于均勻分布。

2.6 Manipulating and Shaping the Walk with Additive Functions

??到目前為止，我們已經(jīng)描述了如何使用帶有一個(gè)或多個(gè)不動(dòng)點(diǎn)的內(nèi)插方程來操縱隨機(jī)游走。內(nèi)插方程保證了隨機(jī)游走一定會(huì)經(jīng)過我們需要的點(diǎn)，但我們無法控制它在一個(gè)區(qū)間里的行為----無論它是沿著一條直線，還是沿著一條曲線，或者是多次突然跳躍。有時(shí)我們想要的正是這種控制，實(shí)現(xiàn)它的一種方法是簡(jiǎn)單地將隨機(jī)游走添加到另一個(gè)函數(shù)中，該函數(shù)提供了我們想要的隨機(jī)游走的基準(zhǔn)模型。在這種方式下，隨機(jī)游走提供了隨機(jī)性來改變?cè)摵瘮?shù)的分布變化。

? 假設(shè)有一個(gè)游戲，游戲里有一個(gè)商品的價(jià)格為90美分，這個(gè)商品的價(jià)格在一小時(shí)后會(huì)漲價(jià)到110美分。我們可以簡(jiǎn)單地使用內(nèi)插公式，來讓隨機(jī)游走在兩個(gè)固定價(jià)格點(diǎn)之間生成一系列的值，如圖2.3a所示。

? 或者，我們可以選擇另外一個(gè)增長(zhǎng)曲線符合要求的函數(shù)-----從90開始到110結(jié)束，并將其添加到由內(nèi)插方程（起始結(jié)束均為0）約束的隨機(jī)游走模型上。

??例如，我們可能希望價(jià)格在固定點(diǎn)之間大致呈線性移動(dòng)，因此我們將使用線性函數(shù)來提供基準(zhǔn)模型：

??為了方便起見，這里對(duì)t進(jìn)行了縮放，使其在開始時(shí)為0，在結(jié)束時(shí)為1。通過將被內(nèi)插方程（起始結(jié)束均為0）約束的隨機(jī)游走添加到該線性函數(shù)生成的值x上，就能生成符合要求的增長(zhǎng)曲線，如圖2.3b。

? 當(dāng)然，我們并不總是需要使用線性函數(shù)來提供基本形式。其他有用的函數(shù)是階躍函數(shù)，它產(chǎn)生一個(gè)突然的跳躍，平滑階躍函數(shù)提供一個(gè)平滑的曲線：

和四分之一圓函數(shù)，該函數(shù)先迅速上升，接著趨于平穩(wěn)：

基于方程2.6和方程2.7的隨機(jī)游走如圖2.3c和圖2.3d。

2.7 Using Additive Functions to Allow for Player Interaction

??我們現(xiàn)在知道如何外推和內(nèi)插隨機(jī)游走，并以有趣的方式控制它們，但我們?nèi)绾问顾鼈兿嗷プ饔?，以便玩家可以影響它們的變化？幸運(yùn)的是，玩家交互只是隨機(jī)游走被操縱的另一種方式，因此已經(jīng)描述的所有技術(shù)都可以用來產(chǎn)生玩家交互。

? 例如，玩家可能會(huì)啟動(dòng)一項(xiàng)研究，該研究將在15分鐘內(nèi)將某個(gè)特定武器的基礎(chǔ)價(jià)格降低25%。該效果可以通過隨機(jī)游走模擬價(jià)格來實(shí)現(xiàn)，該隨機(jī)游走添加了一個(gè)加上零均值的表示平均價(jià)格的函數(shù)，使整個(gè)研究過程平均價(jià)格下降了25%。這將產(chǎn)生一個(gè)隨機(jī)上下變動(dòng)的價(jià)格，但一旦研究項(xiàng)目完成，通常比開始前低25%。

??類似地，一個(gè)玩家如果短時(shí)間內(nèi)大量拋售特定商品，我們可以通過價(jià)格的暫時(shí)性下降來模擬出供大于求的影響。這可以通過下面兩種方法來實(shí)現(xiàn)：

• 在人為降低價(jià)格后立即記錄該行為產(chǎn)生的變化，并通過外推方程來生成未來價(jià)格

• 通過從商品價(jià)格中減去一個(gè)指數(shù)衰減函數(shù)，用隨機(jī)游走的隨機(jī)性來隱藏該函數(shù)

? 就上面那個(gè)研究項(xiàng)目而言，我們必須永久性地記錄玩家的行為及其對(duì)價(jià)格的影響，因?yàn)檫@種影響是永久性的。在供過于求的情況下，這種影響本質(zhì)上是暫時(shí)的，因?yàn)橹笖?shù)衰減將確保它最終會(huì)變得很小以至于可以忽略不計(jì)；在這一點(diǎn)上，游戲選擇性的遺忘它，除非玩家在未來的某個(gè)時(shí)間點(diǎn)上需要用到這個(gè)歷史價(jià)格。?

2.8 Combining Walks to Simulate Dependent Variables

??到目前為止，我們已經(jīng)討論了如何生成獨(dú)立的隨機(jī)游走，并提供了一些簡(jiǎn)單的工具來控制和操控它們。

??實(shí)際上，我們可能需要生成一些互相關(guān)聯(lián)的隨機(jī)游走：也許我們需要兩個(gè)同時(shí)上下移動(dòng)的隨機(jī)游走，或者一個(gè)在另一個(gè)下降時(shí)上升，反之亦然。通過將隨機(jī)游走相加和相乘，以及使用虛擬變量，可以很容易地實(shí)現(xiàn)這些效果。

??假設(shè)我們需要模擬電子零件和機(jī)器人產(chǎn)品的價(jià)格。由于電子產(chǎn)品是機(jī)器人產(chǎn)品的核心組成部分，如果電子產(chǎn)品的價(jià)格上漲，我們預(yù)計(jì)機(jī)器人產(chǎn)品的價(jià)格會(huì)上漲，但這兩種價(jià)格都不能準(zhǔn)確地跟蹤彼此的價(jià)格。通過使用隨機(jī)游走對(duì)電子產(chǎn)品的價(jià)格進(jìn)行建模，然后使用另一個(gè)隨機(jī)游走對(duì)虛擬變量進(jìn)行建模，該虛擬變量表示電子和機(jī)器人產(chǎn)品的價(jià)格差異或其比率。

??如果我們決定使用虛擬變量來表示價(jià)格之間的差異，我們可以使用x* = 100和σ*2 = 100的隨機(jī)游走來建模電子產(chǎn)品的價(jià)格，使用x* = 25和σ*2 = 100的隨機(jī)游走來建模電子產(chǎn)品和機(jī)器人產(chǎn)品的價(jià)格差異。由于機(jī)器人產(chǎn)品的價(jià)格是這兩個(gè)隨機(jī)游走的值之和，所以它也是一個(gè)隨機(jī)游走，它的x* = 125，σ*2 = 200，并且會(huì)隨著電子產(chǎn)品的價(jià)格波動(dòng)而波動(dòng)，如圖2.4所示：

??隨機(jī)游走的組合可以變得非常復(fù)雜。例如，航天器的價(jià)格可以是其各種組件的價(jià)格加上表示實(shí)際銷售價(jià)格與組件總成本偏差的虛擬變量值的加權(quán)和。

? 一般來說，如果一個(gè)隨機(jī)游走是由N個(gè)隨機(jī)均值x1...xN和方差σ*相加，且對(duì)應(yīng)權(quán)重為w1...wN，那它可以表示為：

? 它可以是玩家可以觀察到的總和中所有、部分或全部組件的值。例如，我們可能希望在距離較近的恒星系統(tǒng)中使不同文明的星際商品價(jià)格更為相似，一種方法是在每個(gè)系統(tǒng)中使用虛擬變量來表示玩家無法觀察到的虛擬價(jià)格。玩家在任何特定系統(tǒng)中看到的價(jià)格將是相鄰系統(tǒng)的虛擬價(jià)格的加權(quán)和，其中較大的權(quán)重被分配給較近的系統(tǒng)。

? 值得注意的是，如果等式2.8中的一個(gè)分量具有負(fù)權(quán)重，則它產(chǎn)生負(fù)相關(guān)；也就是說，當(dāng)其值增加時(shí)，它將傾向于減小和的值。當(dāng)隨機(jī)游走表示的是兩個(gè)互相沖突的交戰(zhàn)國(guó)家時(shí)，這種情況是十分有用的。

2.9 Generating Walks with Different Probability Distributions

??如果根據(jù)有界外推方程生成隨機(jī)游走，則在很長(zhǎng)一段時(shí)間內(nèi)，它將是一個(gè)具有均值x*和方差σ*2的正態(tài)分布。對(duì)大多數(shù)游戲來說這已經(jīng)足夠完美了，但我們有時(shí)候希望生成一個(gè)具有不同分布的隨機(jī)游走。

? 例如，利用對(duì)數(shù)正態(tài)分布對(duì)股票進(jìn)行建模，我們可以通過將外推函數(shù)解釋為自然對(duì)數(shù)函數(shù)來生成對(duì)數(shù)正態(tài)分布隨機(jī)游走，并用指數(shù)函數(shù)生成實(shí)際價(jià)格。

? 更一般的，逆采樣變換方法通常用于，通過應(yīng)用非線性變換將均勻分布在零和一之間的隨機(jī)變量，轉(zhuǎn)換為具有特定目標(biāo)分布的另一個(gè)隨機(jī)變量。例如，以均勻分布在0和1之間的隨機(jī)變量的自然對(duì)數(shù)為例，生成一個(gè)具有指數(shù)分布的隨機(jī)變量，該指數(shù)分布可用于真實(shí)地模擬多個(gè)隨機(jī)事件之間的間隔時(shí)間。

??盡管本章中描述的隨機(jī)游走具有正態(tài)分布，但可以通過將其強(qiáng)制限制到固定的間隔（如前所述），或使用累積正態(tài)分布函數(shù)對(duì)其進(jìn)行變換，來使其均勻分布。

??具體來說，如果隨機(jī)游走的樣本x具有均值x*和方差σ*2，我們可以計(jì)算變量：

??其中F是累積正態(tài)分布函數(shù)。變量y將均勻地分布在0和1之間，因此可以與逆變換方法一起用于生成具有廣泛分布的隨機(jī)游走。例如，y的線性變換可用于產(chǎn)生在任意值范圍內(nèi)均勻分布的隨機(jī)游走，而取自然對(duì)數(shù)則產(chǎn)生具有指數(shù)分布的隨機(jī)游走。

? 需要注意的是，當(dāng)使用逆變換方法改變隨機(jī)游動(dòng)的分布時(shí)，隨機(jī)游走采用的步長(zhǎng)將與其值無關(guān)。例如，用逆變換方法約束的隨機(jī)游走分布在0到1的范圍內(nèi)，當(dāng)其值接近其邊界時(shí)將比遠(yuǎn)離邊界時(shí)采用更小的步長(zhǎng)。

2.10 Solving the Persistence Problem with Procedural Generation

??計(jì)算機(jī)生成的隨機(jī)游走的核心是一個(gè)隨機(jī)數(shù)生成器，它可以通過應(yīng)用一個(gè)種子來生成和復(fù)制特定的數(shù)字序列。通過記錄用于構(gòu)造隨機(jī)游走某些部分的種子值，可以在需要時(shí)精確地重現(xiàn)這些部分。

? 例如，有個(gè)玩家第一次拜訪一個(gè)星球，并查看了過去一年中某個(gè)商品的歷史價(jià)格，那么可以通過將玩家拜訪時(shí)間當(dāng)成種子應(yīng)用到隨機(jī)數(shù)生成器上，然后反向應(yīng)用外推方程來生成這部分歷史價(jià)格。如果玩家?guī)讉€(gè)月后回到這個(gè)星球上，想要查看這段歷史，只要根據(jù)相同的種子就能重現(xiàn)，而不需要存儲(chǔ)這部分歷史數(shù)據(jù)。

? 這性質(zhì)對(duì)大型開放世界游戲十分有用，因?yàn)檫@類游戲往往需要將大量細(xì)節(jié)和歷史信息保存在隨機(jī)游走模型中。??

2.11 Conclusion

??本章為生成和操作隨機(jī)游走提供了一些簡(jiǎn)單而強(qiáng)大的技術(shù)。這些技術(shù)使利用隨機(jī)性質(zhì)和重現(xiàn)隨機(jī)浮動(dòng)的值這些方法成為可能，同時(shí)還提供必要的控制，以便在需要時(shí)使其既是腳本化的，也是交互式的。

? 文檔和源碼中演示了文章中所描述的關(guān)鍵概念，以便使讀者可以快速上手，應(yīng)用于實(shí)踐。

文章來源：http://www.gameaipro.com/

如有侵犯版權(quán)，請(qǐng)聯(lián)系譯者刪除。?

翻譯不易，讀者若需要轉(zhuǎn)載，請(qǐng)注明出處。?

若有錯(cuò)誤，歡迎指正。?