前往
大廳
主題

從別人家的糞扣(code)了解學習演算法(algorithm)是有用的

♙♲⚙\~O_O~/⚙♲♙ | 2022-06-04 14:04:00 | 巴幣 4 | 人氣 268

標題所指的糞扣並非變數、函式命名問題,而是效能爛掉。
這篇沒有改過的程式碼可以抄。



在 RPG Maker MV  中,地圖上出現的其他物件被稱為 event (事件) ,而判斷 event 與一 event 是否產生碰撞,流程是這樣的:
每個 event 在每幀都會呼叫一次自己的 update 函式。
每個 event 都要自己移動的前一刻判斷。
一個 event 要詢問所有的 event 。詢問該 event 是否在指定的座標且無法被穿透。
指定的座標且無法被穿透被寫成這樣:

Game_CharacterBase.prototype.posNt = function(x, y) {
    // No through
    return this.pos(x, y) && !this.isThrough();
};



版本:

update 流程:



往某個方向走:

確認可走:

對個別 event 確認碰撞:


取得候選 event :




發現問題了?如果同一幀中所有 event 同時要移動,有 10 個 event 時會呼叫上面的函式 10 * 10 = 100 次; 100 個則是 100 * 100 = 10000 次; 1000 個則是 1000 * 1000 = 1000000 次,呼叫次數呈現 event 數量的平方。

那麼可以怎麼改進呢?能不能只看有機會撞到的 event 就好了?比方說只看在某 x,y 座標的 event ,並透過 O(1) 存取的方式得到他們:
1. 在所有 event 呼叫自己的 update 之前,重新建表:位置 -> 存放在該位置的 event 的陣列。不計 Garbage Collection (垃圾回收)的時間時,時間花費與 event 數量呈線性。
2. 假裝 event 鮮少重疊。
3. 檢查碰撞時將座標代入表中,得到寥寥無幾的 event 。
4. 每個 event 只檢查寥寥無幾的 event ,當 O(1) 。
5. 把 1. 與 4. 的時間花費均攤到每個 event 的 update 上,使得時間複雜度與沒檢查碰撞相同。
6. 若有兩個 event 同時移動到同一格,就給他移,管他的。或是移動後更新一下表格。





Q1: 為什麼寫晶晶體?
A1: 並非所有人都熟悉 RPG Maker MV 的翻譯,此舉是為避免因 RPG Maker MV 的翻譯造成語句上理解的歧義。當中途變成使用另一個語言時,你會很清楚知道那是關鍵字,而不會拿原詞彙的意思解讀。如果以上理由說服不了你,你可以試著把英文的部分換回去中文,會有多難以理解到底是取原意思,還是那是關鍵字。

Q2: 我建表了,還是卡,為什麼?
A2: 因為這部分只是冰山一角。

創作回應

Ctrl+Shift+W
好久沒看到晶晶體這個詞www 然後膜拜大佬
2022-08-10 22:07:36
♙♲⚙\~O_O~/⚙♲♙
有沒有感受到我滿滿的老人味XD
2022-08-11 08:38:46

相關創作

更多創作