堆疊TNT爆炸卡頓分析

2022-08-13 17:56 作者:lovexyn0827 0人讀過 | 我要投稿

前言

在較大型TNT炮的設(shè)計(jì)過程中，爆炸卡頓是一個(gè)不可忽視的重要事項(xiàng)，對(duì)其進(jìn)行一定分析有助于評(píng)估一個(gè)設(shè)計(jì)的可行性，有時(shí)還可以作為爆炸卡頓優(yōu)化的理論依據(jù)。

本次研究采用如下環(huán)境：

Minecraft 1.16.5（MCP-Reborn-MOJO）
Oracle JDK 8u221（單堆）或Oracle JDK 11.0.5（雙堆）
Windows 7旗艦版
Intel Pentium G2030 @ 3000 MHz
4GB RAM, JVM堆空間分配2GB

前置知識(shí)：爆炸瞬間TNT運(yùn)算流程

相對(duì)完整地說來，大概是這樣的：

重力加速度
以當(dāng)前Motion為位移趨勢(shì)進(jìn)行基于Entity.move()的移動(dòng)

如果位移不是絕對(duì)沿軸
如果移動(dòng)絕對(duì)沿軸
假設(shè)TNT的運(yùn)動(dòng)軌跡為沿軸折線，之后的碰撞檢查一次尋找這些軸上的的碰撞
如果區(qū)塊未加載則跳過當(dāng)前方塊且不加載區(qū)塊
如果方塊沒有碰撞箱或容錯(cuò)范圍內(nèi)判定碰撞在當(dāng)前軸上已經(jīng)發(fā)生則跳過當(dāng)前方塊，但會(huì)加載區(qū)塊
將碰撞箱分割成盡可能少個(gè)體素（立體的像素），檢查從起點(diǎn)到目的地每個(gè)體素（方塊外部也被劃分出體素）的碰撞
獲取以移動(dòng)起點(diǎn)和目的地為兩體對(duì)角頂點(diǎn)的長方體，獲取長方體內(nèi)部及表面附近[1]的方塊并對(duì)其進(jìn)行如下檢查
如果方塊沒有碰撞箱或容錯(cuò)范圍內(nèi)判定碰撞已經(jīng)發(fā)生則跳過當(dāng)前方塊，但會(huì)加載區(qū)塊
將碰撞箱分割成盡可能少個(gè)體素，檢查從起點(diǎn)到目的地每個(gè)體素（方塊外部也被劃分出體素）的碰撞
如果檢測到了碰撞，結(jié)束檢查
獲取軌跡附近[1]的每個(gè)方塊碰撞箱進(jìn)行如下檢查
嘗試應(yīng)用蛛網(wǎng)和漿果叢對(duì)本次移動(dòng)的減速作用
對(duì)方塊，世界邊界和固體實(shí)體的碰撞檢查（Entity.adjustMovementForCollisions(Vec3d)）
如果剩余的位移趨勢(shì)大于m，移動(dòng)碰撞箱和坐標(biāo)
一些其他開銷幾乎可以忽略的后續(xù)運(yùn)算

阻力
將引信時(shí)間減一
將自身標(biāo)記為已移除
在坐標(biāo)上方0.06125m處產(chǎn)生一個(gè)4級(jí)爆炸（ServerWorld.createExplosion()）

計(jì)算爆炸接觸率
加速并傷害實(shí)體
在1356條軌跡上進(jìn)行檢查以獲取被破壞的方塊列表
對(duì)距離TNT坐標(biāo)點(diǎn)8m內(nèi)的未移除實(shí)體進(jìn)行如下運(yùn)算
破壞方塊
掉落被破壞方塊的掉落物
產(chǎn)生火焰
向客戶端發(fā)送爆炸數(shù)據(jù)包

流體推動(dòng)相關(guān)更新

[1]用于保證碰撞箱超出所在方塊網(wǎng)格的方塊的碰撞檢查正常進(jìn)行，通常延伸的曼哈頓距離不超過實(shí)體大小 + 2

不過，一般情況下開銷較大的只有碰撞檢查、獲取被破壞的方塊列表以及接觸率運(yùn)算開銷較大。

單堆TNT爆炸卡頓

此處單堆TNT為若干個(gè)被巖漿防爆處理、坐標(biāo)完全重合、靜止且著地的TNT。

理論分析

容易得知，單堆TNT移動(dòng)過程中無水平位移趨勢(shì)，即水平趨勢(shì)絕對(duì)沿Y軸，同時(shí)由于下方存在方塊阻擋，碰撞檢查被立即終止，開銷基本可以忽略。

爆炸接觸率運(yùn)算過程固定，預(yù)計(jì)每次的開銷基本一致，進(jìn)而，理論上單個(gè)TNT對(duì)其他TNT實(shí)體的爆炸接觸率運(yùn)算耗時(shí)與剩余TNT個(gè)數(shù)成正比關(guān)系，總耗時(shí)與總TNT個(gè)數(shù)的平方接近成正比關(guān)系。

防爆處理下其他階段的運(yùn)算開銷幾乎不受內(nèi)外環(huán)境影響，可認(rèn)為耗時(shí)大致相同。

若設(shè)TNT個(gè)數(shù)為N，則預(yù)計(jì)可以用以下模型擬合TNT爆炸總耗時(shí)：

$%0A%0At%3DT_0N%5E2%2BT_1N$

統(tǒng)計(jì)數(shù)據(jù)

橫軸為一次堆疊TNT爆炸中某個(gè)TNT爆炸的序數(shù)，編號(hào)從0到1279，共1280次爆炸，縱軸為單個(gè)主要運(yùn)算階段的平均耗時(shí)，單位為納秒?？梢钥闯?，爆炸耗時(shí)與剩余TNT個(gè)數(shù)（1280 - 序數(shù)）成極強(qiáng)的線性關(guān)系，移動(dòng)耗時(shí)極低，幾乎可以忽略不計(jì)。

但移動(dòng)耗時(shí)也不是一點(diǎn)沒有：

移動(dòng)耗時(shí)與剩余TNT個(gè)數(shù)也是成線性關(guān)系，但兩端有微小的向下偏移且第一個(gè)TNT耗時(shí)明顯偏低，其中線性關(guān)系的出現(xiàn)可能與檢查固體實(shí)體碰撞時(shí)需要篩選的TNT個(gè)數(shù)較多有關(guān)。

雙堆TNT爆炸卡頓

但是，雙堆TNT爆炸要比TNT數(shù)量加倍復(fù)雜得多，因?yàn)榇藭r(shí)TNT會(huì)有水平動(dòng)量，進(jìn)而產(chǎn)生了影響明顯且難以分析的移動(dòng)卡頓問題。

此處雙堆TNT以一種典型的珍珠炮TNT炮膛環(huán)境為例，地面Y=16。

統(tǒng)計(jì)數(shù)據(jù)

先放幾張圖來分析分析

橫軸為一次堆疊TNT爆炸中某個(gè)TNT爆炸的序數(shù)，編號(hào)從0開始，共2560次爆炸，縱軸為單個(gè)主要運(yùn)算階段的平均耗時(shí)，單位為納秒?？梢钥闯?，爆炸耗時(shí)與剩余TNT個(gè)數(shù)（1280 - 序數(shù)）成仍有較強(qiáng)的線性關(guān)系，但移動(dòng)耗時(shí)不再小得可以忽略。

另外爆炸數(shù)據(jù)中的較高的散點(diǎn)（應(yīng)是GC活動(dòng)的結(jié)果）相對(duì)移動(dòng)數(shù)據(jù)中這樣的散點(diǎn)數(shù)量較多，可以推測整體而言爆炸運(yùn)算過程中產(chǎn)生新對(duì)象實(shí)例較多，內(nèi)存開銷較大，而且這一開銷隨剩余TNT數(shù)量遞增。

移動(dòng)的平均卡頓大小會(huì)隨TNT總數(shù)先加速上升然后接近線性增加，整體不好用多項(xiàng)式合理地?cái)M合。

一輪較為典型的爆炸的耗時(shí)數(shù)據(jù)如下：

第一堆TNT爆炸時(shí)，移動(dòng)的耗時(shí)極低，與單堆TNT爆炸類似，然后，移動(dòng)耗時(shí)開始突增并繼續(xù)增加，最終趨近于線性增長。

圖中每一個(gè)點(diǎn)對(duì)于一輪兩堆TNT數(shù)量均為隨機(jī)0-640個(gè)的雙堆TNT爆炸，從紅到紫耗時(shí)依次增大（三張圖中尺度不同），從左到右分別為總耗時(shí)，移動(dòng)耗時(shí)和爆炸耗時(shí)，X，Y軸分別為后爆炸的和先爆炸的TNT數(shù)量。

其中，僅有爆炸耗時(shí)的圖像中任意直線x+y=k（k為常數(shù)）上耗時(shí)大致相同，即爆炸總耗時(shí)僅與TNT總數(shù)有關(guān)。移動(dòng)耗時(shí)不僅與TNT總數(shù)有關(guān)，還與兩組TNT的數(shù)目比有關(guān)，而且先爆炸的TNT似乎比后爆炸的TNT對(duì)移動(dòng)總耗時(shí)的貢獻(xiàn)更大。

也可以做得更直觀一些。固定總TNT個(gè)數(shù)為1280，可以繪制出各階段的平均耗時(shí)如圖，其中紅、黃、綠色散點(diǎn)分別對(duì)應(yīng)總耗時(shí)，爆炸耗時(shí)和移動(dòng)耗時(shí)，橫軸為后引爆的TNT個(gè)數(shù)：

容易得出，爆炸耗時(shí)受TNT數(shù)目影響不大，只是中間（兩堆TNT數(shù)目接近時(shí)）的耗時(shí)略高。

但是移動(dòng)總耗時(shí)受數(shù)目比例影響極大，總體趨勢(shì)為先引爆的TNT占到總TNT個(gè)數(shù)的約1/5時(shí)耗時(shí)最多，其他情況下耗時(shí)略少，由此現(xiàn)象應(yīng)該可以設(shè)計(jì)出一種能自動(dòng)減小爆炸卡頓的珍珠炮配置系統(tǒng)。根據(jù)僅有的幾組數(shù)據(jù)，這一峰值出現(xiàn)時(shí)兩堆TNT的數(shù)目比在TNT總數(shù)不同時(shí)似乎也不同，似乎呈現(xiàn)出一種先減后增的趨勢(shì)，在1280TNT處會(huì)取到一個(gè)較小值。

理論解釋

目前進(jìn)行的分析尚不能對(duì)所有實(shí)驗(yàn)現(xiàn)象作出合理解釋，在此僅能推測部分簡單現(xiàn)象的成因。

1. 移動(dòng)卡頓大小遠(yuǎn)大于單堆TNT

雙堆TNT中先爆炸的一堆TNT給另一堆TNT一個(gè)較大的水平動(dòng)量，后爆炸的一堆TNT移動(dòng)的絕對(duì)沿軸狀態(tài)被破壞，進(jìn)而導(dǎo)致一個(gè)較大區(qū)域中的方塊（可能有數(shù)萬個(gè)，有些時(shí)候甚至可能包含所有已加載方塊）全部參與碰撞檢查，而且一些有結(jié)構(gòu)精細(xì)的方塊在Bugjump的奇葩代碼下被檢查的效率奇低，每檢查一個(gè)這樣的方塊就有可能會(huì)檢查數(shù)萬個(gè)體素的潛在碰撞。由此，雙堆TNT爆炸的移動(dòng)卡頓大小遠(yuǎn)大于單堆TNT爆炸。

2. 移動(dòng)卡頓總時(shí)長與TNT數(shù)量和比例的關(guān)系

舉一個(gè)例子，假設(shè)左邊的一堆TNT先運(yùn)算，則右邊的TNT在移動(dòng)時(shí)差不多會(huì)檢查圖中紫色方框中的所有方塊的碰撞（此處僅做演示），且隨著自身動(dòng)量的增加，檢查范圍還會(huì)繼續(xù)向右或向下延伸，直到延伸到未加載區(qū)塊。在未加載區(qū)塊被覆蓋前，右邊第一個(gè)TNT檢查的方塊的數(shù)量與TNT動(dòng)量大小的平方大致成正比，也就是與左側(cè)TNT的個(gè)數(shù)的平方大致成正比；在范圍延伸到未加載區(qū)塊后，右邊第一個(gè)TNT檢查的方塊數(shù)量不再受左邊TNT數(shù)量的影響。同時(shí)，檢查單個(gè)方塊時(shí)檢查的體素?cái)?shù)量與實(shí)體各軸動(dòng)量和成正比，另外，在獲取方塊和進(jìn)行一些初步排除檢查時(shí)也會(huì)牽扯到一些與方塊數(shù)量成正比的卡頓，所以，那個(gè)TNT總共檢查的體素個(gè)數(shù)在檢查范圍延伸到未加載區(qū)塊前與左邊一堆TNT數(shù)量近似成三次關(guān)系（還應(yīng)有二次項(xiàng)和一次項(xiàng)，下面類似），在檢查范圍延伸到未加載區(qū)塊后開始線性增長。

到這還沒完，類似地，右邊的TNT自己爆炸時(shí)也會(huì)給同一堆余下的TNT以Y軸上的沖量（加速），使檢查方塊數(shù)量在檢查范圍延伸到世界底層前隨爆炸序數(shù)（第幾個(gè)爆炸）線性增加，在范圍延伸到世界底層后不再增加。同時(shí)，檢查一個(gè)方塊的復(fù)雜度也跟著檢查的體素?cái)?shù)量隨爆炸序數(shù)線性增加，最終右邊的TNT除左邊的TNT造成的卡頓突增外，還會(huì)繼續(xù)附加一個(gè)隨爆炸序數(shù)先二次增長再線性增長的卡頓。

總的來說，TNT移動(dòng)卡頓大小與TNT數(shù)目的關(guān)系式應(yīng)該可以以一種不超過三次的多元分段多項(xiàng)式函數(shù)的形式寫出，但意義不是很大。

至于比例，兩堆TNT的爆炸的卡頓主要由后一堆提供，除前一堆TNT爆炸提供的動(dòng)量外，卡頓大小還取決于后一堆TNT的數(shù)量和其內(nèi)部加速提供的動(dòng)量，這兩者的相互作用存在一個(gè)平衡點(diǎn)，即峰值卡頓出現(xiàn)的情形，如果比例有所改變，總共的卡頓大小就會(huì)下降。

在這些結(jié)論下，前面猜測的峰值卡頓出現(xiàn)時(shí)的TNT比例隨TNT總數(shù)的變化規(guī)律或許也能說的通了。

3. 爆炸卡頓在兩組TNT數(shù)目相近時(shí)略高

同一堆內(nèi)TNT計(jì)算接觸率時(shí)進(jìn)行的Raycast較短，而兩組堆NT間接觸率的計(jì)算就會(huì)用到相對(duì)較長的Raycast，根據(jù)數(shù)學(xué)關(guān)系很容易得到，若TNT總量確定，理論上兩堆TNT數(shù)量相同時(shí)進(jìn)行的組間Raycast最多，進(jìn)而卡頓就會(huì)略微地增大。

輕松的實(shí)踐篇：爆炸推進(jìn)弱加載的實(shí)體

假設(shè)某弱加載區(qū)域有一個(gè)實(shí)體需用TNT推進(jìn)將水平速度加速到 $v$ ，且每個(gè)TNT提供的沖量固定為 $%5CDelta%20v$ ，所有TNT以每堆數(shù)量相同的單堆堆疊形式爆炸，配合使用/tick warp以保證服務(wù)器線程不間斷運(yùn)行，問若要確定加速所需的最短時(shí)間及此時(shí)的加速方案，需測定哪些數(shù)據(jù)，并用測得數(shù)據(jù)的表示所需結(jié)果。

顯然，這種條件下需要的TNT數(shù)量是確定的，可以設(shè)為N。

在測定了運(yùn)行環(huán)境下單堆TNT爆炸總卡頓與TNT數(shù)目的關(guān)系式系數(shù) $T_0$ 、 $T_1$ ，以及/tick warp條件下以及歸中陣列的運(yùn)行周期T，再設(shè)每一堆TNT數(shù)目為 $N_0$ ，則很容易寫出總用時(shí)

$t%3D%5Cfrac%7BN%7D%7BN_0%7D(T_0N_0%5E2%2BT_1N_0%2BT)%3DT_0N_0N%2B%5Cfrac%7BNT%7D%7BN_0%7D%2BNT_1$

由基本不等式很容易得出用時(shí)的最大值為 $NT_1%2BN%5Csqrt%7BTT_0%7D$ ，在 $N_0%3D%5Csqrt%7B%5Cfrac%7BT%7D%7BT_0%7D%7D$ 時(shí)取到。

TODOs

研究做到一半電腦就幾乎撐不住了，經(jīng)常自己斷電，很可能是硬件問題，不得已將下面的幾個(gè)研究項(xiàng)目暫時(shí)擱置，等換了電腦再繼續(xù)完成。

Java版本的影響
Minecraft版本的影響
爆炸點(diǎn)相對(duì)區(qū)塊位置的影響
爆炸卡頓對(duì)其他服務(wù)端運(yùn)算階段耗時(shí)的影響
雙堆TNT爆炸卡頓與爆炸時(shí)序關(guān)系的進(jìn)一步探究。

標(biāo)簽：