談 tile 計算效率的優化處理

tile 在遊戲資料中可以視為是一個 8x8 pixels 的單位元素 (當然也可能有更大的組成) , 可以視為是一個組成畫面區塊的最基本要素,在任天堂紅白機或是GameBoy中一個 title 由兩個 16 Byte 的資料組成, 從兩個 16byte 的資料要處理解碼出 title 在遊戲主機中用的是硬體 pipline 設計去處理 , 因此雖然一個 tile 有 64個  pixel ,在硬體處理之下也僅只是一件一個步驟的事情 , 但由軟體模擬去處理可就不是這樣,算是相當耗費計算的工作 ( 64 * n 次動作 ),但通常來說 title 變動的頻率極低 , 多數是在換關卡等等之類的況下, 才會有tile 資料變動 , 因此多數會使用cache的技巧,也就是說 tile table(這些title會存放記錄在一個連續的記憶體區域,稱tile table ,但每台遊戲主機在稱呼上多少有著不同,但觀念是差不多的) 計算過一次 記錄下來結果, 之後除非再異動, 不然不會每次整個table都重算一次,這是一種cach的等級,比較進階的甚至會再細部到只處理table中某個位置tile的變動.

1.每次畫面存取 , 全部 table 裡的全部title重算一次 (loading最重,通常會造成嚴重效率問題)
2.每次畫面存取, 除非 table裡面的某些資料有異動,才會整個將table重算一次
3.每次畫面存取,僅只更新table裡面有異動的 title 部分.

(優化到啥程度,看各家本領,有時候優化過頭沒處理好,還會漏掉....)

通常一個還算能跑的模擬器,最少要達成 第二步驟的優化,除此外像是background title map也會進行cache優化 (簡稱BG MAP,一個二維陣列,每個位置紀錄放置哪個title來呈現出遊戲背景畫面).

如果以上聽模模糊糊,沒關係,再多看一些相關資料,就會通了.

上面是針對 tile cache的優化,但解 title 本身的計算處理優化又是另一個議題.

這邊我先假設讀者已經知道解 title 的方法 (也許以後再另行篇章撰寫),通常最少會有3曾迴圈

第一層迴圈 : 處理每個 tile , 好比說 title 有 256 個 , 迴圈就從 0 ~ 255
第二層迴圈 : tile的每一行 ,共有 8 行
第三層迴圈 : tile 的每一行中的每一個 pixel , 每行共 8個 pixel

我原本有想過說,tile算過後, table更新後,即使是最佳化的cache , 還是得針對有異動過的位置重算,如果算完能夠記錄住,直接搬移過來放置,不是就ok了? (話先說再前頭,這想法失敗)

每個 title 由 32 byte 組,共64bits,如果能建立一個索引關係,豈不是每次table更新,只要更新索引就好?

其實問題點就是這索引機制的設計,32BYTE 共 64bits,如果用 array 資料結構來 index ,這 64bits的資料量非常可怕 , 2^64 ,後來採用 C# 的 dictionary, key 就是由 64bits的 title 資料而來,value則是解出的 title 2維 pixles , 測試起來由於使用到比較進階複雜的資料結構物件,雖然免於重複計算,但光是建立索引的 key 和 從 dictionary 去撈取 value,本身就比解一個title的標準動作費時不少...... orz... 如果不靠 dictionary 物件呢? 自己建立特殊的資料結構 ? 想了又想....最主要的問題還是在於光是要生成這個 key 和建立mapping索引關係,到撈取資料,本身就有不少計算量,並沒有佔到便宜.....

原先的想法更單純,把所有 8x8 的可能性窮舉法算出來, 後來算一算後才知道不實際....

那靠多核心計算來當平行處理呢? 更慘....並不是任何計算處理靠平行和多核就一定能吃香,因為本身會有很多context switch , 這個會占用一定的時間,如果相對於計算任務來說, context switch 本身就超過計算時間,那並不划算,實測結果把 第三層 for 迴圈改成 平行處理的寫法下去,更慢..... orz.....

最後有明顯效果提升的,但也不是新花招的,大概就是迴圈展開這招,速度是提升,當然會多一點code的量,簡單來說就是把第三層的迴圈移除掉,直接把相同的code copy/paste 上 8次,並且將一些可以事先算好的東西先算好,出來的結果速度快了原來非常非常多倍......

這技巧是用空間換時間,並且事先把一些能夠前置處理掉的計算事先算好,少掉那些計算與每次回圈的counet判斷和 jump 的時間,效率就提升很多 , 至於把第二層環圈也移除掉呢 ? 效率會再提升多少,我不清楚,但的確也可以嘗試.... 不過就變成多了最少64倍的程使碼量就是,反正copy paste也不會太久.

結果最後還是繞回一個傳統.常見的老方法才是正解.

ps.如果有更好的技巧或是想法也歡迎分享