軍團(tuán)戰(zhàn)棋英雄時(shí)代觸發(fā)器之?dāng)?shù)學(xué)運(yùn)算如下：

軍團(tuán)的地圖編輯器觸發(fā)器系統(tǒng)是一門編程語言。

……開個(gè)玩笑，但它真能干很多奇怪的事情。

長文警告，胡言亂語警告

1. 乘法

觸發(fā)器自身提供了加法和減法——即計(jì)數(shù)器A，“增加”，“使用計(jì)數(shù)器”，計(jì)數(shù)器B的效果，可以視作A+=B。

利用這個(gè)，就可以得到最初級的乘法運(yùn)算：

令計(jì)數(shù)器X=0，調(diào)用“乘法器”B次，后者的內(nèi)容則是令計(jì)數(shù)器X增加計(jì)數(shù)器A。

這樣足夠好嗎？當(dāng)然不。調(diào)用一個(gè)觸發(fā)器的上限是500次，而根據(jù)設(shè)備運(yùn)算能力的不同，有時(shí)達(dá)不到500次設(shè)備就會卡死，我們顯然不希望得到錯(cuò)誤的結(jié)果或干脆直接卡掉。

那么要怎么辦呢？

乘法本質(zhì)上是一些加法。我們重復(fù)了B次增加A的操作，使得總觸發(fā)數(shù)量達(dá)到了B次。如果試圖減少它，就必須增加每次令結(jié)果增加的數(shù)值。

一個(gè)很自然的想法是令每次增加的數(shù)值都“最有意義”——例如，我們將一個(gè)數(shù)乘以20，可以先算出其10倍，儲存起來，再加上一次這個(gè)10倍，這樣就只需要加兩次了。很自然地這個(gè)思路最終會延展到——二進(jìn)制。

我們來計(jì)算A乘以X。首先，我們把X化成二進(jìn)制的序列，然后對于從1開始的每一個(gè)位，我們令A(yù)自加一次，當(dāng)對應(yīng)位是1的時(shí)候我們把這個(gè)臨時(shí)結(jié)果加到最終結(jié)果中去。例如我們計(jì)算10*5，首先將5化作二進(jìn)制序列101，然后對應(yīng)這個(gè)我們先將結(jié)果增加10、然后乘數(shù)自加一次變?yōu)?0，下一次對應(yīng)位是0不加跳過，乘數(shù)繼續(xù)自加為40，再下一次加成10+40=50，就得到了需要的積。由于自加和結(jié)果增加之間有一個(gè)判斷，需要分開成兩個(gè)觸發(fā)器，每個(gè)各觸發(fā)3次，以及，沒錯(cuò)，將7序列化也需要一個(gè)觸發(fā)器運(yùn)行3次。我們在游戲初始化時(shí)儲存1、2、4、8……等32個(gè)位的值，然后依次比較并相減就可以得到序列化的結(jié)果。

因此這樣的計(jì)算中觸發(fā)次數(shù)是9次。然而，當(dāng)被乘的規(guī)模放大的時(shí)候，我們也只需要增加很少的次數(shù)。實(shí)際上，游戲計(jì)數(shù)器的上限是2147483647（2^31-1，32位符號整數(shù)的上限），因此每個(gè)循環(huán)實(shí)際上只有31次，就算步驟多一些，也不可能超過設(shè)備上限的。

以下是所用到觸發(fā)器的詳情：

初始化：游戲開始時(shí)觸發(fā)，令A(yù)=1、I=0、調(diào)用“初始化位”31次；初始化位：令比特[I]=A，然后A增加A，然后I增加1。這個(gè)序列執(zhí)行完畢后我們會得到比特0=1，比特1=2，比特2=4，一直到比特30=1073741824（下一個(gè)是-2147483648，不能多算，否則溢出會導(dǎo)致整個(gè)邏輯錯(cuò)誤）。

乘法：計(jì)算A×X

（1）清理：令I(lǐng)=0、（X比特[I]=0、I增加1）31次；然后Y=0，將所需的計(jì)數(shù)器都清理干凈。因?yàn)?2)的效果中沒有“否則”，因此這里要給每一位預(yù)先清零。

（2）序列化：令I(lǐng)=30、（當(dāng)前比特=比特[I]，（條件：X大于等于當(dāng)前比特，效果：X減少當(dāng)前比特，X比特[I]=1），I減少1）31次。

（3）加和：令I(lǐng)=0、（當(dāng)前X比特=X比特[I]，（條件：X比特等于1，效果：Y增加A），A增加A，I增加1）31次。

最后，這個(gè)算法依舊是X那方只能計(jì)算正數(shù)，并且，A自加的時(shí)候要額外判斷一下是否溢出，所以A最好也是正數(shù)。

我們這里用了兩個(gè)臨時(shí)變量當(dāng)前比特，是因?yàn)槟壳坝|發(fā)器系統(tǒng)的bug，在條件欄里無法寫[]。

2. 帶余除法

作為乘法的逆運(yùn)算，除法因?yàn)榇嬖谟鄶?shù)的干擾相對復(fù)雜那么一丁點(diǎn)……也不是很多。

通常我們計(jì)算A/X，可以令A(yù)分別減X，直到A

還是一樣引入二進(jìn)制，我們先記錄X的1、2、4、8……倍是多少，然后用A從高到低挨個(gè)比較下來，就可以得到商的各個(gè)位值。最后用已存好的二進(jìn)制位對應(yīng)相加就得到了商數(shù)。

初始化同上。

除法：計(jì)算A/X=Y...A

（1）清理：Y=0，其他不用清理因?yàn)槲覀儠觅x值覆蓋掉。

（2）X序列化：令I(lǐng)=0，（X倍數(shù)[I]=X，X增加X）31次；

（3）求商：令I(lǐng)=30，（當(dāng)前X倍數(shù)=X倍數(shù)[I]，（條件：A大于等于當(dāng)前X倍數(shù)，效果：A減少當(dāng)前X倍數(shù)，Y增加比特[I]），I減少1）31次

3. 開根號

在開玩笑？并沒有。

開根號有一種叫長除法的遞推算法，本質(zhì)上是和除法差不多的一個(gè)計(jì)算。它的原理是這樣的：要開根號A，我們先進(jìn)行試商得到一個(gè)初值X，并且保證X^2

我們接下來要試一個(gè)更接近的數(shù)值，比如X+D。

因?yàn)?X+D)^2=X^2+2XD+D^2，要求其小于A，我們注意到計(jì)算過幾次后D會很小，這里扔掉平方項(xiàng)，演變成D<（A-X^2）/2X，每一位都是一個(gè)除法。

但其實(shí)還不用那么麻煩。記得我們剛用的的二進(jìn)制大法嗎？如果每次只前進(jìn)一個(gè)二進(jìn)制位，那么這個(gè)除法的商只可能是0或者1，這樣它就退化成了一次比較，這個(gè)就方便多了。

我們引入一個(gè)已有商記錄已開過根號的粗結(jié)果X，再引入一個(gè)位標(biāo)記，當(dāng)標(biāo)記走到1的時(shí)候，X就是最接近的開平方結(jié)果，而A中剩下的數(shù)值則是余數(shù)。

那么怎么計(jì)算A-X^2呢？

我們這里注意到X每一次計(jì)算的時(shí)候它是2^I的倍數(shù)，那么它的平方就是4^I的倍數(shù)，如果我們將A直接序列化為四進(jìn)制數(shù)，我們每次扔掉一位就OK了，不用計(jì)算這個(gè)差值。

這樣優(yōu)化的結(jié)果就變成如下的步驟：

初始化同上。

開平方：計(jì)算Sqr(A)=X

（1）清理：令I(lǐng)=0、（A比特[I]=0、I增加1）16次；二進(jìn)制31位就是四進(jìn)制16位。

（2）序列化：令I(lǐng)=30、（當(dāng)前比特=比特[I]，（條件：A>當(dāng)前比特，效果：A減少當(dāng)前比特、A比特[I]增加1）調(diào)用3次，然后I減少2）

這里是直接一個(gè)商最多為3的簡單除法，就嵌入式寫在里面了。

（3）長除法：這里只寫最終優(yōu)化過的一個(gè)手順，畢竟中間的列表計(jì)算和比較太復(fù)雜了，講起來還得這文這么長。

要用到三個(gè)變量，先令X=0，Y=0，Z=0。

然后I=15，（Y增加Y，Y增加Y，Y增加A比特[I]，X增加X，Z=X，Z增加X，（條件：Y>Z，效果：X增加1，Y減少Z，Y減少1），然后I減少1）16次。

最終X中就是開平方的結(jié)果，Y中則是余數(shù)。

4. 偽隨機(jī)數(shù)

其實(shí)這篇和開平方?jīng)]關(guān)系，但因?yàn)槭潜壬厦鎺讉€(gè)基礎(chǔ)計(jì)算更上一級的算法，就寫在這里了。

軍團(tuán)自帶有一個(gè)隨機(jī)執(zhí)行的功能，設(shè)置兩個(gè)效果：X=0和X=1，隨機(jī)其中1個(gè)效果，就得到一個(gè)隨機(jī)的比特。

然而，如何得到一個(gè)隨機(jī)序列，它具有一定的可預(yù)測性（例如不會連續(xù)為0很多次）、最重要的是保持反復(fù)游戲中結(jié)果不變呢？這里就需要使用偽隨機(jī)數(shù)發(fā)生器了。

軍團(tuán)的機(jī)能能夠?qū)崿F(xiàn)的最理想的發(fā)生器是LCG（線性同余發(fā)生器），它的工作機(jī)制是：從上一個(gè)隨機(jī)數(shù)R1，經(jīng)過R2=(A*R1+C) mod M來得到下一個(gè)隨機(jī)數(shù)。仔細(xì)選擇參數(shù)，可以實(shí)現(xiàn)一個(gè)周期為M、范圍為0到M-1的隨機(jī)序列。而對于每個(gè)輸入的相同的A1，這個(gè)序列都是相同的。

軍團(tuán)的計(jì)數(shù)器上限是32位整數(shù)，我們這里需要保證取到最大值M-1的時(shí)候A*M-1低于32位，否則雖然理論上可以計(jì)算，但我們的乘法器算不了啊。

所以這里M只能選擇到20位，把剩下10位讓給A。具體參數(shù)選擇就不多講了，我個(gè)人用的是R2=1033*R1+12345 mod 1048576。

這個(gè)R2實(shí)際上還有隨機(jī)性不是很足的問題，不過我們可以去掉后5位，也就是除以32取商，這樣得到0-32767之間的數(shù)字隨機(jī)性會相對充分。進(jìn)一步地我們可以讓它除以我們需要的上限（比如100）再取余，這樣會比固定上限靈活很多，而只增加不多的工作量。我們的種子R1則存儲于內(nèi)部計(jì)數(shù)器中不拿出來使用。

更多花活待下期（如果有的話）補(bǔ)充。

以上就是軍團(tuán)戰(zhàn)棋英雄時(shí)代觸發(fā)器之?dāng)?shù)學(xué)運(yùn)算相關(guān)內(nèi)容。